{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "「FINAL Template_for CIS521_midterm notes.ipynb」的副本",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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": "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": "1a62e317-533f-4a63-aaea-539af2d2eae9"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "1. rationality: doing right things.\\n\n",
        "2. (acting humanly) turing test: A computer passes the test if a human interrogator, after posing some written questions, cannot tell\n",
        "whether the written responses come from a person or from a comp. The test results do not depend on the ability to give correct answers to questions, \n",
        "only how closely one's answers resemble those a human would give \\n\n",
        "  6 AI discipline:\\n\n",
        "    a. natural language processin: to communicate successfully in a human language;\\n\n",
        "    b. knowledge representation: to store what it knows or hears; \\n\n",
        "    c. automated reasoning: to answer questions and to draw new conclusions;\\n\n",
        "    d. machine learning: to adapt to new circumstances and to detect and extrapolate patterns;\\n\n",
        "    e. (physical simulation)computer vision: and speech recognition to perceive the world;\\n\n",
        "    d. robotics: to manipulate objects and move about.\\n\n",
        "  \n",
        "\n",
        "3. think humanly: cognitive modelling\\n\n",
        "  a. intropection:trying to catch our own thoughts as they go by;\\n\n",
        "  b. psychological experiments:observing a person in action;\\n\n",
        "  c. braining image:observing the brain in action\\n\n",
        "4. A rational agent:an agent that perceives its environment and and behaves rationally.\\n\n",
        "5. Rational behavior: doing the right thing: to maximize its performance measure/expected value\\n\n",
        "\n",
        "6. agent is specified by agent funtion f:p->a,p is perception, a is action\\n\n",
        "7. performance measure:An objective criterion for success of an agent's behavior;given the evidence provided by the percept sequence\\n\n",
        "8. search problem:\\n\n",
        "  a.goal: place to end \\n\n",
        "  b.search problem: states/actions/performance measure \\n\n",
        "  c.solution \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 =\"\"\" \n",
        "1. agent action=built-in knowledge+entire percept sequence(complete history of everything the agent has observed)\\n\n",
        "2. consequentialism: we evaluate an agent’s behavior by its Consequentialism\n",
        "consequences\\n\n",
        "3. performance measure: evaluates any Performance measure\n",
        "given sequence of environment states.\\n\n",
        "4. nature of environment: \\n\n",
        "  a. Fully observable vs. partially observable: If an agent’s sensors give it access to the Fully observable\n",
        "complete state of the environment at each point in time, then we say that the task environ- Partially observable\n",
        "ment is fully observable. A task environment is effectively fully observable if the sensors\n",
        "detect all aspects that are relevant to the choice of action;\\n\\\n",
        "5. Deterministic vs. nondeterministic. If the next state of the environment is completely \n",
        "determined by the current state and the action executed by the agent(s), then we say the\n",
        "environment is deterministic; otherwise, it is nondeterministic \\n\n",
        "6. the environment can change while an agent is deliberating, then \n",
        "we say the environment is dynamic for that agent; otherwise, it is static;\n",
        "If the environment itself does not change with the\n",
        "passage of time but the agent’s performance score does, then we say the environment is\n",
        "semidynamic.\\n\n",
        "7. The distinction between known and unknown environments is not the same as the one\n",
        "between fully and partially observable environments. It is quite possible for a known environment\n",
        "to be partially observable—for example, in solitaire card games, I know the rules but\n",
        "am still unable to see the cards that have not yet been turned over. Conversely, an unknown\n",
        "environment can be fully observable \\n\n",
        "\n",
        "```\n",
        "def model_based_reflex_agent(percept):\n",
        "\tstate = update_state(state, action, percept, model)\n",
        "\trule = match_rule(state, rules)\n",
        "\taction = rule.Action\n",
        "\treturn action\n",
        "```\n",
        "\n",
        "```\n",
        "def simple_reflex_agent(percept):\n",
        "\tstate = get_state_from_percept(percept)\n",
        "\trule = match_rule(state, rules)\n",
        "\taction = rule.Action\n",
        "\treturn action\n",
        "```\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "chapter2_3 = \"\"\" \n",
        "1. In an episodic task environment, the agent’s experience is devided into atomic episodes. In each episode the agent receives a percept and then performs Sequential a single action. Crucially, the next episode does not depend on the actions taken in previous\n",
        "episodes.\n",
        "Since episodes are independent of one another and the agent doesn't need to know the effect of its actions.\\n\n",
        "Many classification tasks are episodic. \n",
        "For example, an agent that has to spot defective parts on an assembly line bases each decision on the current part, regardless\n",
        "of previous decisions \\n\n",
        "2. In sequential environments, on the other hand, the current decision could affect\n",
        "all future decisions \\n\n",
        "3. If the next state of the environment is completely Deterministic\n",
        "determined by the current state and the action executed by the agent(s), \\n\n",
        "4. If the environment can change while an agent is deliberating, then Static\n",
        "we say the environment is dynamic for that agent \\n\n",
        "5. If the environment itself does not change with the\n",
        "passage of time but the agent’s performance score does, then we say the environment is\n",
        "semidynamic.\n",
        "6. Properties of the task environment:\n",
        "▶ Fully observable v.s. partially observable\n",
        "▶ Deterministic v.s. stochastic\n",
        "▶ Static v.s. dynamic\n",
        "▶ Episodic v.s. sequential\n",
        "▶ Known v.s. unknown\n",
        "▶ Single agent v.s. multi-agent \\n\n",
        "\n",
        "7. An environment is uncertain if\n",
        "▶ It is not fully observable, or\n",
        "▶ It is not deterministic.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "chapter2_4 = \"\"\"\n",
        "1. agent program: The agent programs take the current percept as input from the sensors and return an action to the actuators.\\n\n",
        "Notice the difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history. \n",
        "The agent program has no choice but to take just the current percept as input because nothing more is available from the environment.\n",
        "if the agent’s actions need to depend on the entire percept sequence, the agent will have to remember the percepts.  \n",
        "2. basic agent programs: \\n\n",
        "  a. Simple Reflex Agents:\n",
        "  They only looks at the current state and decides what to do,\n",
        "  Their intelligence is only based on the given static table \\n\n",
        "  b. Model-based Reflex Agents: \\n\n",
        "  A model based agent holds an internal state based on the percept history, each step it updates the internal state.\\n\n",
        "  Updating internal state requires two kinds of knowledge \\n\n",
        "    1. Agent needs to know how the world evolves independently from the agent. \\n\n",
        "    2. How the agent’s actions affect the environment. \\n\n",
        "  PS:It is rarely possible to determine exact state of a partially observable environment. \\n\n",
        "  c. Goal-Based Agents: \\n\n",
        "  A goal-based agent combines model-based agent’s model with a goal. To reach its goal. it often uses Search and Planning algorithms. \\n\n",
        "  d. Utility-Based Agents: \\n\n",
        "  With Utility-Based agents we use utility function which is essentially an internationalization of the performance measurement \n",
        "  (It kinda defines how happy will we be if we choose this path).\n",
        "  Also, if there are multiple goals(yes, you heard me right. \n",
        "  Might be multiple goals.) and these goals conflicts in some cases, utility function specifies the appropriate tradeoff. \n",
        "  Also, if non of these goals can be achieved with certainty, utility may provide likelihood of success.\n",
        "##### Three ways to represent states and the transitions between them\n",
        "3. In an atomic representation each state of the world is indivisible—it has no internal structures,\n",
        "The standard algorithms\n",
        "underlying search and game-playing (Chapters 3–5), hidden Markov models (Chapter 14),\n",
        "and Markov decision processes (Chapter 17) all work with atomic representations \\n\n",
        "4. A factored representation splits up each state into a fixed set of variables or attributes,\n",
        "each of which can have a value.Many important areas of AI are based on factored representations, including constraint\n",
        "satisfaction algorithms (Chapter 6), propositional logic (Chapter 7), planning (Chapter 11),\n",
        "Bayesian networks (Chapters 12–16), and various machine learning algorithms \\n\n",
        "5. structured representation:we need to understand the world as having things in it that are related\n",
        "to each other, not just variables with values,Structured representations underlie relational databases and first-order logic\n",
        "(Chapters 8, 9, and 10), first-order probability models (Chapter 15), and much of natural language\n",
        "understanding (Chapters 23 and 24). In fact, much of what humans express in natural\n",
        "language concerns objects and their relationships\\n\n",
        "\n",
        "\n",
        "\n",
        "```\n",
        "function TABLE-DRIVEN-AGENT(percept) returns an action persistent:\n",
        "  percepts, a sequence, initially empty\n",
        "    table, a table of actions, indexed by percept sequences, initially fully specified\n",
        "  append percept to the end of percepts \n",
        "  action LOOKUP(percepts, table)\n",
        "  return action\n",
        "\n",
        "```\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "1. The hardest case is: Continuous,\n",
        "Partially Observable,\n",
        "Stochastic,\n",
        "Multiagent \\n\n",
        "\n",
        "2. A simple reflex agent is one that selects an action based on the current percept, and\n",
        "ignores the rest of the percept history. \\n\n",
        "3. A problem-solving agent must plan ahead. It will consider a sequence of actions that\n",
        "form a path to a goal state. The computational process that it undertakes is called\n",
        "search. \\n\n",
        "#####summary\n",
        "• An agent is something that perceives and acts in an environment. The agent function\n",
        "for an agent specifies the action taken by the agent in response to any percept sequence. \\n\n",
        "• The performance measure evaluates the behavior of the agent in an environment. A\n",
        "rational agent acts so as to maximize the expected value of the performance measure,\n",
        "given the percept sequence it has seen so far. \\n\n",
        "• A task environment specification includes the performance measure, the external environment,\n",
        "the actuators, and the sensors. In designing an agent, the first step must\n",
        "always be to specify the task environment as fully as possible. \\n\n",
        "• Task environments vary along several significant dimensions. They can be fully or partially\n",
        "observable, single-agent or multiagent, deterministic or nondeterministic, episodic\n",
        "or sequential, static or dynamic, discrete or continuous, and known or unknown. \\n\n",
        "• In cases where the performance measure is unknown or hard to specify correctly, there\n",
        "is a significant risk of the agent optimizing the wrong objective. In such cases the agent\n",
        "design should reflect uncertainty about the true objective. \\n\n",
        "• The agent program implements the agent function. There exists a variety of basic\n",
        "agent program designs reflecting the kind of information made explicit and used in the\n",
        "decision process. The designs vary in efficiency, compactness, and flexibility. The\n",
        "appropriate design of the agent program depends on the nature of the environment. \\n\n",
        "• Simple reflex agents respond directly to percepts, whereas model-based reflex agents\n",
        "maintain internal state to track aspects of the world that are not evident in the current\n",
        "percept. Goal-based agents act to achieve their goals, and utility-based agents try to\n",
        "maximize their own expected “happiness.” \\n\n",
        "• All agents can improve their performance through learning. \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\":\"anything that can perceive and act in an environment\",\n",
        "\"percept\":\"the agent’s perceptual inputs at any given instance\",\n",
        "\"right thing\":\"the objective that we provide to the agente\",\n",
        "\"performance measure\":\"evaluates the behavior of the agent in an environment\",\n",
        "\"rational agent\":\" maximize the expected value of the performance measure\",\n",
        "\"agent program\":\" implements the agent function\",\n",
        "\"environment nature\":\"fully/partially observable,static.dynamic,discrete/continuous,known/unknown\",\n",
        "\" limited rationality\":\"acting appropriately when there is not enough computation.\",\n",
        "\"value alignment problem\":\"values or objectives put into Value alignment problem the machine must be aligned with those of the human.\",\n",
        "\"task environment\":\"Performance measure,Environment,Environment,Sensors\",\n",
        "\"reflex agent\":\"anything that can perceive/act in an environment,ignore rest of percept history\",\n",
        "\"simple reflex agent\":\"respond directly to percepts\",\n",
        "\"model-based reflex agent\":\"maintain internal state to track aspects of the world that are not evident in the current \\\n",
        "percept\",\n",
        "\" utility-based agent\":\"maximize expected reward\",\n",
        "\"goal-based agent\":\"act to achieve their goal\",\n",
        "}\n"
      ],
      "execution_count": 112,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FxlZkb07tNPu"
      },
      "source": [
        "def model_based_reflex_agent(percept):\n",
        "\tstate = update_state(state, action, percept, model)\n",
        "\trule = match_rule(state, rules)\n",
        "\taction = rule.Action\n",
        "\treturn action"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1C8qUiqGtTe3"
      },
      "source": [
        "def simple_reflex_agent(percept):\n",
        "\tstate = get_state_from_percept(percept)\n",
        "\trule = match_rule(state, rules)\n",
        "\taction = rule.Action\n",
        "\treturn action"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e586ce99-2498-4659-f1e2-65f9534aa10b"
      },
      "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": 113,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA 2.4 The Structure of Agents' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n1. rationality: doing right things.\n\n2. (acting humanly) turing test: A computer passes the test if a human interrogator, after posing some written questions, cannot tell\nwhether the written responses come from a person or from a comp. The test results do not depend on the ability to give correct answers to questions, \nonly how closely one's answers resemble those a human would give \n\n  6 AI discipline:\n\n    a. natural language processin: to communicate successfully in a human language;\n\n    b. knowledge representation: to store what it knows or hears; \n\n    c. automated reasoning: to answer questions and to draw new conclusions;\n\n    d. machine learning: to adapt to new circumstances and to detect and extrapolate patterns;\n\n    e. (physical simulation)computer vision: and speech recognition to perceive the world;\n\n    d. robotics: to manipulate objects and move about.\n\n  \n\n3. think humanly: cognitive modelling\n\n  a. intropection:trying to catch our own thoughts as they go by;\n\n  b. psychological experiments:observing a person in action;\n\n  c. braining image:observing the brain in action\n\n4. A rational agent:an agent that perceives its environment and and behaves rationally.\n\n5. Rational behavior: doing the right thing: to maximize its performance measure/expected value\n\n\n6. agent is specified by agent funtion f:p->a,p is perception, a is action\n\n7. performance measure:An objective criterion for success of an agent's behavior;given the evidence provided by the percept sequence\n\n8. search problem:\n\n  a.goal: place to end \n\n  b.search problem: states/actions/performance measure \n\n  c.solution \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \n1. agent action=built-in knowledge+entire percept sequence(complete history of everything the agent has observed)\n\n2. consequentialism: we evaluate an agent’s behavior by its Consequentialism\nconsequences\n\n3. performance measure: evaluates any Performance measure\ngiven sequence of environment states.\n\n4. nature of environment: \n\n  a. Fully observable vs. partially observable: If an agent’s sensors give it access to the Fully observable\ncomplete state of the environment at each point in time, then we say that the task environ- Partially observable\nment is fully observable. A task environment is effectively fully observable if the sensors\ndetect all aspects that are relevant to the choice of action;\n5. Deterministic vs. nondeterministic. If the next state of the environment is completely \ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic \n\n6. the environment can change while an agent is deliberating, then \nwe say the environment is dynamic for that agent; otherwise, it is static;\nIf the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.\n\n7. The distinction between known and unknown environments is not the same as the one\nbetween fully and partially observable environments. It is quite possible for a known environment\nto be partially observable—for example, in solitaire card games, I know the rules but\nam still unable to see the cards that have not yet been turned over. Conversely, an unknown\nenvironment can be fully observable \n\n\n```\ndef model_based_reflex_agent(percept):\n\tstate = update_state(state, action, percept, model)\n\trule = match_rule(state, rules)\n\taction = rule.Action\n\treturn action\n```\n\n```\ndef simple_reflex_agent(percept):\n\tstate = get_state_from_percept(percept)\n\trule = match_rule(state, rules)\n\taction = rule.Action\n\treturn action\n```\n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n \n1. In an episodic task environment, the agent’s experience is devided into atomic episodes. In each episode the agent receives a percept and then performs Sequential a single action. Crucially, the next episode does not depend on the actions taken in previous\nepisodes.\nSince episodes are independent of one another and the agent doesn't need to know the effect of its actions.\n\nMany classification tasks are episodic. \nFor example, an agent that has to spot defective parts on an assembly line bases each decision on the current part, regardless\nof previous decisions \n\n2. In sequential environments, on the other hand, the current decision could affect\nall future decisions \n\n3. If the next state of the environment is completely Deterministic\ndetermined by the current state and the action executed by the agent(s), \n\n4. If the environment can change while an agent is deliberating, then Static\nwe say the environment is dynamic for that agent \n\n5. If the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.\n6. Properties of the task environment:\n▶ Fully observable v.s. partially observable\n▶ Deterministic v.s. stochastic\n▶ Static v.s. dynamic\n▶ Episodic v.s. sequential\n▶ Known v.s. unknown\n▶ Single agent v.s. multi-agent \n\n\n7. An environment is uncertain if\n▶ It is not fully observable, or\n▶ It is not deterministic.\n\n\n\n\n\n\n\n \n\n## AIMA 2.4 The Structure of Agents\n\n1. agent program: The agent programs take the current percept as input from the sensors and return an action to the actuators.\n\nNotice the difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history. \nThe agent program has no choice but to take just the current percept as input because nothing more is available from the environment.\nif the agent’s actions need to depend on the entire percept sequence, the agent will have to remember the percepts.  \n2. basic agent programs: \n\n  a. Simple Reflex Agents:\n  They only looks at the current state and decides what to do,\n  Their intelligence is only based on the given static table \n\n  b. Model-based Reflex Agents: \n\n  A model based agent holds an internal state based on the percept history, each step it updates the internal state.\n\n  Updating internal state requires two kinds of knowledge \n\n    1. Agent needs to know how the world evolves independently from the agent. \n\n    2. How the agent’s actions affect the environment. \n\n  PS:It is rarely possible to determine exact state of a partially observable environment. \n\n  c. Goal-Based Agents: \n\n  A goal-based agent combines model-based agent’s model with a goal. To reach its goal. it often uses Search and Planning algorithms. \n\n  d. Utility-Based Agents: \n\n  With Utility-Based agents we use utility function which is essentially an internationalization of the performance measurement \n  (It kinda defines how happy will we be if we choose this path).\n  Also, if there are multiple goals(yes, you heard me right. \n  Might be multiple goals.) and these goals conflicts in some cases, utility function specifies the appropriate tradeoff. \n  Also, if non of these goals can be achieved with certainty, utility may provide likelihood of success.\n##### Three ways to represent states and the transitions between them\n3. In an atomic representation each state of the world is indivisible—it has no internal structures,\nThe standard algorithms\nunderlying search and game-playing (Chapters 3–5), hidden Markov models (Chapter 14),\nand Markov decision processes (Chapter 17) all work with atomic representations \n\n4. A factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value.Many important areas of AI are based on factored representations, including constraint\nsatisfaction algorithms (Chapter 6), propositional logic (Chapter 7), planning (Chapter 11),\nBayesian networks (Chapters 12–16), and various machine learning algorithms \n\n5. structured representation:we need to understand the world as having things in it that are related\nto each other, not just variables with values,Structured representations underlie relational databases and first-order logic\n(Chapters 8, 9, and 10), first-order probability models (Chapter 15), and much of natural language\nunderstanding (Chapters 23 and 24). In fact, much of what humans express in natural\nlanguage concerns objects and their relationships\n\n\n\n\n```\nfunction TABLE-DRIVEN-AGENT(percept) returns an action persistent:\n  percepts, a sequence, initially empty\n    table, a table of actions, indexed by percept sequences, initially fully specified\n  append percept to the end of percepts \n  action LOOKUP(percepts, table)\n  return action\n\n```\n\n\n\n## Module 1 Lecture Notes\n\n1. The hardest case is: Continuous,\nPartially Observable,\nStochastic,\nMultiagent \n\n\n2. A simple reflex agent is one that selects an action based on the current percept, and\nignores the rest of the percept history. \n\n3. A problem-solving agent must plan ahead. It will consider a sequence of actions that\nform a path to a goal state. The computational process that it undertakes is called\nsearch. \n\n#####summary\n• An agent is something that perceives and acts in an environment. The agent function\nfor an agent specifies the action taken by the agent in response to any percept sequence. \n\n• The performance measure evaluates the behavior of the agent in an environment. A\nrational agent acts so as to maximize the expected value of the performance measure,\ngiven the percept sequence it has seen so far. \n\n• A task environment specification includes the performance measure, the external environment,\nthe actuators, and the sensors. In designing an agent, the first step must\nalways be to specify the task environment as fully as possible. \n\n• Task environments vary along several significant dimensions. They can be fully or partially\nobservable, single-agent or multiagent, deterministic or nondeterministic, episodic\nor sequential, static or dynamic, discrete or continuous, and known or unknown. \n\n• In cases where the performance measure is unknown or hard to specify correctly, there\nis a significant risk of the agent optimizing the wrong objective. In such cases the agent\ndesign should reflect uncertainty about the true objective. \n\n• The agent program implements the agent function. There exists a variety of basic\nagent program designs reflecting the kind of information made explicit and used in the\ndecision process. The designs vary in efficiency, compactness, and flexibility. The\nappropriate design of the agent program depends on the nature of the environment. \n\n• Simple reflex agents respond directly to percepts, whereas model-based reflex agents\nmaintain internal state to track aspects of the world that are not evident in the current\npercept. Goal-based agents act to achieve their goals, and utility-based agents try to\nmaximize their own expected “happiness.” \n\n• All agents can improve their performance through learning. \n\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the agent’s perceptual inputs at any given instance\n* **Right thing** - the objective that we provide to the agente\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Rational agent** -  maximize the expected value of the performance measure\n* **Agent program** -  implements the agent function\n* **Environment nature** - fully/partially observable,static.dynamic,discrete/continuous,known/unknown\n* ** limited rationality** - acting appropriately when there is not enough computation.\n* **Value alignment problem** - values or objectives put into Value alignment problem the machine must be aligned with those of the human.\n* **Task environment** - Performance measure,Environment,Environment,Sensors\n* **Reflex agent** - anything that can perceive/act in an environment,ignore rest of percept history\n* **Simple reflex agent** - respond directly to percepts\n* **Model-based reflex agent** - maintain internal state to track aspects of the world that are not evident in the current percept\n* ** utility-based agent** - maximize expected reward\n* **Goal-based agent** - act to achieve their goal\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",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" 1.terminal REPL:read evaluation print loo \n",
        "\\n\n",
        "2.scripts \n",
        "\\n\n",
        "4.immutable:\n",
        "tuple:t = (23, 'abc', 4.56, (2,3), 'def')\n",
        "string:st='hello'\n",
        "\\n\n",
        "5.mutable:list[],li = ['abc', 34, 4.34, 23]\n",
        "索引：左包右-1\n",
        " t[1:4]=('abc', 4.56, (2,3))\n",
        " t[1:-1]=('abc', 4.56, (2,3))\n",
        "  t[1:-1:2]= t[1:-1:2]\n",
        "\\n\n",
        "6.operation on lists\n",
        "li = [1, 11, 3, 4, 5,1] \\n\n",
        "inplace operation: append,insert,remove,reverse,sort\n",
        "li.index('1')(index of first occurrence)\n",
        "li.append('a')加在最后 \\n\n",
        "li.insert(2, 'i') 加在index=2的位置 \\n\n",
        "7.operation on string:split,capitalize,upper\n",
        "s = \"Pretend this sentence makes sense.\"\\n\n",
        " words = s.split(\" \")\n",
        " word=['Pretend', 'this', 'sentence', 'makes', 'sense.']\n",
        "string.capitalize()/string.upper()只针对string，is not inplace\n",
        "8.dictionary:unordered & work by hashing, so keys must be immutable：\n",
        "index by keys\\n\n",
        "d = {'user' : 'R2D2', 'pswd': 1234}\n",
        " d['pswd'] = 'thx1138'\n",
        "{'user': 'R2D2', 'pswd': 'thx1138'}\n",
        "d.keys()/d.values()\n",
        "dict_keys(['user', 'p', 'i’])#list of currernts keys\n",
        "d.items()#list of tuple \n",
        "dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n",
        "9.return multi values is a tuple\\n\n",
        "10.Functions can be called with arguments out of order\n",
        "Keyword arguments can be used after all other arguments\\n\n",
        "11.*args:只有数值a\n",
        "def print_everything(*args):\n",
        "  print(args)\n",
        "lst = ['a','b']\n",
        "print_everything(*lst)\n",
        "('a','b') \\n\n",
        "lst = ['a']\n",
        "print_everything(*lst)\n",
        "('a')\\n\n",
        "12. **kwargs，有等号a=1\\n\n",
        "def print_keyword_args(**kwargs):\n",
        "  print(kwargs) \\n\n",
        "print_keyword_args(first=\"John\", last=\"Doe\")\n",
        "{'first': 'John', 'last': 'Doe’}\n",
        "my_dict = {'f': 'Wei', 'l': 'Xu’}\n",
        "print_keyword_args(**my_dict)\n",
        "{'f': 'Wei', 'l': 'Xu'}\\n\n",
        "13.magic function:\\__str__\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"immutable\" : \"a tuple cannot be modified once created Items can be of mixed types, including collection types \",\n",
        "}"
      ],
      "execution_count": 114,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 619
        },
        "outputId": "c24b2c35-20c6-4fa5-e832-17478956e846"
      },
      "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": 115,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n 1.terminal REPL:read evaluation print loo \n\n\n2.scripts \n\n\n4.immutable:\ntuple:t = (23, 'abc', 4.56, (2,3), 'def')\nstring:st='hello'\n\n\n5.mutable:list[],li = ['abc', 34, 4.34, 23]\n索引：左包右-1\n t[1:4]=('abc', 4.56, (2,3))\n t[1:-1]=('abc', 4.56, (2,3))\n  t[1:-1:2]= t[1:-1:2]\n\n\n6.operation on lists\nli = [1, 11, 3, 4, 5,1] \n\ninplace operation: append,insert,remove,reverse,sort\nli.index('1')(index of first occurrence)\nli.append('a')加在最后 \n\nli.insert(2, 'i') 加在index=2的位置 \n\n7.operation on string:split,capitalize,upper\ns = \"Pretend this sentence makes sense.\"\n\n words = s.split(\" \")\n word=['Pretend', 'this', 'sentence', 'makes', 'sense.']\nstring.capitalize()/string.upper()只针对string，is not inplace\n8.dictionary:unordered & work by hashing, so keys must be immutable：\nindex by keys\n\nd = {'user' : 'R2D2', 'pswd': 1234}\n d['pswd'] = 'thx1138'\n{'user': 'R2D2', 'pswd': 'thx1138'}\nd.keys()/d.values()\ndict_keys(['user', 'p', 'i’])#list of currernts keys\nd.items()#list of tuple \ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n9.return multi values is a tuple\n\n10.Functions can be called with arguments out of order\nKeyword arguments can be used after all other arguments\n\n11.*args:只有数值a\ndef print_everything(*args):\n  print(args)\nlst = ['a','b']\nprint_everything(*lst)\n('a','b') \n\nlst = ['a']\nprint_everything(*lst)\n('a')\n\n12. **kwargs，有等号a=1\n\ndef print_keyword_args(**kwargs):\n  print(kwargs) \n\nprint_keyword_args(first=\"John\", last=\"Doe\")\n{'first': 'John', 'last': 'Doe’}\nmy_dict = {'f': 'Wei', 'l': 'Xu’}\nprint_keyword_args(**my_dict)\n{'f': 'Wei', 'l': 'Xu'}\n\n13.magic function:\\__str__\n \n\n## Module 2 Definitions\n* **Immutable** - a tuple cannot be modified once created Items can be of mixed types, including collection types \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "1. problem-solving agent: When the correct action to take is not immediately obvious, an agent may need to to plan\n",
        "ahead: to consider a sequence of actions that form a path to a goal state \\n\n",
        "2. Problem-solving agents use **atomic** representations,that Search\n",
        "is, states of the world are considered as wholes, with no internal structure visible to the\n",
        "problem-solving algorithms \\n\n",
        "3. Agents that use **factored or structured** representations of states\n",
        "are called planning agents \\n\n",
        "4. informed algorithms: agent can estimate how\n",
        "far it is from the goal \\n\n",
        "5. four-phase problem-solving process: \\n\n",
        "  a. Goal formulation: The agent adopts the goal of reaching Bucharest. Goals organize Goal formulation\n",
        "behavior by limiting the objectives and hence the actions to be considered.\n",
        "  b. Problem formulation: The agent devises a description of the Problem formulation states and actions necessary\n",
        "to reach the goal \\n\n",
        "  c. Search: Before taking any action in the real world, the agent simulates sequences of\n",
        "actions in its model, searching until it finds a sequence of actions that reaches the goal. \\n\n",
        "  d. execution \\n\n",
        "6. path: a squence of actions \\n\n",
        "  solution: a path from initial state to goal \\n\n",
        "  optimal solution has the lowest path cost among all solutions \\n\n",
        "7. The process of removing detail from a representation is called Abstraction abstraction \\n\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "### 3.2 example problem\n",
        "  1. A standardized problem is intended to illustrate or exercise various problem-solving meth-\n",
        "problem.It can be given a concise, exact description and hence is suitable as a benchmark for\n",
        "Real-world problem researchers to compare the performance of algorithms. \\n\n",
        "  2. real-world problem, such as robot\n",
        "navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic,\n",
        "not standardized, because, for example, each robot has different sensors that produce\n",
        "different data. \\n\n",
        "####3.2.1 standardized problems : grid world problems \\n\n",
        "####3.2.2 real-world prblems: route-finding problem \\n\n",
        "\n",
        "#####node.PATH-COST: the total cost of the path from the initial state to this node. In mathematical\n",
        "formulas, we use g(node) as a synonym for PATH-COST.\n",
        "\n",
        "##### best-first-search\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 , with node as an element\n",
        "  reached←a lookup table, with one entry with key problem.INITIAL and value node\n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node←POP(frontier)\n",
        "    if problem.IS-GOAL(node.STATE) then return node\n",
        "    for each child in EXPAND(problem, node) do\n",
        "      s←child.STATE\n",
        "      if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
        "        reached[s]←child\n",
        "        add child to frontier\n",
        "  return failure\n",
        "\n",
        "\n",
        "\n",
        "function EXPAND(problem, node) yields nodes\n",
        "  s←node.STATE\n",
        "  for each action in problem.ACTIONS(s) do\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",
        "```\n",
        "\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "### 3.3 search algo\n",
        "  1. search algo: takes a search problem as input, returns a solution or failure \\n\n",
        "  2. **distinction** between the state space and the search tree:\n",
        "The state space describes the (possibly infinite) set of states in the world, and the actions\n",
        "that allow transitions from one state to another. \n",
        "The search tree describes paths between these states, reaching towards the goal. \n",
        "The search tree may have multiple paths to any given state, \n",
        "but each node in the tree has a unique path back to the\n",
        "root (as in all trees) \\n\n",
        "  3. The **frontier** is the set of nodes that have been reached but not yet\n",
        "expanded;\n",
        "interior is the set of nodes that have been expanded;\n",
        "exterior is the set of states that have not been reached.\n",
        "\n",
        "#### 3.3.1 best-first search\n",
        "1. best-first search: choose a node, n, with minimum value of some f(n).\\n\n",
        "\n",
        "#### 3.3.2 search data structures\n",
        "1. node = <state, parent-node, children,\n",
        "action, path-cost, depth> \\n\n",
        "  data structures to store the frontier:queue, 3 operations on a frontier are: \\n\n",
        "  • IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.\\n\n",
        "  • POP(frontier) removes the top node from the frontier and returns it.\\n\n",
        "  • TOP(frontier) returns (but does not remove) the top node of the frontier.\\n\n",
        "\n",
        "2. 3 kinds of queues: \\n\n",
        "  • Priority queue: first pops the node with the minimum cost according to some evaluation\n",
        "function, f , used in best-first search. \\n\n",
        "  • A FIFO queue or first-in-first-out queue first pops the node that was added to the queue\n",
        "first; used in breadth-first search. \\n\n",
        "  • A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most\n",
        "Stack recently added node; used in depth-first search. \\n\n",
        "\n",
        "#### 3.3.3 search data structures\n",
        "1. redundant path: a worse way to get to the same state \\n\n",
        "2. how to eliminate repeated states/redundant path?  \\n\n",
        "  • remember all previously reached states (as best-first search does), allowing \\n\n",
        "  • don't need to worry: some problem formulations where it is rare or impossible for two paths to reach the same state.allowing \n",
        "  ##### We call a search algorithm a graph search if it checks for redundant \\n\n",
        "Tree-like search paths and a tree-like search6 if it does not check.\n",
        "  • only check for cycles, but not for redundant paths in general:\n",
        "  see if the state at the end of the path has appeared earlier in the path. \\n\n",
        "##### 3.3.4 measure problem-solving performance\n",
        "  • Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not? \\n\n",
        "  • Cost optimality: Does it find a solution with the lowest path cost of all solutions? \\n\n",
        "  • Time complexity: How long does it take to find a solution? This can be measured in\n",
        "seconds, or more abstractly by the number of states and actions considered.\\n\n",
        "  • Space complexity: How much memory is needed to perform the search? \n",
        "3. complete guarantee: systematic in the way it explores an infinite state space, \n",
        "  making sure it can eventually reach any state that is connected to the initial state. \\n\n",
        "  \n",
        "  \"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" \n",
        "###3.4 uinformed search\n",
        "#### 3.4.1 breadth-first search\n",
        "1. complete: \\n\n",
        "  • a systematic search strategy:if the root node is expanded first, \n",
        "  then all the successors of the root node are expanded next,\n",
        "then their successors. BFS is complete\n",
        "even on infinite state spaces. \\n\n",
        "  • implement BFS as a call to\n",
        "BEST-FIRST-SEARCH where $f(n)=depth of the node$ \\n\n",
        " • BFS always finds a solution with a minimal number of actions, because\n",
        "when it is generating nodes at depth d, it has already generated all the nodes at depth d-1,\n",
        "so if one of them were a solution, it would have been found. \\n\n",
        " • it is cost-optimal if all actions have same cost \\n\n",
        "  #####efficient tricks: \n",
        "  • A first-in-first-out queue:faster than a priority queue, and will give correct order of nodes: new\n",
        "nodes go to the back of the queue \\n\n",
        "  • can do an **early goal test**,\n",
        "Late goal test checking whether a node is a solution as soon as it is generated, rather than **late goal test**\n",
        "that best-first search uses, waiting until a node is popped off the queue. \\n\n",
        "\n",
        "#### 3.4.2 Dijkstra's algo or uniform-cost search\n",
        "1.  Dijkstra's algo: When actions have different costs, an obvious choice is to use best-first search where $\n",
        "f(n)=cost from root to current node$.\\n\n",
        "2. time and space complexity is $O(b^{1+[C^*/{\\epsilon]}}),C^*:$ the cost of the optimal solution; \n",
        "$\\epsilon$: a lower bound on the cost of each action \\n\n",
        "  • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\n",
        "before exploring paths involving a high-cost and perhaps useful action. \\n\n",
        "  • When all action costs are equal, it is just O(b^(d+1)), and it is similar to BFS.\\n\n",
        "\n",
        "3. complete and cost-optimal: \n",
        "  • the first solution it finds\n",
        "will have a cost that is at least as low as the cost of any other node. \n",
        "  • it considers all paths systematically in order of increasing cost, never getting caught\n",
        "going down a single infinite path \n",
        "\n",
        "#### 3.4.3 depth-first search\n",
        "1. DFS always expands the deepest node in the frontier. It could be implemented\n",
        "as a call to BEST-FIRST-SEARCH where $f(n)=negative\n",
        "of the depth$.\\n\n",
        "2. not cost-optimal: it returns the first solution it\n",
        "finds, even if it is not cheapest \\n\n",
        "3. incomplete: In cyclic state spaces it can get stuck in an infinite loop; some implementations\n",
        "of DFS check each new node for cycles. DFS\n",
        "search is not systematic: it can get stuck going down an infinite path, even if there are no\n",
        "cycles. \\n\n",
        "4. where a tree-like search is feasible,\n",
        "depth-first search has much smaller needs for memory. \\n\n",
        "5. A variant of depth-first search **backtracking search**: use less memory  \\n\n",
        "  • only one successor is generated at a time rather; \n",
        "  each partially expanded node remembers which successor to generate next.\\n\n",
        "  • successors are generated by modifying the current state description directly\n",
        "rather than allocating memory for a brand-new state. This reduces the memory requirements\n",
        "to just one state description and a path of O(m) actions \\n\n",
        "  • backtracking has the option of maintaining an\n",
        "efficient set data structure for the states on the current path, allowing to check for a cyclic\n",
        "path in O(1) time rather than O(m).\\n\n",
        "  • must undo each action when we backtrack.\\n\n",
        "\n",
        "#### 3.4.4 depth-limited and iterative deepening search\n",
        "##### depth-limited\n",
        "1. depth-limited: a version of DFS which we supply a depth limit,$l$, treat all nodes\n",
        "at depth l as if they had no successors \\n\n",
        "2. The time complexity is $O(b^l)$ and\n",
        "the space complexity is $O(bl)$\n",
        "\\n\n",
        "3. incomplete \\n\n",
        "4. can't eliminate redundant paths but can eliminate cycles \\n\n",
        "5. diameter of the state-space graph can reduce l and give a better depth limit \\n\n",
        "\n",
        "##### iterative deepening search\n",
        "6. solves the problem of picking a good value for l by trying\n",
        "search all values: 0,1,2...—until either a solution is found, \n",
        "or the returns the failure value rather than the cutoff value\n",
        "7. combine DFS & BDF: \\n\n",
        "  •DFS: memory requirements: O(bd) when there is a\n",
        "solution, or O(bm) on finite state spaces with no solution \\n\n",
        " • BFS: IDS is optimal for problems where all actions have the same cost, and is complete on\n",
        "finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the\n",
        "way up the path. \\n\n",
        "8. time complexity is O(b^d) when there is a solution, or O(b^m) when there is none.\n",
        "but BFS does this by storing all nodes in memory, while IDS by repeating the previous levels, \n",
        "thereby saving memory at the cost of more time \\n\n",
        "9.IDS is preferred uninformed search when search state space is larger than can fit in memory and\n",
        "the depth of the solution is not known.\n",
        "\n",
        "#### 3.4.5 Bidirectional search\n",
        "1. bidirectional search simultaneously\n",
        "searches forward from the initial state and backwards from the goal state(s), hoping that the\n",
        "two searches will meet \\n\n",
        "\n",
        "\n",
        "\n",
        "##### breadth-first-search and uniform-cost search algorithms.\n",
        " \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) then return node\n",
        "  frontier←a FIFO queue, with node as an element\n",
        "  reached←{problem.INITIAL}\n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node←POP(frontier)\n",
        "    for each child in EXPAND(problem, node) do\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",
        "##### Iterative deepening and depth-limited tree-like search.\n",
        "  ```\n",
        "function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure\n",
        "  for depth = 0 to ¥ do\n",
        "    result←DEPTH-LIMITED-SEARCH(problem, depth)\n",
        "    if result 6= cutoff then return result\n",
        "\n",
        "function DEPTH-LIMITED-SEARCH(problem, ℓ) returns a node or failure or cutoff\n",
        "  frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element\n",
        "  result←failure\n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node←POP(frontier)\n",
        "    if problem.IS-GOAL(node.STATE) then return node\n",
        "    if DEPTH(node) > ℓ then\n",
        "      result←cutoff\n",
        "    else if not IS-CYCLE(node) do\n",
        "      for each child in EXPAND(problem, node) do\n",
        "        add child to frontier\n",
        "  return result\n",
        "\n",
        "\n",
        "  ```\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "  \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "This chapter has introduced search algorithms that an agent can use to select action sequences\n",
        "in a wide variety of environments—as long as they are **episodic, single-agent, fully observable,\n",
        "deterministic, static, discrete, and completely known** \\n\n",
        "1. A problem-solving agent must **plan ahead**.The computational process that it\n",
        "undertakes is called **search**.\n",
        "It will consider a sequence of actions that form a path to a goal state. \n",
        "Such a sequence is called a solution.\\n\n",
        "2. define search problem:States,initial state,Actions,Transition Mode,Path cost,Goal test\n",
        "3. basic search algo:\\n\n",
        "  A.  tree search: \\n\n",
        "    a.  Enumerate in some order all possible paths from the initial state\\n\n",
        "    b.  ROOT= initial state \\n\n",
        "    Nodes in search tree generated through transition model \\n\n",
        "    treats different paths to the same node as distinct \\n\n",
        "    c. A state is a (representation of a) physical configuration \\n\n",
        "    d. A state is a (representation of a) physical configuration, node = <state, parent-node, children,\n",
        "action, path-cost, depth>,EXPAND function uses the Actions and Transition Model to create the\n",
        "corresponding states creates new nodes,\n",
        "  B. graph search:\\n\n",
        "    a. Check to see if a node has been visited before adding to search queue\\n\n",
        "    b. must keep track of all possible states (can use a lot of memory)\\n\n",
        "4. Uninformed search: All non-goal nodes in frontier look equally good, Informed search: Some non-goal nodes can be ranked above others.\n",
        "5. $b$: maximum branching factor\\n\n",
        "  $d$: depth of least cost solution\\n\n",
        "  $m$: maximum depth of state space($\\infty$)\\n\n",
        "6. **Breadth-first search**: \n",
        "  expand shallowest unexpanded node \\n\n",
        "  frontier is FIFO (First-In-First-Out) Queue(Put successors at the end of frontier successor list)\\n\n",
        "  property:\\n\n",
        "    1. complete: yes if b is finte\\n\n",
        "    2. optimal: yes if cost=1/step, not optimal in general\\n\n",
        "    3. time complexity:  $1+b+b^2+b^3+… +b^d = O(b^d)$\n",
        "    4. space complexity: $O(b^d)$(keeps every node in memory)\n",
        "\n",
        "\n",
        "6. **depth-first search**: \n",
        "  expand deepest unexpanded node \\n\n",
        "  LIFO(Last-In-First-Out:Put successors at the front of frontier successor list)\n",
        "  property:\\n\n",
        "    1. complete: No. It fails in infinite-depth spaces, spaces with loops.If we modify it to avoid repeated states along path, then it is complete in finite spaces \\n\n",
        "    2. optimal: No \\n\n",
        "    3. time complexity:  $ O(b^m)$, This is terrible if m is much larger than d,but if solutions are dense, may be much faster than breadth-first \\n\n",
        "    4. space complexity: $O(bm)$, linear space \\n\n",
        "7. Use depth-first if: \\n\n",
        "    Space is restricted \\n\n",
        "    There are many possible solutions with long paths and wrong paths are usually terminated quickly \\n\n",
        "    Search can be fine-tuned quickly \\n\n",
        "    solution are dense \\n\n",
        "8. Use breadth-first if: \\n\n",
        "  Possible infinite paths \\n\n",
        "  Some solutions have short paths \\n\n",
        "  Can quickly discard unlikely paths \\n\n",
        "\n",
        "9. Depth-limited search: Depth-First search but with depth limit l, If l = d (by luck!), then optimal \\n\n",
        "  But:\\n\n",
        "    a. If l < d then incomplete \\n\n",
        "    b. If l > d then not optimal \\n\n",
        "  Time complexity: O(b^1)\n",
        "  Space complexity: O(bl) \\n\n",
        "\n",
        "10. Iterative deepening search: A general strategy to find best depth limit l \\n\n",
        "use Depth-limited search as subroutine, with increasing l.\n",
        "bottom level (depth d) are generated once, up to the children of the root, which are\n",
        "generated d times \\n\n",
        "Complete & optimal: Goal is always found at depth d, the depth of the shallowest goal-node. \\n\n",
        "time complexity: O(b^d) \\n\n",
        "space complexity: O(bd) \\n\n",
        "N(IDS) = $(d)(b^1) +(d−1)(b^2)+(d−2)(b^3)...+b^d$ \\n\n",
        " \n",
        "11. Impact of Task Environments: The properties of the task environments change the types of solutions that we need.\n",
        "  a. If an environment is: \\n\n",
        "    • Fully observable \\n\n",
        "    • Deterministic  \\n\n",
        "    • Known environment \\n\n",
        "  The solution to any problem in such an environment is a fixed sequence of actions. \\n\n",
        "  b. if the environment is:  \\n\n",
        "    • Partially observable or  \\n\n",
        "    • Nondeterministic   \\n\n",
        "  The solution must recommend different future actions depending on the what\n",
        "percepts it receives. This could be in the form of a branching strategy \\n\n",
        "12. This comparison is for tree-like search versions which don’t check for\n",
        "repeated states. For graph searches which do check, the main differences are that depth-first\n",
        "search is complete for finite state spaces, and the space and time complexities are bounded\n",
        "by the size of the state space (the number of vertices and edges, |V|+|E|).\n",
        "#### summary\n",
        "  • Before an agent can start searching, a well-defined problem must be formulated.\\n\n",
        "  • A problem consists of five parts: the initial state, a set of actions, a transition model\n",
        "describing the results of those actions, a set of goal states, and an action cost function.\\n\n",
        "  • The environment of the problem is represented by a state space graph. A path through\n",
        "the state space (a sequence of actions) from the initial state to a goal state is a solution.\\n\n",
        "  • Search algorithms generally treat states and actions as atomic, without any internal\n",
        "structure (although we introduced features of states when it came time to do learning).\\n\n",
        "  • Search algorithms are judged on the basis of completeness, cost optimality, time complexity,\n",
        "and space complexity.\\n\n",
        "  • **Uninformed search** methods have access only to the problem definition. Algorithms\n",
        "build a search tree in an attempt to find a solution. Algorithms differ based on which\n",
        "node they expand first:\\n\n",
        "      • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\n",
        "Best-first search selects nodes for expansion using to an evaluation function.\n",
        "      • Breadth-first search expands the shallowest nodes first; it is complete, optimal\n",
        "for unit action costs, but has exponential space complexity.\\n\n",
        "      • Uniform-cost search expands the node with lowest path cost, g(n), and is optimal\n",
        "for general action costs.\\n\n",
        "      • Depth-first search expands the deepest unexpanded node first. It is neither complete\n",
        "nor optimal, but has linear space complexity. Depth-limited search adds a\n",
        "depth bound.\\n\n",
        "      • Iterative deepening search calls depth-first search with increasing depth limits\n",
        "until a goal is found. It is complete when full cycle checking is done, optimal for\n",
        "unit action costs, has time complexity comparable to breadth-first search, and has\n",
        "linear space complexity.\\n\n",
        "      • Bidirectional search expands two frontiers, one around the initial state and one\n",
        "around the goal, stopping when the two frontiers meet.\n",
        "\"\"\"\n",
        "\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",
        "\"State space\" : \"all states reachable from the initial state by any sequence of actions\",\n",
        "\"path\" : \"a sequence of actions leading from one state to another state\",\n",
        "\"Solution\" : \"a path from initial state to goal state\",\n",
        "\"optimal solution\" : \"no solution has a lower path cost\",\n",
        "\"frontier\" : \"states are available for expanding\",\n",
        "\"Time complexity\" : \"# of nodes generated (worst case)\",\n",
        "\"Completeness\" : \"always find the solution\",\n",
        "\"Space complexity\" : \"# of nodes simultaneously in memory (worst case)\",\n",
        "\"Strategies\" : \"order of tree expansion, implemented by different queue structures (LIFO, FIFO, priority)\",\n",
        "\"reached\" : \"state that has had a node generated for it has been reached\",\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 116,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H3Gzh8Eix8Vu"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0ff18bc5-1c2f-45e7-dcf5-692790f8c49f"
      },
      "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",
        "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": 117,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 3.3 Search Algorithms' is too long!\nWARNING: Your summary of 'AIMA Chapter 3.4 Uninformed Search Strategies' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n1. problem-solving agent: When the correct action to take is not immediately obvious, an agent may need to to plan\nahead: to consider a sequence of actions that form a path to a goal state \n\n2. Problem-solving agents use **atomic** representations,that Search\nis, states of the world are considered as wholes, with no internal structure visible to the\nproblem-solving algorithms \n\n3. Agents that use **factored or structured** representations of states\nare called planning agents \n\n4. informed algorithms: agent can estimate how\nfar it is from the goal \n\n5. four-phase problem-solving process: \n\n  a. Goal formulation: The agent adopts the goal of reaching Bucharest. Goals organize Goal formulation\nbehavior by limiting the objectives and hence the actions to be considered.\n  b. Problem formulation: The agent devises a description of the Problem formulation states and actions necessary\nto reach the goal \n\n  c. Search: Before taking any action in the real world, the agent simulates sequences of\nactions in its model, searching until it finds a sequence of actions that reaches the goal. \n\n  d. execution \n\n6. path: a squence of actions \n\n  solution: a path from initial state to goal \n\n  optimal solution has the lowest path cost among all solutions \n\n7. The process of removing detail from a representation is called Abstraction abstraction \n\n \n\n## AIMA Chapter 3.2 Example Problems\n \n### 3.2 example problem\n  1. A standardized problem is intended to illustrate or exercise various problem-solving meth-\nproblem.It can be given a concise, exact description and hence is suitable as a benchmark for\nReal-world problem researchers to compare the performance of algorithms. \n\n  2. real-world problem, such as robot\nnavigation, is one whose solutions people actually use, and whose formulation is idiosyncratic,\nnot standardized, because, for example, each robot has different sensors that produce\ndifferent data. \n\n####3.2.1 standardized problems : grid world problems \n\n####3.2.2 real-world prblems: route-finding problem \n\n\n#####node.PATH-COST: the total cost of the path from the initial state to this node. In mathematical\nformulas, we use g(node) as a synonym for PATH-COST.\n\n##### best-first-search\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 , with node as an element\n  reached←a lookup table, with one entry with key problem.INITIAL and value node\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    for each child in EXPAND(problem, node) do\n      s←child.STATE\n      if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n        reached[s]←child\n        add child to frontier\n  return failure\n\n\n\nfunction EXPAND(problem, node) yields nodes\n  s←node.STATE\n  for each action in problem.ACTIONS(s) do\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```\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \n### 3.3 search algo\n  1. search algo: takes a search problem as input, returns a solution or failure \n\n  2. **distinction** between the state space and the search tree:\nThe state space describes the (possibly infinite) set of states in the world, and the actions\nthat allow transitions from one state to another. \nThe search tree describes paths between these states, reaching towards the goal. \nThe search tree may have multiple paths to any given state, \nbut each node in the tree has a unique path back to the\nroot (as in all trees) \n\n  3. The **frontier** is the set of nodes that have been reached but not yet\nexpanded;\ninterior is the set of nodes that have been expanded;\nexterior is the set of states that have not been reached.\n\n#### 3.3.1 best-first search\n1. best-first search: choose a node, n, with minimum value of some f(n).\n\n\n#### 3.3.2 search data structures\n1. node = <state, parent-node, children,\naction, path-cost, depth> \n\n  data structures to store the frontier:queue, 3 operations on a frontier are: \n\n  • IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.\n\n  • POP(frontier) removes the top node from the frontier and returns it.\n\n  • TOP(frontier) returns (but does not remove) the top node of the frontier.\n\n\n2. 3 kinds of queues: \n\n  • Priority queue: first pops the node with the minimum cost according to some evaluation\nfunction, f , used in best-first search. \n\n  • A FIFO queue or first-in-first-out queue first pops the node that was added to the queue\nfirst; used in breadth-first search. \n\n  • A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most\nStack recently added node; used in depth-first search. \n\n\n#### 3.3.3 search data structures\n1. redundant path: a worse way to get to the same state \n\n2. how to eliminate repeated states/redundant path?  \n\n  • remember all previously reached states (as best-first search does), allowing \n\n  • don't need to worry: some problem formulations where it is rare or impossible for two paths to reach the same state.allowing \n  ##### We call a search algorithm a graph search if it checks for redundant \n\nTree-like search paths and a tree-like search6 if it does not check.\n  • only check for cycles, but not for redundant paths in general:\n  see if the state at the end of the path has appeared earlier in the path. \n\n##### 3.3.4 measure problem-solving performance\n  • Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not? \n\n  • Cost optimality: Does it find a solution with the lowest path cost of all solutions? \n\n  • Time complexity: How long does it take to find a solution? This can be measured in\nseconds, or more abstractly by the number of states and actions considered.\n\n  • Space complexity: How much memory is needed to perform the search? \n3. complete guarantee: systematic in the way it explores an infinite state space, \n  making sure it can eventually reach any state that is connected to the initial state. \n\n  \n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n###3.4 uinformed search\n#### 3.4.1 breadth-first search\n1. complete: \n\n  • a systematic search strategy:if the root node is expanded first, \n  then all the successors of the root node are expanded next,\nthen their successors. BFS is complete\neven on infinite state spaces. \n\n  • implement BFS as a call to\nBEST-FIRST-SEARCH where $f(n)=depth of the node$ \n\n • BFS always finds a solution with a minimal number of actions, because\nwhen it is generating nodes at depth d, it has already generated all the nodes at depth d-1,\nso if one of them were a solution, it would have been found. \n\n • it is cost-optimal if all actions have same cost \n\n  #####efficient tricks: \n  • A first-in-first-out queue:faster than a priority queue, and will give correct order of nodes: new\nnodes go to the back of the queue \n\n  • can do an **early goal test**,\nLate goal test checking whether a node is a solution as soon as it is generated, rather than **late goal test**\nthat best-first search uses, waiting until a node is popped off the queue. \n\n\n#### 3.4.2 Dijkstra's algo or uniform-cost search\n1.  Dijkstra's algo: When actions have different costs, an obvious choice is to use best-first search where $\nf(n)=cost from root to current node$.\n\n2. time and space complexity is $O(b^{1+[C^*/{\\epsilon]}}),C^*:$ the cost of the optimal solution; \n$\\epsilon$: a lower bound on the cost of each action \n\n  • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\nbefore exploring paths involving a high-cost and perhaps useful action. \n\n  • When all action costs are equal, it is just O(b^(d+1)), and it is similar to BFS.\n\n\n3. complete and cost-optimal: \n  • the first solution it finds\nwill have a cost that is at least as low as the cost of any other node. \n  • it considers all paths systematically in order of increasing cost, never getting caught\ngoing down a single infinite path \n\n#### 3.4.3 depth-first search\n1. DFS always expands the deepest node in the frontier. It could be implemented\nas a call to BEST-FIRST-SEARCH where $f(n)=negative\nof the depth$.\n\n2. not cost-optimal: it returns the first solution it\nfinds, even if it is not cheapest \n\n3. incomplete: In cyclic state spaces it can get stuck in an infinite loop; some implementations\nof DFS check each new node for cycles. DFS\nsearch is not systematic: it can get stuck going down an infinite path, even if there are no\ncycles. \n\n4. where a tree-like search is feasible,\ndepth-first search has much smaller needs for memory. \n\n5. A variant of depth-first search **backtracking search**: use less memory  \n\n  • only one successor is generated at a time rather; \n  each partially expanded node remembers which successor to generate next.\n\n  • successors are generated by modifying the current state description directly\nrather than allocating memory for a brand-new state. This reduces the memory requirements\nto just one state description and a path of O(m) actions \n\n  • backtracking has the option of maintaining an\nefficient set data structure for the states on the current path, allowing to check for a cyclic\npath in O(1) time rather than O(m).\n\n  • must undo each action when we backtrack.\n\n\n#### 3.4.4 depth-limited and iterative deepening search\n##### depth-limited\n1. depth-limited: a version of DFS which we supply a depth limit,$l$, treat all nodes\nat depth l as if they had no successors \n\n2. The time complexity is $O(b^l)$ and\nthe space complexity is $O(bl)$\n\n\n3. incomplete \n\n4. can't eliminate redundant paths but can eliminate cycles \n\n5. diameter of the state-space graph can reduce l and give a better depth limit \n\n\n##### iterative deepening search\n6. solves the problem of picking a good value for l by trying\nsearch all values: 0,1,2...—until either a solution is found, \nor the returns the failure value rather than the cutoff value\n7. combine DFS & BDF: \n\n  •DFS: memory requirements: O(bd) when there is a\nsolution, or O(bm) on finite state spaces with no solution \n\n • BFS: IDS is optimal for problems where all actions have the same cost, and is complete on\nfinite acyclic state spaces, or on any finite state space when we check nodes for cycles all the\nway up the path. \n\n8. time complexity is O(b^d) when there is a solution, or O(b^m) when there is none.\nbut BFS does this by storing all nodes in memory, while IDS by repeating the previous levels, \nthereby saving memory at the cost of more time \n\n9.IDS is preferred uninformed search when search state space is larger than can fit in memory and\nthe depth of the solution is not known.\n\n#### 3.4.5 Bidirectional search\n1. bidirectional search simultaneously\nsearches forward from the initial state and backwards from the goal state(s), hoping that the\ntwo searches will meet \n\n\n\n\n##### breadth-first-search and uniform-cost search algorithms.\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) then return node\n  frontier←a FIFO queue, with node as an element\n  reached←{problem.INITIAL}\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    for each child in EXPAND(problem, node) do\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##### Iterative deepening and depth-limited tree-like search.\n  ```\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure\n  for depth = 0 to ¥ do\n    result←DEPTH-LIMITED-SEARCH(problem, depth)\n    if result 6= cutoff then return result\n\nfunction DEPTH-LIMITED-SEARCH(problem, ℓ) returns a node or failure or cutoff\n  frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element\n  result←failure\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    if DEPTH(node) > ℓ then\n      result←cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do\n        add child to frontier\n  return result\n\n\n  ```\n\n\n\n\n\n  \n\n\n## Module 3 Lecture Notes\n\nThis chapter has introduced search algorithms that an agent can use to select action sequences\nin a wide variety of environments—as long as they are **episodic, single-agent, fully observable,\ndeterministic, static, discrete, and completely known** \n\n1. A problem-solving agent must **plan ahead**.The computational process that it\nundertakes is called **search**.\nIt will consider a sequence of actions that form a path to a goal state. \nSuch a sequence is called a solution.\n\n2. define search problem:States,initial state,Actions,Transition Mode,Path cost,Goal test\n3. basic search algo:\n\n  A.  tree search: \n\n    a.  Enumerate in some order all possible paths from the initial state\n\n    b.  ROOT= initial state \n\n    Nodes in search tree generated through transition model \n\n    treats different paths to the same node as distinct \n\n    c. A state is a (representation of a) physical configuration \n\n    d. A state is a (representation of a) physical configuration, node = <state, parent-node, children,\naction, path-cost, depth>,EXPAND function uses the Actions and Transition Model to create the\ncorresponding states creates new nodes,\n  B. graph search:\n\n    a. Check to see if a node has been visited before adding to search queue\n\n    b. must keep track of all possible states (can use a lot of memory)\n\n4. Uninformed search: All non-goal nodes in frontier look equally good, Informed search: Some non-goal nodes can be ranked above others.\n5. $b$: maximum branching factor\n\n  $d$: depth of least cost solution\n\n  $m$: maximum depth of state space($\\infty$)\n\n6. **Breadth-first search**: \n  expand shallowest unexpanded node \n\n  frontier is FIFO (First-In-First-Out) Queue(Put successors at the end of frontier successor list)\n\n  property:\n\n    1. complete: yes if b is finte\n\n    2. optimal: yes if cost=1/step, not optimal in general\n\n    3. time complexity:  $1+b+b^2+b^3+… +b^d = O(b^d)$\n    4. space complexity: $O(b^d)$(keeps every node in memory)\n\n\n6. **depth-first search**: \n  expand deepest unexpanded node \n\n  LIFO(Last-In-First-Out:Put successors at the front of frontier successor list)\n  property:\n\n    1. complete: No. It fails in infinite-depth spaces, spaces with loops.If we modify it to avoid repeated states along path, then it is complete in finite spaces \n\n    2. optimal: No \n\n    3. time complexity:  $ O(b^m)$, This is terrible if m is much larger than d,but if solutions are dense, may be much faster than breadth-first \n\n    4. space complexity: $O(bm)$, linear space \n\n7. Use depth-first if: \n\n    Space is restricted \n\n    There are many possible solutions with long paths and wrong paths are usually terminated quickly \n\n    Search can be fine-tuned quickly \n\n    solution are dense \n\n8. Use breadth-first if: \n\n  Possible infinite paths \n\n  Some solutions have short paths \n\n  Can quickly discard unlikely paths \n\n\n9. Depth-limited search: Depth-First search but with depth limit l, If l = d (by luck!), then optimal \n\n  But:\n\n    a. If l < d then incomplete \n\n    b. If l > d then not optimal \n\n  Time complexity: O(b^1)\n  Space complexity: O(bl) \n\n\n10. Iterative deepening search: A general strategy to find best depth limit l \n\nuse Depth-limited search as subroutine, with increasing l.\nbottom level (depth d) are generated once, up to the children of the root, which are\ngenerated d times \n\nComplete & optimal: Goal is always found at depth d, the depth of the shallowest goal-node. \n\ntime complexity: O(b^d) \n\nspace complexity: O(bd) \n\nN(IDS) = $(d)(b^1) +(d−1)(b^2)+(d−2)(b^3)...+b^d$ \n\n \n11. Impact of Task Environments: The properties of the task environments change the types of solutions that we need.\n  a. If an environment is: \n\n    • Fully observable \n\n    • Deterministic  \n\n    • Known environment \n\n  The solution to any problem in such an environment is a fixed sequence of actions. \n\n  b. if the environment is:  \n\n    • Partially observable or  \n\n    • Nondeterministic   \n\n  The solution must recommend different future actions depending on the what\npercepts it receives. This could be in the form of a branching strategy \n\n12. This comparison is for tree-like search versions which don’t check for\nrepeated states. For graph searches which do check, the main differences are that depth-first\nsearch is complete for finite state spaces, and the space and time complexities are bounded\nby the size of the state space (the number of vertices and edges, |V|+|E|).\n#### summary\n  • Before an agent can start searching, a well-defined problem must be formulated.\n\n  • A problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n  • The environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\n\n  • Search algorithms generally treat states and actions as atomic, without any internal\nstructure (although we introduced features of states when it came time to do learning).\n\n  • Search algorithms are judged on the basis of completeness, cost optimality, time complexity,\nand space complexity.\n\n  • **Uninformed search** methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n\n      • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\nBest-first search selects nodes for expansion using to an evaluation function.\n      • Breadth-first search expands the shallowest nodes first; it is complete, optimal\nfor unit action costs, but has exponential space complexity.\n\n      • Uniform-cost search expands the node with lowest path cost, g(n), and is optimal\nfor general action costs.\n\n      • Depth-first search expands the deepest unexpanded node first. It is neither complete\nnor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n      • Iterative deepening search calls depth-first search with increasing depth limits\nuntil a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has\nlinear space complexity.\n\n      • Bidirectional search expands two frontiers, one around the initial state and one\naround the goal, stopping when the two frontiers meet.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - all states reachable from the initial state by any sequence of actions\n* **Path** - a sequence of actions leading from one state to another state\n* **Solution** - a path from initial state to goal state\n* **Optimal solution** - no solution has a lower path cost\n* **Frontier** - states are available for expanding\n* **Time complexity** - # of nodes generated (worst case)\n* **Completeness** - always find the solution\n* **Space complexity** - # of nodes simultaneously in memory (worst case)\n* **Strategies** - order of tree expansion, implemented by different queue structures (LIFO, FIFO, priority)\n* **Reached** - state that has had a node generated for it has been reached\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": "zl8uHPoAa1W5"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "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",
        "### 3.5.1 greedy best-first search \n",
        "1. f(n) = h(n)\n",
        "### 3.5.2 A*\n",
        "1. f(n) = g(n)+h(n) \\n\n",
        "2. A∗ search is complete. \\n\n",
        "3. properties of h(n): admissibilty/consistency\n",
        "  if h(n) is admissible, A* is cost-optimal \\n\n",
        "  • g∗(n) to mean the cost of the optimal path from the start \\n\n",
        "  • h∗(n) to mean the cost of the optimal path from n to the nearest goal, we have:\\n\n",
        "  • f(n) > C∗ (otherwise n would have been expanded)\\n\n",
        "  • f(n) = g(n)+h(n) (by definition)\\n\n",
        "  • f(n) = g∗(n)+h(n) (because n is on an optimal path)\\n\n",
        "  • f(n) ≤ g∗(n)+h∗(n) (because of admissibility, h(n) ≤ h∗(n))\\n\n",
        "  • f(n) ≤ C∗ (by definition, C∗ = g∗(n)+h∗(n)) \\n \n",
        "  The first and last lines form a contradiction, so it must be that A∗ returns only cost-optimal paths.\\n\n",
        "4. consistency:\\n \n",
        "  • A heuristic h(Consistency n) is consistent if, for\n",
        "every node n and every successor n′ of n generated by an action a, we have:\\n\n",
        "  h(n) ≤ c(n,a,n′)+h(n′) (Triangle inequality)\\n\n",
        "  • c(n,a,a′) of the action from n to n' \\n\n",
        "5. Every consistent heuristic is admissible (but not vice versa), with a consistent heuristic,\n",
        "A∗ is cost-optimal \\n\n",
        "  with a consistent heuristic, the first time we reach a state it will be on an optimal path, \n",
        "  so we never have to re-add a state to the frontier, and never have to change an entry in reached. \n",
        "  But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, \n",
        "  and if each new path has a lower path cost than the previous one, \n",
        "  then we will end up with multiple nodes for that state in the frontier, \n",
        "  costing us both time and space. \n",
        "  to avoid inconsistency, some implementations of A∗ take care to only enter a state\n",
        "into the frontier once, and if a better path to the state is found, all the successors of the state\n",
        "are updated (which requires that nodes have child pointers as well as parent pointers). \\n\n",
        "\n",
        "### 3.5.4 weighted A∗ \n",
        "1. f(n) = g(n)+W×h(n), for some W>1 \\n\n",
        "2. \n",
        "• A∗ search: g(n)+h(n)(W=1) \\n\n",
        "• Uniform-cost search: g(n)(W=0) \\n\n",
        "• Greedy best-first search: h(n) (W=$\\infty$) \\n\n",
        "• Weighted A∗ search: g(n)+W×h(n) (1<W<$\\infty$) \\n\n",
        "\n",
        "\n",
        "##### recursive best-first search\n",
        "  ```\n",
        "function RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution or failure\n",
        "  solution, fvalue←RBFS(problem,NODE(problem.INITIAL),¥)\n",
        "  return solution\n",
        "\n",
        "function RBFS(problem, node, f limit) returns a solution or failure, and a new f -cost limit\n",
        "  if problem.IS-GOAL(node.STATE) then return node\n",
        "  successors←LIST(EXPAND(node))\n",
        "  if successors is empty then return failure, ¥\n",
        "  for each s in successors do // update f with value from previous search\n",
        "    s.f ←max(s.PATH-COST + h(s), node.f ))\n",
        "  while true do\n",
        "    best←the node in successors with lowest f -value\n",
        "    if best. f > f limit then return failure, best. f\n",
        "    alternative←the second-lowest f -value among successors\n",
        "    result, best. f ←RBFS(problem, best,min( f limit,alternative))\n",
        "    if result 6= failure then return result, best. f\n",
        "\n",
        "  ```\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "#### 3.6.1 The effect of heuristic accuracy\n",
        "1. effective branching factor b∗: The effective branching factor can vary across problem instances, but usually\n",
        "for a specific domain (such as 8-puzzles) it is fairly constant across all nontrivial problem instances.\n",
        "Therefore, experimental measurements of b∗ on a small set of problems can provide a\n",
        "good guide to the heuristic’s overall usefulness. A well-designed heuristic would have a value \\n\n",
        "of b∗ close to 1\n",
        "2. reduces the effective depth by a constant kh compared to\n",
        "the true depth.\n",
        "3. it is better to use a\n",
        "heuristic function with higher values, provided it is consistent and that the computation time\n",
        "for the heuristic is not too long. higher h(n) drawback\n",
        "is that h(n) takes longer to compute.\n",
        "4.derive h(n) from relaxed problem\n",
        "• The state-space graph of the relaxed problem is a supergraph of the original state Relaxed problem\n",
        "space because the removal of restrictions creates added edges in the graph\n",
        "• the relaxed problem adds edges to the state-space graph, any optimal solution in\n",
        "the original problem is, by definition, also a solution in the relaxed problem\n",
        "5. derived from subproblem of a given\n",
        "problem.\n",
        "• pattern databases is to store these exact solution costs for every possible Pattern database\n",
        "subproblem instance\n",
        "6. with landmarks:\n",
        "choose a few (perhaps 10 or 20) landmark points, then for each landmark L and for each other vertex v in the graph, we compute\n",
        "and store C∗(v,L), the exact cost of the optimal path from v to L.\n",
        "A greedy approach is to pick a first landmark at random, then find the point\n",
        "that is furthest from that, and add it to the set of landmarks, and continue, at each iteration\n",
        "adding the point that maximizes the distance to the nearest landmark.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "1. Best-first search: $evaluation funct = f(n)$ \\n\n",
        "2. A heuristic function h(n): takes a state n and\n",
        "returns an estimate of the distance from n. \\n\n",
        "3. Greedy Best-First Search: $ f(n)=h(n)$ \\n\n",
        "4. A*:\n",
        "  • Best-known form of best-first search.\\n\n",
        "  • $f(n)=g(n) + h(n)$\n",
        "    1. g(n) the actual cost (so far) to reach the node \\n\n",
        "    2. h(n) estimated cost to get from the node to the goal\\n\n",
        "    3. f(n) estimated total cost of path through n to goal \\n\n",
        "5. A heuristic h(n) is **admissible or optimistic** if it never overestimates the cost to reach the goal \\n\n",
        "  • Formally: for all n, n a node:\\n\n",
        "  • $ 0  \\leqslant h(n) \\leqslant h*(n)$ where h*(n) is the true cost from n\n",
        "  • h(n)>=0 so h(G)=0 for any goal G.\\n\n",
        "  Example: $h_{SLD}(n)$ never overestimates the actual road distance\\n\n",
        "  Theorem: If h(n) is admissible, A* using Tree Search is optimal\\n\n",
        "6. Relaxed problems \\n\n",
        "  • A problem with fewer restrictions on the actions \\n\n",
        "  • The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
        "original problem \\n\n",
        "7. Dominance: A metric on better heuristics \\n\n",
        "  If $ h_{2}(n) $ ≥ $ h_{1}(n) $ for all n (both admissible) \\n\n",
        "    • then  $h_{2}$ dominates $ h_{1} $ \\n\n",
        "  So  $ h_{2} $ is optimistic, but more accurate than $h_{1}$ \\n\n",
        "    • $ h_{2} $ is therefore better for search \\n\n",
        "    • Notice: $ h_{md} $ dominates $ h_{oop} $\n",
        "    • ($ h_{oop} $ = number of out of place tiles,If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\n",
        "gives the shortest solution \\n\n",
        "    • $h_{md}$= total Manhattan distance,If the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\n",
        "gives the shortest solution) \\n\n",
        "    • h*(n) dominates all other heuristics \\n\n",
        "    • $ h_{teleportation}(n)=0 $ is dominated by all heuristics 瞬间转移\\n\n",
        "8.comparision\n",
        "  • if want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. \\n \n",
        "  • Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary. \\n\n",
        "  • If want to find paths to one location, or the closest of several goals, use Greedy Best First Search or A*. \\n\n",
        "  • Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. \n",
        "  Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic admissible. \\n\n",
        "  • As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. \n",
        "  As the heuristic becomes larger, A* turns into Greedy Best First Search.\n",
        "##### summary\n",
        "1. Informed search methods have access to a heuristic function h(n) that estimates the\n",
        "cost of a solution from n. They may have access to additional information such as\n",
        "pattern databases with solution costs. \\n\n",
        "  • Greedy best-first search expands nodes with minimal h(n). It is not optimal but\n",
        "is often efficient.\\n\n",
        "  • A∗ search expands nodes with minimal f (n) = g(n)+h(n). A∗ is complete and\n",
        "optimal, provided that h(n) is admissible. The space complexity of A∗ is still an\n",
        "issue for many problems.\\n\n",
        "  • Bidirectional A∗ search is sometimes more efficient than A∗ itself.\\n\n",
        "  • IDA∗ (iterative deepening A∗ search) is an iterative deepening version of A∗, and\n",
        "thus adresses the space complexity issue.\\n\n",
        "  • RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗)\n",
        "are robust, optimal search algorithms that use limited amounts of memory; given\n",
        "enough time, they can solve problems for which A∗ runs out of memory.\n",
        "Beam search puts a limit on the size of the frontier; that makes it incomplete\n",
        "and suboptimal, but it often finds reasonably good solutions and runs faster than\n",
        "complete searches.\\n\n",
        "  • Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\n",
        "but sacrificing optimality\\n\n",
        "2. good heuristic function: \n",
        "  • relaxing the problem definition \\n\n",
        "  • storing precomputed solution costs for subproblems in a pattern database\\n\n",
        "  • defining landmarks \\n\n",
        "  • learning from experience with the problem class\\n\n",
        "\n",
        "\n",
        "#### 3.5.5 memory-bounded search\n",
        "1. in implementation of best-first search, a state that is on the frontier is stored in two places: as a node in the frontier(to expand next)\n",
        "and as an entry in the table of reached states (visited). \n",
        "\n",
        "But some implementations keep a state in only one of the two places, saving a bit of space at the\n",
        "cost of complicating (and perhaps slowing down) the algorithm \\n\n",
        "  • remove states from reached when we can prove that they are\n",
        "no longer needed. For some problems, we can use the separation propert, along with the prohibition of U-turn actions, to ensure that all actions either move\n",
        "outwards from the frontier or onto another frontier state. In that case, we need only check the\n",
        "frontier for redundant paths, and we can eliminate the reached table \\n\n",
        "  • keep reference counts of the number of times a state has\n",
        "been reached, and remove it from the reached table when there are no more ways to reach\n",
        "the state. For example, on a grid world where each state can be reached only from its four\n",
        "neighbors, once we have reached a state four times, we can remove it from the table.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 118,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kq6gbjf-yKLv"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c0eaf234-10ec-472b-f0fc-f1ad1e210383"
      },
      "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": 119,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 3.5 Informed (Heuristic) Search Strategies' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n\n### 3.5.1 greedy best-first search \n1. f(n) = h(n)\n### 3.5.2 A*\n1. f(n) = g(n)+h(n) \n\n2. A∗ search is complete. \n\n3. properties of h(n): admissibilty/consistency\n  if h(n) is admissible, A* is cost-optimal \n\n  • g∗(n) to mean the cost of the optimal path from the start \n\n  • h∗(n) to mean the cost of the optimal path from n to the nearest goal, we have:\n\n  • f(n) > C∗ (otherwise n would have been expanded)\n\n  • f(n) = g(n)+h(n) (by definition)\n\n  • f(n) = g∗(n)+h(n) (because n is on an optimal path)\n\n  • f(n) ≤ g∗(n)+h∗(n) (because of admissibility, h(n) ≤ h∗(n))\n\n  • f(n) ≤ C∗ (by definition, C∗ = g∗(n)+h∗(n)) \n \n  The first and last lines form a contradiction, so it must be that A∗ returns only cost-optimal paths.\n\n4. consistency:\n \n  • A heuristic h(Consistency n) is consistent if, for\nevery node n and every successor n′ of n generated by an action a, we have:\n\n  h(n) ≤ c(n,a,n′)+h(n′) (Triangle inequality)\n\n  • c(n,a,a′) of the action from n to n' \n\n5. Every consistent heuristic is admissible (but not vice versa), with a consistent heuristic,\nA∗ is cost-optimal \n\n  with a consistent heuristic, the first time we reach a state it will be on an optimal path, \n  so we never have to re-add a state to the frontier, and never have to change an entry in reached. \n  But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, \n  and if each new path has a lower path cost than the previous one, \n  then we will end up with multiple nodes for that state in the frontier, \n  costing us both time and space. \n  to avoid inconsistency, some implementations of A∗ take care to only enter a state\ninto the frontier once, and if a better path to the state is found, all the successors of the state\nare updated (which requires that nodes have child pointers as well as parent pointers). \n\n\n### 3.5.4 weighted A∗ \n1. f(n) = g(n)+W×h(n), for some W>1 \n\n2. \n• A∗ search: g(n)+h(n)(W=1) \n\n• Uniform-cost search: g(n)(W=0) \n\n• Greedy best-first search: h(n) (W=$\\infty$) \n\n• Weighted A∗ search: g(n)+W×h(n) (1<W<$\\infty$) \n\n\n\n##### recursive best-first search\n  ```\nfunction RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution or failure\n  solution, fvalue←RBFS(problem,NODE(problem.INITIAL),¥)\n  return solution\n\nfunction RBFS(problem, node, f limit) returns a solution or failure, and a new f -cost limit\n  if problem.IS-GOAL(node.STATE) then return node\n  successors←LIST(EXPAND(node))\n  if successors is empty then return failure, ¥\n  for each s in successors do // update f with value from previous search\n    s.f ←max(s.PATH-COST + h(s), node.f ))\n  while true do\n    best←the node in successors with lowest f -value\n    if best. f > f limit then return failure, best. f\n    alternative←the second-lowest f -value among successors\n    result, best. f ←RBFS(problem, best,min( f limit,alternative))\n    if result 6= failure then return result, best. f\n\n  ```\n\n\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n#### 3.6.1 The effect of heuristic accuracy\n1. effective branching factor b∗: The effective branching factor can vary across problem instances, but usually\nfor a specific domain (such as 8-puzzles) it is fairly constant across all nontrivial problem instances.\nTherefore, experimental measurements of b∗ on a small set of problems can provide a\ngood guide to the heuristic’s overall usefulness. A well-designed heuristic would have a value \n\nof b∗ close to 1\n2. reduces the effective depth by a constant kh compared to\nthe true depth.\n3. it is better to use a\nheuristic function with higher values, provided it is consistent and that the computation time\nfor the heuristic is not too long. higher h(n) drawback\nis that h(n) takes longer to compute.\n4.derive h(n) from relaxed problem\n• The state-space graph of the relaxed problem is a supergraph of the original state Relaxed problem\nspace because the removal of restrictions creates added edges in the graph\n• the relaxed problem adds edges to the state-space graph, any optimal solution in\nthe original problem is, by definition, also a solution in the relaxed problem\n5. derived from subproblem of a given\nproblem.\n• pattern databases is to store these exact solution costs for every possible Pattern database\nsubproblem instance\n6. with landmarks:\nchoose a few (perhaps 10 or 20) landmark points, then for each landmark L and for each other vertex v in the graph, we compute\nand store C∗(v,L), the exact cost of the optimal path from v to L.\nA greedy approach is to pick a first landmark at random, then find the point\nthat is furthest from that, and add it to the set of landmarks, and continue, at each iteration\nadding the point that maximizes the distance to the nearest landmark.\n\n\n\n\n\n\n\n## Module 4 Lecture Notes\n\n1. Best-first search: $evaluation funct = f(n)$ \n\n2. A heuristic function h(n): takes a state n and\nreturns an estimate of the distance from n. \n\n3. Greedy Best-First Search: $ f(n)=h(n)$ \n\n4. A*:\n  • Best-known form of best-first search.\n\n  • $f(n)=g(n) + h(n)$\n    1. g(n) the actual cost (so far) to reach the node \n\n    2. h(n) estimated cost to get from the node to the goal\n\n    3. f(n) estimated total cost of path through n to goal \n\n5. A heuristic h(n) is **admissible or optimistic** if it never overestimates the cost to reach the goal \n\n  • Formally: for all n, n a node:\n\n  • $ 0  \\leqslant h(n) \\leqslant h*(n)$ where h*(n) is the true cost from n\n  • h(n)>=0 so h(G)=0 for any goal G.\n\n  Example: $h_{SLD}(n)$ never overestimates the actual road distance\n\n  Theorem: If h(n) is admissible, A* using Tree Search is optimal\n\n6. Relaxed problems \n\n  • A problem with fewer restrictions on the actions \n\n  • The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem \n\n7. Dominance: A metric on better heuristics \n\n  If $ h_{2}(n) $ ≥ $ h_{1}(n) $ for all n (both admissible) \n\n    • then  $h_{2}$ dominates $ h_{1} $ \n\n  So  $ h_{2} $ is optimistic, but more accurate than $h_{1}$ \n\n    • $ h_{2} $ is therefore better for search \n\n    • Notice: $ h_{md} $ dominates $ h_{oop} $\n    • ($ h_{oop} $ = number of out of place tiles,If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\ngives the shortest solution \n\n    • $h_{md}$= total Manhattan distance,If the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\ngives the shortest solution) \n\n    • h*(n) dominates all other heuristics \n\n    • $ h_{teleportation}(n)=0 $ is dominated by all heuristics 瞬间转移\n\n8.comparision\n  • if want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. \n \n  • Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary. \n\n  • If want to find paths to one location, or the closest of several goals, use Greedy Best First Search or A*. \n\n  • Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. \n  Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic admissible. \n\n  • As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. \n  As the heuristic becomes larger, A* turns into Greedy Best First Search.\n##### summary\n1. Informed search methods have access to a heuristic function h(n) that estimates the\ncost of a solution from n. They may have access to additional information such as\npattern databases with solution costs. \n\n  • Greedy best-first search expands nodes with minimal h(n). It is not optimal but\nis often efficient.\n\n  • A∗ search expands nodes with minimal f (n) = g(n)+h(n). A∗ is complete and\noptimal, provided that h(n) is admissible. The space complexity of A∗ is still an\nissue for many problems.\n\n  • Bidirectional A∗ search is sometimes more efficient than A∗ itself.\n\n  • IDA∗ (iterative deepening A∗ search) is an iterative deepening version of A∗, and\nthus adresses the space complexity issue.\n\n  • RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗)\nare robust, optimal search algorithms that use limited amounts of memory; given\nenough time, they can solve problems for which A∗ runs out of memory.\nBeam search puts a limit on the size of the frontier; that makes it incomplete\nand suboptimal, but it often finds reasonably good solutions and runs faster than\ncomplete searches.\n\n  • Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\nbut sacrificing optimality\n\n2. good heuristic function: \n  • relaxing the problem definition \n\n  • storing precomputed solution costs for subproblems in a pattern database\n\n  • defining landmarks \n\n  • learning from experience with the problem class\n\n\n\n#### 3.5.5 memory-bounded search\n1. in implementation of best-first search, a state that is on the frontier is stored in two places: as a node in the frontier(to expand next)\nand as an entry in the table of reached states (visited). \n\nBut some implementations keep a state in only one of the two places, saving a bit of space at the\ncost of complicating (and perhaps slowing down) the algorithm \n\n  • remove states from reached when we can prove that they are\nno longer needed. For some problems, we can use the separation propert, along with the prohibition of U-turn actions, to ensure that all actions either move\noutwards from the frontier or onto another frontier state. In that case, we need only check the\nfrontier for redundant paths, and we can eliminate the reached table \n\n  • keep reference counts of the number of times a state has\nbeen reached, and remove it from the reached table when there are no more ways to reach\nthe state. For example, on a grid world where each state can be reached only from its four\nneighbors, once we have reached a state four times, we can remove it from the table.\n\n \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "### 5.1.1 two-player zero-sum game\n",
        "1.The games most commonly studied within AI (such as chess and Go) are what game theorists\n",
        "call deterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect Perfect information\n",
        "information” is a synonym for “fully observable,”and “zero-sum” means that what is good Zero-sum games\n",
        "for one player is just as bad for the other: there is no “win-win” outcome. For games we often\n",
        "use the term move as a synonym for “action” and position as a synonym for “state \n",
        "2. the initial state, ACTIONS function, and RESULT function define the\n",
        "state space graph—a graph where the vertices are states, the edges are moves and a state State space graph\n",
        "might be reached by multiple paths.\n",
        "3. The minimax algorithm performs a complete depth-first exploration of the game tree.\n",
        "If the maximum depth of the tree is m and there are b legal moves at each point, then the\n",
        "time complexity of the minimax algorithm is O(b^m). The space complexity is O(bm) for an\n",
        "algorithm that generates all actions at once, or O(m) for an algorithm that generates actions\n",
        "one at a time \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "\n",
        "#### 5.2.3\n",
        "α = the value of the best (highest-value) choice we have found so far at any choice point\n",
        "along the path for MAX. Think: α = “at least.”\n",
        "β = the value of the best (lowest-value) choice we have found so far at any choice point\n",
        "along the path for MIN. Think: β = “at most.”\n",
        "\n",
        "##### minimax\n",
        " \n",
        "  ```\n",
        "\n",
        "\n",
        "function MINIMAX-SEARCH(game, state) returns an action\n",
        "  player←game.TO-MOVE(state)\n",
        "  value, move←MAX-VALUE(game, state)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n",
        "  v←$-\\infty$\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MIN-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 > v then\n",
        "    v, move←v2, a\n",
        "  return v, move\n",
        "\n",
        "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n",
        "  v←+$\\infty$\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MAX-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 < v then\n",
        "      v, move←v2, a\n",
        "  return v, move\n",
        "\n",
        "  ```\n",
        "##### alpha-beta pruning\n",
        "\n",
        " ```\n",
        "function ALPHA-BETA-SEARCH(game, state) returns an action\n",
        "  player←game.TO-MOVE(state)\n",
        "  value, move←MAX-VALUE(game, state,−¥,+¥)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state,α, β) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n",
        "  v←−$-\\infty$\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α, β)\n",
        "    if v2 > v then\n",
        "      v, move←v2, a\n",
        "      α←MAX(α, v)\n",
        "    if v ≥ β then return v, move\n",
        "  return v, move\n",
        "\n",
        "function MIN-VALUE(game, state,α, β) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n",
        "  v←+$\\infty$\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α, β)\n",
        "    if v2 < v then\n",
        "      v, move←v2, a\n",
        "      β←MIN(β, v)\n",
        "    if v ≤ α then return v, move\n",
        "  return v, move\n",
        "\n",
        " ```\n",
        "\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "1. In other words, we replace the UTILITY function with EVAL, which estimates a\n",
        "state’s utility. We also replace the terminal test by a cutoff test, which Cutoff test must return true for\n",
        "terminal states, but is otherwise free to decide when to cut off the search, based on the search\n",
        "depth and any property of the state that it chooses to consider\n",
        "2. heuristic evaluation func EVAL(s,p) returns an estimate of the expected utility of state\n",
        "s to player p, just as the heuristic functions.For terminal states, it must be that EVAL(s, p)=UTILITY(s, p) and for nonterminal\n",
        "states, the evaluation must be somewhere between a loss and a win: UTILITY(loss, p) ≤\n",
        "EVAL(s, p) ≤ UTILITY(win, p).\n",
        "3. The evaluation function should be applied only to positions that Quiescence are quiescent—that is,\n",
        "positions in which there is no pending move (such as a capturing the queen) that would wildly\n",
        "swing the evaluation. For nonquiescent positions the IS-CUTOFF returns false, and the search\n",
        "Quiescence search continues until quiescent positions are reached\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "\n",
        "1. A game\n",
        "tree in backgammon must include chance nodes in addition to MAX and MIN nodes.\n",
        "2. we can only calculate the expected value of a position: the average over all\n",
        "possible outcomes of the chance node\n",
        "3. \n",
        "This leads us to the expectiminimax value for games with chance nodes\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\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",
        "\n",
        "1. simplest game envi: \\n\n",
        "  • Multiagent \\n\n",
        "  • Static: No change while an agent is deliberating.\\n\n",
        "  • Discrete: A finite set of percepts and actions.\\n\n",
        "  • Fully observable: An agent's sensors give it the complete state of the environment. \\n\n",
        "  • Strategic: The next state is determined by the current state and the action executed\n",
        "by the agent and the actions of one other agent.\\n\n",
        "\n",
        "2. key property: \n",
        "  • Two players alternate moves \\n\n",
        "  • Zero-sum: one player’s loss is another’s gain \\n\n",
        "  • Clear set of legal moves \\n\n",
        "  • Well-defined outcomes (e.g. win, lose, draw) \\n\n",
        "\n",
        "3. minimax:\\n\n",
        "Idea: Make the best move for MAX assuming that MIN always replies with the best\n",
        "move for MIN \\n\n",
        "• For a MAX node, the backed-up value is the maximum of the values of its\n",
        "children (i.e. the best for MAX) \\n\n",
        "• For a MIN node, the backed-up value is the minimum of the values of its\n",
        "children (i.e. the best for MIN)  \\n\n",
        "\n",
        "4. adversarial search(minimax):\n",
        "MAX assumes MIN plays optimally: Maximizes worst-case outcome for MAX. \\n\n",
        "  • The backed-up value of each node in the tree is determined by the values of its\n",
        "children: \\n\n",
        "  • For a MAX node, the backed-up value is the maximum of the values of its\n",
        "children (i.e. the best for MAX) \\n\n",
        "  • For a MIN node, the backed-up value is the minimum of the values of its\n",
        "children (i.e. the best for MIN) \\n\n",
        "  o Even levels represent turns for MAX, initialization= $-infty$ \\n\n",
        "  o Odd levels represent turns for MIN, initialization= $+infty$ \\n\n",
        "\n",
        "5. Alpha-Beta Pruning: \\n\n",
        "  o During Minimax, keep track of two additional values: \\n\n",
        "    α: MAX’s current lower bound on MAX’s outcome， MAX's best action  \\n\n",
        "    β: MIN’s current upper bound on MIN’s outcome \\n\n",
        "  o MAX will never allow a move that could lead to a worse score (for MAX) than α, \n",
        "  for max node , α越大越好 \\n\n",
        "  o MIN will never allow a move that could lead to a better score (for MAX) than β,\n",
        "  for min node 𝛽 越小越好 \\n\n",
        "  o Therefore, stop evaluating a branch whenever: \\n\n",
        "  When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up \\n\n",
        "    • MIN will never select that MAX node \\n\n",
        "  When evaluating a MIN node: a value 𝑣 ≤ 𝛼 is found \\n\n",
        "    • MAX will never select that MIN node \\n\n",
        "\n",
        "6. expectimax and utilities: \\n\n",
        "  Expectimax search: compute the average score under optimal\n",
        "play \\n\n",
        "  Max nodes as in minimax search\n",
        "  Chance nodes are like min nodes but the outcome is\n",
        "  uncertain to Calculate their expected utilities \\n\n",
        "\n",
        "\n",
        "### summary\n",
        "• A game can be defined by the initial state (how the board is set up), the legal actions\n",
        "in each state, the result of each action, a terminal test (which says when the game is\n",
        "over), and a utility function that applies to terminal states to say who won and what the\n",
        "final score is. \\n\n",
        "• In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\n",
        "the minimax algorithm can select optimal moves by a depth-first enumeration\n",
        "of the game tree. \\n\n",
        "• The alpha–beta search algorithm computes the same optimal move as minimax, but\n",
        "achieves much greater efficiency by eliminating subtrees that are provably irrelevant. \\n\n",
        "• Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\n",
        "need to cut the search off at some point and apply a heuristic evaluation function that\n",
        "estimates the utility of a state. \\n\n",
        "• An alternative called Monte Carlo tree search (MCTS) evaluates states not by applying\n",
        "a heuristic function, but by playing out the game all the way to the end and using\n",
        "the rules of the game to see who won. Since the moves chosen during the playout may\n",
        "not have been optimal moves, the process is repeated multiple times and the evaluation\n",
        "is an average of the results. \\n\n",
        "• Many game programs precompute tables of best moves in the opening and endgame so\n",
        "that they can look up a move rather than search. \\n\n",
        "• Games of chance can be handled by expectiminimax, an extension to the minimax\n",
        "algorithm that evaluates a chance node by taking the average utility of all its children,\n",
        "weighted by the probability of each child. \\n\n",
        "• In games of imperfect information, such as Kriegspiel and poker, optimal play requires\n",
        "reasoning about the current and future belief states of each player. A simple approximation can be obtained by averaging the value of an action over each possible\n",
        "configuration of missing information. \\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 111,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "84891643-113d-4d8b-e816-931924c61366"
      },
      "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": 120,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n### 5.1.1 two-player zero-sum game\n1.The games most commonly studied within AI (such as chess and Go) are what game theorists\ncall deterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect Perfect information\ninformation” is a synonym for “fully observable,”and “zero-sum” means that what is good Zero-sum games\nfor one player is just as bad for the other: there is no “win-win” outcome. For games we often\nuse the term move as a synonym for “action” and position as a synonym for “state \n2. the initial state, ACTIONS function, and RESULT function define the\nstate space graph—a graph where the vertices are states, the edges are moves and a state State space graph\nmight be reached by multiple paths.\n3. The minimax algorithm performs a complete depth-first exploration of the game tree.\nIf the maximum depth of the tree is m and there are b legal moves at each point, then the\ntime complexity of the minimax algorithm is O(b^m). The space complexity is O(bm) for an\nalgorithm that generates all actions at once, or O(m) for an algorithm that generates actions\none at a time \n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n#### 5.2.3\nα = the value of the best (highest-value) choice we have found so far at any choice point\nalong the path for MAX. Think: α = “at least.”\nβ = the value of the best (lowest-value) choice we have found so far at any choice point\nalong the path for MIN. Think: β = “at most.”\n\n##### minimax\n \n  ```\n\n\nfunction MINIMAX-SEARCH(game, state) returns an action\n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←$-\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n    v, move←v2, a\n  return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←+$\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move←v2, a\n  return v, move\n\n  ```\n##### alpha-beta pruning\n\n ```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action\n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state,−¥,+¥)\n  return move\n\nfunction MAX-VALUE(game, state,α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←−$-\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α, β)\n    if v2 > v then\n      v, move←v2, a\n      α←MAX(α, v)\n    if v ≥ β then return v, move\n  return v, move\n\nfunction MIN-VALUE(game, state,α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←+$\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α, β)\n    if v2 < v then\n      v, move←v2, a\n      β←MIN(β, v)\n    if v ≤ α then return v, move\n  return v, move\n\n ```\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n1. In other words, we replace the UTILITY function with EVAL, which estimates a\nstate’s utility. We also replace the terminal test by a cutoff test, which Cutoff test must return true for\nterminal states, but is otherwise free to decide when to cut off the search, based on the search\ndepth and any property of the state that it chooses to consider\n2. heuristic evaluation func EVAL(s,p) returns an estimate of the expected utility of state\ns to player p, just as the heuristic functions.For terminal states, it must be that EVAL(s, p)=UTILITY(s, p) and for nonterminal\nstates, the evaluation must be somewhere between a loss and a win: UTILITY(loss, p) ≤\nEVAL(s, p) ≤ UTILITY(win, p).\n3. The evaluation function should be applied only to positions that Quiescence are quiescent—that is,\npositions in which there is no pending move (such as a capturing the queen) that would wildly\nswing the evaluation. For nonquiescent positions the IS-CUTOFF returns false, and the search\nQuiescence search continues until quiescent positions are reached\n\n\n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \n\n1. A game\ntree in backgammon must include chance nodes in addition to MAX and MIN nodes.\n2. we can only calculate the expected value of a position: the average over all\npossible outcomes of the chance node\n3. \nThis leads us to the expectiminimax value for games with chance nodes\n\n\n\n\n\n\n\n\n\n\n\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 \n\n1. simplest game envi: \n\n  • Multiagent \n\n  • Static: No change while an agent is deliberating.\n\n  • Discrete: A finite set of percepts and actions.\n\n  • Fully observable: An agent's sensors give it the complete state of the environment. \n\n  • Strategic: The next state is determined by the current state and the action executed\nby the agent and the actions of one other agent.\n\n\n2. key property: \n  • Two players alternate moves \n\n  • Zero-sum: one player’s loss is another’s gain \n\n  • Clear set of legal moves \n\n  • Well-defined outcomes (e.g. win, lose, draw) \n\n\n3. minimax:\n\nIdea: Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN \n\n• For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX) \n\n• For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)  \n\n\n4. adversarial search(minimax):\nMAX assumes MIN plays optimally: Maximizes worst-case outcome for MAX. \n\n  • The backed-up value of each node in the tree is determined by the values of its\nchildren: \n\n  • For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX) \n\n  • For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN) \n\n  o Even levels represent turns for MAX, initialization= $-infty$ \n\n  o Odd levels represent turns for MIN, initialization= $+infty$ \n\n\n5. Alpha-Beta Pruning: \n\n  o During Minimax, keep track of two additional values: \n\n    α: MAX’s current lower bound on MAX’s outcome， MAX's best action  \n\n    β: MIN’s current upper bound on MIN’s outcome \n\n  o MAX will never allow a move that could lead to a worse score (for MAX) than α, \n  for max node , α越大越好 \n\n  o MIN will never allow a move that could lead to a better score (for MAX) than β,\n  for min node 𝛽 越小越好 \n\n  o Therefore, stop evaluating a branch whenever: \n\n  When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up \n\n    • MIN will never select that MAX node \n\n  When evaluating a MIN node: a value 𝑣 ≤ 𝛼 is found \n\n    • MAX will never select that MIN node \n\n\n6. expectimax and utilities: \n\n  Expectimax search: compute the average score under optimal\nplay \n\n  Max nodes as in minimax search\n  Chance nodes are like min nodes but the outcome is\n  uncertain to Calculate their expected utilities \n\n\n\n### summary\n• A game can be defined by the initial state (how the board is set up), the legal actions\nin each state, the result of each action, a terminal test (which says when the game is\nover), and a utility function that applies to terminal states to say who won and what the\nfinal score is. \n\n• In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\nthe minimax algorithm can select optimal moves by a depth-first enumeration\nof the game tree. \n\n• The alpha–beta search algorithm computes the same optimal move as minimax, but\nachieves much greater efficiency by eliminating subtrees that are provably irrelevant. \n\n• Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\nneed to cut the search off at some point and apply a heuristic evaluation function that\nestimates the utility of a state. \n\n• An alternative called Monte Carlo tree search (MCTS) evaluates states not by applying\na heuristic function, but by playing out the game all the way to the end and using\nthe rules of the game to see who won. Since the moves chosen during the playout may\nnot have been optimal moves, the process is repeated multiple times and the evaluation\nis an average of the results. \n\n• Many game programs precompute tables of best moves in the opening and endgame so\nthat they can look up a move rather than search. \n\n• Games of chance can be handled by expectiminimax, an extension to the minimax\nalgorithm that evaluates a chance node by taking the average utility of all its children,\nweighted by the probability of each child. \n\n• In games of imperfect information, such as Kriegspiel and poker, optimal play requires\nreasoning about the current and future belief states of each player. A simple approximation can be obtained by averaging the value of an action over each possible\nconfiguration of missing information. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\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",
        "1. In this chapter we break open the black box by using a factored representation for each\n",
        "state: a set of variables, each of which has a value. A problem is solved when each variable\n",
        "has a value that satisfies all the constraints on the variable. A problem described this way is\n",
        "called a constraint satisfaction problem, or CSP \\n\n",
        "\n",
        "2. CSPs deal with assignments of values to variables, {Xi =vi,Xj =vj, . . .}. An assignment \n",
        "that does not violate any constraints is called a consistent or legal assignment. A complete \n",
        "assignment is one in which every variable is assigned a value, and a solution to a CSP is\n",
        "a consistent, complete assignment. A partial assignment is one that leaves some variables Solution\n",
        "unassigned, and a partial solution is consistent. Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that Partial solution\n",
        "can be solved very efficiently. \\n\n",
        "\n",
        "3. every finite-domain constraint can\n",
        "be reduced to a set of binary constraints if enough auxiliary variables are introduced. This\n",
        "means that we could transform any CSP into one with only binary constraints—which certainly\n",
        "makes the life of the algorithm designer simpler. Another way to convert an n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be\n",
        "one variable for each constraint in the original graph, and one binary constraint for each pair\n",
        "of constraints in the original graph that share variables \\n\n",
        "\n",
        "\"unary constraint\" : \"restricts the value of a single variable, SA != greeni.\",  \\n\n",
        "\"binary constraint\" : \"A binary constraint relates two variables, SA!=NSW.\",    \\n\n",
        "\"higher-order constraints\" : \"involve 3 or more variables\",    \n",
        "\"Preference (soft constraints)\" : \"indicating which solutions are preferred, red is better than green can be represented by a cost for each variable assignment\", \\n   \n",
        "4. CSPs with preferences can be\n",
        "solved with optimization search methods, either path-based or local. We call such a problem\n",
        "a constrained optimization problem \\n\n",
        "5. constraint propagation: using the constraints to reduce the number of legal values for a variable \\n\n",
        "6. Path consistency tightens the binary constraints by using implicit constraints\n",
        "that are inferred by looking at triples of variables. A two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for\n",
        "every assignment {Xi = a,Xj =b} consistent with the constraints (if any) on {Xi,Xj}, there is\n",
        "an assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}.\n",
        " time is only O(n2d).\\n\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "1. local consistency: treat each variable Local consistency as a node in a graph (see\n",
        "Figure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local\n",
        "consistency in each part of the graph causes inconsistent values \\n\n",
        "2. node-consitent: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\n",
        "values in the variable’s domain satisfy the variable’s unary constraints \\n\n",
        "3. arc-consistent: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\n",
        "binary constraints \\n\n",
        "  More formally, Xi is arc-consistent with respect to another variable Xj if\n",
        "for every value in the current domain Di there is some value in the domain Dj that satisfies\n",
        "the binary constraint on the arc (Xi,Xj) \\n\n",
        "4. A CSP is k-consistent: if, for any set of k−1 variables and for any consistent assignment to those variables,\n",
        "a consistent value can always be assigned to any kth variable.\\n\n",
        "5. A CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-\n",
        "k-consistent consistent,...all the way down to 1-consistent. Now suppose we have a CSP with n nodes\n",
        "and make it strongly n-consistent (i.e., strongly k-consistent for k=n). We can then solve\n",
        "the problem as follows: First, we choose a consistent value for X1. We are then guaranteed\n",
        "to be able to choose a value for X2 because the graph is 2-consistent, for X3 because it is\n",
        "3-consistent, and so on. For each variable Xi, we need only search through the d values in the\n",
        "domain to find a value consistent with X1,...,Xi−1. The total run \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "\n",
        "1. ac-3：\\n\n",
        "forward checking. Forward checking Whenever a variable\n",
        "X is assigned, the forward-checking process establishes arc consistency for it: for each unassigned\n",
        "variable Y that is connected to X by a constraint, delete from Y’s domain any value\n",
        "that is inconsistent with the value chosen for X \\n\n",
        "2. Given d values, checking arc (i,j) takes O(d^2) time worst case \\n\n",
        "To make an arc (i,j) arc consistent, \\n\n",
        "  for each value v on Xi , \\n\n",
        "    if there is no label on Yj consistent with v \\n\n",
        "    then remove v from Xi \\n\n",
        "\n",
        "\n",
        "\n",
        "```\n",
        "function AC-3(csp) return the CSP, possibly with reduced domains\n",
        "  inputs: csp, a binary csp with variables {X1, X2, …, Xn}\n",
        "  local variables: queue, a queue of arcs initially the arcs incsp\n",
        "  while queue is not empty do\n",
        "    (Xi, Xj) ¬queue.pop()\n",
        "  if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n",
        "    for each Xk in NEIGHBORS[Xi ] – {Xj} do\n",
        "      add (Xk, Xi) to queue\n",
        "\n",
        "function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n",
        "  removed <- false\n",
        "  for each x in DOMAIN[Xi] do\n",
        "    if no value y in DOMAIN[Xj] allows (x,y) to satisfy\n",
        "      the constraints between Xi and Xj\n",
        "    then delete x from DOMAIN[Xi]; removed ¬ true\n",
        "  return removed\n",
        "\n",
        "```\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        " \n",
        "1. constriant satisfaction problem:\\n\n",
        "  • A CSP consists of:\\n\n",
        "    Finite set of variables X1, X2, …, Xn \\n\n",
        "  • Nonempty domain of possible values for each variable\n",
        "    D1, D2, … Dn where Di = {v1, …, vk}\\n\n",
        "  • Finite set of constraints C1, C2, …, Cm \\n\n",
        "  • Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2 A\n",
        "state is defined as an assignment of values to some or all variables.\\n\n",
        "  o A consistent assignment does not violate the\n",
        "constraints.\\n\n",
        "2. \n",
        "  o An assignment is complete when every variable is assigned\n",
        "a value. \\n\n",
        "  o A solution to a CSP is a complete, consistent assignment.\\n\n",
        "  o Solutions to CSPs can be found by a completely general\n",
        "purpose algorithm, given only the formal specification of\n",
        "the CSP.\\n\n",
        "3. benefits of csp \\n\n",
        "  o Clean specification of many problems, generic goal,\n",
        "successor function & heuristics \\n\n",
        "  o CSP “knows” which variables violate a constraint\n",
        "And hence where to focus the search \\n\n",
        "  o CSPs: Automatically prune off all branches that violate\n",
        "constraints\\n\n",
        "  (State space search could do this only by hand-building constraints\n",
        "into the successor function)\n",
        "\n",
        "4. representations: Constraint graph:\\n\n",
        "  nodes are variables\\n\n",
        "  arcs are (binary) constraints\\n\n",
        "\n",
        "5. CSP as a search problem \\n\n",
        "  o A CSP can easily be expressed as a search problem \\n\n",
        "    Initial State: the empty assignment {}.\\n\n",
        "    Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\\n \n",
        "    Goal test: the current assignment is complete.\\n\n",
        "    Path cost: a constant cost for every step.\\n\n",
        "  o Solution is always found at depth n, for n variables \\n\n",
        "    Depth First Search can be used \\n\n",
        "      n variables of domain size d \\n\n",
        "        • Branching factor at the root is n*d \\n\n",
        "        • Branching factor at next level is (n-1)*d \\n\n",
        "        • Tree has n!*(d^n) leaves \\n\n",
        "  o The variable assignments are commutative \\n\n",
        "    Eg [ step 1: WA = red; step 2: NT = green ] \\n\n",
        "    equivalent to [ step 1: NT = green; step 2: WA = red ] \\n\n",
        "    Therefore, a tree search, not a graph search \\n\n",
        "  o Only need to consider assignments to a single variable at each\n",
        "node: b = d and there are d^n leaves (n variables, domain size d )\\n\n",
        "\n",
        "\n",
        "6. Search and Backtracking \\n\n",
        "  o Depth-first search for CSPs with single-variable assignments is called\n",
        "backtracking search  \\n\n",
        "  o The term backtracking search is used for a depth-first search that chooses\n",
        "values for one variable at a time and backtracks when a variable has no legal\n",
        "values left to assign. \\n\n",
        "  o Backtracking search is the basic uninformed algorithm for CSPs \\n\n",
        "\n",
        "7. Improving backtracking efficiency \\n\n",
        "  • Heuristics: \\n\n",
        "  Q: Which variable should be assigned next? \\n\n",
        "    1. Most constrained variable \\n\n",
        "    2. (if ties:) Most constraining variable \\n\n",
        "  Q: In what order should that variable’s values be tried? \\n\n",
        "    3. Least constraining value,the one that rules out the fewest values in the remaining variables \\n\n",
        "  Q: Can we detect inevitable failure early? \\n\n",
        "    4. Forward checking,Keep track of remaining legal values for unassigned variables,\n",
        "    Terminate search when any unassigned variable has no remaining\n",
        "legal values \\n\n",
        "\n",
        "8. CSP solvers combine search and inference Search \\n\n",
        "  • assigning a value to a variable \\n\n",
        "  Constraint propagation (inference): Eliminates possible values for a variable\n",
        "if the value would violate local consistency \\n\n",
        "  o Local consistency \\n\n",
        "  Node consistency: satisfies unary constraints \\n\n",
        "  Arc consistency: satisfies binary constraints \\n\n",
        "  • ($X_i$ is arc-consistent w.r.t. $X_j$ if for every value v in $D_i$, there is some value w in\n",
        "$dD_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$) \\n\n",
        "9. AC-3 \\n\n",
        "The most popular algorithm for enforcing arc consistency is called AC-3 (see Figure 6.3).\n",
        "To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider.\n",
        "Initially, the queue contains all the arcs in the CSP. (Each binary constraint becomes\n",
        "two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj. If this leaves Di unchanged, the algorithm\n",
        "just moves on to the next arc. But if this revises Di (makes the domain smaller), then we add\n",
        "to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi. We need to do that because the\n",
        "change in Di might enable further reductions in Dk, even if we have previously considered Xk. \\n \n",
        "\n",
        "##### summary\n",
        "• Constraint satisfaction problems (CSPs) represent a state with a set of variable/value\n",
        "pairs and represent the conditions for a solution by a set of constraints on the variables.\n",
        "Many important real-world problems can be described as CSPs. \\n\n",
        "• A number of inference techniques use the constraints to rule out certain variable assignments.\n",
        "These include node, arc, path, and k-consistency. \\n\n",
        "• Backtracking search, a form of depth-first search, is commonly used for solving CSPs.\n",
        "Inference can be interwoven with search. \\n\n",
        "• Th eminimum-remaining-values and degree heuristics are domain-independent methods\n",
        "for deciding which variable to choose next in a backtracking search. The leastconstraining-\n",
        "value heuristic helps in deciding which value to try first for a given\n",
        "variable. Backtracking occurs when no legal assignment can be found for a variable.\n",
        "Conflict-directed backjumping backtracks directly to the source of the problem. Constraint\n",
        "learning records the conflicts as they are encountered during search in order to\n",
        "avoid the same conflict later in the search. \\n\n",
        "• Local search using the min-conflicts heuristic has also been applied to constraint satisfaction\n",
        "problems with great success. \\n\n",
        "• The complexity of solving a CSP is strongly related to the structure of its constraint\n",
        "graph. Tree-structured problems can be solved in linear time. Cutset conditioning can\n",
        "reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\n",
        "memory) if a small cutset can be found. Tree decomposition techniques transform\n",
        "the CSP into a tree of subproblems and are efficient if the tree width of the constraint\n",
        "graph is small; however they need memory exponential in the tree width of the constraint\n",
        "graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time. \\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\n",
        "}\n"
      ],
      "execution_count": 121,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7f7429a9-c520-4120-e5bc-57e10dc3b08f"
      },
      "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": 122,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n1. In this chapter we break open the black box by using a factored representation for each\nstate: a set of variables, each of which has a value. A problem is solved when each variable\nhas a value that satisfies all the constraints on the variable. A problem described this way is\ncalled a constraint satisfaction problem, or CSP \n\n\n2. CSPs deal with assignments of values to variables, {Xi =vi,Xj =vj, . . .}. An assignment \nthat does not violate any constraints is called a consistent or legal assignment. A complete \nassignment is one in which every variable is assigned a value, and a solution to a CSP is\na consistent, complete assignment. A partial assignment is one that leaves some variables Solution\nunassigned, and a partial solution is consistent. Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that Partial solution\ncan be solved very efficiently. \n\n\n3. every finite-domain constraint can\nbe reduced to a set of binary constraints if enough auxiliary variables are introduced. This\nmeans that we could transform any CSP into one with only binary constraints—which certainly\nmakes the life of the algorithm designer simpler. Another way to convert an n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be\none variable for each constraint in the original graph, and one binary constraint for each pair\nof constraints in the original graph that share variables \n\n\n\"unary constraint\" : \"restricts the value of a single variable, SA != greeni.\",  \n\n\"binary constraint\" : \"A binary constraint relates two variables, SA!=NSW.\",    \n\n\"higher-order constraints\" : \"involve 3 or more variables\",    \n\"Preference (soft constraints)\" : \"indicating which solutions are preferred, red is better than green can be represented by a cost for each variable assignment\", \n   \n4. CSPs with preferences can be\nsolved with optimization search methods, either path-based or local. We call such a problem\na constrained optimization problem \n\n5. constraint propagation: using the constraints to reduce the number of legal values for a variable \n\n6. Path consistency tightens the binary constraints by using implicit constraints\nthat are inferred by looking at triples of variables. A two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for\nevery assignment {Xi = a,Xj =b} consistent with the constraints (if any) on {Xi,Xj}, there is\nan assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}.\n time is only O(n2d).\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n1. local consistency: treat each variable Local consistency as a node in a graph (see\nFigure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local\nconsistency in each part of the graph causes inconsistent values \n\n2. node-consitent: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints \n\n3. arc-consistent: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints \n\n  More formally, Xi is arc-consistent with respect to another variable Xj if\nfor every value in the current domain Di there is some value in the domain Dj that satisfies\nthe binary constraint on the arc (Xi,Xj) \n\n4. A CSP is k-consistent: if, for any set of k−1 variables and for any consistent assignment to those variables,\na consistent value can always be assigned to any kth variable.\n\n5. A CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-\nk-consistent consistent,...all the way down to 1-consistent. Now suppose we have a CSP with n nodes\nand make it strongly n-consistent (i.e., strongly k-consistent for k=n). We can then solve\nthe problem as follows: First, we choose a consistent value for X1. We are then guaranteed\nto be able to choose a value for X2 because the graph is 2-consistent, for X3 because it is\n3-consistent, and so on. For each variable Xi, we need only search through the d values in the\ndomain to find a value consistent with X1,...,Xi−1. The total run \n\n\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n\n1. ac-3：\n\nforward checking. Forward checking Whenever a variable\nX is assigned, the forward-checking process establishes arc consistency for it: for each unassigned\nvariable Y that is connected to X by a constraint, delete from Y’s domain any value\nthat is inconsistent with the value chosen for X \n\n2. Given d values, checking arc (i,j) takes O(d^2) time worst case \n\nTo make an arc (i,j) arc consistent, \n\n  for each value v on Xi , \n\n    if there is no label on Yj consistent with v \n\n    then remove v from Xi \n\n\n\n\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\n  inputs: csp, a binary csp with variables {X1, X2, …, Xn}\n  local variables: queue, a queue of arcs initially the arcs incsp\n  while queue is not empty do\n    (Xi, Xj) ¬queue.pop()\n  if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n    for each Xk in NEIGHBORS[Xi ] – {Xj} do\n      add (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n  removed <- false\n  for each x in DOMAIN[Xi] do\n    if no value y in DOMAIN[Xj] allows (x,y) to satisfy\n      the constraints between Xi and Xj\n    then delete x from DOMAIN[Xi]; removed ¬ true\n  return removed\n\n```\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \n \n1. constriant satisfaction problem:\n\n  • A CSP consists of:\n\n    Finite set of variables X1, X2, …, Xn \n\n  • Nonempty domain of possible values for each variable\n    D1, D2, … Dn where Di = {v1, …, vk}\n\n  • Finite set of constraints C1, C2, …, Cm \n\n  • Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2 A\nstate is defined as an assignment of values to some or all variables.\n\n  o A consistent assignment does not violate the\nconstraints.\n\n2. \n  o An assignment is complete when every variable is assigned\na value. \n\n  o A solution to a CSP is a complete, consistent assignment.\n\n  o Solutions to CSPs can be found by a completely general\npurpose algorithm, given only the formal specification of\nthe CSP.\n\n3. benefits of csp \n\n  o Clean specification of many problems, generic goal,\nsuccessor function & heuristics \n\n  o CSP “knows” which variables violate a constraint\nAnd hence where to focus the search \n\n  o CSPs: Automatically prune off all branches that violate\nconstraints\n\n  (State space search could do this only by hand-building constraints\ninto the successor function)\n\n4. representations: Constraint graph:\n\n  nodes are variables\n\n  arcs are (binary) constraints\n\n\n5. CSP as a search problem \n\n  o A CSP can easily be expressed as a search problem \n\n    Initial State: the empty assignment {}.\n\n    Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n \n    Goal test: the current assignment is complete.\n\n    Path cost: a constant cost for every step.\n\n  o Solution is always found at depth n, for n variables \n\n    Depth First Search can be used \n\n      n variables of domain size d \n\n        • Branching factor at the root is n*d \n\n        • Branching factor at next level is (n-1)*d \n\n        • Tree has n!*(d^n) leaves \n\n  o The variable assignments are commutative \n\n    Eg [ step 1: WA = red; step 2: NT = green ] \n\n    equivalent to [ step 1: NT = green; step 2: WA = red ] \n\n    Therefore, a tree search, not a graph search \n\n  o Only need to consider assignments to a single variable at each\nnode: b = d and there are d^n leaves (n variables, domain size d )\n\n\n\n6. Search and Backtracking \n\n  o Depth-first search for CSPs with single-variable assignments is called\nbacktracking search  \n\n  o The term backtracking search is used for a depth-first search that chooses\nvalues for one variable at a time and backtracks when a variable has no legal\nvalues left to assign. \n\n  o Backtracking search is the basic uninformed algorithm for CSPs \n\n\n7. Improving backtracking efficiency \n\n  • Heuristics: \n\n  Q: Which variable should be assigned next? \n\n    1. Most constrained variable \n\n    2. (if ties:) Most constraining variable \n\n  Q: In what order should that variable’s values be tried? \n\n    3. Least constraining value,the one that rules out the fewest values in the remaining variables \n\n  Q: Can we detect inevitable failure early? \n\n    4. Forward checking,Keep track of remaining legal values for unassigned variables,\n    Terminate search when any unassigned variable has no remaining\nlegal values \n\n\n8. CSP solvers combine search and inference Search \n\n  • assigning a value to a variable \n\n  Constraint propagation (inference): Eliminates possible values for a variable\nif the value would violate local consistency \n\n  o Local consistency \n\n  Node consistency: satisfies unary constraints \n\n  Arc consistency: satisfies binary constraints \n\n  • ($X_i$ is arc-consistent w.r.t. $X_j$ if for every value v in $D_i$, there is some value w in\n$dD_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$) \n\n9. AC-3 \n\nThe most popular algorithm for enforcing arc consistency is called AC-3 (see Figure 6.3).\nTo make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider.\nInitially, the queue contains all the arcs in the CSP. (Each binary constraint becomes\ntwo arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj. If this leaves Di unchanged, the algorithm\njust moves on to the next arc. But if this revises Di (makes the domain smaller), then we add\nto the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi. We need to do that because the\nchange in Di might enable further reductions in Dk, even if we have previously considered Xk. \n \n\n##### summary\n• Constraint satisfaction problems (CSPs) represent a state with a set of variable/value\npairs and represent the conditions for a solution by a set of constraints on the variables.\nMany important real-world problems can be described as CSPs. \n\n• A number of inference techniques use the constraints to rule out certain variable assignments.\nThese include node, arc, path, and k-consistency. \n\n• Backtracking search, a form of depth-first search, is commonly used for solving CSPs.\nInference can be interwoven with search. \n\n• Th eminimum-remaining-values and degree heuristics are domain-independent methods\nfor deciding which variable to choose next in a backtracking search. The leastconstraining-\nvalue heuristic helps in deciding which value to try first for a given\nvariable. Backtracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem. Constraint\nlearning records the conflicts as they are encountered during search in order to\navoid the same conflict later in the search. \n\n• Local search using the min-conflicts heuristic has also been applied to constraint satisfaction\nproblems with great success. \n\n• The complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform\nthe CSP into a tree of subproblems and are efficient if the tree width of the constraint\ngraph is small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time. \n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "1. Propositional logic is\n",
        "a factored representation \\n\n",
        "2. The central component of a knowledge-based agent is its knowledge base, or KB. A knowl-\n",
        "edge base is a set of sentences. (Here “sentence” is used as a technical term. It is related Sentence\n",
        "but not identical to the sentences of English and other natural languages.) Each sentence is\n",
        "expressed in a language called a knowledge representation language and represents some assertion about the world. When the sentence is taken as being given without being derived\n",
        "from other sentences, we call it an axiom. \\n\n",
        "3. knowledge-based agent program. Like all our agents,\n",
        "it takes a percept as input and returns an action. The agent maintains a knowledge base, KB,\n",
        "which may initially contain some background knowledge \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "1. These sentences are\n",
        "expressed according to the syntax of the representation language, Syntax which specifies all the\n",
        "sentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic:\n",
        "“x+y = 4” is a well-formed sentence, whereas “x4y+ =” is not. \\n\n",
        "2. A logic must also define the semantics, or meaning, of sentences. The semantics defines\n",
        "Truth the truth of each sentence with respect to each possible world. For example, the semantics\n",
        "Possible world for arithmetic specifies that the sentence “x+y=4” is true in a world where x is 2 and y is 2,\n",
        "but false in a world where x is 1 and y is 1. \\n\n",
        "\n",
        "3. entailment\n",
        "Now that we have a notion of truth, we are ready to talk about logical reasoning. This inEntailment\n",
        "volves the relation of logical entailment between sentences—the idea that a sentence follows\n",
        "logically from another sentence. In mathematical notation, we write \\n\n",
        "  α |= β\\n\n",
        "to mean that the sentence α entails the sentence β. The formal definition of entailment is this: \\n\n",
        "  α |= β if and only if, in every model in which α is true, β is also true. Using the notation just\n",
        "introduced, we can write \\n\n",
        "  α |= β if and only if M(α) ⊆ M(β)\\n\n",
        "4. sound and complete:\n",
        "  • An inference algorithm that derives only entailed sentences is called sound or truth\n",
        "preserving. Soundness is a highly desirable property. An unsound inference procedure essentially\n",
        "makes things up as it goes along—it announces the discovery of nonexistent needles.\n",
        "It is easy to see that model checking, when it is applicable, is a sound procedure. \\n\n",
        "  • The property of completeness is also desirable: an inference algorithm is complete if\n",
        "it can derive any sentence that is entailed. \\n\n",
        "\n",
        "5. KB is true in the real world, then any\n",
        "sentence α derived from KB by a sound inference procedure is also true in the real world. So,\n",
        "while an inference process operates on “syntax”—internal physical configurations such as\n",
        "bits in registers or patterns of electrical blips in brains—the process corresponds to the realworld\n",
        "relationship whereby some aspect of the real world is the case by virtue of other aspects\n",
        "of the real world being the case\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "\n",
        "1. propositional logic:\\n\n",
        "  • ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3.\\n\n",
        "  • ∧ (and). A sentence whose main connective is ∧, is called a conjunction;\n",
        "its parts are the conjuncts.\\n\n",
        "  • ∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction;\n",
        "its parts are disjuncts—in this example, (W1,3 ∧P3,1) and W2,2. \\n\n",
        "  • ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- Implication\n",
        "ditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent Premise\n",
        "is ¬W2,2. Implications are also known as rules or if–then statements. The implication Conclusion\n",
        "symbol is sometimes written in other books as ⊃ or →. \\n\n",
        "  • ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional. \\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "1.first concept is logical equivalence: two sentences\n",
        "α and β are logically equivalent if they are true in the same set of models. We write\n",
        "this as α ≡ β. \\n\n",
        "2. theorem proving—applying rules of inference directly to the sentences\n",
        "in our knowledge base to construct a proof of the desired sentence without consulting models. \\n\n",
        "3. validity: A sentence is valid if it is true in all models. For\n",
        "Tautology example, the sentence P∨¬P is valid \\n\n",
        "4. satisfiability: A sentence is satisfiable if it is true\n",
        "in, or satisfied by, some model.Satisfiability can be checked by enumerating the possible models until one is\n",
        "found that satisfies the sentence \\n\n",
        "5.Standard logical equivalences: \\n\n",
        "  (α∧β) ≡ (β ∧α) commutativity of ∧ \\n\n",
        "  (α∨β) ≡ (β ∨α) commutativity of ∨ \\n\n",
        "  ((α∧β)∧γ) ≡ (α∧(β ∧γ)) associativity of ∧ \\n\n",
        "  ((α∨β)∨γ) ≡ (α∨(β ∨γ)) associativity of ∨ \\n\n",
        "  ¬(¬α) ≡ α double-negation elimination \\n\n",
        "  (α ⇒ β) ≡ (¬β ⇒ ¬α) contraposition \\n\n",
        "  (α ⇒ β) ≡ (¬α∨β) implication elimination \\n\n",
        "  (α ⇔ β) ≡ ((α ⇒ β)∧(β ⇒ α)) biconditional elimination \\n\n",
        "  ¬(α∧β) ≡ (¬α∨¬β) De Morgan \\n\n",
        "  ¬(α∨β) ≡ (¬α∧¬β) De Morgan \\n\n",
        "  (α∧(β ∨γ)) ≡ ((α∧β)∨(α∧γ)) distributivity of ∧ over ∨ \\n\n",
        "  (α∨(β ∧γ)) ≡ ((α∨β)∧(α∨γ)) distributivity of ∨ over ∧ \\n\n",
        "6.Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively,\n",
        "α is satisfiable iff ¬α is not valid. We also have the following useful result:\\n\n",
        "  α |= β if and only if the sentence (α∧¬β) is unsatisfiable.\\n\n",
        "7. conjunctive normal form \\n\n",
        "  CNFSentence → Clause_1 ∧...∧ Clause_n \\n\n",
        "  Clause → Literal_1 ∨...∨ Literal_m \\n\n",
        "  Fact → Symbol \\n\n",
        "  Literal → Symbol | ¬Symbol \\n\n",
        "  Symbol → P | Q | R | ... \\n\n",
        "  HornClauseForm → DefiniteClauseForm | GoalClauseForm \\n\n",
        "  DefiniteClauseForm → Fact | (Symbol_1 ∧...∧ Symbol_l ) ⇒ Symbol  \\n\n",
        "  GoalClauseForm → (Symbol_1 ∧...∧ Symbol_l ) ⇒ False \\n\n",
        "\n",
        "\n",
        "\n",
        " \"\"\" \n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "1. problem-solving agents have performed a search over states in order to find a plan. The representation of states has been atomic. \\n\n",
        "2. Knowledge-based agents use a process of reasoning over an internal\n",
        "representation of knowledge to decide what action to take. \\n\n",
        "3. There are two kinds of sentences: \\n\n",
        "  • Axioms – a sentence that is given \\n\n",
        "  • Derived sentences – a new sentence that is derived from others sentences \\n\n",
        "  The process of deriving new sentences from old sentences is called inference. \\n\n",
        "4. A KB can initially contain some background information about the world, and a\n",
        "knowledge-based agent can add to the information in the KB through its observations\n",
        "of the world. \\n\n",
        "5. In addition to asserting new knowledge into its KB, a knowledge-based agent can also\n",
        "query the KB and ask it to derive new knowledge in order to select what action it\n",
        "should take. \\n\n",
        "6.Logic can serve as a general class of representations for knowledge-based agents.\n",
        "Here we are going to examine Propositional Logic. \\n\n",
        "  • KB consists of sentences in the representation language \\n\n",
        "  • Representation language has a syntax that specifies sentences that are well-formed \\n\n",
        "  • A logic defines the semantics of the sentences, which is their meaning \\n\n",
        "  • The semantics defines the truth of each sentence with respect to a possible world,\n",
        "which we will often call a model \\n\n",
        "7. Possible worlds and models \\n\n",
        "  • Models are mathematical abstractions that have a fixed set of truth values which\n",
        "are {true, false} for each sentence. \\n\n",
        "  • If sentence 𝛂 is true in model m then we say \\n\n",
        "  • m satisfies 𝛂, or \\n\n",
        "  • m is a model of 𝛂 \\n\n",
        "  • We use the notation M(𝛂) to mean the set of all models of 𝛂. \\n\n",
        "  For instance, 𝛂 could be a sentence that means “there is no pit in [2,2]”. In that case,\n",
        "M(𝛂) would be all instances of Wampa World where [2,2] doesn’t have a pit. \\n\n",
        "\n",
        "8. Logical Entailment \\n\n",
        "  • Once we have a notion of truth, we can start to define logical reasoning. Logical\n",
        "reasoning involves the entailment relation between sentence. \\n\n",
        "  • To write sentence 𝛂 entails sentence β in mathematical notation we use the ⊨ symbol: \\n\n",
        "      𝛂⊨β \\n\n",
        "  • The definition is 𝛂⊨β if and only if M(𝛂) ⊆ M(β), \\n\n",
        "  • This means that 𝛂 is more specific, or stronger than, β. For instances, β could mean\n",
        "that “The agent is a robot” and 𝛂 could mean “The agent is an astromech”. \\n\n",
        "\n",
        "9. The KB is false in models that contradict\n",
        "what the agent knows. \\n\n",
        "10. Possible Worlds is the process of\n",
        "enumerating all Possible Worlds that are\n",
        "compatible with the KB. M(KB) ⊆ M(𝛂_1) \\n\n",
        "11. logical inference \\n\n",
        "  • Entailment can be applied to derive conclusions, which is the process of logical\n",
        "inference. \\n\n",
        "  • We can think about the consequences of a KB as a large set of additional sentences\n",
        "that are entailed given the sentences that have been added to the KB. \\n\n",
        "  • We would like to design inference algorithms to enumerate these sentences.\n",
        "When an inference algorithm i allows us to conclude that 𝛂 is true, then we write \\n\n",
        "  • KB ⊢i 𝛂m“𝛂 is derived from KB by i” \\n\n",
        "\n",
        "12.logically equivalent \\n\n",
        " • Two sentences 𝛂 and β are logically equivalent if they are true in the same set of\n",
        "models. We write this as \\n \n",
        "  𝛂 ≡ β\\n\n",
        " • An alternate definition of logical equivalence is that two sentences 𝛂 and β are logically\n",
        "equivalent if any only if they entail each other.\\n\n",
        "  𝛂 ≡ β if and only if 𝛂⊨β and β⊨𝛂. \\n\n",
        "13. search algo：\\n\n",
        "  We can use search algorithms to find a\n",
        "sequence of steps that constitutes a proof!\\n\n",
        "  • Initial State: the initial knowledge base.\\n\n",
        "  • Actions: All inference rules applied to\\n\n",
        "all sentence that match the top half of\n",
        "the inference rule.\\n\n",
        "  • Result: Add the sentence on the\n",
        "bottom half to the KB.\\n\n",
        "  • Goal: The goal is a state that contains\n",
        "the sentence that we are trying to proce\\n\n",
        "14. monotonicity: \\n\n",
        "Monotonicity says that the set of entailed sentence can only increase as information is\n",
        "assed to the KB. \\n\n",
        "if KB⊨𝛂 then KB ⋀ β⊨𝛂 \\n\n",
        "If we add additional information to the KB, it doesn’t invalidate any other info that\n",
        "we’ve already inferred. \\n\n",
        "Therefore it is sound it will only derive entailed sentences. \\n\n",
        "15. Conjunctive Normal Form (CNF)\\n\n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n",
        "Clauses are disjunctions of literals.\\n\n",
        "  1. Eliminate ⇔ by replacing 𝛂 ⇔ β with (𝛂⟹β) ⋀ (β ⟹𝛂)\\n\n",
        "  2. Eliminate ⟹by replacing 𝛂⟹β with ¬𝛂 ⋁ β\\n\n",
        "  3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\\n\n",
        "  4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\n",
        "distributivity law to distribute ⋁ over ⋀ wherever possible.\\n\n",
        "16. resolution: a single inference rule:yields a complete inference\n",
        "algorithm when coupled with any complete search algorithm.\\n\n",
        "17. Resolution Algorithm \\n\n",
        "Inference procedures based on resolution work using the principle of proof by\n",
        "contradiction.\\n\n",
        "To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n",
        "Here’s how:\\n\n",
        "• First, convert (KB ⋀ ¬𝛂) into CNF\\n\n",
        "• Then apply the resolution rule to the resulting clauses.\\n\n",
        "• Resolve every pair that contains complementary literals to produce a new clause\\n\n",
        "• If that new clause isn’t already present, then add it to the set.\\n\n",
        "• Continue the process until one of two things happens:\\n\n",
        "  1. There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \\n\n",
        "  2. Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂 \\n\n",
        "\n",
        "18. Horn Clauses and Definite Clauses\\n\n",
        "The resolution algorithm is complete! This makes is a very important inference\n",
        "method.\\n\n",
        "However, we don’t always need the full power of resolution. Some KBs are formulated\n",
        "in a more restrictive form which enables them to use more efficient inference\n",
        "algorithms.\\n\n",
        "• Definite clause – disjunction of literals where exactly one is positive\\n\n",
        "• Horn clause – disjunction of literals where at most one is positive\\n\n",
        "• This includes definite clauses\\n\n",
        "• And clauses with no positive literals \\n\n",
        "\n",
        "19.Forward Chaining and Backward Chaining\\n\n",
        "Forward Chaining is a kind of data-driven reasoning. An agent can start with known\n",
        "data, adding premises as new percepts come in, and then incrementally apply the\n",
        "forward chaining algorithm to derive new conclusions. It doesn’t have to have a\n",
        "specific query in mind to do so.\\n\n",
        "Backward chaining works backwards from a query. If the query is known to be true,\n",
        "then no work is needed. Otherwise, the algorithm finds implications in the KB whose\n",
        "conclusions is the query. If all the premises of one of those can be proved to be true\n",
        "(via backward chaining), then the query is true.\\n\n",
        "Backward chaining is a form of goal-directed reasoning.\\n\n",
        "\n",
        "##### summary:\n",
        "  • Intelligent agents need knowledge about the world in order to reach good decisions. \\n\n",
        "  • Knowledge is contained in agents in the form of sentences in a knowledge representation\n",
        "language that are stored in a knowledge base. \\n\n",
        "  • A knowledge-based agent is composed of a knowledge base and an inference mechanism.\n",
        "It operates by storing sentences about the world in its knowledge base, using the\n",
        "inference mechanism to infer new sentences, and using these sentences to decide what\n",
        "action to take. \\n\n",
        "  • A representation language is defined by its syntax, which specifies the structure of\n",
        "sentences, and its semantics, which defines the truth of each sentence in each possible\n",
        "world or model. \\n\n",
        "  • The relationship of entailment between sentences is crucial to our understanding of\n",
        "reasoning. A sentence α entails another sentence β if β is true in all worlds where\n",
        "α is true. Equivalent definitions include the validity of the sentence α ⇒ β and the\n",
        "unsatisfiability of the sentence α∧¬β. \\n\n",
        "  • Inference is the process of deriving new sentences from old ones. Sound inference algorithms\n",
        "derive only sentences that are entailed; complete algorithms derive all sentences\n",
        "that are entailed. \\n\n",
        "  • Propositional logic is a simple language consisting of proposition symbols and logical\n",
        "connectives. It can handle propositions that are known to be true, known to be false, or\n",
        "completely unknown. \\n\n",
        "  • The set of possible models, given a fixed propositional vocabulary, is finite, so entailment\n",
        "can be checked by enumerating models. Efficient model-checking inference\n",
        "algorithms for propositional logic include backtracking and local search methods and\n",
        "can often solve large problems quickly. \\n\n",
        "  • Inference rules are patterns of sound inference that can be used to find proofs. The\n",
        "resolution rule yields a complete inference algorithm for knowledge bases that are\n",
        "expressed in conjunctive normal form. Forward chaining and backward chaining\n",
        "are very natural reasoning algorithms for knowledge bases in Horn form. \\n\n",
        "  • Local search methods such as WALKSAT can be used to find solutions. Such algorithms\n",
        "are sound but not complete. \\n\n",
        "  • Logical state estimation involves maintaining a logical sentence that describes the set\n",
        "of possible states consistent with the observation history. Each update step requires\n",
        "inference using the transition model of the environment, which is built from successorstate\n",
        "axioms that specify how each fluent changes. \\n\n",
        "  • Decisions within a logical agent can be made by SAT solving: finding possible models\n",
        "specifying future action sequences that reach the goal. This approach works only for\n",
        "fully observable or sensorless environments. \\n\n",
        "  • Propositional logic does not scale to environments of unbounded size because it lacks\n",
        "the expressive power to deal concisely with time, space, and universal patterns of relationships\n",
        "among objects. \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 123,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KhUn3d0FPklM"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "217659be-2a60-43ae-9d91-5cccf1af57a7"
      },
      "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": 124,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n1. Propositional logic is\na factored representation \n\n2. The central component of a knowledge-based agent is its knowledge base, or KB. A knowl-\nedge base is a set of sentences. (Here “sentence” is used as a technical term. It is related Sentence\nbut not identical to the sentences of English and other natural languages.) Each sentence is\nexpressed in a language called a knowledge representation language and represents some assertion about the world. When the sentence is taken as being given without being derived\nfrom other sentences, we call it an axiom. \n\n3. knowledge-based agent program. Like all our agents,\nit takes a percept as input and returns an action. The agent maintains a knowledge base, KB,\nwhich may initially contain some background knowledge \n\n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n \n1. These sentences are\nexpressed according to the syntax of the representation language, Syntax which specifies all the\nsentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic:\n“x+y = 4” is a well-formed sentence, whereas “x4y+ =” is not. \n\n2. A logic must also define the semantics, or meaning, of sentences. The semantics defines\nTruth the truth of each sentence with respect to each possible world. For example, the semantics\nPossible world for arithmetic specifies that the sentence “x+y=4” is true in a world where x is 2 and y is 2,\nbut false in a world where x is 1 and y is 1. \n\n\n3. entailment\nNow that we have a notion of truth, we are ready to talk about logical reasoning. This inEntailment\nvolves the relation of logical entailment between sentences—the idea that a sentence follows\nlogically from another sentence. In mathematical notation, we write \n\n  α |= β\n\nto mean that the sentence α entails the sentence β. The formal definition of entailment is this: \n\n  α |= β if and only if, in every model in which α is true, β is also true. Using the notation just\nintroduced, we can write \n\n  α |= β if and only if M(α) ⊆ M(β)\n\n4. sound and complete:\n  • An inference algorithm that derives only entailed sentences is called sound or truth\npreserving. Soundness is a highly desirable property. An unsound inference procedure essentially\nmakes things up as it goes along—it announces the discovery of nonexistent needles.\nIt is easy to see that model checking, when it is applicable, is a sound procedure. \n\n  • The property of completeness is also desirable: an inference algorithm is complete if\nit can derive any sentence that is entailed. \n\n\n5. KB is true in the real world, then any\nsentence α derived from KB by a sound inference procedure is also true in the real world. So,\nwhile an inference process operates on “syntax”—internal physical configurations such as\nbits in registers or patterns of electrical blips in brains—the process corresponds to the realworld\nrelationship whereby some aspect of the real world is the case by virtue of other aspects\nof the real world being the case\n\n\n\n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n\n1. propositional logic:\n\n  • ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3.\n\n  • ∧ (and). A sentence whose main connective is ∧, is called a conjunction;\nits parts are the conjuncts.\n\n  • ∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction;\nits parts are disjuncts—in this example, (W1,3 ∧P3,1) and W2,2. \n\n  • ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- Implication\nditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent Premise\nis ¬W2,2. Implications are also known as rules or if–then statements. The implication Conclusion\nsymbol is sometimes written in other books as ⊃ or →. \n\n  • ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n1.first concept is logical equivalence: two sentences\nα and β are logically equivalent if they are true in the same set of models. We write\nthis as α ≡ β. \n\n2. theorem proving—applying rules of inference directly to the sentences\nin our knowledge base to construct a proof of the desired sentence without consulting models. \n\n3. validity: A sentence is valid if it is true in all models. For\nTautology example, the sentence P∨¬P is valid \n\n4. satisfiability: A sentence is satisfiable if it is true\nin, or satisfied by, some model.Satisfiability can be checked by enumerating the possible models until one is\nfound that satisfies the sentence \n\n5.Standard logical equivalences: \n\n  (α∧β) ≡ (β ∧α) commutativity of ∧ \n\n  (α∨β) ≡ (β ∨α) commutativity of ∨ \n\n  ((α∧β)∧γ) ≡ (α∧(β ∧γ)) associativity of ∧ \n\n  ((α∨β)∨γ) ≡ (α∨(β ∨γ)) associativity of ∨ \n\n  ¬(¬α) ≡ α double-negation elimination \n\n  (α ⇒ β) ≡ (¬β ⇒ ¬α) contraposition \n\n  (α ⇒ β) ≡ (¬α∨β) implication elimination \n\n  (α ⇔ β) ≡ ((α ⇒ β)∧(β ⇒ α)) biconditional elimination \n\n  ¬(α∧β) ≡ (¬α∨¬β) De Morgan \n\n  ¬(α∨β) ≡ (¬α∧¬β) De Morgan \n\n  (α∧(β ∨γ)) ≡ ((α∧β)∨(α∧γ)) distributivity of ∧ over ∨ \n\n  (α∨(β ∧γ)) ≡ ((α∨β)∧(α∨γ)) distributivity of ∨ over ∧ \n\n6.Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively,\nα is satisfiable iff ¬α is not valid. We also have the following useful result:\n\n  α |= β if and only if the sentence (α∧¬β) is unsatisfiable.\n\n7. conjunctive normal form \n\n  CNFSentence → Clause_1 ∧...∧ Clause_n \n\n  Clause → Literal_1 ∨...∨ Literal_m \n\n  Fact → Symbol \n\n  Literal → Symbol | ¬Symbol \n\n  Symbol → P | Q | R | ... \n\n  HornClauseForm → DefiniteClauseForm | GoalClauseForm \n\n  DefiniteClauseForm → Fact | (Symbol_1 ∧...∧ Symbol_l ) ⇒ Symbol  \n\n  GoalClauseForm → (Symbol_1 ∧...∧ Symbol_l ) ⇒ False \n\n\n\n\n \n\n## Module 7 Lecture Notes\n \n\n1. problem-solving agents have performed a search over states in order to find a plan. The representation of states has been atomic. \n\n2. Knowledge-based agents use a process of reasoning over an internal\nrepresentation of knowledge to decide what action to take. \n\n3. There are two kinds of sentences: \n\n  • Axioms – a sentence that is given \n\n  • Derived sentences – a new sentence that is derived from others sentences \n\n  The process of deriving new sentences from old sentences is called inference. \n\n4. A KB can initially contain some background information about the world, and a\nknowledge-based agent can add to the information in the KB through its observations\nof the world. \n\n5. In addition to asserting new knowledge into its KB, a knowledge-based agent can also\nquery the KB and ask it to derive new knowledge in order to select what action it\nshould take. \n\n6.Logic can serve as a general class of representations for knowledge-based agents.\nHere we are going to examine Propositional Logic. \n\n  • KB consists of sentences in the representation language \n\n  • Representation language has a syntax that specifies sentences that are well-formed \n\n  • A logic defines the semantics of the sentences, which is their meaning \n\n  • The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model \n\n7. Possible worlds and models \n\n  • Models are mathematical abstractions that have a fixed set of truth values which\nare {true, false} for each sentence. \n\n  • If sentence 𝛂 is true in model m then we say \n\n  • m satisfies 𝛂, or \n\n  • m is a model of 𝛂 \n\n  • We use the notation M(𝛂) to mean the set of all models of 𝛂. \n\n  For instance, 𝛂 could be a sentence that means “there is no pit in [2,2]”. In that case,\nM(𝛂) would be all instances of Wampa World where [2,2] doesn’t have a pit. \n\n\n8. Logical Entailment \n\n  • Once we have a notion of truth, we can start to define logical reasoning. Logical\nreasoning involves the entailment relation between sentence. \n\n  • To write sentence 𝛂 entails sentence β in mathematical notation we use the ⊨ symbol: \n\n      𝛂⊨β \n\n  • The definition is 𝛂⊨β if and only if M(𝛂) ⊆ M(β), \n\n  • This means that 𝛂 is more specific, or stronger than, β. For instances, β could mean\nthat “The agent is a robot” and 𝛂 could mean “The agent is an astromech”. \n\n\n9. The KB is false in models that contradict\nwhat the agent knows. \n\n10. Possible Worlds is the process of\nenumerating all Possible Worlds that are\ncompatible with the KB. M(KB) ⊆ M(𝛂_1) \n\n11. logical inference \n\n  • Entailment can be applied to derive conclusions, which is the process of logical\ninference. \n\n  • We can think about the consequences of a KB as a large set of additional sentences\nthat are entailed given the sentences that have been added to the KB. \n\n  • We would like to design inference algorithms to enumerate these sentences.\nWhen an inference algorithm i allows us to conclude that 𝛂 is true, then we write \n\n  • KB ⊢i 𝛂m“𝛂 is derived from KB by i” \n\n\n12.logically equivalent \n\n • Two sentences 𝛂 and β are logically equivalent if they are true in the same set of\nmodels. We write this as \n \n  𝛂 ≡ β\n\n • An alternate definition of logical equivalence is that two sentences 𝛂 and β are logically\nequivalent if any only if they entail each other.\n\n  𝛂 ≡ β if and only if 𝛂⊨β and β⊨𝛂. \n\n13. search algo：\n\n  We can use search algorithms to find a\nsequence of steps that constitutes a proof!\n\n  • Initial State: the initial knowledge base.\n\n  • Actions: All inference rules applied to\n\nall sentence that match the top half of\nthe inference rule.\n\n  • Result: Add the sentence on the\nbottom half to the KB.\n\n  • Goal: The goal is a state that contains\nthe sentence that we are trying to proce\n\n14. monotonicity: \n\nMonotonicity says that the set of entailed sentence can only increase as information is\nassed to the KB. \n\nif KB⊨𝛂 then KB ⋀ β⊨𝛂 \n\nIf we add additional information to the KB, it doesn’t invalidate any other info that\nwe’ve already inferred. \n\nTherefore it is sound it will only derive entailed sentences. \n\n15. Conjunctive Normal Form (CNF)\n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals.\n\n  1. Eliminate ⇔ by replacing 𝛂 ⇔ β with (𝛂⟹β) ⋀ (β ⟹𝛂)\n\n  2. Eliminate ⟹by replacing 𝛂⟹β with ¬𝛂 ⋁ β\n\n  3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n\n  4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.\n\n16. resolution: a single inference rule:yields a complete inference\nalgorithm when coupled with any complete search algorithm.\n\n17. Resolution Algorithm \n\nInference procedures based on resolution work using the principle of proof by\ncontradiction.\n\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\nHere’s how:\n\n• First, convert (KB ⋀ ¬𝛂) into CNF\n\n• Then apply the resolution rule to the resulting clauses.\n\n• Resolve every pair that contains complementary literals to produce a new clause\n\n• If that new clause isn’t already present, then add it to the set.\n\n• Continue the process until one of two things happens:\n\n  1. There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \n\n  2. Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂 \n\n\n18. Horn Clauses and Definite Clauses\n\nThe resolution algorithm is complete! This makes is a very important inference\nmethod.\n\nHowever, we don’t always need the full power of resolution. Some KBs are formulated\nin a more restrictive form which enables them to use more efficient inference\nalgorithms.\n\n• Definite clause – disjunction of literals where exactly one is positive\n\n• Horn clause – disjunction of literals where at most one is positive\n\n• This includes definite clauses\n\n• And clauses with no positive literals \n\n\n19.Forward Chaining and Backward Chaining\n\nForward Chaining is a kind of data-driven reasoning. An agent can start with known\ndata, adding premises as new percepts come in, and then incrementally apply the\nforward chaining algorithm to derive new conclusions. It doesn’t have to have a\nspecific query in mind to do so.\n\nBackward chaining works backwards from a query. If the query is known to be true,\nthen no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true\n(via backward chaining), then the query is true.\n\nBackward chaining is a form of goal-directed reasoning.\n\n\n##### summary:\n  • Intelligent agents need knowledge about the world in order to reach good decisions. \n\n  • Knowledge is contained in agents in the form of sentences in a knowledge representation\nlanguage that are stored in a knowledge base. \n\n  • A knowledge-based agent is composed of a knowledge base and an inference mechanism.\nIt operates by storing sentences about the world in its knowledge base, using the\ninference mechanism to infer new sentences, and using these sentences to decide what\naction to take. \n\n  • A representation language is defined by its syntax, which specifies the structure of\nsentences, and its semantics, which defines the truth of each sentence in each possible\nworld or model. \n\n  • The relationship of entailment between sentences is crucial to our understanding of\nreasoning. A sentence α entails another sentence β if β is true in all worlds where\nα is true. Equivalent definitions include the validity of the sentence α ⇒ β and the\nunsatisfiability of the sentence α∧¬β. \n\n  • Inference is the process of deriving new sentences from old ones. Sound inference algorithms\nderive only sentences that are entailed; complete algorithms derive all sentences\nthat are entailed. \n\n  • Propositional logic is a simple language consisting of proposition symbols and logical\nconnectives. It can handle propositions that are known to be true, known to be false, or\ncompletely unknown. \n\n  • The set of possible models, given a fixed propositional vocabulary, is finite, so entailment\ncan be checked by enumerating models. Efficient model-checking inference\nalgorithms for propositional logic include backtracking and local search methods and\ncan often solve large problems quickly. \n\n  • Inference rules are patterns of sound inference that can be used to find proofs. The\nresolution rule yields a complete inference algorithm for knowledge bases that are\nexpressed in conjunctive normal form. Forward chaining and backward chaining\nare very natural reasoning algorithms for knowledge bases in Horn form. \n\n  • Local search methods such as WALKSAT can be used to find solutions. Such algorithms\nare sound but not complete. \n\n  • Logical state estimation involves maintaining a logical sentence that describes the set\nof possible states consistent with the observation history. Each update step requires\ninference using the transition model of the environment, which is built from successorstate\naxioms that specify how each fluent changes. \n\n  • Decisions within a logical agent can be made by SAT solving: finding possible models\nspecifying future action sequences that reach the goal. This approach works only for\nfully observable or sensorless environments. \n\n  • Propositional logic does not scale to environments of unbounded size because it lacks\nthe expressive power to deal concisely with time, space, and universal patterns of relationships\namong objects. \n\n\n \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "4790c55c-ebba-494b-bd58-d4d67f9dda45"
      },
      "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": 125,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA 2.4 The Structure of Agents' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n1. rationality: doing right things.\n\n2. (acting humanly) turing test: A computer passes the test if a human interrogator, after posing some written questions, cannot tell\nwhether the written responses come from a person or from a comp. The test results do not depend on the ability to give correct answers to questions, \nonly how closely one's answers resemble those a human would give \n\n  6 AI discipline:\n\n    a. natural language processin: to communicate successfully in a human language;\n\n    b. knowledge representation: to store what it knows or hears; \n\n    c. automated reasoning: to answer questions and to draw new conclusions;\n\n    d. machine learning: to adapt to new circumstances and to detect and extrapolate patterns;\n\n    e. (physical simulation)computer vision: and speech recognition to perceive the world;\n\n    d. robotics: to manipulate objects and move about.\n\n  \n\n3. think humanly: cognitive modelling\n\n  a. intropection:trying to catch our own thoughts as they go by;\n\n  b. psychological experiments:observing a person in action;\n\n  c. braining image:observing the brain in action\n\n4. A rational agent:an agent that perceives its environment and and behaves rationally.\n\n5. Rational behavior: doing the right thing: to maximize its performance measure/expected value\n\n\n6. agent is specified by agent funtion f:p->a,p is perception, a is action\n\n7. performance measure:An objective criterion for success of an agent's behavior;given the evidence provided by the percept sequence\n\n8. search problem:\n\n  a.goal: place to end \n\n  b.search problem: states/actions/performance measure \n\n  c.solution \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \n1. agent action=built-in knowledge+entire percept sequence(complete history of everything the agent has observed)\n\n2. consequentialism: we evaluate an agent’s behavior by its Consequentialism\nconsequences\n\n3. performance measure: evaluates any Performance measure\ngiven sequence of environment states.\n\n4. nature of environment: \n\n  a. Fully observable vs. partially observable: If an agent’s sensors give it access to the Fully observable\ncomplete state of the environment at each point in time, then we say that the task environ- Partially observable\nment is fully observable. A task environment is effectively fully observable if the sensors\ndetect all aspects that are relevant to the choice of action;\n5. Deterministic vs. nondeterministic. If the next state of the environment is completely \ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic \n\n6. the environment can change while an agent is deliberating, then \nwe say the environment is dynamic for that agent; otherwise, it is static;\nIf the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.\n\n7. The distinction between known and unknown environments is not the same as the one\nbetween fully and partially observable environments. It is quite possible for a known environment\nto be partially observable—for example, in solitaire card games, I know the rules but\nam still unable to see the cards that have not yet been turned over. Conversely, an unknown\nenvironment can be fully observable \n\n\n```\ndef model_based_reflex_agent(percept):\n\tstate = update_state(state, action, percept, model)\n\trule = match_rule(state, rules)\n\taction = rule.Action\n\treturn action\n```\n\n```\ndef simple_reflex_agent(percept):\n\tstate = get_state_from_percept(percept)\n\trule = match_rule(state, rules)\n\taction = rule.Action\n\treturn action\n```\n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n \n1. In an episodic task environment, the agent’s experience is devided into atomic episodes. In each episode the agent receives a percept and then performs Sequential a single action. Crucially, the next episode does not depend on the actions taken in previous\nepisodes.\nSince episodes are independent of one another and the agent doesn't need to know the effect of its actions.\n\nMany classification tasks are episodic. \nFor example, an agent that has to spot defective parts on an assembly line bases each decision on the current part, regardless\nof previous decisions \n\n2. In sequential environments, on the other hand, the current decision could affect\nall future decisions \n\n3. If the next state of the environment is completely Deterministic\ndetermined by the current state and the action executed by the agent(s), \n\n4. If the environment can change while an agent is deliberating, then Static\nwe say the environment is dynamic for that agent \n\n5. If the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.\n6. Properties of the task environment:\n▶ Fully observable v.s. partially observable\n▶ Deterministic v.s. stochastic\n▶ Static v.s. dynamic\n▶ Episodic v.s. sequential\n▶ Known v.s. unknown\n▶ Single agent v.s. multi-agent \n\n\n7. An environment is uncertain if\n▶ It is not fully observable, or\n▶ It is not deterministic.\n\n\n\n\n\n\n\n \n\n## AIMA 2.4 The Structure of Agents\n\n1. agent program: The agent programs take the current percept as input from the sensors and return an action to the actuators.\n\nNotice the difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history. \nThe agent program has no choice but to take just the current percept as input because nothing more is available from the environment.\nif the agent’s actions need to depend on the entire percept sequence, the agent will have to remember the percepts.  \n2. basic agent programs: \n\n  a. Simple Reflex Agents:\n  They only looks at the current state and decides what to do,\n  Their intelligence is only based on the given static table \n\n  b. Model-based Reflex Agents: \n\n  A model based agent holds an internal state based on the percept history, each step it updates the internal state.\n\n  Updating internal state requires two kinds of knowledge \n\n    1. Agent needs to know how the world evolves independently from the agent. \n\n    2. How the agent’s actions affect the environment. \n\n  PS:It is rarely possible to determine exact state of a partially observable environment. \n\n  c. Goal-Based Agents: \n\n  A goal-based agent combines model-based agent’s model with a goal. To reach its goal. it often uses Search and Planning algorithms. \n\n  d. Utility-Based Agents: \n\n  With Utility-Based agents we use utility function which is essentially an internationalization of the performance measurement \n  (It kinda defines how happy will we be if we choose this path).\n  Also, if there are multiple goals(yes, you heard me right. \n  Might be multiple goals.) and these goals conflicts in some cases, utility function specifies the appropriate tradeoff. \n  Also, if non of these goals can be achieved with certainty, utility may provide likelihood of success.\n##### Three ways to represent states and the transitions between them\n3. In an atomic representation each state of the world is indivisible—it has no internal structures,\nThe standard algorithms\nunderlying search and game-playing (Chapters 3–5), hidden Markov models (Chapter 14),\nand Markov decision processes (Chapter 17) all work with atomic representations \n\n4. A factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value.Many important areas of AI are based on factored representations, including constraint\nsatisfaction algorithms (Chapter 6), propositional logic (Chapter 7), planning (Chapter 11),\nBayesian networks (Chapters 12–16), and various machine learning algorithms \n\n5. structured representation:we need to understand the world as having things in it that are related\nto each other, not just variables with values,Structured representations underlie relational databases and first-order logic\n(Chapters 8, 9, and 10), first-order probability models (Chapter 15), and much of natural language\nunderstanding (Chapters 23 and 24). In fact, much of what humans express in natural\nlanguage concerns objects and their relationships\n\n\n\n\n```\nfunction TABLE-DRIVEN-AGENT(percept) returns an action persistent:\n  percepts, a sequence, initially empty\n    table, a table of actions, indexed by percept sequences, initially fully specified\n  append percept to the end of percepts \n  action LOOKUP(percepts, table)\n  return action\n\n```\n\n\n\n## Module 1 Lecture Notes\n\n1. The hardest case is: Continuous,\nPartially Observable,\nStochastic,\nMultiagent \n\n\n2. A simple reflex agent is one that selects an action based on the current percept, and\nignores the rest of the percept history. \n\n3. A problem-solving agent must plan ahead. It will consider a sequence of actions that\nform a path to a goal state. The computational process that it undertakes is called\nsearch. \n\n#####summary\n• An agent is something that perceives and acts in an environment. The agent function\nfor an agent specifies the action taken by the agent in response to any percept sequence. \n\n• The performance measure evaluates the behavior of the agent in an environment. A\nrational agent acts so as to maximize the expected value of the performance measure,\ngiven the percept sequence it has seen so far. \n\n• A task environment specification includes the performance measure, the external environment,\nthe actuators, and the sensors. In designing an agent, the first step must\nalways be to specify the task environment as fully as possible. \n\n• Task environments vary along several significant dimensions. They can be fully or partially\nobservable, single-agent or multiagent, deterministic or nondeterministic, episodic\nor sequential, static or dynamic, discrete or continuous, and known or unknown. \n\n• In cases where the performance measure is unknown or hard to specify correctly, there\nis a significant risk of the agent optimizing the wrong objective. In such cases the agent\ndesign should reflect uncertainty about the true objective. \n\n• The agent program implements the agent function. There exists a variety of basic\nagent program designs reflecting the kind of information made explicit and used in the\ndecision process. The designs vary in efficiency, compactness, and flexibility. The\nappropriate design of the agent program depends on the nature of the environment. \n\n• Simple reflex agents respond directly to percepts, whereas model-based reflex agents\nmaintain internal state to track aspects of the world that are not evident in the current\npercept. Goal-based agents act to achieve their goals, and utility-based agents try to\nmaximize their own expected “happiness.” \n\n• All agents can improve their performance through learning. \n\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the agent’s perceptual inputs at any given instance\n* **Right thing** - the objective that we provide to the agente\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Rational agent** -  maximize the expected value of the performance measure\n* **Agent program** -  implements the agent function\n* **Environment nature** - fully/partially observable,static.dynamic,discrete/continuous,known/unknown\n* ** limited rationality** - acting appropriately when there is not enough computation.\n* **Value alignment problem** - values or objectives put into Value alignment problem the machine must be aligned with those of the human.\n* **Task environment** - Performance measure,Environment,Environment,Sensors\n* **Reflex agent** - anything that can perceive/act in an environment,ignore rest of percept history\n* **Simple reflex agent** - respond directly to percepts\n* **Model-based reflex agent** - maintain internal state to track aspects of the world that are not evident in the current percept\n* ** utility-based agent** - maximize expected reward\n* **Goal-based agent** - act to achieve their goal\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n 1.terminal REPL:read evaluation print loo \n\n\n2.scripts \n\n\n4.immutable:\ntuple:t = (23, 'abc', 4.56, (2,3), 'def')\nstring:st='hello'\n\n\n5.mutable:list[],li = ['abc', 34, 4.34, 23]\n索引：左包右-1\n t[1:4]=('abc', 4.56, (2,3))\n t[1:-1]=('abc', 4.56, (2,3))\n  t[1:-1:2]= t[1:-1:2]\n\n\n6.operation on lists\nli = [1, 11, 3, 4, 5,1] \n\ninplace operation: append,insert,remove,reverse,sort\nli.index('1')(index of first occurrence)\nli.append('a')加在最后 \n\nli.insert(2, 'i') 加在index=2的位置 \n\n7.operation on string:split,capitalize,upper\ns = \"Pretend this sentence makes sense.\"\n\n words = s.split(\" \")\n word=['Pretend', 'this', 'sentence', 'makes', 'sense.']\nstring.capitalize()/string.upper()只针对string，is not inplace\n8.dictionary:unordered & work by hashing, so keys must be immutable：\nindex by keys\n\nd = {'user' : 'R2D2', 'pswd': 1234}\n d['pswd'] = 'thx1138'\n{'user': 'R2D2', 'pswd': 'thx1138'}\nd.keys()/d.values()\ndict_keys(['user', 'p', 'i’])#list of currernts keys\nd.items()#list of tuple \ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n9.return multi values is a tuple\n\n10.Functions can be called with arguments out of order\nKeyword arguments can be used after all other arguments\n\n11.*args:只有数值a\ndef print_everything(*args):\n  print(args)\nlst = ['a','b']\nprint_everything(*lst)\n('a','b') \n\nlst = ['a']\nprint_everything(*lst)\n('a')\n\n12. **kwargs，有等号a=1\n\ndef print_keyword_args(**kwargs):\n  print(kwargs) \n\nprint_keyword_args(first=\"John\", last=\"Doe\")\n{'first': 'John', 'last': 'Doe’}\nmy_dict = {'f': 'Wei', 'l': 'Xu’}\nprint_keyword_args(**my_dict)\n{'f': 'Wei', 'l': 'Xu'}\n\n13.magic function:\\__str__\n \n\n## Module 2 Definitions\n* **Immutable** - a tuple cannot be modified once created Items can be of mixed types, including collection types \n\n\n## WARNING: Your summary of 'AIMA Chapter 3.3 Search Algorithms' is too long!\nWARNING: Your summary of 'AIMA Chapter 3.4 Uninformed Search Strategies' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n1. problem-solving agent: When the correct action to take is not immediately obvious, an agent may need to to plan\nahead: to consider a sequence of actions that form a path to a goal state \n\n2. Problem-solving agents use **atomic** representations,that Search\nis, states of the world are considered as wholes, with no internal structure visible to the\nproblem-solving algorithms \n\n3. Agents that use **factored or structured** representations of states\nare called planning agents \n\n4. informed algorithms: agent can estimate how\nfar it is from the goal \n\n5. four-phase problem-solving process: \n\n  a. Goal formulation: The agent adopts the goal of reaching Bucharest. Goals organize Goal formulation\nbehavior by limiting the objectives and hence the actions to be considered.\n  b. Problem formulation: The agent devises a description of the Problem formulation states and actions necessary\nto reach the goal \n\n  c. Search: Before taking any action in the real world, the agent simulates sequences of\nactions in its model, searching until it finds a sequence of actions that reaches the goal. \n\n  d. execution \n\n6. path: a squence of actions \n\n  solution: a path from initial state to goal \n\n  optimal solution has the lowest path cost among all solutions \n\n7. The process of removing detail from a representation is called Abstraction abstraction \n\n \n\n## AIMA Chapter 3.2 Example Problems\n \n### 3.2 example problem\n  1. A standardized problem is intended to illustrate or exercise various problem-solving meth-\nproblem.It can be given a concise, exact description and hence is suitable as a benchmark for\nReal-world problem researchers to compare the performance of algorithms. \n\n  2. real-world problem, such as robot\nnavigation, is one whose solutions people actually use, and whose formulation is idiosyncratic,\nnot standardized, because, for example, each robot has different sensors that produce\ndifferent data. \n\n####3.2.1 standardized problems : grid world problems \n\n####3.2.2 real-world prblems: route-finding problem \n\n\n#####node.PATH-COST: the total cost of the path from the initial state to this node. In mathematical\nformulas, we use g(node) as a synonym for PATH-COST.\n\n##### best-first-search\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 , with node as an element\n  reached←a lookup table, with one entry with key problem.INITIAL and value node\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    for each child in EXPAND(problem, node) do\n      s←child.STATE\n      if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n        reached[s]←child\n        add child to frontier\n  return failure\n\n\n\nfunction EXPAND(problem, node) yields nodes\n  s←node.STATE\n  for each action in problem.ACTIONS(s) do\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```\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \n### 3.3 search algo\n  1. search algo: takes a search problem as input, returns a solution or failure \n\n  2. **distinction** between the state space and the search tree:\nThe state space describes the (possibly infinite) set of states in the world, and the actions\nthat allow transitions from one state to another. \nThe search tree describes paths between these states, reaching towards the goal. \nThe search tree may have multiple paths to any given state, \nbut each node in the tree has a unique path back to the\nroot (as in all trees) \n\n  3. The **frontier** is the set of nodes that have been reached but not yet\nexpanded;\ninterior is the set of nodes that have been expanded;\nexterior is the set of states that have not been reached.\n\n#### 3.3.1 best-first search\n1. best-first search: choose a node, n, with minimum value of some f(n).\n\n\n#### 3.3.2 search data structures\n1. node = <state, parent-node, children,\naction, path-cost, depth> \n\n  data structures to store the frontier:queue, 3 operations on a frontier are: \n\n  • IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.\n\n  • POP(frontier) removes the top node from the frontier and returns it.\n\n  • TOP(frontier) returns (but does not remove) the top node of the frontier.\n\n\n2. 3 kinds of queues: \n\n  • Priority queue: first pops the node with the minimum cost according to some evaluation\nfunction, f , used in best-first search. \n\n  • A FIFO queue or first-in-first-out queue first pops the node that was added to the queue\nfirst; used in breadth-first search. \n\n  • A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most\nStack recently added node; used in depth-first search. \n\n\n#### 3.3.3 search data structures\n1. redundant path: a worse way to get to the same state \n\n2. how to eliminate repeated states/redundant path?  \n\n  • remember all previously reached states (as best-first search does), allowing \n\n  • don't need to worry: some problem formulations where it is rare or impossible for two paths to reach the same state.allowing \n  ##### We call a search algorithm a graph search if it checks for redundant \n\nTree-like search paths and a tree-like search6 if it does not check.\n  • only check for cycles, but not for redundant paths in general:\n  see if the state at the end of the path has appeared earlier in the path. \n\n##### 3.3.4 measure problem-solving performance\n  • Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not? \n\n  • Cost optimality: Does it find a solution with the lowest path cost of all solutions? \n\n  • Time complexity: How long does it take to find a solution? This can be measured in\nseconds, or more abstractly by the number of states and actions considered.\n\n  • Space complexity: How much memory is needed to perform the search? \n3. complete guarantee: systematic in the way it explores an infinite state space, \n  making sure it can eventually reach any state that is connected to the initial state. \n\n  \n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n###3.4 uinformed search\n#### 3.4.1 breadth-first search\n1. complete: \n\n  • a systematic search strategy:if the root node is expanded first, \n  then all the successors of the root node are expanded next,\nthen their successors. BFS is complete\neven on infinite state spaces. \n\n  • implement BFS as a call to\nBEST-FIRST-SEARCH where $f(n)=depth of the node$ \n\n • BFS always finds a solution with a minimal number of actions, because\nwhen it is generating nodes at depth d, it has already generated all the nodes at depth d-1,\nso if one of them were a solution, it would have been found. \n\n • it is cost-optimal if all actions have same cost \n\n  #####efficient tricks: \n  • A first-in-first-out queue:faster than a priority queue, and will give correct order of nodes: new\nnodes go to the back of the queue \n\n  • can do an **early goal test**,\nLate goal test checking whether a node is a solution as soon as it is generated, rather than **late goal test**\nthat best-first search uses, waiting until a node is popped off the queue. \n\n\n#### 3.4.2 Dijkstra's algo or uniform-cost search\n1.  Dijkstra's algo: When actions have different costs, an obvious choice is to use best-first search where $\nf(n)=cost from root to current node$.\n\n2. time and space complexity is $O(b^{1+[C^*/{\\epsilon]}}),C^*:$ the cost of the optimal solution; \n$\\epsilon$: a lower bound on the cost of each action \n\n  • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\nbefore exploring paths involving a high-cost and perhaps useful action. \n\n  • When all action costs are equal, it is just O(b^(d+1)), and it is similar to BFS.\n\n\n3. complete and cost-optimal: \n  • the first solution it finds\nwill have a cost that is at least as low as the cost of any other node. \n  • it considers all paths systematically in order of increasing cost, never getting caught\ngoing down a single infinite path \n\n#### 3.4.3 depth-first search\n1. DFS always expands the deepest node in the frontier. It could be implemented\nas a call to BEST-FIRST-SEARCH where $f(n)=negative\nof the depth$.\n\n2. not cost-optimal: it returns the first solution it\nfinds, even if it is not cheapest \n\n3. incomplete: In cyclic state spaces it can get stuck in an infinite loop; some implementations\nof DFS check each new node for cycles. DFS\nsearch is not systematic: it can get stuck going down an infinite path, even if there are no\ncycles. \n\n4. where a tree-like search is feasible,\ndepth-first search has much smaller needs for memory. \n\n5. A variant of depth-first search **backtracking search**: use less memory  \n\n  • only one successor is generated at a time rather; \n  each partially expanded node remembers which successor to generate next.\n\n  • successors are generated by modifying the current state description directly\nrather than allocating memory for a brand-new state. This reduces the memory requirements\nto just one state description and a path of O(m) actions \n\n  • backtracking has the option of maintaining an\nefficient set data structure for the states on the current path, allowing to check for a cyclic\npath in O(1) time rather than O(m).\n\n  • must undo each action when we backtrack.\n\n\n#### 3.4.4 depth-limited and iterative deepening search\n##### depth-limited\n1. depth-limited: a version of DFS which we supply a depth limit,$l$, treat all nodes\nat depth l as if they had no successors \n\n2. The time complexity is $O(b^l)$ and\nthe space complexity is $O(bl)$\n\n\n3. incomplete \n\n4. can't eliminate redundant paths but can eliminate cycles \n\n5. diameter of the state-space graph can reduce l and give a better depth limit \n\n\n##### iterative deepening search\n6. solves the problem of picking a good value for l by trying\nsearch all values: 0,1,2...—until either a solution is found, \nor the returns the failure value rather than the cutoff value\n7. combine DFS & BDF: \n\n  •DFS: memory requirements: O(bd) when there is a\nsolution, or O(bm) on finite state spaces with no solution \n\n • BFS: IDS is optimal for problems where all actions have the same cost, and is complete on\nfinite acyclic state spaces, or on any finite state space when we check nodes for cycles all the\nway up the path. \n\n8. time complexity is O(b^d) when there is a solution, or O(b^m) when there is none.\nbut BFS does this by storing all nodes in memory, while IDS by repeating the previous levels, \nthereby saving memory at the cost of more time \n\n9.IDS is preferred uninformed search when search state space is larger than can fit in memory and\nthe depth of the solution is not known.\n\n#### 3.4.5 Bidirectional search\n1. bidirectional search simultaneously\nsearches forward from the initial state and backwards from the goal state(s), hoping that the\ntwo searches will meet \n\n\n\n\n##### breadth-first-search and uniform-cost search algorithms.\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) then return node\n  frontier←a FIFO queue, with node as an element\n  reached←{problem.INITIAL}\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    for each child in EXPAND(problem, node) do\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##### Iterative deepening and depth-limited tree-like search.\n  ```\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure\n  for depth = 0 to ¥ do\n    result←DEPTH-LIMITED-SEARCH(problem, depth)\n    if result 6= cutoff then return result\n\nfunction DEPTH-LIMITED-SEARCH(problem, ℓ) returns a node or failure or cutoff\n  frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element\n  result←failure\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    if DEPTH(node) > ℓ then\n      result←cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do\n        add child to frontier\n  return result\n\n\n  ```\n\n\n\n\n\n  \n\n\n## Module 3 Lecture Notes\n\nThis chapter has introduced search algorithms that an agent can use to select action sequences\nin a wide variety of environments—as long as they are **episodic, single-agent, fully observable,\ndeterministic, static, discrete, and completely known** \n\n1. A problem-solving agent must **plan ahead**.The computational process that it\nundertakes is called **search**.\nIt will consider a sequence of actions that form a path to a goal state. \nSuch a sequence is called a solution.\n\n2. define search problem:States,initial state,Actions,Transition Mode,Path cost,Goal test\n3. basic search algo:\n\n  A.  tree search: \n\n    a.  Enumerate in some order all possible paths from the initial state\n\n    b.  ROOT= initial state \n\n    Nodes in search tree generated through transition model \n\n    treats different paths to the same node as distinct \n\n    c. A state is a (representation of a) physical configuration \n\n    d. A state is a (representation of a) physical configuration, node = <state, parent-node, children,\naction, path-cost, depth>,EXPAND function uses the Actions and Transition Model to create the\ncorresponding states creates new nodes,\n  B. graph search:\n\n    a. Check to see if a node has been visited before adding to search queue\n\n    b. must keep track of all possible states (can use a lot of memory)\n\n4. Uninformed search: All non-goal nodes in frontier look equally good, Informed search: Some non-goal nodes can be ranked above others.\n5. $b$: maximum branching factor\n\n  $d$: depth of least cost solution\n\n  $m$: maximum depth of state space($\\infty$)\n\n6. **Breadth-first search**: \n  expand shallowest unexpanded node \n\n  frontier is FIFO (First-In-First-Out) Queue(Put successors at the end of frontier successor list)\n\n  property:\n\n    1. complete: yes if b is finte\n\n    2. optimal: yes if cost=1/step, not optimal in general\n\n    3. time complexity:  $1+b+b^2+b^3+… +b^d = O(b^d)$\n    4. space complexity: $O(b^d)$(keeps every node in memory)\n\n\n6. **depth-first search**: \n  expand deepest unexpanded node \n\n  LIFO(Last-In-First-Out:Put successors at the front of frontier successor list)\n  property:\n\n    1. complete: No. It fails in infinite-depth spaces, spaces with loops.If we modify it to avoid repeated states along path, then it is complete in finite spaces \n\n    2. optimal: No \n\n    3. time complexity:  $ O(b^m)$, This is terrible if m is much larger than d,but if solutions are dense, may be much faster than breadth-first \n\n    4. space complexity: $O(bm)$, linear space \n\n7. Use depth-first if: \n\n    Space is restricted \n\n    There are many possible solutions with long paths and wrong paths are usually terminated quickly \n\n    Search can be fine-tuned quickly \n\n    solution are dense \n\n8. Use breadth-first if: \n\n  Possible infinite paths \n\n  Some solutions have short paths \n\n  Can quickly discard unlikely paths \n\n\n9. Depth-limited search: Depth-First search but with depth limit l, If l = d (by luck!), then optimal \n\n  But:\n\n    a. If l < d then incomplete \n\n    b. If l > d then not optimal \n\n  Time complexity: O(b^1)\n  Space complexity: O(bl) \n\n\n10. Iterative deepening search: A general strategy to find best depth limit l \n\nuse Depth-limited search as subroutine, with increasing l.\nbottom level (depth d) are generated once, up to the children of the root, which are\ngenerated d times \n\nComplete & optimal: Goal is always found at depth d, the depth of the shallowest goal-node. \n\ntime complexity: O(b^d) \n\nspace complexity: O(bd) \n\nN(IDS) = $(d)(b^1) +(d−1)(b^2)+(d−2)(b^3)...+b^d$ \n\n \n11. Impact of Task Environments: The properties of the task environments change the types of solutions that we need.\n  a. If an environment is: \n\n    • Fully observable \n\n    • Deterministic  \n\n    • Known environment \n\n  The solution to any problem in such an environment is a fixed sequence of actions. \n\n  b. if the environment is:  \n\n    • Partially observable or  \n\n    • Nondeterministic   \n\n  The solution must recommend different future actions depending on the what\npercepts it receives. This could be in the form of a branching strategy \n\n12. This comparison is for tree-like search versions which don’t check for\nrepeated states. For graph searches which do check, the main differences are that depth-first\nsearch is complete for finite state spaces, and the space and time complexities are bounded\nby the size of the state space (the number of vertices and edges, |V|+|E|).\n#### summary\n  • Before an agent can start searching, a well-defined problem must be formulated.\n\n  • A problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n  • The environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\n\n  • Search algorithms generally treat states and actions as atomic, without any internal\nstructure (although we introduced features of states when it came time to do learning).\n\n  • Search algorithms are judged on the basis of completeness, cost optimality, time complexity,\nand space complexity.\n\n  • **Uninformed search** methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n\n      • it can be much greater than O(b^d). because uniform-cost search can explore large trees of actions with low costs\nBest-first search selects nodes for expansion using to an evaluation function.\n      • Breadth-first search expands the shallowest nodes first; it is complete, optimal\nfor unit action costs, but has exponential space complexity.\n\n      • Uniform-cost search expands the node with lowest path cost, g(n), and is optimal\nfor general action costs.\n\n      • Depth-first search expands the deepest unexpanded node first. It is neither complete\nnor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n      • Iterative deepening search calls depth-first search with increasing depth limits\nuntil a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has\nlinear space complexity.\n\n      • Bidirectional search expands two frontiers, one around the initial state and one\naround the goal, stopping when the two frontiers meet.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - all states reachable from the initial state by any sequence of actions\n* **Path** - a sequence of actions leading from one state to another state\n* **Solution** - a path from initial state to goal state\n* **Optimal solution** - no solution has a lower path cost\n* **Frontier** - states are available for expanding\n* **Time complexity** - # of nodes generated (worst case)\n* **Completeness** - always find the solution\n* **Space complexity** - # of nodes simultaneously in memory (worst case)\n* **Strategies** - order of tree expansion, implemented by different queue structures (LIFO, FIFO, priority)\n* **Reached** - state that has had a node generated for it has been reached\n\n\n## WARNING: Your summary of 'AIMA Chapter 3.5 Informed (Heuristic) Search Strategies' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n\n### 3.5.1 greedy best-first search \n1. f(n) = h(n)\n### 3.5.2 A*\n1. f(n) = g(n)+h(n) \n\n2. A∗ search is complete. \n\n3. properties of h(n): admissibilty/consistency\n  if h(n) is admissible, A* is cost-optimal \n\n  • g∗(n) to mean the cost of the optimal path from the start \n\n  • h∗(n) to mean the cost of the optimal path from n to the nearest goal, we have:\n\n  • f(n) > C∗ (otherwise n would have been expanded)\n\n  • f(n) = g(n)+h(n) (by definition)\n\n  • f(n) = g∗(n)+h(n) (because n is on an optimal path)\n\n  • f(n) ≤ g∗(n)+h∗(n) (because of admissibility, h(n) ≤ h∗(n))\n\n  • f(n) ≤ C∗ (by definition, C∗ = g∗(n)+h∗(n)) \n \n  The first and last lines form a contradiction, so it must be that A∗ returns only cost-optimal paths.\n\n4. consistency:\n \n  • A heuristic h(Consistency n) is consistent if, for\nevery node n and every successor n′ of n generated by an action a, we have:\n\n  h(n) ≤ c(n,a,n′)+h(n′) (Triangle inequality)\n\n  • c(n,a,a′) of the action from n to n' \n\n5. Every consistent heuristic is admissible (but not vice versa), with a consistent heuristic,\nA∗ is cost-optimal \n\n  with a consistent heuristic, the first time we reach a state it will be on an optimal path, \n  so we never have to re-add a state to the frontier, and never have to change an entry in reached. \n  But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, \n  and if each new path has a lower path cost than the previous one, \n  then we will end up with multiple nodes for that state in the frontier, \n  costing us both time and space. \n  to avoid inconsistency, some implementations of A∗ take care to only enter a state\ninto the frontier once, and if a better path to the state is found, all the successors of the state\nare updated (which requires that nodes have child pointers as well as parent pointers). \n\n\n### 3.5.4 weighted A∗ \n1. f(n) = g(n)+W×h(n), for some W>1 \n\n2. \n• A∗ search: g(n)+h(n)(W=1) \n\n• Uniform-cost search: g(n)(W=0) \n\n• Greedy best-first search: h(n) (W=$\\infty$) \n\n• Weighted A∗ search: g(n)+W×h(n) (1<W<$\\infty$) \n\n\n\n##### recursive best-first search\n  ```\nfunction RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution or failure\n  solution, fvalue←RBFS(problem,NODE(problem.INITIAL),¥)\n  return solution\n\nfunction RBFS(problem, node, f limit) returns a solution or failure, and a new f -cost limit\n  if problem.IS-GOAL(node.STATE) then return node\n  successors←LIST(EXPAND(node))\n  if successors is empty then return failure, ¥\n  for each s in successors do // update f with value from previous search\n    s.f ←max(s.PATH-COST + h(s), node.f ))\n  while true do\n    best←the node in successors with lowest f -value\n    if best. f > f limit then return failure, best. f\n    alternative←the second-lowest f -value among successors\n    result, best. f ←RBFS(problem, best,min( f limit,alternative))\n    if result 6= failure then return result, best. f\n\n  ```\n\n\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n#### 3.6.1 The effect of heuristic accuracy\n1. effective branching factor b∗: The effective branching factor can vary across problem instances, but usually\nfor a specific domain (such as 8-puzzles) it is fairly constant across all nontrivial problem instances.\nTherefore, experimental measurements of b∗ on a small set of problems can provide a\ngood guide to the heuristic’s overall usefulness. A well-designed heuristic would have a value \n\nof b∗ close to 1\n2. reduces the effective depth by a constant kh compared to\nthe true depth.\n3. it is better to use a\nheuristic function with higher values, provided it is consistent and that the computation time\nfor the heuristic is not too long. higher h(n) drawback\nis that h(n) takes longer to compute.\n4.derive h(n) from relaxed problem\n• The state-space graph of the relaxed problem is a supergraph of the original state Relaxed problem\nspace because the removal of restrictions creates added edges in the graph\n• the relaxed problem adds edges to the state-space graph, any optimal solution in\nthe original problem is, by definition, also a solution in the relaxed problem\n5. derived from subproblem of a given\nproblem.\n• pattern databases is to store these exact solution costs for every possible Pattern database\nsubproblem instance\n6. with landmarks:\nchoose a few (perhaps 10 or 20) landmark points, then for each landmark L and for each other vertex v in the graph, we compute\nand store C∗(v,L), the exact cost of the optimal path from v to L.\nA greedy approach is to pick a first landmark at random, then find the point\nthat is furthest from that, and add it to the set of landmarks, and continue, at each iteration\nadding the point that maximizes the distance to the nearest landmark.\n\n\n\n\n\n\n\n## Module 4 Lecture Notes\n\n1. Best-first search: $evaluation funct = f(n)$ \n\n2. A heuristic function h(n): takes a state n and\nreturns an estimate of the distance from n. \n\n3. Greedy Best-First Search: $ f(n)=h(n)$ \n\n4. A*:\n  • Best-known form of best-first search.\n\n  • $f(n)=g(n) + h(n)$\n    1. g(n) the actual cost (so far) to reach the node \n\n    2. h(n) estimated cost to get from the node to the goal\n\n    3. f(n) estimated total cost of path through n to goal \n\n5. A heuristic h(n) is **admissible or optimistic** if it never overestimates the cost to reach the goal \n\n  • Formally: for all n, n a node:\n\n  • $ 0  \\leqslant h(n) \\leqslant h*(n)$ where h*(n) is the true cost from n\n  • h(n)>=0 so h(G)=0 for any goal G.\n\n  Example: $h_{SLD}(n)$ never overestimates the actual road distance\n\n  Theorem: If h(n) is admissible, A* using Tree Search is optimal\n\n6. Relaxed problems \n\n  • A problem with fewer restrictions on the actions \n\n  • The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem \n\n7. Dominance: A metric on better heuristics \n\n  If $ h_{2}(n) $ ≥ $ h_{1}(n) $ for all n (both admissible) \n\n    • then  $h_{2}$ dominates $ h_{1} $ \n\n  So  $ h_{2} $ is optimistic, but more accurate than $h_{1}$ \n\n    • $ h_{2} $ is therefore better for search \n\n    • Notice: $ h_{md} $ dominates $ h_{oop} $\n    • ($ h_{oop} $ = number of out of place tiles,If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\ngives the shortest solution \n\n    • $h_{md}$= total Manhattan distance,If the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\ngives the shortest solution) \n\n    • h*(n) dominates all other heuristics \n\n    • $ h_{teleportation}(n)=0 $ is dominated by all heuristics 瞬间转移\n\n8.comparision\n  • if want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. \n \n  • Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary. \n\n  • If want to find paths to one location, or the closest of several goals, use Greedy Best First Search or A*. \n\n  • Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. \n  Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic admissible. \n\n  • As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. \n  As the heuristic becomes larger, A* turns into Greedy Best First Search.\n##### summary\n1. Informed search methods have access to a heuristic function h(n) that estimates the\ncost of a solution from n. They may have access to additional information such as\npattern databases with solution costs. \n\n  • Greedy best-first search expands nodes with minimal h(n). It is not optimal but\nis often efficient.\n\n  • A∗ search expands nodes with minimal f (n) = g(n)+h(n). A∗ is complete and\noptimal, provided that h(n) is admissible. The space complexity of A∗ is still an\nissue for many problems.\n\n  • Bidirectional A∗ search is sometimes more efficient than A∗ itself.\n\n  • IDA∗ (iterative deepening A∗ search) is an iterative deepening version of A∗, and\nthus adresses the space complexity issue.\n\n  • RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗)\nare robust, optimal search algorithms that use limited amounts of memory; given\nenough time, they can solve problems for which A∗ runs out of memory.\nBeam search puts a limit on the size of the frontier; that makes it incomplete\nand suboptimal, but it often finds reasonably good solutions and runs faster than\ncomplete searches.\n\n  • Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\nbut sacrificing optimality\n\n2. good heuristic function: \n  • relaxing the problem definition \n\n  • storing precomputed solution costs for subproblems in a pattern database\n\n  • defining landmarks \n\n  • learning from experience with the problem class\n\n\n\n#### 3.5.5 memory-bounded search\n1. in implementation of best-first search, a state that is on the frontier is stored in two places: as a node in the frontier(to expand next)\nand as an entry in the table of reached states (visited). \n\nBut some implementations keep a state in only one of the two places, saving a bit of space at the\ncost of complicating (and perhaps slowing down) the algorithm \n\n  • remove states from reached when we can prove that they are\nno longer needed. For some problems, we can use the separation propert, along with the prohibition of U-turn actions, to ensure that all actions either move\noutwards from the frontier or onto another frontier state. In that case, we need only check the\nfrontier for redundant paths, and we can eliminate the reached table \n\n  • keep reference counts of the number of times a state has\nbeen reached, and remove it from the reached table when there are no more ways to reach\nthe state. For example, on a grid world where each state can be reached only from its four\nneighbors, once we have reached a state four times, we can remove it from the table.\n\n \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n### 5.1.1 two-player zero-sum game\n1.The games most commonly studied within AI (such as chess and Go) are what game theorists\ncall deterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect Perfect information\ninformation” is a synonym for “fully observable,”and “zero-sum” means that what is good Zero-sum games\nfor one player is just as bad for the other: there is no “win-win” outcome. For games we often\nuse the term move as a synonym for “action” and position as a synonym for “state \n2. the initial state, ACTIONS function, and RESULT function define the\nstate space graph—a graph where the vertices are states, the edges are moves and a state State space graph\nmight be reached by multiple paths.\n3. The minimax algorithm performs a complete depth-first exploration of the game tree.\nIf the maximum depth of the tree is m and there are b legal moves at each point, then the\ntime complexity of the minimax algorithm is O(b^m). The space complexity is O(bm) for an\nalgorithm that generates all actions at once, or O(m) for an algorithm that generates actions\none at a time \n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n#### 5.2.3\nα = the value of the best (highest-value) choice we have found so far at any choice point\nalong the path for MAX. Think: α = “at least.”\nβ = the value of the best (lowest-value) choice we have found so far at any choice point\nalong the path for MIN. Think: β = “at most.”\n\n##### minimax\n \n  ```\n\n\nfunction MINIMAX-SEARCH(game, state) returns an action\n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←$-\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n    v, move←v2, a\n  return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←+$\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move←v2, a\n  return v, move\n\n  ```\n##### alpha-beta pruning\n\n ```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action\n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state,−¥,+¥)\n  return move\n\nfunction MAX-VALUE(game, state,α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←−$-\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α, β)\n    if v2 > v then\n      v, move←v2, a\n      α←MAX(α, v)\n    if v ≥ β then return v, move\n  return v, move\n\nfunction MIN-VALUE(game, state,α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n  v←+$\\infty$\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α, β)\n    if v2 < v then\n      v, move←v2, a\n      β←MIN(β, v)\n    if v ≤ α then return v, move\n  return v, move\n\n ```\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n1. In other words, we replace the UTILITY function with EVAL, which estimates a\nstate’s utility. We also replace the terminal test by a cutoff test, which Cutoff test must return true for\nterminal states, but is otherwise free to decide when to cut off the search, based on the search\ndepth and any property of the state that it chooses to consider\n2. heuristic evaluation func EVAL(s,p) returns an estimate of the expected utility of state\ns to player p, just as the heuristic functions.For terminal states, it must be that EVAL(s, p)=UTILITY(s, p) and for nonterminal\nstates, the evaluation must be somewhere between a loss and a win: UTILITY(loss, p) ≤\nEVAL(s, p) ≤ UTILITY(win, p).\n3. The evaluation function should be applied only to positions that Quiescence are quiescent—that is,\npositions in which there is no pending move (such as a capturing the queen) that would wildly\nswing the evaluation. For nonquiescent positions the IS-CUTOFF returns false, and the search\nQuiescence search continues until quiescent positions are reached\n\n\n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \n\n1. A game\ntree in backgammon must include chance nodes in addition to MAX and MIN nodes.\n2. we can only calculate the expected value of a position: the average over all\npossible outcomes of the chance node\n3. \nThis leads us to the expectiminimax value for games with chance nodes\n\n\n\n\n\n\n\n\n\n\n\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 \n\n1. simplest game envi: \n\n  • Multiagent \n\n  • Static: No change while an agent is deliberating.\n\n  • Discrete: A finite set of percepts and actions.\n\n  • Fully observable: An agent's sensors give it the complete state of the environment. \n\n  • Strategic: The next state is determined by the current state and the action executed\nby the agent and the actions of one other agent.\n\n\n2. key property: \n  • Two players alternate moves \n\n  • Zero-sum: one player’s loss is another’s gain \n\n  • Clear set of legal moves \n\n  • Well-defined outcomes (e.g. win, lose, draw) \n\n\n3. minimax:\n\nIdea: Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN \n\n• For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX) \n\n• For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)  \n\n\n4. adversarial search(minimax):\nMAX assumes MIN plays optimally: Maximizes worst-case outcome for MAX. \n\n  • The backed-up value of each node in the tree is determined by the values of its\nchildren: \n\n  • For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX) \n\n  • For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN) \n\n  o Even levels represent turns for MAX, initialization= $-infty$ \n\n  o Odd levels represent turns for MIN, initialization= $+infty$ \n\n\n5. Alpha-Beta Pruning: \n\n  o During Minimax, keep track of two additional values: \n\n    α: MAX’s current lower bound on MAX’s outcome， MAX's best action  \n\n    β: MIN’s current upper bound on MIN’s outcome \n\n  o MAX will never allow a move that could lead to a worse score (for MAX) than α, \n  for max node , α越大越好 \n\n  o MIN will never allow a move that could lead to a better score (for MAX) than β,\n  for min node 𝛽 越小越好 \n\n  o Therefore, stop evaluating a branch whenever: \n\n  When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up \n\n    • MIN will never select that MAX node \n\n  When evaluating a MIN node: a value 𝑣 ≤ 𝛼 is found \n\n    • MAX will never select that MIN node \n\n\n6. expectimax and utilities: \n\n  Expectimax search: compute the average score under optimal\nplay \n\n  Max nodes as in minimax search\n  Chance nodes are like min nodes but the outcome is\n  uncertain to Calculate their expected utilities \n\n\n\n### summary\n• A game can be defined by the initial state (how the board is set up), the legal actions\nin each state, the result of each action, a terminal test (which says when the game is\nover), and a utility function that applies to terminal states to say who won and what the\nfinal score is. \n\n• In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\nthe minimax algorithm can select optimal moves by a depth-first enumeration\nof the game tree. \n\n• The alpha–beta search algorithm computes the same optimal move as minimax, but\nachieves much greater efficiency by eliminating subtrees that are provably irrelevant. \n\n• Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\nneed to cut the search off at some point and apply a heuristic evaluation function that\nestimates the utility of a state. \n\n• An alternative called Monte Carlo tree search (MCTS) evaluates states not by applying\na heuristic function, but by playing out the game all the way to the end and using\nthe rules of the game to see who won. Since the moves chosen during the playout may\nnot have been optimal moves, the process is repeated multiple times and the evaluation\nis an average of the results. \n\n• Many game programs precompute tables of best moves in the opening and endgame so\nthat they can look up a move rather than search. \n\n• Games of chance can be handled by expectiminimax, an extension to the minimax\nalgorithm that evaluates a chance node by taking the average utility of all its children,\nweighted by the probability of each child. \n\n• In games of imperfect information, such as Kriegspiel and poker, optimal play requires\nreasoning about the current and future belief states of each player. A simple approximation can be obtained by averaging the value of an action over each possible\nconfiguration of missing information. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n1. In this chapter we break open the black box by using a factored representation for each\nstate: a set of variables, each of which has a value. A problem is solved when each variable\nhas a value that satisfies all the constraints on the variable. A problem described this way is\ncalled a constraint satisfaction problem, or CSP \n\n\n2. CSPs deal with assignments of values to variables, {Xi =vi,Xj =vj, . . .}. An assignment \nthat does not violate any constraints is called a consistent or legal assignment. A complete \nassignment is one in which every variable is assigned a value, and a solution to a CSP is\na consistent, complete assignment. A partial assignment is one that leaves some variables Solution\nunassigned, and a partial solution is consistent. Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that Partial solution\ncan be solved very efficiently. \n\n\n3. every finite-domain constraint can\nbe reduced to a set of binary constraints if enough auxiliary variables are introduced. This\nmeans that we could transform any CSP into one with only binary constraints—which certainly\nmakes the life of the algorithm designer simpler. Another way to convert an n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be\none variable for each constraint in the original graph, and one binary constraint for each pair\nof constraints in the original graph that share variables \n\n\n\"unary constraint\" : \"restricts the value of a single variable, SA != greeni.\",  \n\n\"binary constraint\" : \"A binary constraint relates two variables, SA!=NSW.\",    \n\n\"higher-order constraints\" : \"involve 3 or more variables\",    \n\"Preference (soft constraints)\" : \"indicating which solutions are preferred, red is better than green can be represented by a cost for each variable assignment\", \n   \n4. CSPs with preferences can be\nsolved with optimization search methods, either path-based or local. We call such a problem\na constrained optimization problem \n\n5. constraint propagation: using the constraints to reduce the number of legal values for a variable \n\n6. Path consistency tightens the binary constraints by using implicit constraints\nthat are inferred by looking at triples of variables. A two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for\nevery assignment {Xi = a,Xj =b} consistent with the constraints (if any) on {Xi,Xj}, there is\nan assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}.\n time is only O(n2d).\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n1. local consistency: treat each variable Local consistency as a node in a graph (see\nFigure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local\nconsistency in each part of the graph causes inconsistent values \n\n2. node-consitent: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints \n\n3. arc-consistent: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints \n\n  More formally, Xi is arc-consistent with respect to another variable Xj if\nfor every value in the current domain Di there is some value in the domain Dj that satisfies\nthe binary constraint on the arc (Xi,Xj) \n\n4. A CSP is k-consistent: if, for any set of k−1 variables and for any consistent assignment to those variables,\na consistent value can always be assigned to any kth variable.\n\n5. A CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-\nk-consistent consistent,...all the way down to 1-consistent. Now suppose we have a CSP with n nodes\nand make it strongly n-consistent (i.e., strongly k-consistent for k=n). We can then solve\nthe problem as follows: First, we choose a consistent value for X1. We are then guaranteed\nto be able to choose a value for X2 because the graph is 2-consistent, for X3 because it is\n3-consistent, and so on. For each variable Xi, we need only search through the d values in the\ndomain to find a value consistent with X1,...,Xi−1. The total run \n\n\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n\n1. ac-3：\n\nforward checking. Forward checking Whenever a variable\nX is assigned, the forward-checking process establishes arc consistency for it: for each unassigned\nvariable Y that is connected to X by a constraint, delete from Y’s domain any value\nthat is inconsistent with the value chosen for X \n\n2. Given d values, checking arc (i,j) takes O(d^2) time worst case \n\nTo make an arc (i,j) arc consistent, \n\n  for each value v on Xi , \n\n    if there is no label on Yj consistent with v \n\n    then remove v from Xi \n\n\n\n\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\n  inputs: csp, a binary csp with variables {X1, X2, …, Xn}\n  local variables: queue, a queue of arcs initially the arcs incsp\n  while queue is not empty do\n    (Xi, Xj) ¬queue.pop()\n  if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n    for each Xk in NEIGHBORS[Xi ] – {Xj} do\n      add (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n  removed <- false\n  for each x in DOMAIN[Xi] do\n    if no value y in DOMAIN[Xj] allows (x,y) to satisfy\n      the constraints between Xi and Xj\n    then delete x from DOMAIN[Xi]; removed ¬ true\n  return removed\n\n```\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \n \n1. constriant satisfaction problem:\n\n  • A CSP consists of:\n\n    Finite set of variables X1, X2, …, Xn \n\n  • Nonempty domain of possible values for each variable\n    D1, D2, … Dn where Di = {v1, …, vk}\n\n  • Finite set of constraints C1, C2, …, Cm \n\n  • Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2 A\nstate is defined as an assignment of values to some or all variables.\n\n  o A consistent assignment does not violate the\nconstraints.\n\n2. \n  o An assignment is complete when every variable is assigned\na value. \n\n  o A solution to a CSP is a complete, consistent assignment.\n\n  o Solutions to CSPs can be found by a completely general\npurpose algorithm, given only the formal specification of\nthe CSP.\n\n3. benefits of csp \n\n  o Clean specification of many problems, generic goal,\nsuccessor function & heuristics \n\n  o CSP “knows” which variables violate a constraint\nAnd hence where to focus the search \n\n  o CSPs: Automatically prune off all branches that violate\nconstraints\n\n  (State space search could do this only by hand-building constraints\ninto the successor function)\n\n4. representations: Constraint graph:\n\n  nodes are variables\n\n  arcs are (binary) constraints\n\n\n5. CSP as a search problem \n\n  o A CSP can easily be expressed as a search problem \n\n    Initial State: the empty assignment {}.\n\n    Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n \n    Goal test: the current assignment is complete.\n\n    Path cost: a constant cost for every step.\n\n  o Solution is always found at depth n, for n variables \n\n    Depth First Search can be used \n\n      n variables of domain size d \n\n        • Branching factor at the root is n*d \n\n        • Branching factor at next level is (n-1)*d \n\n        • Tree has n!*(d^n) leaves \n\n  o The variable assignments are commutative \n\n    Eg [ step 1: WA = red; step 2: NT = green ] \n\n    equivalent to [ step 1: NT = green; step 2: WA = red ] \n\n    Therefore, a tree search, not a graph search \n\n  o Only need to consider assignments to a single variable at each\nnode: b = d and there are d^n leaves (n variables, domain size d )\n\n\n\n6. Search and Backtracking \n\n  o Depth-first search for CSPs with single-variable assignments is called\nbacktracking search  \n\n  o The term backtracking search is used for a depth-first search that chooses\nvalues for one variable at a time and backtracks when a variable has no legal\nvalues left to assign. \n\n  o Backtracking search is the basic uninformed algorithm for CSPs \n\n\n7. Improving backtracking efficiency \n\n  • Heuristics: \n\n  Q: Which variable should be assigned next? \n\n    1. Most constrained variable \n\n    2. (if ties:) Most constraining variable \n\n  Q: In what order should that variable’s values be tried? \n\n    3. Least constraining value,the one that rules out the fewest values in the remaining variables \n\n  Q: Can we detect inevitable failure early? \n\n    4. Forward checking,Keep track of remaining legal values for unassigned variables,\n    Terminate search when any unassigned variable has no remaining\nlegal values \n\n\n8. CSP solvers combine search and inference Search \n\n  • assigning a value to a variable \n\n  Constraint propagation (inference): Eliminates possible values for a variable\nif the value would violate local consistency \n\n  o Local consistency \n\n  Node consistency: satisfies unary constraints \n\n  Arc consistency: satisfies binary constraints \n\n  • ($X_i$ is arc-consistent w.r.t. $X_j$ if for every value v in $D_i$, there is some value w in\n$dD_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$) \n\n9. AC-3 \n\nThe most popular algorithm for enforcing arc consistency is called AC-3 (see Figure 6.3).\nTo make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider.\nInitially, the queue contains all the arcs in the CSP. (Each binary constraint becomes\ntwo arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj. If this leaves Di unchanged, the algorithm\njust moves on to the next arc. But if this revises Di (makes the domain smaller), then we add\nto the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi. We need to do that because the\nchange in Di might enable further reductions in Dk, even if we have previously considered Xk. \n \n\n##### summary\n• Constraint satisfaction problems (CSPs) represent a state with a set of variable/value\npairs and represent the conditions for a solution by a set of constraints on the variables.\nMany important real-world problems can be described as CSPs. \n\n• A number of inference techniques use the constraints to rule out certain variable assignments.\nThese include node, arc, path, and k-consistency. \n\n• Backtracking search, a form of depth-first search, is commonly used for solving CSPs.\nInference can be interwoven with search. \n\n• Th eminimum-remaining-values and degree heuristics are domain-independent methods\nfor deciding which variable to choose next in a backtracking search. The leastconstraining-\nvalue heuristic helps in deciding which value to try first for a given\nvariable. Backtracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem. Constraint\nlearning records the conflicts as they are encountered during search in order to\navoid the same conflict later in the search. \n\n• Local search using the min-conflicts heuristic has also been applied to constraint satisfaction\nproblems with great success. \n\n• The complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform\nthe CSP into a tree of subproblems and are efficient if the tree width of the constraint\ngraph is small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time. \n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n1. Propositional logic is\na factored representation \n\n2. The central component of a knowledge-based agent is its knowledge base, or KB. A knowl-\nedge base is a set of sentences. (Here “sentence” is used as a technical term. It is related Sentence\nbut not identical to the sentences of English and other natural languages.) Each sentence is\nexpressed in a language called a knowledge representation language and represents some assertion about the world. When the sentence is taken as being given without being derived\nfrom other sentences, we call it an axiom. \n\n3. knowledge-based agent program. Like all our agents,\nit takes a percept as input and returns an action. The agent maintains a knowledge base, KB,\nwhich may initially contain some background knowledge \n\n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n \n1. These sentences are\nexpressed according to the syntax of the representation language, Syntax which specifies all the\nsentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic:\n“x+y = 4” is a well-formed sentence, whereas “x4y+ =” is not. \n\n2. A logic must also define the semantics, or meaning, of sentences. The semantics defines\nTruth the truth of each sentence with respect to each possible world. For example, the semantics\nPossible world for arithmetic specifies that the sentence “x+y=4” is true in a world where x is 2 and y is 2,\nbut false in a world where x is 1 and y is 1. \n\n\n3. entailment\nNow that we have a notion of truth, we are ready to talk about logical reasoning. This inEntailment\nvolves the relation of logical entailment between sentences—the idea that a sentence follows\nlogically from another sentence. In mathematical notation, we write \n\n  α |= β\n\nto mean that the sentence α entails the sentence β. The formal definition of entailment is this: \n\n  α |= β if and only if, in every model in which α is true, β is also true. Using the notation just\nintroduced, we can write \n\n  α |= β if and only if M(α) ⊆ M(β)\n\n4. sound and complete:\n  • An inference algorithm that derives only entailed sentences is called sound or truth\npreserving. Soundness is a highly desirable property. An unsound inference procedure essentially\nmakes things up as it goes along—it announces the discovery of nonexistent needles.\nIt is easy to see that model checking, when it is applicable, is a sound procedure. \n\n  • The property of completeness is also desirable: an inference algorithm is complete if\nit can derive any sentence that is entailed. \n\n\n5. KB is true in the real world, then any\nsentence α derived from KB by a sound inference procedure is also true in the real world. So,\nwhile an inference process operates on “syntax”—internal physical configurations such as\nbits in registers or patterns of electrical blips in brains—the process corresponds to the realworld\nrelationship whereby some aspect of the real world is the case by virtue of other aspects\nof the real world being the case\n\n\n\n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n\n1. propositional logic:\n\n  • ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3.\n\n  • ∧ (and). A sentence whose main connective is ∧, is called a conjunction;\nits parts are the conjuncts.\n\n  • ∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction;\nits parts are disjuncts—in this example, (W1,3 ∧P3,1) and W2,2. \n\n  • ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- Implication\nditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent Premise\nis ¬W2,2. Implications are also known as rules or if–then statements. The implication Conclusion\nsymbol is sometimes written in other books as ⊃ or →. \n\n  • ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n1.first concept is logical equivalence: two sentences\nα and β are logically equivalent if they are true in the same set of models. We write\nthis as α ≡ β. \n\n2. theorem proving—applying rules of inference directly to the sentences\nin our knowledge base to construct a proof of the desired sentence without consulting models. \n\n3. validity: A sentence is valid if it is true in all models. For\nTautology example, the sentence P∨¬P is valid \n\n4. satisfiability: A sentence is satisfiable if it is true\nin, or satisfied by, some model.Satisfiability can be checked by enumerating the possible models until one is\nfound that satisfies the sentence \n\n5.Standard logical equivalences: \n\n  (α∧β) ≡ (β ∧α) commutativity of ∧ \n\n  (α∨β) ≡ (β ∨α) commutativity of ∨ \n\n  ((α∧β)∧γ) ≡ (α∧(β ∧γ)) associativity of ∧ \n\n  ((α∨β)∨γ) ≡ (α∨(β ∨γ)) associativity of ∨ \n\n  ¬(¬α) ≡ α double-negation elimination \n\n  (α ⇒ β) ≡ (¬β ⇒ ¬α) contraposition \n\n  (α ⇒ β) ≡ (¬α∨β) implication elimination \n\n  (α ⇔ β) ≡ ((α ⇒ β)∧(β ⇒ α)) biconditional elimination \n\n  ¬(α∧β) ≡ (¬α∨¬β) De Morgan \n\n  ¬(α∨β) ≡ (¬α∧¬β) De Morgan \n\n  (α∧(β ∨γ)) ≡ ((α∧β)∨(α∧γ)) distributivity of ∧ over ∨ \n\n  (α∨(β ∧γ)) ≡ ((α∨β)∧(α∨γ)) distributivity of ∨ over ∧ \n\n6.Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively,\nα is satisfiable iff ¬α is not valid. We also have the following useful result:\n\n  α |= β if and only if the sentence (α∧¬β) is unsatisfiable.\n\n7. conjunctive normal form \n\n  CNFSentence → Clause_1 ∧...∧ Clause_n \n\n  Clause → Literal_1 ∨...∨ Literal_m \n\n  Fact → Symbol \n\n  Literal → Symbol | ¬Symbol \n\n  Symbol → P | Q | R | ... \n\n  HornClauseForm → DefiniteClauseForm | GoalClauseForm \n\n  DefiniteClauseForm → Fact | (Symbol_1 ∧...∧ Symbol_l ) ⇒ Symbol  \n\n  GoalClauseForm → (Symbol_1 ∧...∧ Symbol_l ) ⇒ False \n\n\n\n\n \n\n## Module 7 Lecture Notes\n \n\n1. problem-solving agents have performed a search over states in order to find a plan. The representation of states has been atomic. \n\n2. Knowledge-based agents use a process of reasoning over an internal\nrepresentation of knowledge to decide what action to take. \n\n3. There are two kinds of sentences: \n\n  • Axioms – a sentence that is given \n\n  • Derived sentences – a new sentence that is derived from others sentences \n\n  The process of deriving new sentences from old sentences is called inference. \n\n4. A KB can initially contain some background information about the world, and a\nknowledge-based agent can add to the information in the KB through its observations\nof the world. \n\n5. In addition to asserting new knowledge into its KB, a knowledge-based agent can also\nquery the KB and ask it to derive new knowledge in order to select what action it\nshould take. \n\n6.Logic can serve as a general class of representations for knowledge-based agents.\nHere we are going to examine Propositional Logic. \n\n  • KB consists of sentences in the representation language \n\n  • Representation language has a syntax that specifies sentences that are well-formed \n\n  • A logic defines the semantics of the sentences, which is their meaning \n\n  • The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model \n\n7. Possible worlds and models \n\n  • Models are mathematical abstractions that have a fixed set of truth values which\nare {true, false} for each sentence. \n\n  • If sentence 𝛂 is true in model m then we say \n\n  • m satisfies 𝛂, or \n\n  • m is a model of 𝛂 \n\n  • We use the notation M(𝛂) to mean the set of all models of 𝛂. \n\n  For instance, 𝛂 could be a sentence that means “there is no pit in [2,2]”. In that case,\nM(𝛂) would be all instances of Wampa World where [2,2] doesn’t have a pit. \n\n\n8. Logical Entailment \n\n  • Once we have a notion of truth, we can start to define logical reasoning. Logical\nreasoning involves the entailment relation between sentence. \n\n  • To write sentence 𝛂 entails sentence β in mathematical notation we use the ⊨ symbol: \n\n      𝛂⊨β \n\n  • The definition is 𝛂⊨β if and only if M(𝛂) ⊆ M(β), \n\n  • This means that 𝛂 is more specific, or stronger than, β. For instances, β could mean\nthat “The agent is a robot” and 𝛂 could mean “The agent is an astromech”. \n\n\n9. The KB is false in models that contradict\nwhat the agent knows. \n\n10. Possible Worlds is the process of\nenumerating all Possible Worlds that are\ncompatible with the KB. M(KB) ⊆ M(𝛂_1) \n\n11. logical inference \n\n  • Entailment can be applied to derive conclusions, which is the process of logical\ninference. \n\n  • We can think about the consequences of a KB as a large set of additional sentences\nthat are entailed given the sentences that have been added to the KB. \n\n  • We would like to design inference algorithms to enumerate these sentences.\nWhen an inference algorithm i allows us to conclude that 𝛂 is true, then we write \n\n  • KB ⊢i 𝛂m“𝛂 is derived from KB by i” \n\n\n12.logically equivalent \n\n • Two sentences 𝛂 and β are logically equivalent if they are true in the same set of\nmodels. We write this as \n \n  𝛂 ≡ β\n\n • An alternate definition of logical equivalence is that two sentences 𝛂 and β are logically\nequivalent if any only if they entail each other.\n\n  𝛂 ≡ β if and only if 𝛂⊨β and β⊨𝛂. \n\n13. search algo：\n\n  We can use search algorithms to find a\nsequence of steps that constitutes a proof!\n\n  • Initial State: the initial knowledge base.\n\n  • Actions: All inference rules applied to\n\nall sentence that match the top half of\nthe inference rule.\n\n  • Result: Add the sentence on the\nbottom half to the KB.\n\n  • Goal: The goal is a state that contains\nthe sentence that we are trying to proce\n\n14. monotonicity: \n\nMonotonicity says that the set of entailed sentence can only increase as information is\nassed to the KB. \n\nif KB⊨𝛂 then KB ⋀ β⊨𝛂 \n\nIf we add additional information to the KB, it doesn’t invalidate any other info that\nwe’ve already inferred. \n\nTherefore it is sound it will only derive entailed sentences. \n\n15. Conjunctive Normal Form (CNF)\n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals.\n\n  1. Eliminate ⇔ by replacing 𝛂 ⇔ β with (𝛂⟹β) ⋀ (β ⟹𝛂)\n\n  2. Eliminate ⟹by replacing 𝛂⟹β with ¬𝛂 ⋁ β\n\n  3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n\n  4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.\n\n16. resolution: a single inference rule:yields a complete inference\nalgorithm when coupled with any complete search algorithm.\n\n17. Resolution Algorithm \n\nInference procedures based on resolution work using the principle of proof by\ncontradiction.\n\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\nHere’s how:\n\n• First, convert (KB ⋀ ¬𝛂) into CNF\n\n• Then apply the resolution rule to the resulting clauses.\n\n• Resolve every pair that contains complementary literals to produce a new clause\n\n• If that new clause isn’t already present, then add it to the set.\n\n• Continue the process until one of two things happens:\n\n  1. There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \n\n  2. Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂 \n\n\n18. Horn Clauses and Definite Clauses\n\nThe resolution algorithm is complete! This makes is a very important inference\nmethod.\n\nHowever, we don’t always need the full power of resolution. Some KBs are formulated\nin a more restrictive form which enables them to use more efficient inference\nalgorithms.\n\n• Definite clause – disjunction of literals where exactly one is positive\n\n• Horn clause – disjunction of literals where at most one is positive\n\n• This includes definite clauses\n\n• And clauses with no positive literals \n\n\n19.Forward Chaining and Backward Chaining\n\nForward Chaining is a kind of data-driven reasoning. An agent can start with known\ndata, adding premises as new percepts come in, and then incrementally apply the\nforward chaining algorithm to derive new conclusions. It doesn’t have to have a\nspecific query in mind to do so.\n\nBackward chaining works backwards from a query. If the query is known to be true,\nthen no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true\n(via backward chaining), then the query is true.\n\nBackward chaining is a form of goal-directed reasoning.\n\n\n##### summary:\n  • Intelligent agents need knowledge about the world in order to reach good decisions. \n\n  • Knowledge is contained in agents in the form of sentences in a knowledge representation\nlanguage that are stored in a knowledge base. \n\n  • A knowledge-based agent is composed of a knowledge base and an inference mechanism.\nIt operates by storing sentences about the world in its knowledge base, using the\ninference mechanism to infer new sentences, and using these sentences to decide what\naction to take. \n\n  • A representation language is defined by its syntax, which specifies the structure of\nsentences, and its semantics, which defines the truth of each sentence in each possible\nworld or model. \n\n  • The relationship of entailment between sentences is crucial to our understanding of\nreasoning. A sentence α entails another sentence β if β is true in all worlds where\nα is true. Equivalent definitions include the validity of the sentence α ⇒ β and the\nunsatisfiability of the sentence α∧¬β. \n\n  • Inference is the process of deriving new sentences from old ones. Sound inference algorithms\nderive only sentences that are entailed; complete algorithms derive all sentences\nthat are entailed. \n\n  • Propositional logic is a simple language consisting of proposition symbols and logical\nconnectives. It can handle propositions that are known to be true, known to be false, or\ncompletely unknown. \n\n  • The set of possible models, given a fixed propositional vocabulary, is finite, so entailment\ncan be checked by enumerating models. Efficient model-checking inference\nalgorithms for propositional logic include backtracking and local search methods and\ncan often solve large problems quickly. \n\n  • Inference rules are patterns of sound inference that can be used to find proofs. The\nresolution rule yields a complete inference algorithm for knowledge bases that are\nexpressed in conjunctive normal form. Forward chaining and backward chaining\nare very natural reasoning algorithms for knowledge bases in Horn form. \n\n  • Local search methods such as WALKSAT can be used to find solutions. Such algorithms\nare sound but not complete. \n\n  • Logical state estimation involves maintaining a logical sentence that describes the set\nof possible states consistent with the observation history. Each update step requires\ninference using the transition model of the environment, which is built from successorstate\naxioms that specify how each fluent changes. \n\n  • Decisions within a logical agent can be made by SAT solving: finding possible models\nspecifying future action sequences that reach the goal. This approach works only for\nfully observable or sensorless environments. \n\n  • Propositional logic does not scale to environments of unbounded size because it lacks\nthe expressive power to deal concisely with time, space, and universal patterns of relationships\namong objects. \n\n\n \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AqT2d7VXJUHD"
      },
      "source": [
        "from google.colab import drive\n",
        "drive.mount('/content/drive')"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}