{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Namita - FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c5cccc67-af03-4a86-8c9a-7b99ca3b4f8e"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1c168929-29d0-41f1-e6a5-030260ab7fc1"
      },
      "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": 3,
      "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": 4,
      "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 = \"\"\" From these two dimensions— _human vs. rational and thought vs. behavior_ —there are four possible combinations, and there have been adherents and research programs for all four.\n",
        "The Turing test, a computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or from a computer. \\n\n",
        "\n",
        "The interdisciplinary field of __cognitive science__ brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind. \\n\n",
        "\n",
        "AI approaches: turing (acting humanly), cognitive (thinking humanly), logic (thinking rationally), rational agent(acting rationally). \\n\n",
        "\n",
        "The rational-agent approach to AI has __two advantages__ over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. The standard of rationality is mathematically well defined and completely general. \\n\n",
        "\n",
        "__the issue of limited rationality__—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good starting point for theoretical analysis. (might not do the optimal thing always). \\n\n",
        "\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" __weak AI__—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking). \\n\n",
        "\n",
        "Turing says human thinking is too complex to be quantified in rules and inferences and hence coded. Humans use some kind of informal thinking.\n",
        "But deep learning has started capturing most of it, hence, logical inferences might not always give the solution needed. \\n\n",
        "\n",
        "__Mathematical Objection__: because machines are formal systems that are limited by the incompleteness theorem—they cannot establish the truth of their own Gödel sentence—while humans have no such limitation. \\n\n",
        "\n",
        "Briefly, for any formal axiomatic framework F  powerful enough to do arithmetic, it is possible to construct a so-called Gödel sentence G(F)  with the following properties:\n",
        "G(F)  is a sentence of F , but cannot be proved within F .\n",
        "If F  is consistent, then G(F) is true. \\n\n",
        "\n",
        "\n",
        "__Measuring AI__: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc. \\n\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Some philosophers claim that a machine that acts intelligently would not be actually thinking, but would be only a simulation of thinking. \\n\n",
        "\n",
        "Chinese: Blurting out chinese responses through a set of rules.\n",
        "Therefore, there is no understanding of Chinese. And Searle says that the Chinese room is doing the same thing that a computer would do, so therefore computers generate no understanding. \\n\n",
        "\n",
        "__Biological Naturalism__: Humans are made of cells and cells have no understanding.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" We use the term __percept__ to refer to the content an agent’s sensors are perceiving. An agent’s __percept sequence__ is the complete history of everything the agent has ever perceived. \\n\n",
        "\n",
        "Mathematically speaking, we say that an agent’s behavior is described by the __agent function__ that maps any given percept sequence to an action. \\n\n",
        "\n",
        "__The agent function__ is an abstract mathematical description; __the agent program__ is a concrete implementation, running within some physical system. \\n \"\"\"\n",
        "chapter2_2 = \"\"\" __Performance measure__: This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\n",
        "general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \\n\n",
        "\n",
        "__What is rational at any given time depends on four things__: \\n\n",
        "The performance measure that defines the criterion of success. \\n\n",
        "The agent’s prior knowledge of the environment. \\n\n",
        "The actions that the agent can perform. \\n\n",
        "The agent’s percept sequence to date. \\n\n",
        "\n",
        "\n",
        "__Formal definition of rational agent__: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. \\n\n",
        "\n",
        "rationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance. Rationality doesn't require omniscience. \\n\n",
        "\n",
        "Doing actions in order to modify future percepts—sometimes called __information gathering__ —is an important part of rationality. A second example of information gathering is provided by the __exploration__ that must be undertaken by a vacuum-cleaning agent in an initially unknown environment. \\n\n",
        "\n",
        "Our definition requires a rational agent not only to gather information but also to __learn__ as much as possible from what it perceives. \\n\n",
        "\n",
        "To the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks __autonomy__. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge. \\n \"\"\"\n",
        "chapter2_3 = \"\"\" We must think about __task environments__, which are essentially the “problems” to which rational agents are the “solutions.” (can be real or virtual). \\n\n",
        "\n",
        "For the acronymically minded, we call this the __PEAS (Performance, Environment, Actuators, Sensors)__ description. In designing an agent, the first step must always be to specify the task environment as fully as possible. \\n\n",
        "__Properties of Task Environments__: \\n\n",
        "__FULLY vs PARTIALLY OBSERVABLE__: If the agent has no sensors at all then the environment is unobservable. \\n\n",
        "__SINGLE-AGENT VS. MULTIAGENT__: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot). \\n\n",
        "\n",
        "__DETERMINISTIC VS NON DETERMINISTIC__:\n",
        " If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.  \\n\n",
        "\n",
        "__EPISODIC VS. SEQUENTIAL:__ \n",
        "In episodic, every episode is atomic and independent of the previous episode.Examples of sequential -  Chess and taxi driving are sequential \\n\n",
        "\n",
        "__STATIC vs DYNAMIC:__\n",
        " If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock). \\n\n",
        "\n",
        "__DISCRETE VS. CONTINUOUS__: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem. \\n\n",
        "\n",
        "__KNOWN VS. UNKNOWN__:\n",
        "Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. \\n\n",
        "\n",
        "Experiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class. \\n\n",
        "​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. \\n\n",
        "Conversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them. \\n\n",
        "Experiments are often carried out not for a single environment but for many environments drawn from an __environment class__. For example, to evaluate a taxi driver in simulated traffic,\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "__Agent = architecture + program__\n",
        "In general, __the architecture__ makes the percepts from the sensors available to the program, runs the program, and feeds the program’s action choices to the actuators as they are generated. \\n\n",
        "\n",
        "__The agent programs__ that we design in this book all have the same skeleton: they take the current percept as input from the sensors and return an action to the actuators. \\n\n",
        "\n",
        "The simplest kind of agent is the  __simple reflex agent__. These agents select actions on the basis of the current percept, ignoring the rest of the percept history. \\n\n",
        "\n",
        "__Simple Reflex Actions __have limited intelligence. They work well only in fully observable environments. Can get caught in infinite loops that are partially observable. \\n\n",
        "Solution: randomize actions. Hence, a randomized simple reflex agent might outperform a deterministic simple reflex agent. \\n\n",
        "\n",
        "__Model-based Reflex Actions__:\n",
        "Keep track of the world using internal state through agent’s sensors. \\n\n",
        "\n",
        "Info about how the world changes: transition model. \\n\n",
        "\n",
        "For example, when the car in front initiates braking, one or more illuminated red regions appear in the forward-facing camera image, This kind of knowledge is called a sensor model. \\n\n",
        "\n",
        "Goal based agent:\n",
        "The agent program can combine this with the model (the same information as was used in the model-based reflex agent) to choose actions that achieve the goal through search and planning. \\n\n",
        "\n",
        "Utility-based agents:\n",
        "Goal + Utility (happy state, sad state of a rider in a taxi). \\n\n",
        "An agent’s utility function is essentially an internalization of the performance measure. Provided that the internal utility function and the external performance measure are in agreement, an agent that chooses actions to maximize its utility will be rational according to the external performance measure. \\n\n",
        "\n",
        "Learning Agents:\n",
        "Autonomy: \\n\n",
        "The most important distinction is between the learning element, which is responsible for making improvements, and the performance element, which is responsible for selecting external actions. The performance element is what we have previously considered to be the entire agent: it takes in percepts and decides on actions. The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better in the future. \\n\n",
        "The last component of the learning agent is the problem generator. It is responsible for suggesting actions that will lead to new and informative experiences. \\n\n",
        "Reward and Penalty \\n\n",
        "\n",
        " \"\"\"\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"An agent is anything that perceives its environment through sensors and acts upon that environment through actuators.\",\n",
        "\"Rationality\" : \"doing the right thing\",\n",
        "\"Turing Test\" : \"NLP, knowledge representation, automated reasoning, machine learning\",\n",
        "\"Total turing test\": \"requires interaction with the real world, computer vision and robotics\",\n",
        "\"Syllogisms\":\"logic, but world is not certain, hence, probability is introduced\",\n",
        "\"Rational Agent\":\"acts to achieve best expected outcome, A rational agent is one that does the right thing.\",\n",
        "\"Standard Model\":\"AI has focused on the study and construction of agents that do the right thing.\",\n",
        "\"GOFAI\":\"Good old fashioned AI corresponds to the simplest logical agent design\",\n",
        "\"The embodied cognition approach\":\" makes no sense to consider brain separately,cognition takes place within a body,embedded in an environment\",\n",
        "\"The “argument from disability”\":\"makes the claim that a machine can never do X (can love, be kind etc ).\",\n",
        "\"Qualia and Consciousness\":\"The technical term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ab2f3c03-4909-4545-fa11-c66a52a5fde3"
      },
      "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": 56,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n From these two dimensions— _human vs. rational and thought vs. behavior_ —there are four possible combinations, and there have been adherents and research programs for all four.\nThe Turing test, a computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or from a computer. \n\n\nThe interdisciplinary field of __cognitive science__ brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind. \n\n\nAI approaches: turing (acting humanly), cognitive (thinking humanly), logic (thinking rationally), rational agent(acting rationally). \n\n\nThe rational-agent approach to AI has __two advantages__ over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. The standard of rationality is mathematically well defined and completely general. \n\n\n__the issue of limited rationality__—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good starting point for theoretical analysis. (might not do the optimal thing always). \n\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n __weak AI__—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking). \n\n\nTuring says human thinking is too complex to be quantified in rules and inferences and hence coded. Humans use some kind of informal thinking.\nBut deep learning has started capturing most of it, hence, logical inferences might not always give the solution needed. \n\n\n__Mathematical Objection__: because machines are formal systems that are limited by the incompleteness theorem—they cannot establish the truth of their own Gödel sentence—while humans have no such limitation. \n\n\nBriefly, for any formal axiomatic framework F  powerful enough to do arithmetic, it is possible to construct a so-called Gödel sentence G(F)  with the following properties:\nG(F)  is a sentence of F , but cannot be proved within F .\nIf F  is consistent, then G(F) is true. \n\n\n\n__Measuring AI__: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Some philosophers claim that a machine that acts intelligently would not be actually thinking, but would be only a simulation of thinking. \n\n\nChinese: Blurting out chinese responses through a set of rules.\nTherefore, there is no understanding of Chinese. And Searle says that the Chinese room is doing the same thing that a computer would do, so therefore computers generate no understanding. \n\n\n__Biological Naturalism__: Humans are made of cells and cells have no understanding.\n\n \n\n## AIMA 2.1 Agents and Environments\n We use the term __percept__ to refer to the content an agent’s sensors are perceiving. An agent’s __percept sequence__ is the complete history of everything the agent has ever perceived. \n\n\nMathematically speaking, we say that an agent’s behavior is described by the __agent function__ that maps any given percept sequence to an action. \n\n\n__The agent function__ is an abstract mathematical description; __the agent program__ is a concrete implementation, running within some physical system. \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n __Performance measure__: This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\ngeneral rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n\n\n__What is rational at any given time depends on four things__: \n\nThe performance measure that defines the criterion of success. \n\nThe agent’s prior knowledge of the environment. \n\nThe actions that the agent can perform. \n\nThe agent’s percept sequence to date. \n\n\n\n__Formal definition of rational agent__: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. \n\n\nrationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance. Rationality doesn't require omniscience. \n\n\nDoing actions in order to modify future percepts—sometimes called __information gathering__ —is an important part of rationality. A second example of information gathering is provided by the __exploration__ that must be undertaken by a vacuum-cleaning agent in an initially unknown environment. \n\n\nOur definition requires a rational agent not only to gather information but also to __learn__ as much as possible from what it perceives. \n\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks __autonomy__. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge. \n \n\n## AIMA 2.3 The Nature of Environments\n We must think about __task environments__, which are essentially the “problems” to which rational agents are the “solutions.” (can be real or virtual). \n\n\nFor the acronymically minded, we call this the __PEAS (Performance, Environment, Actuators, Sensors)__ description. In designing an agent, the first step must always be to specify the task environment as fully as possible. \n\n__Properties of Task Environments__: \n\n__FULLY vs PARTIALLY OBSERVABLE__: If the agent has no sensors at all then the environment is unobservable. \n\n__SINGLE-AGENT VS. MULTIAGENT__: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot). \n\n\n__DETERMINISTIC VS NON DETERMINISTIC__:\n If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.  \n\n\n__EPISODIC VS. SEQUENTIAL:__ \nIn episodic, every episode is atomic and independent of the previous episode.Examples of sequential -  Chess and taxi driving are sequential \n\n\n__STATIC vs DYNAMIC:__\n If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock). \n\n\n__DISCRETE VS. CONTINUOUS__: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem. \n\n\n__KNOWN VS. UNKNOWN__:\nStrictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. \n\n\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class. \n\n​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. \n\nConversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them. \n\nExperiments are often carried out not for a single environment but for many environments drawn from an __environment class__. For example, to evaluate a taxi driver in simulated traffic,\n\n\n## AIMA 2.4 The Structure of Agents\n\n__Agent = architecture + program__\nIn general, __the architecture__ makes the percepts from the sensors available to the program, runs the program, and feeds the program’s action choices to the actuators as they are generated. \n\n\n__The agent programs__ that we design in this book all have the same skeleton: they take the current percept as input from the sensors and return an action to the actuators. \n\n\nThe simplest kind of agent is the  __simple reflex agent__. These agents select actions on the basis of the current percept, ignoring the rest of the percept history. \n\n\n__Simple Reflex Actions __have limited intelligence. They work well only in fully observable environments. Can get caught in infinite loops that are partially observable. \n\nSolution: randomize actions. Hence, a randomized simple reflex agent might outperform a deterministic simple reflex agent. \n\n\n__Model-based Reflex Actions__:\nKeep track of the world using internal state through agent’s sensors. \n\n\nInfo about how the world changes: transition model. \n\n\nFor example, when the car in front initiates braking, one or more illuminated red regions appear in the forward-facing camera image, This kind of knowledge is called a sensor model. \n\n\nGoal based agent:\nThe agent program can combine this with the model (the same information as was used in the model-based reflex agent) to choose actions that achieve the goal through search and planning. \n\n\nUtility-based agents:\nGoal + Utility (happy state, sad state of a rider in a taxi). \n\nAn agent’s utility function is essentially an internalization of the performance measure. Provided that the internal utility function and the external performance measure are in agreement, an agent that chooses actions to maximize its utility will be rational according to the external performance measure. \n\n\nLearning Agents:\nAutonomy: \n\nThe most important distinction is between the learning element, which is responsible for making improvements, and the performance element, which is responsible for selecting external actions. The performance element is what we have previously considered to be the entire agent: it takes in percepts and decides on actions. The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better in the future. \n\nThe last component of the learning agent is the problem generator. It is responsible for suggesting actions that will lead to new and informative experiences. \n\nReward and Penalty \n\n\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - An agent is anything that perceives its environment through sensors and acts upon that environment through actuators.\n* **Rationality** - doing the right thing\n* **Turing test** - NLP, knowledge representation, automated reasoning, machine learning\n* **Total turing test** - requires interaction with the real world, computer vision and robotics\n* **Syllogisms** - logic, but world is not certain, hence, probability is introduced\n* **Rational agent** - acts to achieve best expected outcome, A rational agent is one that does the right thing.\n* **Standard model** - AI has focused on the study and construction of agents that do the right thing.\n* **Gofai** - Good old fashioned AI corresponds to the simplest logical agent design\n* **The embodied cognition approach** -  makes no sense to consider brain separately,cognition takes place within a body,embedded in an environment\n* **The “argument from disability”** - makes the claim that a machine can never do X (can love, be kind etc ).\n* **Qualia and consciousness** - The technical term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "__Portable__: \\n\n",
        "Programs run on major platforms without change. \\n\n",
        "__REPL__: Run Evaluate Print Loop : type python3 in your terminal\\n\n",
        "All data treated as objects. An object is deleted (by garbage collection) once unreachable \\n\n",
        "Strong typing means that the type of a value doesn't change in unexpected ways. A string containing only digits doesn't magically become a number, as may happen in Perl. Every change of type requires an explicit conversion. \\n\n",
        "Dynamic typing, you don't need to specify the type of variable before defining. \\n \\n\n",
        "\n",
        "__STRINGS__: \\n\n",
        "Immutable \\n\n",
        "== checks whether variables point to objects of the same value \\n\n",
        "is checks whether variables point to the same object \\n\n",
        "\n",
        "__Operations on Strings__ \\n\n",
        "s = \"Pretend this sentence makes sense.\" \\n\n",
        "words = s.split(\" \") \\n\n",
        "words \\b\n",
        "['Pretend', 'this', 'sentence', 'makes', 'sense.'] \\n\n",
        "\"_\".join(words) #join method of obj \"_\" \\n\n",
        "'Pretend_this_sentence_makes_sense.' \\n\n",
        "s = 'dog' \\n\n",
        "s.capitalize() \\n\n",
        "'Dog' \\n\n",
        "s.upper() \\n\n",
        "'DOG’ \\n\n",
        "‘hi --'.strip(' –') \\n\n",
        "'Hi’ \\n\n",
        "\n",
        "\n",
        "__LISTS__: \\n\n",
        "Mutable ordered sequence of items of mixed types \\n\n",
        "use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value \\n\n",
        "A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original. \\n\n",
        "A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original. \\n\n",
        "\n",
        "Operations on Lists: \\n\n",
        ">>> li.append('a') # Note the method syntax  \\n\n",
        ">>> li.insert(2, 'i')  \\n\n",
        ">>> li [1, 11, 'i', 3, 4, 5, 'a'] \\n\n",
        ">>> li = ['a', 'b', 'c', 'b'] \\n\n",
        ">>> li.index('b') # index of first occurrence 1  \\n\n",
        ">>> li.count('b') # number of occurrences 2 \\n\n",
        ">>> li.remove('b') # remove first occurrence \\n\n",
        ">>> li.reverse() # reverse the list *in place* (modify) \\n\n",
        ">>> li.sort() # sort the list *in place*  \\n\n",
        ">>> li.sort(some_function) # sort in place using user-defined comparison  \\n\n",
        ">>> sorted(li) #return a *copy* sorted \\n\n",
        "\n",
        "__TUPLES__: \\n\n",
        "A simple immutable ordered sequence of items \\n\n",
        "Immutable: a tuple cannot be modified once created \\n\n",
        "Items can be of mixed types, including collection types \\n\n",
        "\n",
        "__SLICING__: \\n\n",
        "t[1:4] #slicing ends before last index \\n\n",
        "t[1:-1] #using negative index \\n\n",
        "('abc', 4.56, (2,3)) \\n\n",
        "t[1:-1:2] # selection of every nth item. \\n\n",
        "('abc', (2,3)) \\n\n",
        "t[:2] # copy from beginning of sequence \\n\n",
        "(23, 'abc') \\n\n",
        "t[2:] # copy to the very end of the sequence \\n\n",
        "(4.56, (2,3), 'def') \\n\n",
        "A[::-1] = reverses \\n\n",
        "<object_name> [ <start_index>, <stop_index> , <step> ] \\n\n",
        "This means step is gonna slice every step_index from the given start index, till the stop index. \\n\n",
        "Stop Index is not included in slicing  \\n\n",
        "\n",
        "\n",
        "__DICTIONARIES__: \\n\n",
        "● Dictionaries are unordered & work by hashing, so keys must be immutable \\n\n",
        "● Constant average time add, lookup, update \\n\n",
        "d['pswd'] = 'thx1138' # Assigning to an existing key replaces its value. \\n\n",
        "d \\n {'user': 'R2D2', 'pswd': 'thx1138'} \\n\n",
        "d = {'user':'R2D2', 'p':1234, 'i':34} \\n\n",
        "d.keys() # List of current keys \\n\n",
        "dict_keys(['user', 'p', 'i’]) \\n\n",
        "d.values() # List of current values. \\n\n",
        "dict_values(['R2D2', 1234, 34]) \\n\n",
        "d.items() # List of item tuples. \\n\n",
        "dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)]) \\n\n",
        "Default dict and Counter \\n\n",
        "from collections import defaultdict \\n\n",
        "d = defaultdict(str) \\n\n",
        "D['a'] -> \" \" \\n\n",
        "from collections import Counter \\n\n",
        "d = Counter() \\n\n",
        "D['a'] -> 0 \\n \\n\n",
        "\n",
        "\n",
        "__FUNCTIONS__: \\n\n",
        "Multiple return types: returned as tuples \\n\n",
        "No function overloading \\n\n",
        "Operator overloading possible through special types \\n\n",
        "Non-default argument should always precede default arguments; otherwise, it reports SyntaxError \\n\n",
        "\n",
        "__Keyword arguments__: when function params are called out of order \\n\n",
        "But true (positional arguments) should always precede the keyword arguments \\n\n",
        ">>> myfun(c=43, b=1, a=2)  \\n\n",
        "*args: when you want to accept variable number of arguments in the function \\n\n",
        "**kwargs: variable number of keyword arguments \\n\n",
        "Functions are first class citizens in python as Pass functions as arguments to other functions, Return functions as the values from other functions, Assign functions to variables or store them in data structures \\n \\n\n",
        "\n",
        "__CLASSES__: \\n\n",
        "To define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition. No extends keyword. class AI_Student(Student): \\n Multiple inheritance is supported. \\n\n",
        "\n",
        "__Misc__: \\n\n",
        "if __name__ == '__main__': \\n\n",
        "\n",
        "Duck typing is a concept related to dynamic typing, where the type or the class of an object is less important than the methods it defines. When you use duck typing, you do not check types at all. Instead, you check for the presence of a given method or attribute. \\n \n",
        "\n",
        "__FOR Loops__: \\n\n",
        "newlist = [expression for item in iterable if condition == True] \\n\n",
        "Dictionary/Set Comprehension: \\n\n",
        "d = { k: v for k,v in lst1 } \\n\n",
        "s = { x for x in lst2 } \\n\n",
        "\n",
        "__Iterators__: \\n\n",
        "$__next__$ \\n\n",
        "Python iterators do not have a hasnext() method. Just catch the StopIteration exception. \\n\n",
        "Iterators use memory efficiently. \\n With range you pre-build your list, but xrange is an iterator and yields the next item when needed instead. \\n\n",
        "Generators (its an iterator) use yield. \\n\n",
        "Less code than writing a standard iterator, Maintains local state automatically \\n\n",
        "Values are computed one at a time, as they’re needed \\n\n",
        "Avoids storing the entire sequence in memory, Good for aggregating (summing, counting) items. \\n One pass, Crucial for infinite sequences, Bad if you need to inspect the individual values \\n\n",
        "\n",
        "A __set__ is an unordered collection of items. Every set element is unique (no duplicates) and must be immutable (cannot be changed). \\n\n",
        "\n",
        "However, a set itself is mutable. We can add or remove items from it. \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "23f7b65e-68d0-4bf1-c1a7-84249bf40637"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \n__Portable__: \n\nPrograms run on major platforms without change. \n\n__REPL__: Run Evaluate Print Loop : type python3 in your terminal\n\nAll data treated as objects. An object is deleted (by garbage collection) once unreachable \n\nStrong typing means that the type of a value doesn't change in unexpected ways. A string containing only digits doesn't magically become a number, as may happen in Perl. Every change of type requires an explicit conversion. \n\nDynamic typing, you don't need to specify the type of variable before defining. \n \n\n\n__STRINGS__: \n\nImmutable \n\n== checks whether variables point to objects of the same value \n\nis checks whether variables point to the same object \n\n\n__Operations on Strings__ \n\ns = \"Pretend this sentence makes sense.\" \n\nwords = s.split(\" \") \n\nwords \b\n['Pretend', 'this', 'sentence', 'makes', 'sense.'] \n\n\"_\".join(words) #join method of obj \"_\" \n\n'Pretend_this_sentence_makes_sense.' \n\ns = 'dog' \n\ns.capitalize() \n\n'Dog' \n\ns.upper() \n\n'DOG’ \n\n‘hi --'.strip(' –') \n\n'Hi’ \n\n\n\n__LISTS__: \n\nMutable ordered sequence of items of mixed types \n\nuse y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value \n\nA shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original. \n\nA deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original. \n\n\nOperations on Lists: \n\n>>> li.append('a') # Note the method syntax  \n\n>>> li.insert(2, 'i')  \n\n>>> li [1, 11, 'i', 3, 4, 5, 'a'] \n\n>>> li = ['a', 'b', 'c', 'b'] \n\n>>> li.index('b') # index of first occurrence 1  \n\n>>> li.count('b') # number of occurrences 2 \n\n>>> li.remove('b') # remove first occurrence \n\n>>> li.reverse() # reverse the list *in place* (modify) \n\n>>> li.sort() # sort the list *in place*  \n\n>>> li.sort(some_function) # sort in place using user-defined comparison  \n\n>>> sorted(li) #return a *copy* sorted \n\n\n__TUPLES__: \n\nA simple immutable ordered sequence of items \n\nImmutable: a tuple cannot be modified once created \n\nItems can be of mixed types, including collection types \n\n\n__SLICING__: \n\nt[1:4] #slicing ends before last index \n\nt[1:-1] #using negative index \n\n('abc', 4.56, (2,3)) \n\nt[1:-1:2] # selection of every nth item. \n\n('abc', (2,3)) \n\nt[:2] # copy from beginning of sequence \n\n(23, 'abc') \n\nt[2:] # copy to the very end of the sequence \n\n(4.56, (2,3), 'def') \n\nA[::-1] = reverses \n\n<object_name> [ <start_index>, <stop_index> , <step> ] \n\nThis means step is gonna slice every step_index from the given start index, till the stop index. \n\nStop Index is not included in slicing  \n\n\n\n__DICTIONARIES__: \n\n● Dictionaries are unordered & work by hashing, so keys must be immutable \n\n● Constant average time add, lookup, update \n\nd['pswd'] = 'thx1138' # Assigning to an existing key replaces its value. \n\nd \n {'user': 'R2D2', 'pswd': 'thx1138'} \n\nd = {'user':'R2D2', 'p':1234, 'i':34} \n\nd.keys() # List of current keys \n\ndict_keys(['user', 'p', 'i’]) \n\nd.values() # List of current values. \n\ndict_values(['R2D2', 1234, 34]) \n\nd.items() # List of item tuples. \n\ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)]) \n\nDefault dict and Counter \n\nfrom collections import defaultdict \n\nd = defaultdict(str) \n\nD['a'] -> \" \" \n\nfrom collections import Counter \n\nd = Counter() \n\nD['a'] -> 0 \n \n\n\n\n__FUNCTIONS__: \n\nMultiple return types: returned as tuples \n\nNo function overloading \n\nOperator overloading possible through special types \n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError \n\n\n__Keyword arguments__: when function params are called out of order \n\nBut true (positional arguments) should always precede the keyword arguments \n\n>>> myfun(c=43, b=1, a=2)  \n\n*args: when you want to accept variable number of arguments in the function \n\n**kwargs: variable number of keyword arguments \n\nFunctions are first class citizens in python as Pass functions as arguments to other functions, Return functions as the values from other functions, Assign functions to variables or store them in data structures \n \n\n\n__CLASSES__: \n\nTo define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition. No extends keyword. class AI_Student(Student): \n Multiple inheritance is supported. \n\n\n__Misc__: \n\nif __name__ == '__main__': \n\n\nDuck typing is a concept related to dynamic typing, where the type or the class of an object is less important than the methods it defines. When you use duck typing, you do not check types at all. Instead, you check for the presence of a given method or attribute. \n \n\n__FOR Loops__: \n\nnewlist = [expression for item in iterable if condition == True] \n\nDictionary/Set Comprehension: \n\nd = { k: v for k,v in lst1 } \n\ns = { x for x in lst2 } \n\n\n__Iterators__: \n\n$__next__$ \n\nPython iterators do not have a hasnext() method. Just catch the StopIteration exception. \n\nIterators use memory efficiently. \n With range you pre-build your list, but xrange is an iterator and yields the next item when needed instead. \n\nGenerators (its an iterator) use yield. \n\nLess code than writing a standard iterator, Maintains local state automatically \n\nValues are computed one at a time, as they’re needed \n\nAvoids storing the entire sequence in memory, Good for aggregating (summing, counting) items. \n One pass, Crucial for infinite sequences, Bad if you need to inspect the individual values \n\n\nA __set__ is an unordered collection of items. Every set element is unique (no duplicates) and must be immutable (cannot be changed). \n\n\nHowever, a set itself is mutable. We can add or remove items from it. \n\n\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Open Loop: when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state. \\n\n",
        "Closed Loop: If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts. \\n\n",
        "Search Problem Formulation: \\n\n",
        "State Space: A set of possible states that the environment can be in: \\n\n",
        "Initial State \\n\n",
        "Goal States \\n\n",
        "Actions \\n\n",
        "Transition Model \\n\n",
        "Action Cost Function \\n\n",
        "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. \\n\n",
        "The process of removing detail from a representation is called abstraction. \\n\n",
        "The abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. \\n\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. \\n\n",
        " A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data. \\n\n",
        " \n",
        "Absolute movements: movement direction acc to viewer \\n\n",
        "Egocentric: movement direction acc to the robot \\n\n",
        " \n",
        "Standardized problems: grid world, sokoban puzzle, sliding tile puzzle \\n\n",
        "Real world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence \\n\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" A search algorithm takes a search problem as input and returns a solution, or an indication of failure. \\n\n",
        "Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.  \\n\n",
        "The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. \\n\n",
        "Frontier of the search tree is the node we choose to expand first. \\n\n",
        "Note that the frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached. \\n\n",
        " \n",
        "We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.  \\n\n",
        "Graph search is more memory intensive than tree search as it keeps track of redundant paths. \\n\n",
        "Graph search is faster than tree search. \\n\n",
        "Best First Search:\n",
        "Evaluating the node n with the minimum evaluation function f(n). \\n\n",
        "On each iteration we choose a node on the frontier with minimum  value, return it if its state is a goal state, and otherwise apply Expand to generate child nodes. \\n \n",
        "Each child node is added to the frontier if it has not been reached before, or is re-added if it is now being reached with a path that has a lower path cost than any previous path. \\n\n",
        "It checks if the node is the goal state only after it gets popped out of the queue for expansion. \\n\n",
        "Graph Like Search (that is, it checks for redundant paths) \\n \\n\n",
        "To be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state. \\n\n",
        "For an implicit state space, complexity can be measured in terms of  d, the depth or number of actions in an optimal solution;  m, the maximum number of actions in any path; and b,  the branching factor or number of successors of a node that need to be considered. \\n\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" Breadth First Search: \\n\n",
        "When all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. This is a systematic search strategy that is therefore complete even on infinite state spaces. \\n\n",
        "FIFO Queue is used \\n\n",
        "That also means we can do an early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search uses, waiting until a node is popped off the queue. \\n\n",
        "Complete  \\n\n",
        "Optimal \\n\n",
        "but memory intensive as it is storing all the expanded nodes.  \\n\n",
        "Time and Space: O(b^d) \\n\n",
        " \n",
        "Uniform Cost Search or Djisktra’s: \\n\n",
        "Best First Search:  the algorithm tests for goals only when it expands a node, not when it generates a node, so it has not yet detected that this is a path to the goal. \\n\n",
        "Complete \\n\n",
        "Optimal \\n\n",
        " \n",
        "Depth First Search: \\n\n",
        "Depth-first search always expands the deepest node in the frontier first. It could be implemented as a call to Best-First-Search where the evaluation function f  is the negative of the depth. \\n\n",
        "However, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.  \\n\n",
        "Incomplete \\n\n",
        "Non optimal \\n\n",
        "Time: O(b^m) \\n\n",
        "Space: O(bm) \\n\n",
        "Backtracking depth first search: space O(m), only one successor at a time is expanded. \\n \n",
        " \n",
        "Depth Limited Search: \\n \n",
        "DFS with a limit of depth L \\n\n",
        "Incomplete \\n\n",
        "Non optimal \\n\n",
        "Time: O(b^l) \\n\n",
        "Space: O(bl) \\n\n",
        " \n",
        "Iterative Deepening Search: \\n\n",
        "Depth Limited Search while iterating over L\n",
        "Complete \\n\n",
        "Optimal \\n \n",
        "Time: O(b^d) \\n\n",
        "Space: O(bd) \\n\n",
        " \n",
        "Bidirectional Search: \\n\n",
        "An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s),hoping that the two searches will meet. \\n \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" ​​Use depth-first if \\n\n",
        "• Space is restricted \\n\n",
        "• There are many possible solutions with long paths and wrong paths are usually\n",
        "terminated quickly \\n\n",
        "• Search can be fine-tuned quickly \\n\n",
        "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",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b523fed5-3a63-4b51-f244-abe5724a7e16"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Open Loop: when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state. \n\nClosed Loop: If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts. \n\nSearch Problem Formulation: \n\nState Space: A set of possible states that the environment can be in: \n\nInitial State \n\nGoal States \n\nActions \n\nTransition Model \n\nAction Cost Function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state. \n\nThe process of removing detail from a representation is called abstraction. \n\nThe abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. \n\n \n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. \n\n A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data. \n\n \nAbsolute movements: movement direction acc to viewer \n\nEgocentric: movement direction acc to the robot \n\n \nStandardized problems: grid world, sokoban puzzle, sliding tile puzzle \n\nReal world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution, or an indication of failure. \n\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.  \n\nThe state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. \n\nFrontier of the search tree is the node we choose to expand first. \n\nNote that the frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached. \n\n \nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.  \n\nGraph search is more memory intensive than tree search as it keeps track of redundant paths. \n\nGraph search is faster than tree search. \n\nBest First Search:\nEvaluating the node n with the minimum evaluation function f(n). \n\nOn each iteration we choose a node on the frontier with minimum  value, return it if its state is a goal state, and otherwise apply Expand to generate child nodes. \n \nEach child node is added to the frontier if it has not been reached before, or is re-added if it is now being reached with a path that has a lower path cost than any previous path. \n\nIt checks if the node is the goal state only after it gets popped out of the queue for expansion. \n\nGraph Like Search (that is, it checks for redundant paths) \n \n\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state. \n\nFor an implicit state space, complexity can be measured in terms of  d, the depth or number of actions in an optimal solution;  m, the maximum number of actions in any path; and b,  the branching factor or number of successors of a node that need to be considered. \n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth First Search: \n\nWhen all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. This is a systematic search strategy that is therefore complete even on infinite state spaces. \n\nFIFO Queue is used \n\nThat also means we can do an early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search uses, waiting until a node is popped off the queue. \n\nComplete  \n\nOptimal \n\nbut memory intensive as it is storing all the expanded nodes.  \n\nTime and Space: O(b^d) \n\n \nUniform Cost Search or Djisktra’s: \n\nBest First Search:  the algorithm tests for goals only when it expands a node, not when it generates a node, so it has not yet detected that this is a path to the goal. \n\nComplete \n\nOptimal \n\n \nDepth First Search: \n\nDepth-first search always expands the deepest node in the frontier first. It could be implemented as a call to Best-First-Search where the evaluation function f  is the negative of the depth. \n\nHowever, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.  \n\nIncomplete \n\nNon optimal \n\nTime: O(b^m) \n\nSpace: O(bm) \n\nBacktracking depth first search: space O(m), only one successor at a time is expanded. \n \n \nDepth Limited Search: \n \nDFS with a limit of depth L \n\nIncomplete \n\nNon optimal \n\nTime: O(b^l) \n\nSpace: O(bl) \n\n \nIterative Deepening Search: \n\nDepth Limited Search while iterating over L\nComplete \n\nOptimal \n \nTime: O(b^d) \n\nSpace: O(bd) \n\n \nBidirectional Search: \n\nAn alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s),hoping that the two searches will meet. \n \n\n## Module 3 Lecture Notes\n ​​Use depth-first if \n\n• Space is restricted \n\n• There are many possible solutions with long paths and wrong paths are usually\nterminated quickly \n\n• Search can be fine-tuned quickly \n\nUse 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\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Heuristic: estimated cost of the cheapest path from state at node n to goal state. \\n\n",
        "Greedy best first search: picking the node with the lowest heuristic first, not optimal \\n\n",
        "A* search: \\n\n",
        "Best first search with evaluation: f(n) = g(n) + h(n) \\n\n",
        "g(n) is path cost, h(n) is estimated path cost (heuristic) \\n\n",
        "A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. \\n\n",
        "A slightly stronger property is called consistency. A heuristic h(n)  is consistent if, for every node n and every successor n’ of  generated by an action a we have: \\n\n",
        "h(n) < = c(n,a,n’) + h(n’) (triangle inequality) \\n\n",
        "Every consistent heuristic is admissible (not vice versa). \\n\n",
        "In addition, with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry. But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, and if each new path has a lower path cost than the previous one, then we will end up with multiple nodes for that state in the frontier, costing us both time and space. \\n\n",
        "Search Contours: A useful way to visualize a search is to draw contours in the state space, just like the contours in a topographic map. \\n\n",
        "The contours with uniform-cost search will be “circular” around the start state, spreading out equally in all directions with no preference towards the goal. \\n\n",
        "f(n) is monotonically increasing iff the heuristic is consistent. \\n\n",
        "Therefore you get concentric contour lines that don’t cross each other, and if you choose to draw the lines fine enough, you can put a line between any two nodes on any path. \\n\n",
        "A*star prunes : The concept of pruning—eliminating possibilities from consideration without having to examine them—is important for many areas of AI. \\n\n",
        "A* search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A* search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded. \\n\n",
        "Weighted A* star = W*h(n) \\n\n",
        "In bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee.\\n\n",
        "In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" A*star \\n\n",
        "Time: O(bd) \\n\n",
        "Space: O(b^d) \\n\n",
        "\n",
        "How to judge quality of heuristics: \\n\n",
        "Effective Branching Factor \\n\n",
        "Effective Depth: depth Kh, O(b^(d-Kh)) \\n\n",
        "Dominating heuristics: h2 dominates h1 if h2(n) >=h1(n) \\n\n",
        "Relaxed problem: lesser restrictions in the problem will make heuristic picking easier \\n\n",
        "The state-space graph of the relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph. \\n\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \\n\n",
        "Generating heuristics from cost of the sub problems \\n\n",
        "The idea behind pattern databases is to store these exact solution costs for every possible subproblem instance. \\n\n",
        "the sum of the two costs is still a lower bound on the cost of solving the entire problem. This is the idea behind disjoint pattern databases. \\n\n",
        " \n",
        "Precomputation of heuristics: \\n\n",
        "Differential heuristic:  \\n\n",
        "Hdh(n) = max |C*(n,L) - C* (goal, L) | \\n\n",
        "Learning to search better: \\n\n",
        "Metalevel state space and object level state space: Meta-learning, or learning to learn, is the science of systematically observing how different machine learning approaches perform on a wide range of learning tasks, and then learning from this experience, or meta-data, to learn new tasks much faster than otherwise possible. \\n\n",
        " \n",
        "Learning from Experience by adding features: h(n) = c1x1(n) + c2x2(n) \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform Cost Search: \\n\n",
        "Expand node with lowest path cost (djisktras) \\n\n",
        "Optimal and Complete \\n\n",
        "Subtle but significant difference from BFS: \\n\n",
        "Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier. \\n\n",
        "Updates a node on the frontier if a better path to the same state is found. \\n\n",
        "So always enqueue a node before checking whether it is a goal. \\n\n",
        " \n",
        "Greedy Best First Search : \\n\n",
        "Expands nodes with lowest heuristic. \\n\n",
        "Not Optimal \\n\n",
        "A* star: \\n \n",
        "Admissible heuristic for 8-puzzle: out of place heuristic and manhattan distance. \\n\n",
        "Relaxed Problem: \\n\n",
        "A problem with fewer restrictions on the actions than the original is called a relaxed\n",
        "Problem. \\n\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
        "original problem. \\n\n",
        "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",
        "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",
        "A* applications:  \\n\n",
        "Pathing / routing problems (A* is in your GPS!) \\n\n",
        "Video games \\n\n",
        "Robot motion planning \\n\n",
        "Resource planning problems \\n\n",
        " \n",
        "Memory Bounded Search:  \\n\n",
        "For making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state. \\n\n",
        "Beam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. \\n\n",
        "Iterative Deepening A* search: \\n\n",
        "Recursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path. \\n\n",
        "RBFS is optimal when h(n) is admissible. \\n\n",
        "MA* and SMA* : memory bounded and simplified memory bounded A* star \\n\n",
        "SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA* always drops the worst leaf node—the one with the highest f -value \\n.\n",
        "Bidirectional A star: \\n\n",
        "Front to end: Hf estimates distance to goal and Hb estimates distance to other frontier. \\n\n",
        "Front to front:  attempts to estimate the distance to the other frontier. \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 59,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2decc59f-ba65-4f15-dbca-916d2e9fca0b"
      },
      "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": 60,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Heuristic: estimated cost of the cheapest path from state at node n to goal state. \n\nGreedy best first search: picking the node with the lowest heuristic first, not optimal \n\nA* search: \n\nBest first search with evaluation: f(n) = g(n) + h(n) \n\ng(n) is path cost, h(n) is estimated path cost (heuristic) \n\nA key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. \n\nA slightly stronger property is called consistency. A heuristic h(n)  is consistent if, for every node n and every successor n’ of  generated by an action a we have: \n\nh(n) < = c(n,a,n’) + h(n’) (triangle inequality) \n\nEvery consistent heuristic is admissible (not vice versa). \n\nIn addition, with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry. But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, and if each new path has a lower path cost than the previous one, then we will end up with multiple nodes for that state in the frontier, costing us both time and space. \n\nSearch Contours: A useful way to visualize a search is to draw contours in the state space, just like the contours in a topographic map. \n\nThe contours with uniform-cost search will be “circular” around the start state, spreading out equally in all directions with no preference towards the goal. \n\nf(n) is monotonically increasing iff the heuristic is consistent. \n\nTherefore you get concentric contour lines that don’t cross each other, and if you choose to draw the lines fine enough, you can put a line between any two nodes on any path. \n\nA*star prunes : The concept of pruning—eliminating possibilities from consideration without having to examine them—is important for many areas of AI. \n\nA* search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A* search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded. \n\nWeighted A* star = W*h(n) \n\nIn bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee.\n\nIn bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly. \n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n A*star \n\nTime: O(bd) \n\nSpace: O(b^d) \n\n\nHow to judge quality of heuristics: \n\nEffective Branching Factor \n\nEffective Depth: depth Kh, O(b^(d-Kh)) \n\nDominating heuristics: h2 dominates h1 if h2(n) >=h1(n) \n\nRelaxed problem: lesser restrictions in the problem will make heuristic picking easier \n\nThe state-space graph of the relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph. \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \n\nGenerating heuristics from cost of the sub problems \n\nThe idea behind pattern databases is to store these exact solution costs for every possible subproblem instance. \n\nthe sum of the two costs is still a lower bound on the cost of solving the entire problem. This is the idea behind disjoint pattern databases. \n\n \nPrecomputation of heuristics: \n\nDifferential heuristic:  \n\nHdh(n) = max |C*(n,L) - C* (goal, L) | \n\nLearning to search better: \n\nMetalevel state space and object level state space: Meta-learning, or learning to learn, is the science of systematically observing how different machine learning approaches perform on a wide range of learning tasks, and then learning from this experience, or meta-data, to learn new tasks much faster than otherwise possible. \n\n \nLearning from Experience by adding features: h(n) = c1x1(n) + c2x2(n) \n\n \n\n## Module 4 Lecture Notes\n Uniform Cost Search: \n\nExpand node with lowest path cost (djisktras) \n\nOptimal and Complete \n\nSubtle but significant difference from BFS: \n\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier. \n\nUpdates a node on the frontier if a better path to the same state is found. \n\nSo always enqueue a node before checking whether it is a goal. \n\n \nGreedy Best First Search : \n\nExpands nodes with lowest heuristic. \n\nNot Optimal \n\nA* star: \n \nAdmissible heuristic for 8-puzzle: out of place heuristic and manhattan distance. \n\nRelaxed Problem: \n\nA problem with fewer restrictions on the actions than the original is called a relaxed\nProblem. \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem. \n\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then Hoop(n)\ngives the shortest solution. \n\nIf the rules are relaxed so that a tile can move to any adjacent square, then Hmd(n)\ngives the shortest solution. \n\nA* applications:  \n\nPathing / routing problems (A* is in your GPS!) \n\nVideo games \n\nRobot motion planning \n\nResource planning problems \n\n \nMemory Bounded Search:  \n\nFor making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state. \n\nBeam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. \n\nIterative Deepening A* search: \n\nRecursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path. \n\nRBFS is optimal when h(n) is admissible. \n\nMA* and SMA* : memory bounded and simplified memory bounded A* star \n\nSMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA* always drops the worst leaf node—the one with the highest f -value \n.\nBidirectional A star: \n\nFront to end: Hf estimates distance to goal and Hb estimates distance to other frontier. \n\nFront to front:  attempts to estimate the distance to the other frontier. \n\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 = \"\"\" We show that pruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.  \\n\n",
        "__Two player zero sum game__: The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\\n\n",
        "__“Perfect information”__ is a synonym for __“fully observable__”1 and “zero-sum” means one player’s loss is another’s gain: there is no “win-win” outcome. For games we often use the term move as a synonym for “action” and position as a synonym for “state.” \\n\n",
        "__Game__: initial state, to move, action state, result, is terminal, utility. \\n\n",
        "__A utility function__ (also called an objective function or payoff function), which defines the final numeric value to player  p when the game ends in terminal state s. \\n\n",
        "__MAX and MIN__ are two players. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "For games with multiple outcome scores, we need a slightly more general algorithm called minimax search. the word “move” means that both players have taken an action; therefore the word ply is used to unambiguously mean one move by one player, bringing us one level deeper in the game tree.) \\n\n",
        "__Minimax__: time complexity O(b^m) and space: O(bm) like DFS. \\n\n",
        " \n",
        " \n",
        "Minimax for multiplayer: form alliances (two or more players team up). \\n\n",
        "__AlphaBeta Pruning:__ \\n\n",
        "Alpha (at least) is MAX’s lower bound on MAX’s outcome. \\n \n",
        "Beta (at most) is MIN’s upper bound on MIN’s outcome. \\n\n",
        "You prune max when v > = beta and prune min  when v < = alpha \\n\n",
        "Alpha and beta are updated only while going down in the right subtree \\n\n",
        "V only checks the children Vs and not alpha and beta \\n\n",
        " \n",
        "__Time complexity__ depends on the ordering of nodes.\n",
        "If this could be done perfectly, alpha-beta would need to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\\n\n",
        "That means effective branches became b^0.5 instead of b \\n\n",
        "With random ordering O(b^3m/4). \\n\n",
        "Therefore, stop evaluating a branch whenever: When evaluating a MAX node: a value v>=beta is backed-up • MIN will never select that MAX node \\n\n",
        "When evaluating a MIN node: a value v ≤ alpha is found • MAX will never select that MIN node \\n\n",
        "Value might not get updated when a tree is pruned. \\n\n",
        " \n",
        "__Expectimax__: \\n\n",
        "Algo: \\n\n",
        "Why wouldn’t we know what the result of an action will be? Explicit randomness: rolling dice \\n\n",
        "Unpredictable opponents: the opponent isn’t optimal \\n\n",
        "Actions can fail: when moving a robot, wheels might slip \\n\n",
        " Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes \\n\n",
        "Expectimax search: compute the average score under optimal playMax nodes as in minimax search Chance nodes are like min nodes but the outcome is uncertain \\n\n",
        "Calculate their expected utilities I.e. take weighted average (expectation) of children \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal.\\n\n",
        "In other words, __we replace the Utility function with Eval,__ which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. \\n\n",
        "A __heuristic evaluation function Eval(s,p)__ returns an estimate of the expected utility of state s to player p. \\n \n",
        "__For terminal states__, Eval(s,p) = Utility(s,p) \\n\n",
        "And for non terminal states: Utility(loss,p) <= Eval(s,p) <= Utility(win,p) \\n\n",
        "__Expected Value__ : averaging \\n\n",
        "__Material Value__ : assigning a value to the pawns in chess (for example) \\n\n",
        "__Weighted Function__: weighted linear function \\n\n",
        "__Cutting Off Search__: modifying alpha beta to cut off at non terminal states. \\n\n",
        "These simple approaches can lead to errors due to the approximate nature of the evaluation function. \\n\n",
        "The evaluation function should be applied only to positions that are __quiescent__—that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation. \\n\n",
        "__The horizon effect__ is more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics. \\n\n",
        "One strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point. \\n\n",
        "__Forward Pruning__: Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error. \\n\n",
        "This can be done using: \\n\n",
        "__Beam search__: consider only a “beam” of the n best moves \\n\n",
        "__ProbCut__: uses statistics gained from prior experience to lessen the chance that the best move will be pruned. \\n\n",
        "Another technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves. \\n\n",
        "__Search vs lookup__ \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" chance nodes \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Agent preferences are captured by utility function which assigns a single number to express the desirability of a state. \\n\n",
        "Decision theory, in its simplest form, deals with choosing among actions based on the desirability of their immediate outcomes; that is, the environment is assumed to be episodic.  \\n\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \\n\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" Constraints on Rational Preferences: \\n\n",
        "Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. \\n\n",
        "Transitivity, \\n\n",
        "Continuity, \\n\n",
        "Substitutability, \\n\n",
        "Monotonicity, \\n\n",
        "Decomposability. \\n\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \\n\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Utility Assessments and Utility Scales: \\n\n",
        "If we want to build a decision-theoretic system that helps a human make decisions or acts on his or her behalf, we must first work out what the human’s utility function is. This process, often called preference elicitation, involves presenting choices to the human and using the observed preferences to pin down the underlying utility function. \\n\n",
        "Normalized Utilities use a scale of 0 or 1 \\n\n",
        " \n",
        "The utility of money: \\n\n",
        "We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\\n\n",
        " \n",
        "Expected utility and post-decision disappointment: \\n\n",
        "Unbiased estimator \\n\n",
        "Human judgment and irrationality: \\n\n",
        "Decision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. \\n\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening . \\n\n",
        "The best moves are known as killer moves, and to try them first is called the killer move heuristic. \\n\n",
        "In game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states. \\n\n",
        "Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 100,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5f5567d2-cd6f-4a01-ee93-877b9bb4fa04"
      },
      "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": 101,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n We show that pruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.  \n\n__Two player zero sum game__: The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n\n__“Perfect information”__ is a synonym for __“fully observable__”1 and “zero-sum” means one player’s loss is another’s gain: there is no “win-win” outcome. For games we often use the term move as a synonym for “action” and position as a synonym for “state.” \n\n__Game__: initial state, to move, action state, result, is terminal, utility. \n\n__A utility function__ (also called an objective function or payoff function), which defines the final numeric value to player  p when the game ends in terminal state s. \n\n__MAX and MIN__ are two players. \n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nFor games with multiple outcome scores, we need a slightly more general algorithm called minimax search. the word “move” means that both players have taken an action; therefore the word ply is used to unambiguously mean one move by one player, bringing us one level deeper in the game tree.) \n\n__Minimax__: time complexity O(b^m) and space: O(bm) like DFS. \n\n \n \nMinimax for multiplayer: form alliances (two or more players team up). \n\n__AlphaBeta Pruning:__ \n\nAlpha (at least) is MAX’s lower bound on MAX’s outcome. \n \nBeta (at most) is MIN’s upper bound on MIN’s outcome. \n\nYou prune max when v > = beta and prune min  when v < = alpha \n\nAlpha and beta are updated only while going down in the right subtree \n\nV only checks the children Vs and not alpha and beta \n\n \n__Time complexity__ depends on the ordering of nodes.\nIf this could be done perfectly, alpha-beta would need to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\n\nThat means effective branches became b^0.5 instead of b \n\nWith random ordering O(b^3m/4). \n\nTherefore, stop evaluating a branch whenever: When evaluating a MAX node: a value v>=beta is backed-up • MIN will never select that MAX node \n\nWhen evaluating a MIN node: a value v ≤ alpha is found • MAX will never select that MIN node \n\nValue might not get updated when a tree is pruned. \n\n \n__Expectimax__: \n\nAlgo: \n\nWhy wouldn’t we know what the result of an action will be? Explicit randomness: rolling dice \n\nUnpredictable opponents: the opponent isn’t optimal \n\nActions can fail: when moving a robot, wheels might slip \n\n Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes \n\nExpectimax search: compute the average score under optimal playMax nodes as in minimax search Chance nodes are like min nodes but the outcome is uncertain \n\nCalculate their expected utilities I.e. take weighted average (expectation) of children \n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal.\n\nIn other words, __we replace the Utility function with Eval,__ which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. \n\nA __heuristic evaluation function Eval(s,p)__ returns an estimate of the expected utility of state s to player p. \n \n__For terminal states__, Eval(s,p) = Utility(s,p) \n\nAnd for non terminal states: Utility(loss,p) <= Eval(s,p) <= Utility(win,p) \n\n__Expected Value__ : averaging \n\n__Material Value__ : assigning a value to the pawns in chess (for example) \n\n__Weighted Function__: weighted linear function \n\n__Cutting Off Search__: modifying alpha beta to cut off at non terminal states. \n\nThese simple approaches can lead to errors due to the approximate nature of the evaluation function. \n\nThe evaluation function should be applied only to positions that are __quiescent__—that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation. \n\n__The horizon effect__ is more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics. \n\nOne strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point. \n\n__Forward Pruning__: Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error. \n\nThis can be done using: \n\n__Beam search__: consider only a “beam” of the n best moves \n\n__ProbCut__: uses statistics gained from prior experience to lessen the chance that the best move will be pruned. \n\nAnother technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves. \n\n__Search vs lookup__ \n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n chance nodes \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent preferences are captured by utility function which assigns a single number to express the desirability of a state. \n\nDecision theory, in its simplest form, deals with choosing among actions based on the desirability of their immediate outcomes; that is, the environment is assumed to be episodic.  \n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints on Rational Preferences: \n\nOrderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. \n\nTransitivity, \n\nContinuity, \n\nSubstitutability, \n\nMonotonicity, \n\nDecomposability. \n\nAs in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility Assessments and Utility Scales: \n\nIf we want to build a decision-theoretic system that helps a human make decisions or acts on his or her behalf, we must first work out what the human’s utility function is. This process, often called preference elicitation, involves presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n\nNormalized Utilities use a scale of 0 or 1 \n\n \nThe utility of money: \n\nWe say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n\n \nExpected utility and post-decision disappointment: \n\nUnbiased estimator \n\nHuman judgment and irrationality: \n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. \n\n \n\n## Module 5 Lecture Notes\n Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening . \n\nThe best moves are known as killer moves, and to try them first is called the killer move heuristic. \n\nIn game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states. \n\nType A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \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",
        "A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a __constraint satisfaction problem,__ or CSP.  \\n\n",
        "CSP comprises of 3 components:  \\n\n",
        "X: set of __variables__ \\n\n",
        "D: set of __domains__ \\n\n",
        "C: set of __constraints__ that specify allowable combinations of value \\n\n",
        "Each constraint has a __pair <scope, rel>__ \\n\n",
        "__Scope__: tuple of variables that participate in the constraint \\n\n",
        "__Rel:__ tuple of the values the variable can take \\n\n",
        "__Complete assignment__: all variables are assigned \\n\n",
        "__Partial assignment__: some variables left unassigned \\n\n",
        "__Map coloring__: different color for adjacent node \\n\n",
        "__Job scheduling__: preceding constraints\\n\n",
        "__Disjunctive constraints__: that don’t overlap(algebraic plus disjunctive)\\n\n",
        "__Special solution algorithms__ exist for linear constraints on integer variables—that is, constraints, such as the one just given, in which each variable appears only in linear form. It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables—the problem is undecidable. \\n\n",
        "__Unary constraints, binary constraints__ \\n\n",
        "__Global constraints__: Aldiff \\n\n",
        "__Constraint Hyper Graph__: A hypergraph consists of ordinary nodes and hypernodes, which represent n-ary constraints— n constraints involving  variables. \\n\n",
        "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 one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variable \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "__Constraint propagation__: setting off a chain reaction to decrease the domain of variables using the constraints. \\n\n",
        "__Local Consistency__: The key idea is local consistency. If we treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph. \\n\n",
        "__Node Consistency__: unary constraints \\n\n",
        "__Arc Consistency__: binary constraints, can be used to reduce domains \\n\n",
        "__AC3__, O(cd^3), c is the number of binary constraints, d is the number of arcs which is O(n^2d^3) \\n\n",
        "For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ) \\n\n",
        "Initially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) \\n\n",
        "AC-3 then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi  arc-consistent with respect to Xj. \\n\n",
        "If this is unchanged,move on to the next arc. \\n\n",
        "But if this revises Di(makes the domain smaller), then we add to the queue all arcs (Xk,Xi)  where Xk is a neighbor of Xi .  \\n\n",
        "If Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return to failure. \\n \\n\n",
        " \n",
        "__Path consistency__ tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. \\n\n",
        "__K consistent__: Stronger forms of propagation can be defined with the notion of k -consistency. A CSP is k -consistent if, for any set of (k-1) variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. \\n\n",
        "__Strongly k consistent: if k consistent, k-1 consistent …. 1 consistent__ \\n\n",
        "__Time complexity for strongly k consistent: O(n^2 d)__ \\n\n",
        "__Global Constraint__: Remember that a global constraint is one involving an arbitrary number of variables (but not necessarily all variables). Hence,  a simple algo: keep deleting the variables with singleton values \\n\n",
        "__Resource Constraint__: at most constraint \\n\n",
        "For large resource-limited problems with integer values—such as logistical problems involving moving thousands of people in hundreds of vehicles—it is usually not possible to represent the domain of each variable as a large set of integers and gradually reduce that set by consistency-checking methods. \\n\n",
        "__Bound Constraint__: Instead, domains are represented by upper and lower bounds and are managed by bounds propagation. \\n\n",
        "We say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y \\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" When after running CSP, domains are not unary. Need to __backtrack__ to check the solution. \\n\n",
        "__Commutativity__: if order of assignment of solution does not matter. \\n\n",
        "Using commutativity in backtracking: \\n\n",
        "State would be a partial assignment, and an action would extend the assignment \\n\n",
        "n! d^n complexity reduced to d^n   \\n\n",
        "__Static ordering backtracking__: choosing variables in order \\n\n",
        "__Random ordering backtracking__: choosing variables in random order \\n\n",
        "__Most constraining backtracking__: \\n\n",
        "This intuitive idea—choosing the variable with the fewest “legal” values—is called the __minimum-remaining-values__ (MRV) heuristic. It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \\n\n",
        "__To pick the first value in MRV__:  In this case, the __degree heuristic__ comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. \\n\n",
        "Now after picking the most constraining variable, the values subsequent ones should be the least constraining values. (in order to find a solution). \\n\n",
        "Variable - fail first, Value - fail last \\n\n",
        "There are two ways to go about it: __search and inference__\\n\n",
        "__Forward Checking (a type of inference):__ Whenever a variable X  is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable X  that is connected to Y  by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for. (just checking the neighbors) \\n\n",
        "__Maintaining arc consistency (MAC)__ : ensure all arcs are consistent after each assignment through a recursive procedure. MAC coupled with AC3 gives better results than MAC \\n\n",
        "__Intelligent backtracking:__ backtrack the most recent variable which made the assignment inconsistent. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" The most obvious approach is to select the value that results in the minimum number of conflicts with other variables—__the min-conflicts heuristic__. Especially for N queens. Move the queens to minimum conflict position. \\n\n",
        "The landscape of a CSP under the min-conflicts heuristic usually has a __series of plateaus__. \\n\n",
        "__Plateau search__—  allowing sideways moves to another state with the same score—can help local search find its way off this plateau. \\n\n",
        "This wandering on the plateau can be directed with a technique called __tabu search__: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus. \\n\n",
        "Another technique called __constraint weighting__ aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights. \\n\n",
        "Another advantage of __local search__ is that it can be used in online settings when the problem changes. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "__Independent sub problems__: Independence can be ascertained simply by finding connected components of the constraint graph. Each problem then can be a CSP. \\n\n",
        "This way, an exponential problem O(d^n) where (d is the size of domain and n: no of variables) is reduced to N/C problems, time complexity decreased to linear O(nd^c/c) \\n\n",
        "Directional arc consistent -> Topological graph \\n\n",
        "__Cutset Conditioning__: The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables from a tree. \\n\n",
        "Runtime complexity: O(d^c * (n-c)*d^2) \\n\n",
        "More time,less than Tree Decomposition\\n\n",
        "Cutset Conditioning is only efficient when a small cutset can be found. \\n\n",
        "__Tree Decomposition:__ \\n\n",
        "They are efficient only wehn tree width is small. \\n\n",
        "In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem. \\n\n",
        "Time Complexity: O(nd^2), n:no of trees, d:size of domain \\n\n",
        "Algo: \\n\n",
        "Every variable in the original problem appears in at least one of the tree nodes. \\n\n",
        "If two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \\n\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \\n\n",
        "The tree width of a tree decomposition of a graph is one less than the size of the largest node; the tree width of the graph itself is defined to be the minimum width among all its tree decompositions. \\n\n",
        "Time complexity: O(nd^w+1) \\n\n",
        "__Value Breaking Symmetry:__\n",
        "We would like to reduce the search space by a factor of d!  by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" __CSP__: general purpose algo, just specify the constraints. \\n\n",
        "__Benefits of CSP__: clean specification of algo, knows where to focus search (as in, which variables are violating the constraints), Automatically prune off all branches that violate constraints. \\n\n",
        "__Varieties of CSP__: n variables, domain size of d -> O(d^n) assignments. \\n\n",
        "__CSP as a search problem__ :  Solution is always found at depth n, for n variables. \\n\n",
        "• n variables of domain size d.\n",
        "• Branching factor at the root is n*d.\n",
        "• Branching factor at next level is (n-1)*d.\n",
        "• Tree has n!*d^n leaves. \\n\n",
        "But CSPs are commutative: so d^n leaves only. \\n\n",
        "__Depth-first search__ for CSPs with single-variable assignments is called __backtracking search__. \\n\n",
        "__Search__: Assigning values to variable. \\n\n",
        "__Inference__: Eliminates possible values for a variable if the value would violate local consistency. \\n\n",
        "__The Waltz Algorithm__: Each intersection is a variable, adjacent intersections impose\n",
        "constraints on each other, Solutions are physically realizable 3D interpretations. \\n\n",
        "__The Backtracking-Search algorithm__ has a very simple policy for what to do when a branch of the search fails: back up to the preceding variable and try a different value for it. This is called chronological backtracking because the most recent decision point is revisited. In this subsection, we consider better possibilities. (sort of like depth first search)\\n\n",
        "__Intelligent backtracking:__ Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set. \\n\n",
        "__Backjumping__ is the same as forward checking. \\n\n",
        "When we reach a contradiction, __backjumping__ can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem. \\n\n",
        "__Conflict directed backjumping__ \\n\n",
        "__Constraint Learning__:  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments). \\n\n",
        "No goods can be computed by forward checking or back jumping. \\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "512d64e6-a0e6-437e-8e00-25d9420614b6"
      },
      "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": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nA problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a __constraint satisfaction problem,__ or CSP.  \n\nCSP comprises of 3 components:  \n\nX: set of __variables__ \n\nD: set of __domains__ \n\nC: set of __constraints__ that specify allowable combinations of value \n\nEach constraint has a __pair <scope, rel>__ \n\n__Scope__: tuple of variables that participate in the constraint \n\n__Rel:__ tuple of the values the variable can take \n\n__Complete assignment__: all variables are assigned \n\n__Partial assignment__: some variables left unassigned \n\n__Map coloring__: different color for adjacent node \n\n__Job scheduling__: preceding constraints\n\n__Disjunctive constraints__: that don’t overlap(algebraic plus disjunctive)\n\n__Special solution algorithms__ exist for linear constraints on integer variables—that is, constraints, such as the one just given, in which each variable appears only in linear form. It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables—the problem is undecidable. \n\n__Unary constraints, binary constraints__ \n\n__Global constraints__: Aldiff \n\n__Constraint Hyper Graph__: A hypergraph consists of ordinary nodes and hypernodes, which represent n-ary constraints— n constraints involving  variables. \n\nAnother 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 one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variable \n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n__Constraint propagation__: setting off a chain reaction to decrease the domain of variables using the constraints. \n\n__Local Consistency__: The key idea is local consistency. If we treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph. \n\n__Node Consistency__: unary constraints \n\n__Arc Consistency__: binary constraints, can be used to reduce domains \n\n__AC3__, O(cd^3), c is the number of binary constraints, d is the number of arcs which is O(n^2d^3) \n\nFor planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ) \n\nInitially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) \n\nAC-3 then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi  arc-consistent with respect to Xj. \n\nIf this is unchanged,move on to the next arc. \n\nBut if this revises Di(makes the domain smaller), then we add to the queue all arcs (Xk,Xi)  where Xk is a neighbor of Xi .  \n\nIf Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return to failure. \n \n\n \n__Path consistency__ tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. \n\n__K consistent__: Stronger forms of propagation can be defined with the notion of k -consistency. A CSP is k -consistent if, for any set of (k-1) variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. \n\n__Strongly k consistent: if k consistent, k-1 consistent …. 1 consistent__ \n\n__Time complexity for strongly k consistent: O(n^2 d)__ \n\n__Global Constraint__: Remember that a global constraint is one involving an arbitrary number of variables (but not necessarily all variables). Hence,  a simple algo: keep deleting the variables with singleton values \n\n__Resource Constraint__: at most constraint \n\nFor large resource-limited problems with integer values—such as logistical problems involving moving thousands of people in hundreds of vehicles—it is usually not possible to represent the domain of each variable as a large set of integers and gradually reduce that set by consistency-checking methods. \n\n__Bound Constraint__: Instead, domains are represented by upper and lower bounds and are managed by bounds propagation. \n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n When after running CSP, domains are not unary. Need to __backtrack__ to check the solution. \n\n__Commutativity__: if order of assignment of solution does not matter. \n\nUsing commutativity in backtracking: \n\nState would be a partial assignment, and an action would extend the assignment \n\nn! d^n complexity reduced to d^n   \n\n__Static ordering backtracking__: choosing variables in order \n\n__Random ordering backtracking__: choosing variables in random order \n\n__Most constraining backtracking__: \n\nThis intuitive idea—choosing the variable with the fewest “legal” values—is called the __minimum-remaining-values__ (MRV) heuristic. It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \n\n__To pick the first value in MRV__:  In this case, the __degree heuristic__ comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. \n\nNow after picking the most constraining variable, the values subsequent ones should be the least constraining values. (in order to find a solution). \n\nVariable - fail first, Value - fail last \n\nThere are two ways to go about it: __search and inference__\n\n__Forward Checking (a type of inference):__ Whenever a variable X  is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable X  that is connected to Y  by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for. (just checking the neighbors) \n\n__Maintaining arc consistency (MAC)__ : ensure all arcs are consistent after each assignment through a recursive procedure. MAC coupled with AC3 gives better results than MAC \n\n__Intelligent backtracking:__ backtrack the most recent variable which made the assignment inconsistent. \n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n The most obvious approach is to select the value that results in the minimum number of conflicts with other variables—__the min-conflicts heuristic__. Especially for N queens. Move the queens to minimum conflict position. \n\nThe landscape of a CSP under the min-conflicts heuristic usually has a __series of plateaus__. \n\n__Plateau search__—  allowing sideways moves to another state with the same score—can help local search find its way off this plateau. \n\nThis wandering on the plateau can be directed with a technique called __tabu search__: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus. \n\nAnother technique called __constraint weighting__ aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights. \n\nAnother advantage of __local search__ is that it can be used in online settings when the problem changes. \n\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\n__Independent sub problems__: Independence can be ascertained simply by finding connected components of the constraint graph. Each problem then can be a CSP. \n\nThis way, an exponential problem O(d^n) where (d is the size of domain and n: no of variables) is reduced to N/C problems, time complexity decreased to linear O(nd^c/c) \n\nDirectional arc consistent -> Topological graph \n\n__Cutset Conditioning__: The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables from a tree. \n\nRuntime complexity: O(d^c * (n-c)*d^2) \n\nMore time,less than Tree Decomposition\n\nCutset Conditioning is only efficient when a small cutset can be found. \n\n__Tree Decomposition:__ \n\nThey are efficient only wehn tree width is small. \n\nIn constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem. \n\nTime Complexity: O(nd^2), n:no of trees, d:size of domain \n\nAlgo: \n\nEvery variable in the original problem appears in at least one of the tree nodes. \n\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n\nThe tree width of a tree decomposition of a graph is one less than the size of the largest node; the tree width of the graph itself is defined to be the minimum width among all its tree decompositions. \n\nTime complexity: O(nd^w+1) \n\n__Value Breaking Symmetry:__\nWe would like to reduce the search space by a factor of d!  by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. \n\n\n\n\n## Module 6 Lecture Notes\n __CSP__: general purpose algo, just specify the constraints. \n\n__Benefits of CSP__: clean specification of algo, knows where to focus search (as in, which variables are violating the constraints), Automatically prune off all branches that violate constraints. \n\n__Varieties of CSP__: n variables, domain size of d -> O(d^n) assignments. \n\n__CSP as a search problem__ :  Solution is always found at depth n, for n variables. \n\n• n variables of domain size d.\n• Branching factor at the root is n*d.\n• Branching factor at next level is (n-1)*d.\n• Tree has n!*d^n leaves. \n\nBut CSPs are commutative: so d^n leaves only. \n\n__Depth-first search__ for CSPs with single-variable assignments is called __backtracking search__. \n\n__Search__: Assigning values to variable. \n\n__Inference__: Eliminates possible values for a variable if the value would violate local consistency. \n\n__The Waltz Algorithm__: Each intersection is a variable, adjacent intersections impose\nconstraints on each other, Solutions are physically realizable 3D interpretations. \n\n__The Backtracking-Search algorithm__ has a very simple policy for what to do when a branch of the search fails: back up to the preceding variable and try a different value for it. This is called chronological backtracking because the most recent decision point is revisited. In this subsection, we consider better possibilities. (sort of like depth first search)\n\n__Intelligent backtracking:__ Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set. \n\n__Backjumping__ is the same as forward checking. \n\nWhen we reach a contradiction, __backjumping__ can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem. \n\n__Conflict directed backjumping__ \n\n__Constraint Learning__:  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments). \n\nNo goods can be computed by forward checking or back jumping. \n\n \n\n## Module 6 Definitions\n* **Concept** - definition\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 = \"\"\" The central component of a knowledge-based agent is its knowledge base, or KB. \\n\n",
        "__A knowledge base__ is a set of sentences. (Here “sentence” is used as a technical term. It is related but not identical to the sentences of English and other natural languages.)\\n\n",
        "Each sentence is expressed in a language called a __knowledge representation language__ and represents some assertion about the world. \n",
        "When the sentence is taken as being given without being derived from other sentences, we call it an __axiom__.\\n\n",
        "Both operations may involve inference—that is, __deriving new sentences from old__. \\n\n",
        " \n",
        "Each time the __agent program__ is called, it does three things:\n",
        "__First__, it Tells the knowledge base what it perceives. \\n\n",
        "__Second__, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\\n\n",
        "__Third__, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\\n\n",
        "Because of the definitions of Tell and Ask, however, the knowledge-based agent is not an arbitrary program for calculating actions. It is amenable to a description at the knowledge level, where we need to specify only what the agent knows and what its goals are, in order to determine its behavior. \\n \n",
        "It is independent of __implementation level knowledge__. \\n\n",
        "Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building.\\n\n",
        "In contrast, the procedural approach encodes desired behaviors directly as program code. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" For an agent in the environment, the main challenge is its initial ignorance of the configuration of the environment; overcoming this ignorance seems to require logical reasoning. In most instances of the wumpus world, it is possible for the agent to retrieve the gold safely. Occasionally, the agent must choose between going home empty-handed and risking death to find the gold. \\n\n",
        "Note that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \\n\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" These sentences are expressed according to the __syntax__ of the representation language, which specifies all the sentences that are well formed. \\n\n",
        "A logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \\n\n",
        "A logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \\n\n",
        "__Entailment__: A|=B if M(A) subset of M(B) \\n\n",
        "An inference algorithm that derives only entailed sentences is called __sound or truth-preserving__. \\n\n",
        "__Definition of entailment__ can be used to derive logical inferences. This is known as __model checking__. \\n\n",
        "__Soundness is a highly desirable property__. An unsound inference procedure essentially makes things up as it goes along—it announces the discovery of nonexistent needles. \\n\n",
        " \n",
        "The property of __completeness__ is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. For real haystacks, which are finite in extent, it seems obvious that a systematic examination can always decide whether the needle is in the haystack. \\n\n",
        " \n",
        "The final issue to consider is __grounding__—the connection between logical reasoning processes and the real environment in which the agent exists. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. \\n\n",
        "__Complex sentences__ are constructed from simpler sentences, using parentheses and operators called logical connectives.\\n\n",
        "__Conjunction__ - intersection - and\n",
        "__Disjunction__ - union - or\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "A sentence is __valid__ if it is true in all models. \\n\n",
        "The final concept we will need is satisfiability. A sentence is __satisfiable__ if it is true in, or satisfied by, some model. \\n\n",
        "__Modus Ponens__: a->b, a = b \\n\n",
        "And__ Elimination__: a^b = a \\n\n",
        "Thus, searching for proofs is an alternative to enumerating models. In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are. \\n\n",
        "One final property of logical systems is __monotonicity__, which says that the set of entailed sentences can only increase as information is added to the knowledge base. \\n\n",
        "\n",
        "The current section introduces a single inference rule, resolution, that yields a complete inference algorithm when coupled with any complete search algorithm. \\n\n",
        "\n",
        "__Resolution__ basically makes a complete set of inferences from the given inferences. \\n\n",
        "\n",
        "__Unit Resolution__: These last two inference steps are examples of the unit resolution inference rule. \\n\n",
        "\n",
        "Thus, the unit resolution rule takes a clause—a disjunction of literals—and a literal and produces a new clause. Note that a single literal can be viewed as a disjunction of one literal, also known as a unit clause. \\n\n",
        "\n",
        "There is one more technical aspect of the resolution rule: the resulting clause should contain only one copy of each literal. The removal of multiple copies of literals is called factoring. \\n\n",
        "\n",
        "__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 a⇔ β with (a ⟹ β) ⋀ (β ⟹a) \\n\n",
        "2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination) \\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",
        "The sentence is now in CNF! \\n\n",
        "\n",
        "We barely need a complete set of inferences. Some KBs are formulated\n",
        "in a more restrictive form which enables them to use more efficient inference\n",
        "algorithms.  \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" __Horn Clauses__: \\n\n",
        "disjunction(union) of literals where at most one is positive. \\n\n",
        "\n",
        "__Definite clauses__: \\n\n",
        "disjunction(union) of literals where exactly one is positive. \\n\n",
        "\n",
        "Inference with Horn clauses can be done through the forward-chaining and\n",
        "backward-chaining algorithms. \\n Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB. \\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",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Sound\" : \" the inference algorithm should only derive entailed sentences.\", \n",
        "\"Complete\" : \"an inference algorithm is complete if it can derive all sentences that are entailed\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 91,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0ae254a5-5b71-44fd-a573-d565f545f46f"
      },
      "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": 92,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n The central component of a knowledge-based agent is its knowledge base, or KB. \n\n__A knowledge base__ is a set of sentences. (Here “sentence” is used as a technical term. It is related but not identical to the sentences of English and other natural languages.)\n\nEach sentence is expressed in a language called a __knowledge representation language__ and represents some assertion about the world. \nWhen the sentence is taken as being given without being derived from other sentences, we call it an __axiom__.\n\nBoth operations may involve inference—that is, __deriving new sentences from old__. \n\n \nEach time the __agent program__ is called, it does three things:\n__First__, it Tells the knowledge base what it perceives. \n\n__Second__, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\n\n__Third__, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n\nBecause of the definitions of Tell and Ask, however, the knowledge-based agent is not an arbitrary program for calculating actions. It is amenable to a description at the knowledge level, where we need to specify only what the agent knows and what its goals are, in order to determine its behavior. \n \nIt is independent of __implementation level knowledge__. \n\nStarting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building.\n\nIn contrast, the procedural approach encodes desired behaviors directly as program code. \n\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n For an agent in the environment, the main challenge is its initial ignorance of the configuration of the environment; overcoming this ignorance seems to require logical reasoning. In most instances of the wumpus world, it is possible for the agent to retrieve the gold safely. Occasionally, the agent must choose between going home empty-handed and risking death to find the gold. \n\nNote that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n\n \n\n## AIMA Chapter 7.3 Logic\n These sentences are expressed according to the __syntax__ of the representation language, which specifies all the sentences that are well formed. \n\nA logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \n\nA logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \n\n__Entailment__: A|=B if M(A) subset of M(B) \n\nAn inference algorithm that derives only entailed sentences is called __sound or truth-preserving__. \n\n__Definition of entailment__ can be used to derive logical inferences. This is known as __model checking__. \n\n__Soundness is a highly desirable property__. An unsound inference procedure essentially makes things up as it goes along—it announces the discovery of nonexistent needles. \n\n \nThe property of __completeness__ is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. For real haystacks, which are finite in extent, it seems obvious that a systematic examination can always decide whether the needle is in the haystack. \n\n \nThe final issue to consider is __grounding__—the connection between logical reasoning processes and the real environment in which the agent exists. \n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. \n\n__Complex sentences__ are constructed from simpler sentences, using parentheses and operators called logical connectives.\n\n__Conjunction__ - intersection - and\n__Disjunction__ - union - or\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nA sentence is __valid__ if it is true in all models. \n\nThe final concept we will need is satisfiability. A sentence is __satisfiable__ if it is true in, or satisfied by, some model. \n\n__Modus Ponens__: a->b, a = b \n\nAnd__ Elimination__: a^b = a \n\nThus, searching for proofs is an alternative to enumerating models. In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are. \n\nOne final property of logical systems is __monotonicity__, which says that the set of entailed sentences can only increase as information is added to the knowledge base. \n\n\nThe current section introduces a single inference rule, resolution, that yields a complete inference algorithm when coupled with any complete search algorithm. \n\n\n__Resolution__ basically makes a complete set of inferences from the given inferences. \n\n\n__Unit Resolution__: These last two inference steps are examples of the unit resolution inference rule. \n\n\nThus, the unit resolution rule takes a clause—a disjunction of literals—and a literal and produces a new clause. Note that a single literal can be viewed as a disjunction of one literal, also known as a unit clause. \n\n\nThere is one more technical aspect of the resolution rule: the resulting clause should contain only one copy of each literal. The removal of multiple copies of literals is called factoring. \n\n\n__CNF__: \n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals. \n\n1. Eliminate ⇔ by replacing a⇔ β with (a ⟹ β) ⋀ (β ⟹a) \n\n2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination) \n\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules \n\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible. \n\nThe sentence is now in CNF! \n\n\nWe barely need a complete set of inferences. Some KBs are formulated\nin a more restrictive form which enables them to use more efficient inference\nalgorithms.  \n\n\n\n \n\n## Module 7 Lecture Notes\n __Horn Clauses__: \n\ndisjunction(union) of literals where at most one is positive. \n\n\n__Definite clauses__: \n\ndisjunction(union) of literals where exactly one is positive. \n\n\nInference with Horn clauses can be done through the forward-chaining and\nbackward-chaining algorithms. \n Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB. \n\n__Forward 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\n__Backward 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## Module 7 Definitions\n* **Sound** -  the inference algorithm should only derive entailed sentences.\n* **Complete** - an inference algorithm is complete if it can derive all sentences that are entailed\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": "4d325ba0-ac4b-46b6-bc80-a96082bf0736"
      },
      "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": 93,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n From these two dimensions— _human vs. rational and thought vs. behavior_ —there are four possible combinations, and there have been adherents and research programs for all four.\nThe Turing test, a computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or from a computer. \n\n\nThe interdisciplinary field of __cognitive science__ brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind. \n\n\nAI approaches: turing (acting humanly), cognitive (thinking humanly), logic (thinking rationally), rational agent(acting rationally). \n\n\nThe rational-agent approach to AI has __two advantages__ over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. The standard of rationality is mathematically well defined and completely general. \n\n\n__the issue of limited rationality__—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good starting point for theoretical analysis. (might not do the optimal thing always). \n\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n __weak AI__—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking). \n\n\nTuring says human thinking is too complex to be quantified in rules and inferences and hence coded. Humans use some kind of informal thinking.\nBut deep learning has started capturing most of it, hence, logical inferences might not always give the solution needed. \n\n\n__Mathematical Objection__: because machines are formal systems that are limited by the incompleteness theorem—they cannot establish the truth of their own Gödel sentence—while humans have no such limitation. \n\n\nBriefly, for any formal axiomatic framework F  powerful enough to do arithmetic, it is possible to construct a so-called Gödel sentence G(F)  with the following properties:\nG(F)  is a sentence of F , but cannot be proved within F .\nIf F  is consistent, then G(F) is true. \n\n\n\n__Measuring AI__: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Some philosophers claim that a machine that acts intelligently would not be actually thinking, but would be only a simulation of thinking. \n\n\nChinese: Blurting out chinese responses through a set of rules.\nTherefore, there is no understanding of Chinese. And Searle says that the Chinese room is doing the same thing that a computer would do, so therefore computers generate no understanding. \n\n\n__Biological Naturalism__: Humans are made of cells and cells have no understanding.\n\n \n\n## AIMA 2.1 Agents and Environments\n We use the term __percept__ to refer to the content an agent’s sensors are perceiving. An agent’s __percept sequence__ is the complete history of everything the agent has ever perceived. \n\n\nMathematically speaking, we say that an agent’s behavior is described by the __agent function__ that maps any given percept sequence to an action. \n\n\n__The agent function__ is an abstract mathematical description; __the agent program__ is a concrete implementation, running within some physical system. \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n __Performance measure__: This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\ngeneral rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n\n\n__What is rational at any given time depends on four things__: \n\nThe performance measure that defines the criterion of success. \n\nThe agent’s prior knowledge of the environment. \n\nThe actions that the agent can perform. \n\nThe agent’s percept sequence to date. \n\n\n\n__Formal definition of rational agent__: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. \n\n\nrationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance. Rationality doesn't require omniscience. \n\n\nDoing actions in order to modify future percepts—sometimes called __information gathering__ —is an important part of rationality. A second example of information gathering is provided by the __exploration__ that must be undertaken by a vacuum-cleaning agent in an initially unknown environment. \n\n\nOur definition requires a rational agent not only to gather information but also to __learn__ as much as possible from what it perceives. \n\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks __autonomy__. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge. \n \n\n## AIMA 2.3 The Nature of Environments\n We must think about __task environments__, which are essentially the “problems” to which rational agents are the “solutions.” (can be real or virtual). \n\n\nFor the acronymically minded, we call this the __PEAS (Performance, Environment, Actuators, Sensors)__ description. In designing an agent, the first step must always be to specify the task environment as fully as possible. \n\n__Properties of Task Environments__: \n\n__FULLY vs PARTIALLY OBSERVABLE__: If the agent has no sensors at all then the environment is unobservable. \n\n__SINGLE-AGENT VS. MULTIAGENT__: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot). \n\n\n__DETERMINISTIC VS NON DETERMINISTIC__:\n If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.  \n\n\n__EPISODIC VS. SEQUENTIAL:__ \nIn episodic, every episode is atomic and independent of the previous episode.Examples of sequential -  Chess and taxi driving are sequential \n\n\n__STATIC vs DYNAMIC:__\n If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock). \n\n\n__DISCRETE VS. CONTINUOUS__: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem. \n\n\n__KNOWN VS. UNKNOWN__:\nStrictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. \n\n\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class. \n\n​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. \n\nConversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them. \n\nExperiments are often carried out not for a single environment but for many environments drawn from an __environment class__. For example, to evaluate a taxi driver in simulated traffic,\n\n\n## AIMA 2.4 The Structure of Agents\n\n__Agent = architecture + program__\nIn general, __the architecture__ makes the percepts from the sensors available to the program, runs the program, and feeds the program’s action choices to the actuators as they are generated. \n\n\n__The agent programs__ that we design in this book all have the same skeleton: they take the current percept as input from the sensors and return an action to the actuators. \n\n\nThe simplest kind of agent is the  __simple reflex agent__. These agents select actions on the basis of the current percept, ignoring the rest of the percept history. \n\n\n__Simple Reflex Actions __have limited intelligence. They work well only in fully observable environments. Can get caught in infinite loops that are partially observable. \n\nSolution: randomize actions. Hence, a randomized simple reflex agent might outperform a deterministic simple reflex agent. \n\n\n__Model-based Reflex Actions__:\nKeep track of the world using internal state through agent’s sensors. \n\n\nInfo about how the world changes: transition model. \n\n\nFor example, when the car in front initiates braking, one or more illuminated red regions appear in the forward-facing camera image, This kind of knowledge is called a sensor model. \n\n\nGoal based agent:\nThe agent program can combine this with the model (the same information as was used in the model-based reflex agent) to choose actions that achieve the goal through search and planning. \n\n\nUtility-based agents:\nGoal + Utility (happy state, sad state of a rider in a taxi). \n\nAn agent’s utility function is essentially an internalization of the performance measure. Provided that the internal utility function and the external performance measure are in agreement, an agent that chooses actions to maximize its utility will be rational according to the external performance measure. \n\n\nLearning Agents:\nAutonomy: \n\nThe most important distinction is between the learning element, which is responsible for making improvements, and the performance element, which is responsible for selecting external actions. The performance element is what we have previously considered to be the entire agent: it takes in percepts and decides on actions. The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better in the future. \n\nThe last component of the learning agent is the problem generator. It is responsible for suggesting actions that will lead to new and informative experiences. \n\nReward and Penalty \n\n\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - An agent is anything that perceives its environment through sensors and acts upon that environment through actuators.\n* **Rationality** - doing the right thing\n* **Turing test** - NLP, knowledge representation, automated reasoning, machine learning\n* **Total turing test** - requires interaction with the real world, computer vision and robotics\n* **Syllogisms** - logic, but world is not certain, hence, probability is introduced\n* **Rational agent** - acts to achieve best expected outcome, A rational agent is one that does the right thing.\n* **Standard model** - AI has focused on the study and construction of agents that do the right thing.\n* **Gofai** - Good old fashioned AI corresponds to the simplest logical agent design\n* **The embodied cognition approach** -  makes no sense to consider brain separately,cognition takes place within a body,embedded in an environment\n* **The “argument from disability”** - makes the claim that a machine can never do X (can love, be kind etc ).\n* **Qualia and consciousness** - The technical term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \n__Portable__: \n\nPrograms run on major platforms without change. \n\n__REPL__: Run Evaluate Print Loop : type python3 in your terminal\n\nAll data treated as objects. An object is deleted (by garbage collection) once unreachable \n\nStrong typing means that the type of a value doesn't change in unexpected ways. A string containing only digits doesn't magically become a number, as may happen in Perl. Every change of type requires an explicit conversion. \n\nDynamic typing, you don't need to specify the type of variable before defining. \n \n\n\n__STRINGS__: \n\nImmutable \n\n== checks whether variables point to objects of the same value \n\nis checks whether variables point to the same object \n\n\n__Operations on Strings__ \n\ns = \"Pretend this sentence makes sense.\" \n\nwords = s.split(\" \") \n\nwords \b\n['Pretend', 'this', 'sentence', 'makes', 'sense.'] \n\n\"_\".join(words) #join method of obj \"_\" \n\n'Pretend_this_sentence_makes_sense.' \n\ns = 'dog' \n\ns.capitalize() \n\n'Dog' \n\ns.upper() \n\n'DOG’ \n\n‘hi --'.strip(' –') \n\n'Hi’ \n\n\n\n__LISTS__: \n\nMutable ordered sequence of items of mixed types \n\nuse y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value \n\nA shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original. \n\nA deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original. \n\n\nOperations on Lists: \n\n>>> li.append('a') # Note the method syntax  \n\n>>> li.insert(2, 'i')  \n\n>>> li [1, 11, 'i', 3, 4, 5, 'a'] \n\n>>> li = ['a', 'b', 'c', 'b'] \n\n>>> li.index('b') # index of first occurrence 1  \n\n>>> li.count('b') # number of occurrences 2 \n\n>>> li.remove('b') # remove first occurrence \n\n>>> li.reverse() # reverse the list *in place* (modify) \n\n>>> li.sort() # sort the list *in place*  \n\n>>> li.sort(some_function) # sort in place using user-defined comparison  \n\n>>> sorted(li) #return a *copy* sorted \n\n\n__TUPLES__: \n\nA simple immutable ordered sequence of items \n\nImmutable: a tuple cannot be modified once created \n\nItems can be of mixed types, including collection types \n\n\n__SLICING__: \n\nt[1:4] #slicing ends before last index \n\nt[1:-1] #using negative index \n\n('abc', 4.56, (2,3)) \n\nt[1:-1:2] # selection of every nth item. \n\n('abc', (2,3)) \n\nt[:2] # copy from beginning of sequence \n\n(23, 'abc') \n\nt[2:] # copy to the very end of the sequence \n\n(4.56, (2,3), 'def') \n\nA[::-1] = reverses \n\n<object_name> [ <start_index>, <stop_index> , <step> ] \n\nThis means step is gonna slice every step_index from the given start index, till the stop index. \n\nStop Index is not included in slicing  \n\n\n\n__DICTIONARIES__: \n\n● Dictionaries are unordered & work by hashing, so keys must be immutable \n\n● Constant average time add, lookup, update \n\nd['pswd'] = 'thx1138' # Assigning to an existing key replaces its value. \n\nd \n {'user': 'R2D2', 'pswd': 'thx1138'} \n\nd = {'user':'R2D2', 'p':1234, 'i':34} \n\nd.keys() # List of current keys \n\ndict_keys(['user', 'p', 'i’]) \n\nd.values() # List of current values. \n\ndict_values(['R2D2', 1234, 34]) \n\nd.items() # List of item tuples. \n\ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)]) \n\nDefault dict and Counter \n\nfrom collections import defaultdict \n\nd = defaultdict(str) \n\nD['a'] -> \" \" \n\nfrom collections import Counter \n\nd = Counter() \n\nD['a'] -> 0 \n \n\n\n\n__FUNCTIONS__: \n\nMultiple return types: returned as tuples \n\nNo function overloading \n\nOperator overloading possible through special types \n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError \n\n\n__Keyword arguments__: when function params are called out of order \n\nBut true (positional arguments) should always precede the keyword arguments \n\n>>> myfun(c=43, b=1, a=2)  \n\n*args: when you want to accept variable number of arguments in the function \n\n**kwargs: variable number of keyword arguments \n\nFunctions are first class citizens in python as Pass functions as arguments to other functions, Return functions as the values from other functions, Assign functions to variables or store them in data structures \n \n\n\n__CLASSES__: \n\nTo define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition. No extends keyword. class AI_Student(Student): \n Multiple inheritance is supported. \n\n\n__Misc__: \n\nif __name__ == '__main__': \n\n\nDuck typing is a concept related to dynamic typing, where the type or the class of an object is less important than the methods it defines. When you use duck typing, you do not check types at all. Instead, you check for the presence of a given method or attribute. \n \n\n__FOR Loops__: \n\nnewlist = [expression for item in iterable if condition == True] \n\nDictionary/Set Comprehension: \n\nd = { k: v for k,v in lst1 } \n\ns = { x for x in lst2 } \n\n\n__Iterators__: \n\n$__next__$ \n\nPython iterators do not have a hasnext() method. Just catch the StopIteration exception. \n\nIterators use memory efficiently. \n With range you pre-build your list, but xrange is an iterator and yields the next item when needed instead. \n\nGenerators (its an iterator) use yield. \n\nLess code than writing a standard iterator, Maintains local state automatically \n\nValues are computed one at a time, as they’re needed \n\nAvoids storing the entire sequence in memory, Good for aggregating (summing, counting) items. \n One pass, Crucial for infinite sequences, Bad if you need to inspect the individual values \n\n\nA __set__ is an unordered collection of items. Every set element is unique (no duplicates) and must be immutable (cannot be changed). \n\n\nHowever, a set itself is mutable. We can add or remove items from it. \n\n\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Open Loop: when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state. \n\nClosed Loop: If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts. \n\nSearch Problem Formulation: \n\nState Space: A set of possible states that the environment can be in: \n\nInitial State \n\nGoal States \n\nActions \n\nTransition Model \n\nAction Cost Function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state. \n\nThe process of removing detail from a representation is called abstraction. \n\nThe abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. \n\n \n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. \n\n A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data. \n\n \nAbsolute movements: movement direction acc to viewer \n\nEgocentric: movement direction acc to the robot \n\n \nStandardized problems: grid world, sokoban puzzle, sliding tile puzzle \n\nReal world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution, or an indication of failure. \n\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.  \n\nThe state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. \n\nFrontier of the search tree is the node we choose to expand first. \n\nNote that the frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached. \n\n \nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.  \n\nGraph search is more memory intensive than tree search as it keeps track of redundant paths. \n\nGraph search is faster than tree search. \n\nBest First Search:\nEvaluating the node n with the minimum evaluation function f(n). \n\nOn each iteration we choose a node on the frontier with minimum  value, return it if its state is a goal state, and otherwise apply Expand to generate child nodes. \n \nEach child node is added to the frontier if it has not been reached before, or is re-added if it is now being reached with a path that has a lower path cost than any previous path. \n\nIt checks if the node is the goal state only after it gets popped out of the queue for expansion. \n\nGraph Like Search (that is, it checks for redundant paths) \n \n\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state. \n\nFor an implicit state space, complexity can be measured in terms of  d, the depth or number of actions in an optimal solution;  m, the maximum number of actions in any path; and b,  the branching factor or number of successors of a node that need to be considered. \n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth First Search: \n\nWhen all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. This is a systematic search strategy that is therefore complete even on infinite state spaces. \n\nFIFO Queue is used \n\nThat also means we can do an early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search uses, waiting until a node is popped off the queue. \n\nComplete  \n\nOptimal \n\nbut memory intensive as it is storing all the expanded nodes.  \n\nTime and Space: O(b^d) \n\n \nUniform Cost Search or Djisktra’s: \n\nBest First Search:  the algorithm tests for goals only when it expands a node, not when it generates a node, so it has not yet detected that this is a path to the goal. \n\nComplete \n\nOptimal \n\n \nDepth First Search: \n\nDepth-first search always expands the deepest node in the frontier first. It could be implemented as a call to Best-First-Search where the evaluation function f  is the negative of the depth. \n\nHowever, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.  \n\nIncomplete \n\nNon optimal \n\nTime: O(b^m) \n\nSpace: O(bm) \n\nBacktracking depth first search: space O(m), only one successor at a time is expanded. \n \n \nDepth Limited Search: \n \nDFS with a limit of depth L \n\nIncomplete \n\nNon optimal \n\nTime: O(b^l) \n\nSpace: O(bl) \n\n \nIterative Deepening Search: \n\nDepth Limited Search while iterating over L\nComplete \n\nOptimal \n \nTime: O(b^d) \n\nSpace: O(bd) \n\n \nBidirectional Search: \n\nAn alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s),hoping that the two searches will meet. \n \n\n## Module 3 Lecture Notes\n ​​Use depth-first if \n\n• Space is restricted \n\n• There are many possible solutions with long paths and wrong paths are usually\nterminated quickly \n\n• Search can be fine-tuned quickly \n\nUse 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\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Heuristic: estimated cost of the cheapest path from state at node n to goal state. \n\nGreedy best first search: picking the node with the lowest heuristic first, not optimal \n\nA* search: \n\nBest first search with evaluation: f(n) = g(n) + h(n) \n\ng(n) is path cost, h(n) is estimated path cost (heuristic) \n\nA key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. \n\nA slightly stronger property is called consistency. A heuristic h(n)  is consistent if, for every node n and every successor n’ of  generated by an action a we have: \n\nh(n) < = c(n,a,n’) + h(n’) (triangle inequality) \n\nEvery consistent heuristic is admissible (not vice versa). \n\nIn addition, with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry. But with an inconsistent heuristic, we may end up with multiple paths reaching the same state, and if each new path has a lower path cost than the previous one, then we will end up with multiple nodes for that state in the frontier, costing us both time and space. \n\nSearch Contours: A useful way to visualize a search is to draw contours in the state space, just like the contours in a topographic map. \n\nThe contours with uniform-cost search will be “circular” around the start state, spreading out equally in all directions with no preference towards the goal. \n\nf(n) is monotonically increasing iff the heuristic is consistent. \n\nTherefore you get concentric contour lines that don’t cross each other, and if you choose to draw the lines fine enough, you can put a line between any two nodes on any path. \n\nA*star prunes : The concept of pruning—eliminating possibilities from consideration without having to examine them—is important for many areas of AI. \n\nA* search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A* search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded. \n\nWeighted A* star = W*h(n) \n\nIn bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee.\n\nIn bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly. \n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n A*star \n\nTime: O(bd) \n\nSpace: O(b^d) \n\n\nHow to judge quality of heuristics: \n\nEffective Branching Factor \n\nEffective Depth: depth Kh, O(b^(d-Kh)) \n\nDominating heuristics: h2 dominates h1 if h2(n) >=h1(n) \n\nRelaxed problem: lesser restrictions in the problem will make heuristic picking easier \n\nThe state-space graph of the relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph. \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \n\nGenerating heuristics from cost of the sub problems \n\nThe idea behind pattern databases is to store these exact solution costs for every possible subproblem instance. \n\nthe sum of the two costs is still a lower bound on the cost of solving the entire problem. This is the idea behind disjoint pattern databases. \n\n \nPrecomputation of heuristics: \n\nDifferential heuristic:  \n\nHdh(n) = max |C*(n,L) - C* (goal, L) | \n\nLearning to search better: \n\nMetalevel state space and object level state space: Meta-learning, or learning to learn, is the science of systematically observing how different machine learning approaches perform on a wide range of learning tasks, and then learning from this experience, or meta-data, to learn new tasks much faster than otherwise possible. \n\n \nLearning from Experience by adding features: h(n) = c1x1(n) + c2x2(n) \n\n \n\n## Module 4 Lecture Notes\n Uniform Cost Search: \n\nExpand node with lowest path cost (djisktras) \n\nOptimal and Complete \n\nSubtle but significant difference from BFS: \n\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier. \n\nUpdates a node on the frontier if a better path to the same state is found. \n\nSo always enqueue a node before checking whether it is a goal. \n\n \nGreedy Best First Search : \n\nExpands nodes with lowest heuristic. \n\nNot Optimal \n\nA* star: \n \nAdmissible heuristic for 8-puzzle: out of place heuristic and manhattan distance. \n\nRelaxed Problem: \n\nA problem with fewer restrictions on the actions than the original is called a relaxed\nProblem. \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem. \n\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then Hoop(n)\ngives the shortest solution. \n\nIf the rules are relaxed so that a tile can move to any adjacent square, then Hmd(n)\ngives the shortest solution. \n\nA* applications:  \n\nPathing / routing problems (A* is in your GPS!) \n\nVideo games \n\nRobot motion planning \n\nResource planning problems \n\n \nMemory Bounded Search:  \n\nFor making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state. \n\nBeam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. \n\nIterative Deepening A* search: \n\nRecursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path. \n\nRBFS is optimal when h(n) is admissible. \n\nMA* and SMA* : memory bounded and simplified memory bounded A* star \n\nSMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA* always drops the worst leaf node—the one with the highest f -value \n.\nBidirectional A star: \n\nFront to end: Hf estimates distance to goal and Hb estimates distance to other frontier. \n\nFront to front:  attempts to estimate the distance to the other frontier. \n\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 We show that pruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.  \n\nTwo player zero sum game: The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n\n“Perfect information” is a synonym for “fully observable,”1 and “zero-sum” means one player’s loss is another’s gain: there is no “win-win” outcome. For games we often use the term move as a synonym for “action” and position as a synonym for “state.” \n\nGame: initial state, to move, action state, result, is terminal, utility. \n\nA utility function (also called an objective function or payoff function), which defines the final numeric value to player  p when the game ends in terminal state s. \n\nMAX and MIN are two players. \n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\nFor games with multiple outcome scores, we need a slightly more general algorithm called minimax search. the word “move” means that both players have taken an action; therefore the word ply is used to unambiguously mean one move by one player, bringing us one level deeper in the game tree.) \n\nMinimax: time complexity O(b^m) and space: O(bm) like DFS. \n\n \n \nMinimax for multiplayer: form alliances (two or more players team up). \n\nAlphaBeta Pruning: \n\nAlpha (at least) is MAX’s lower bound on MAX’s outcome. \n \nBeta (at most) is MIN’s upper bound on MIN’s outcome. \n\nYou prune max when v > = beta and prune min  when v < = alpha \n\nAlpha and beta are updated only while going down in the right subtree \n\nV only checks the children Vs and not alpha and beta \n\n \nTime complexity depends on the ordering of nodes.\nIf this could be done perfectly, alpha-beta would need to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\n\nThat means effective branches became b^0.5 instead of b \n\nWith random ordering O(b^3m/4). \n\nTherefore, stop evaluating a branch whenever: When evaluating a MAX node: a value v>=beta is backed-up • MIN will never select that MAX node \n\nWhen evaluating a MIN node: a value v ≤ alpha is found • MAX will never select that MIN node \n\nValue might not get updated when a tree is pruned. \n\n \nExpectimax: \n\nAlgo: \n\nWhy wouldn’t we know what the result of an action will be? Explicit randomness: rolling dice \n\nUnpredictable opponents: the opponent isn’t optimal \n\nActions can fail: when moving a robot, wheels might slip \n\nValues should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes \n\nExpectimax search: compute the average score under optimal playMax nodes as in minimax search Chance nodes are like min nodes but the outcome is uncertain \n\nCalculate their expected utilities I.e. take weighted average (expectation) of children \n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal.\n\n In other words, we replace the Utility function with Eval, which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. \n\nA heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p. \n \nFor terminal states, Eval(s,p) = Utility(s,p) \n\nAnd for non terminal states: Utility(loss,p) <= Eval(s,p) <= Utility(win,p) \n\nExpected Value : averaging \n\nMaterial Value : assigning a value to the pawns in chess (for example) \n\nWeighted Function: weighted linear function \n\nCutting Off Search: modifying alpha beta to cut off at non terminal states. \n\nThese simple approaches can lead to errors due to the approximate nature of the evaluation function. \n\nThe evaluation function should be applied only to positions that are quiescent—that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation. \n\nThe horizon effect is more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics. \n\nOne strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point. \n\nForward Pruning: Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error. \n\nThis can be done using: \n\nBeam search: consider only a “beam” of the n best moves \n\nProbCut: uses statistics gained from prior experience to lessen the chance that the best move will be pruned. \n\nAnother technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves. \n\nSearch vs lookup \n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n chance nodes \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent preferences are captured by utility function which assigns a single number to express the desirability of a state. \n\nDecision theory, in its simplest form, deals with choosing among actions based on the desirability of their immediate outcomes; that is, the environment is assumed to be episodic.  \n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints on Rational Preferences: \n\nOrderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. \n\nTransitivity, \n\nContinuity, \n\nSubstitutability, \n\nMonotonicity, \n\nDecomposability. \n\nAs in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility Assessments and Utility Scales: \n\nIf we want to build a decision-theoretic system that helps a human make decisions or acts on his or her behalf, we must first work out what the human’s utility function is. This process, often called preference elicitation, involves presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n\nNormalized Utilities use a scale of 0 or 1 \n\n \nThe utility of money: \n\nWe say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n\n \nExpected utility and post-decision disappointment: \n\nUnbiased estimator \n\nHuman judgment and irrationality: \n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. \n\n \n\n## Module 5 Lecture Notes\n Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening . \n\nThe best moves are known as killer moves, and to try them first is called the killer move heuristic. \n\nIn game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states. \n\nType A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \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 \nA problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a __constraint satisfaction problem,__ or CSP.  \n\nCSP comprises of 3 components:  \n\nX: set of __variables__ \n\nD: set of __domains__ \n\nC: set of __constraints__ that specify allowable combinations of value \n\nEach constraint has a __pair <scope, rel>__ \n\n__Scope__: tuple of variables that participate in the constraint \n\n__Rel:__ tuple of the values the variable can take \n\n__Complete assignment__: all variables are assigned \n\n__Partial assignment__: some variables left unassigned \n\n__Map coloring__: different color for adjacent node \n\n__Job scheduling__: preceding constraints\n\n__Disjunctive constraints__: that don’t overlap(algebraic plus disjunctive)\n\n__Special solution algorithms__ exist for linear constraints on integer variables—that is, constraints, such as the one just given, in which each variable appears only in linear form. It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables—the problem is undecidable. \n\n__Unary constraints, binary constraints__ \n\n__Global constraints__: Aldiff \n\n__Constraint Hyper Graph__: A hypergraph consists of ordinary nodes and hypernodes, which represent n-ary constraints— n constraints involving  variables. \n\nAnother 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 one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variable \n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n__Constraint propagation__: setting off a chain reaction to decrease the domain of variables using the constraints. \n\n__Local Consistency__: The key idea is local consistency. If we treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph. \n\n__Node Consistency__: unary constraints \n\n__Arc Consistency__: binary constraints, can be used to reduce domains \n\n__AC3__, O(cd^3), c is the number of binary constraints, d is the number of arcs which is O(n^2d^3) \n\nFor planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ) \n\nInitially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) \n\nAC-3 then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi  arc-consistent with respect to Xj. \n\nIf this is unchanged,move on to the next arc. \n\nBut if this revises Di(makes the domain smaller), then we add to the queue all arcs (Xk,Xi)  where Xk is a neighbor of Xi .  \n\nIf Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return to failure. \n \n\n \n__Path consistency__ tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. \n\n__K consistent__: Stronger forms of propagation can be defined with the notion of k -consistency. A CSP is k -consistent if, for any set of (k-1) variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. \n\n__Strongly k consistent: if k consistent, k-1 consistent …. 1 consistent__ \n\n__Time complexity for strongly k consistent: O(n^2 d)__ \n\n__Global Constraint__: Remember that a global constraint is one involving an arbitrary number of variables (but not necessarily all variables). Hence,  a simple algo: keep deleting the variables with singleton values \n\n__Resource Constraint__: at most constraint \n\nFor large resource-limited problems with integer values—such as logistical problems involving moving thousands of people in hundreds of vehicles—it is usually not possible to represent the domain of each variable as a large set of integers and gradually reduce that set by consistency-checking methods. \n\n__Bound Constraint__: Instead, domains are represented by upper and lower bounds and are managed by bounds propagation. \n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n When after running CSP, domains are not unary. Need to __backtrack__ to check the solution. \n\n__Commutativity__: if order of assignment of solution does not matter. \n\nUsing commutativity in backtracking: \n\nState would be a partial assignment, and an action would extend the assignment \n\nn! d^n complexity reduced to d^n   \n\n__Static ordering backtracking__: choosing variables in order \n\n__Random ordering backtracking__: choosing variables in random order \n\n__Most constraining backtracking__: \n\nThis intuitive idea—choosing the variable with the fewest “legal” values—is called the __minimum-remaining-values__ (MRV) heuristic. It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \n\n__To pick the first value in MRV__:  In this case, the __degree heuristic__ comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. \n\nNow after picking the most constraining variable, the values subsequent ones should be the least constraining values. (in order to find a solution). \n\nVariable - fail first, Value - fail last \n\nThere are two ways to go about it: __search and inference__\n\n__Forward Checking (a type of inference):__ Whenever a variable X  is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable X  that is connected to Y  by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for. (just checking the neighbors) \n\n__Maintaining arc consistency (MAC)__ : ensure all arcs are consistent after each assignment through a recursive procedure. MAC coupled with AC3 gives better results than MAC \n\n__Intelligent backtracking:__ backtrack the most recent variable which made the assignment inconsistent. \n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n The most obvious approach is to select the value that results in the minimum number of conflicts with other variables—__the min-conflicts heuristic__. Especially for N queens. Move the queens to minimum conflict position. \n\nThe landscape of a CSP under the min-conflicts heuristic usually has a __series of plateaus__. \n\n__Plateau search__—  allowing sideways moves to another state with the same score—can help local search find its way off this plateau. \n\nThis wandering on the plateau can be directed with a technique called __tabu search__: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus. \n\nAnother technique called __constraint weighting__ aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights. \n\nAnother advantage of __local search__ is that it can be used in online settings when the problem changes. \n\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\n__Independent sub problems__: Independence can be ascertained simply by finding connected components of the constraint graph. Each problem then can be a CSP. \n\nThis way, an exponential problem O(d^n) where (d is the size of domain and n: no of variables) is reduced to N/C problems, time complexity decreased to linear O(nd^c/c) \n\nDirectional arc consistent -> Topological graph \n\n__Cutset Conditioning__: The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables from a tree. \n\nRuntime complexity: O(d^c * (n-c)*d^2) \n\nMore time,less than Tree Decomposition\n\nCutset Conditioning is only efficient when a small cutset can be found. \n\n__Tree Decomposition:__ \n\nThey are efficient only wehn tree width is small. \n\nIn constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem. \n\nTime Complexity: O(nd^2), n:no of trees, d:size of domain \n\nAlgo: \n\nEvery variable in the original problem appears in at least one of the tree nodes. \n\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n\nThe tree width of a tree decomposition of a graph is one less than the size of the largest node; the tree width of the graph itself is defined to be the minimum width among all its tree decompositions. \n\nTime complexity: O(nd^w+1) \n\n__Value Breaking Symmetry:__\nWe would like to reduce the search space by a factor of d!  by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. \n\n\n\n\n## Module 6 Lecture Notes\n __CSP__: general purpose algo, just specify the constraints. \n\n__Benefits of CSP__: clean specification of algo, knows where to focus search (as in, which variables are violating the constraints), Automatically prune off all branches that violate constraints. \n\n__Varieties of CSP__: n variables, domain size of d -> O(d^n) assignments. \n\n__CSP as a search problem__ :  Solution is always found at depth n, for n variables. \n\n• n variables of domain size d.\n• Branching factor at the root is n*d.\n• Branching factor at next level is (n-1)*d.\n• Tree has n!*d^n leaves. \n\nBut CSPs are commutative: so d^n leaves only. \n\n__Depth-first search__ for CSPs with single-variable assignments is called __backtracking search__. \n\n__Search__: Assigning values to variable. \n\n__Inference__: Eliminates possible values for a variable if the value would violate local consistency. \n\n__The Waltz Algorithm__: Each intersection is a variable, adjacent intersections impose\nconstraints on each other, Solutions are physically realizable 3D interpretations. \n\n__The Backtracking-Search algorithm__ has a very simple policy for what to do when a branch of the search fails: back up to the preceding variable and try a different value for it. This is called chronological backtracking because the most recent decision point is revisited. In this subsection, we consider better possibilities. (sort of like depth first search)\n\n__Intelligent backtracking:__ Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set. \n\n__Backjumping__ is the same as forward checking. \n\nWhen we reach a contradiction, __backjumping__ can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem. \n\n__Conflict directed backjumping__ \n\n__Constraint Learning__:  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments). \n\nNo goods can be computed by forward checking or back jumping. \n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n The central component of a knowledge-based agent is its knowledge base, or KB. \n\n__A knowledge base__ is a set of sentences. (Here “sentence” is used as a technical term. It is related but not identical to the sentences of English and other natural languages.)\n\nEach sentence is expressed in a language called a __knowledge representation language__ and represents some assertion about the world. \nWhen the sentence is taken as being given without being derived from other sentences, we call it an __axiom__.\n\nBoth operations may involve inference—that is, __deriving new sentences from old__. \n\n \nEach time the __agent program__ is called, it does three things:\n__First__, it Tells the knowledge base what it perceives. \n\n__Second__, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\n\n__Third__, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n\nBecause of the definitions of Tell and Ask, however, the knowledge-based agent is not an arbitrary program for calculating actions. It is amenable to a description at the knowledge level, where we need to specify only what the agent knows and what its goals are, in order to determine its behavior. \n \nIt is independent of __implementation level knowledge__. \n\nStarting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building.\n\nIn contrast, the procedural approach encodes desired behaviors directly as program code. \n\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n For an agent in the environment, the main challenge is its initial ignorance of the configuration of the environment; overcoming this ignorance seems to require logical reasoning. In most instances of the wumpus world, it is possible for the agent to retrieve the gold safely. Occasionally, the agent must choose between going home empty-handed and risking death to find the gold. \n\nNote that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n\n \n\n## AIMA Chapter 7.3 Logic\n These sentences are expressed according to the __syntax__ of the representation language, which specifies all the sentences that are well formed. \n\nA logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \n\nA logic must also define the __semantics__, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \n\n__Entailment__: A|=B if M(A) subset of M(B) \n\nAn inference algorithm that derives only entailed sentences is called __sound or truth-preserving__. \n\n__Definition of entailment__ can be used to derive logical inferences. This is known as __model checking__. \n\n__Soundness is a highly desirable property__. An unsound inference procedure essentially makes things up as it goes along—it announces the discovery of nonexistent needles. \n\n \nThe property of __completeness__ is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. For real haystacks, which are finite in extent, it seems obvious that a systematic examination can always decide whether the needle is in the haystack. \n\n \nThe final issue to consider is __grounding__—the connection between logical reasoning processes and the real environment in which the agent exists. \n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. \n\n__Complex sentences__ are constructed from simpler sentences, using parentheses and operators called logical connectives.\n\n__Conjunction__ - intersection - and\n__Disjunction__ - union - or\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nA sentence is __valid__ if it is true in all models. \n\nThe final concept we will need is satisfiability. A sentence is __satisfiable__ if it is true in, or satisfied by, some model. \n\n__Modus Ponens__: a->b, a = b \n\nAnd__ Elimination__: a^b = a \n\nThus, searching for proofs is an alternative to enumerating models. In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are. \n\nOne final property of logical systems is __monotonicity__, which says that the set of entailed sentences can only increase as information is added to the knowledge base. \n\n\nThe current section introduces a single inference rule, resolution, that yields a complete inference algorithm when coupled with any complete search algorithm. \n\n\n__Resolution__ basically makes a complete set of inferences from the given inferences. \n\n\n__Unit Resolution__: These last two inference steps are examples of the unit resolution inference rule. \n\n\nThus, the unit resolution rule takes a clause—a disjunction of literals—and a literal and produces a new clause. Note that a single literal can be viewed as a disjunction of one literal, also known as a unit clause. \n\n\nThere is one more technical aspect of the resolution rule: the resulting clause should contain only one copy of each literal. The removal of multiple copies of literals is called factoring. \n\n\n__CNF__: \n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals. \n\n1. Eliminate ⇔ by replacing a⇔ β with (a ⟹ β) ⋀ (β ⟹a) \n\n2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination) \n\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules \n\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible. \n\nThe sentence is now in CNF! \n\n\nWe barely need a complete set of inferences. Some KBs are formulated\nin a more restrictive form which enables them to use more efficient inference\nalgorithms.  \n\n\n\n \n\n## Module 7 Lecture Notes\n __Horn Clauses__: \n\ndisjunction(union) of literals where at most one is positive. \n\n\n__Definite clauses__: \n\ndisjunction(union) of literals where exactly one is positive. \n\n\nInference with Horn clauses can be done through the forward-chaining and\nbackward-chaining algorithms. \n Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB. \n\n__Forward 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\n__Backward 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## Module 7 Definitions\n* **Sound** -  the inference algorithm should only derive entailed sentences.\n* **Complete** - an inference algorithm is complete if it can derive all sentences that are entailed\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}