{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of 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": "b62752ab-a18c-4f74-f3ee-740a7b2f82a0"
      },
      "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": 37,
      "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": "8573dfb6-e125-4539-831f-0771bf498ac8"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "• natural language processing to enable it to communicate successfully in English;\n",
        "• knowledge representation to store what it knows or hears;\n",
        "• automated reasoning to use the stored information to answer questions and to draw new conclusions;\n",
        "• machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n",
        "\n",
        "We need to get inside the actual workings of human minds.\n",
        "through introspection—trying to catch our own thoughts as they go by;\n",
        "through psychological experiments—observing a person in action;\n",
        "and through brain imaging—observing the brain in action\n",
        "\n",
        "cognitive science brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind.\n",
        "These laws of thought were supposed to govern the operation of the mind; their study initiated the field called logic.\n",
        "\n",
        "First, it is not easy to take informal knowledge and state it in the formal terms required by logical notation, \n",
        "particularly when the knowledge is less than 100% certain.\n",
        "Second, there is a big difference between solving a problem “in principle” and solving it in practice.\n",
        "\n",
        "An agent is just something that acts (agent comes from the Latin agere, to do). Of course, all computer programs do something, \n",
        "but computer agents are expected to do more: operate autonomously, perceive their environment, persist over a prolonged time period, adapt to change, and create and pursue goals. \n",
        "A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n",
        " \n",
        "The rational-agent approach has two advantages over the other approaches. \n",
        "First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. \n",
        "Second, it is more amenable to scientific development than are approaches based on human behavior or human thought.\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 = \"\"\" \n",
        "\n",
        "the assertion that machines could act as if they were intelligent is called the weak AI hypothesis by philosophers, \n",
        "and the assertion that machines that do so are actually thinking (not just simulating thinking) is called the strong AI hypothesis.\n",
        "\n",
        "Philosophers such as J. R. Lucas (1961) have claimed that this theorem shows that machines are mentally inferior to humans, because machines are formal systems that are limited by the incompleteness theore\n",
        "\n",
        "Go ̈del’s incompleteness theorem applies only to formal systems that are powerful enough to do arithmetic.\n",
        "\n",
        "Second, an agent should not be too ashamed that it cannot establish the truth of some sentence while other agents can. Consider the sentence\n",
        "\n",
        "even if we grant that computers have limitations on what they can prove, there is no evidence that humans are immune from those limitations. \n",
        "\n",
        "The inability to capture everything in a set of logical rules is called the qualification problem in AI.\n",
        "\n",
        "Good Old-Fashioned AI,” or GOFAI,\n",
        "\n",
        "o understand how human (or other animal) agents work, we have to consider the whole agent, not just the agent program. Indeed, the embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment. \n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "\n",
        "consciousness—the machine has to be aware of its own mental states and actions.\n",
        "\n",
        "phenomenology, or the study of direct experience: the machine has to actually feel emotions. \n",
        "Others focus on intentionality—that is, the question of whether the machine’s purported beliefs, desires, and\n",
        " other representations are actually “about” some- thing in the real world.\n",
        "\n",
        "Philosophical efforts to solve this mind–body problem are directly relevant to the question of whether machines could have real minds.\n",
        "\n",
        "he monist theory of mind, often called physicalism, avoids this problem by asserting the mind is not separate from the body—that mental states are physical states.\n",
        "\n",
        "intentional states. These are states, such as believing, knowing, desiring, fearing, and so on, that refer to some aspect of the external world. \n",
        "\n",
        "The “wide content” view interprets it from the point of view of an omniscient outside observer with access to the whole situation, who can distinguish differences in the world. \n",
        "\n",
        "Narrow content, on the other hand, considers only the brain state.\n",
        "\n",
        "The theory of functionalism says that a mental state is any intermediate causal condition between input and output.\n",
        "\n",
        "intuition pump: it amplifies one’s prior intuitions, so biological naturalists are more convinced of their positions, and functionalists are convinced only that axiom 3 is unsupported, or that in general Searle’s argument is unconvincing. \n",
        "\n",
        "explanatory gap has led some philosophers to conclude that humans are simply incapable of forming a proper understanding of their own consciousness.\n",
        "\n",
        "inverted spectrum thought experiment, which the subjective experience of per- son X when seeing red objects is the same experience that the rest of us experience when seeing green objects, and vice versa.\n",
        "\n",
        "The technical term for the intrinsic nature of experiences is qualia\n",
        "\n",
        "\n",
        "There are three possible conclusions:\n",
        "1. The causal mechanisms of consciousness that generate these kinds of outputs in normal brains are still operating in the electronic version, which is therefore conscious.\n",
        "2. The conscious mental events in the normal brain have no causal connection to behavior, and are missing from the electronic brain, which is therefore not conscious.\n",
        "3. The experiment is impossible, and therefore speculation about it is meaningless.\n",
        "Although we cannot rule out the second possibility, it reduces consciousness to what philoso- phers call an epiphenomenal role\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n",
        "\n",
        "agent function that maps any given percept sequence to an action.\n",
        "\n",
        "the agent function for an artificial agent will be implemented by an agent program. \n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "A rational agent is one that does the right thing—conceptually speaking, every entry in the table for the agent function is filled out correctly.\n",
        "\n",
        "performance measure that evaluates any given sequence of environment states.\n",
        "\n",
        "Rationality\n",
        "\n",
        "For each possible percept sequence, a rational agent should select an action that is ex- pected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
        "• The performance measure that defines the criterion of success.\n",
        "• The agent’s prior knowledge of the environment. • The actions that the agent can perform.\n",
        "• The agent’s percept sequence to date\n",
        "\n",
        " An omniscient agent knows the actual outcome of its actions and can act accordingly;\n",
        "\n",
        " Doing actions in order to modify future percepts—sometimes called information gather\n",
        "\n",
        " exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n",
        "\n",
        "\n",
        "To the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts, we say that the agent lacks autonomy. \n",
        "\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "PEAS: performance measure, the environment, and the agent’s actuators and sensors.\n",
        "\n",
        "software agents:::softbot Web site operator designed to scan Internet news sources and show the interesting items to its users\n",
        "\n",
        " A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action; relevance, in turn, depends on the performance measure\n",
        "\n",
        " communication often emerges as a rational behavior in multiagent environments; in some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability.\n",
        "\n",
        " If the next state of the environment is completely deter- mined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic.\n",
        "\n",
        " uncertain if it is not fully observable or not deterministic.\n",
        "\n",
        " a nondeterministic environment is one in which actions are characterized by their possible outcomes, but no probabilities are attached to them. \n",
        "\n",
        " In an episodic task environment, the agent’s experience is divided into atomic episodes\n",
        "\n",
        "  Episodic environments are much simpler than sequential environments because the agent does not need to think ahead.\n",
        "\n",
        "   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 semidynamic.\n",
        "\n",
        "   In a known environment, the outcomes (or outcome probabilities if the environment is stochastic) for all actions are given.\n",
        "\n",
        "   It is quite possible for a known environment to be partially observable—for example, in solitaire card games, I know the rules but am still unable to see the cards that have not yet been turned over. \n",
        "\n",
        "   environment generator for each environment class that selects particular environments (with certain likelihoods) in which to run the agent.\n",
        "\n",
        "  \n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "\n",
        "agent = architecture + program .\n",
        "\n",
        "The lookup table will contain 􏰂Tt = 1 |P|t entries.\n",
        "\n",
        "The daunting size of these tables (the number of atoms in the observable universe is less than 1080) means that (a) no physical agent in this universe will have the space to store the table, (b) the designer would not have time to create the table, (c) no agent could ever learn all the right table entries from its experience, and (d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries.\n",
        "\n",
        "• Simple reflex agents;\n",
        "• Model-based reflex agents; • Goal-based agents; and\n",
        "• Utility-based agents.\n",
        "\n",
        "simple reflex agent. These agents select actions on the basis of the current percept, ignoring the rest of the percept history\n",
        "\n",
        "Escape from infinite loops is possible if the agent can randomize its actions.\n",
        "\n",
        "\n",
        "Model-based reflex agents\n",
        "The most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now. \n",
        "That is, the agent should maintain some sort of internal state that depends on the percept history \n",
        "\n",
        " First, we need some information about how the world evolves independently of the agent—for example, that an overtaking car generally will be closer behind than it was a moment ago. \n",
        " Second, we need some information about how the agent’s own actions affect the world—\n",
        "\n",
        "  implemented in simple Boolean circuits or in complete scientific theories—is called a model of the world. An agent that uses such a model is called a model-based agent.\n",
        "\n",
        "\n",
        "Goal-based agents\n",
        "n other words, as well as a current state description, the agent needs some sort of goal information that describes situations that are desirable\n",
        "Search  and planning  to find goal\n",
        "\n",
        "Utility-based agents\n",
        "n agent’s utility function is essentially an internalization of the performance measure. \n",
        "If the internal utility function and the external performance measure are in agreement, \n",
        "then an agent that chooses actions to maximize its utility will be rational according to the external performance measure\n",
        "\n",
        "First, when there are conflicting goals, only some of which can be achieved (for example, speed and safety),\n",
        " the utility function specifies the appropriate tradeoff. \n",
        "Second, when there are several goals that the agent can aim for, none of which can be achieved with certainty,\n",
        " utility provides a way in which the likelihood of success can be weighed against the importance of the goals.\n",
        "\n",
        " Learning agents::: creating state-of-the-art systems.Learning in intelligent agents can be summarized as a process of modification of each component of the agent to bring \n",
        " the components into closer agreement with the available feedback information, \n",
        " thereby improv- ing the overall performance of the agent.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        " learning element, which is re- sponsible for making improvements, and the performance element, which is responsible for selecting external actions.\n",
        "\n",
        " 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",
        " he performance standard distinguishes part of the incoming percept as a reward (or penalty) that provides direct feedback on the quality of the agent’s behavior\n",
        "\n",
        " atomic, factored, and structured.\n",
        "\n",
        " atomic representation each state of the world is indivisible—it has no internal structure. search and game-playing, Hidden Markov models, and Markov decision processes \n",
        "\n",
        "  A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value.\n",
        "  factored representations, including constraint satisfaction algorithms ,propositional logic, planning, Bayesian networks, and the machine learning \n",
        "\n",
        "  Structured representations underlie relational databases and first-order logic , first-order probability models, knowledge-based learning \n",
        "\n",
        "  the axis along which atomic, factored, and structured repre- sentations lie is the axis of increasing expressiveness.\n",
        "  \n",
        "  easoning and learning become more complex as the expressive power of the representation increases.\n",
        "   To gain the benefits of expressive representations while avoiding their drawbacks, \n",
        "   intelligent systems for the real world may need to operate at all points along the axis simultaneously.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 40,
      "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": "0fb83087-5e37-433f-b0e5-e100bda4dc6f"
      },
      "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": 41,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n• natural language processing to enable it to communicate successfully in English;\n• knowledge representation to store what it knows or hears;\n• automated reasoning to use the stored information to answer questions and to draw new conclusions;\n• machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nWe need to get inside the actual workings of human minds.\nthrough introspection—trying to catch our own thoughts as they go by;\nthrough psychological experiments—observing a person in action;\nand through brain imaging—observing the brain in action\n\ncognitive science brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind.\nThese laws of thought were supposed to govern the operation of the mind; their study initiated the field called logic.\n\nFirst, it is not easy to take informal knowledge and state it in the formal terms required by logical notation, \nparticularly when the knowledge is less than 100% certain.\nSecond, there is a big difference between solving a problem “in principle” and solving it in practice.\n\nAn agent is just something that acts (agent comes from the Latin agere, to do). Of course, all computer programs do something, \nbut computer agents are expected to do more: operate autonomously, perceive their environment, persist over a prolonged time period, adapt to change, and create and pursue goals. \nA rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n \nThe rational-agent approach has two advantages over the other approaches. \nFirst, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. \nSecond, it is more amenable to scientific development than are approaches based on human behavior or human thought.\n \n \n\n## AIMA Chapter 27.1 The Limits of AI\n \n\nthe assertion that machines could act as if they were intelligent is called the weak AI hypothesis by philosophers, \nand the assertion that machines that do so are actually thinking (not just simulating thinking) is called the strong AI hypothesis.\n\nPhilosophers such as J. R. Lucas (1961) have claimed that this theorem shows that machines are mentally inferior to humans, because machines are formal systems that are limited by the incompleteness theore\n\nGo ̈del’s incompleteness theorem applies only to formal systems that are powerful enough to do arithmetic.\n\nSecond, an agent should not be too ashamed that it cannot establish the truth of some sentence while other agents can. Consider the sentence\n\neven if we grant that computers have limitations on what they can prove, there is no evidence that humans are immune from those limitations. \n\nThe inability to capture everything in a set of logical rules is called the qualification problem in AI.\n\nGood Old-Fashioned AI,” or GOFAI,\n\no understand how human (or other animal) agents work, we have to consider the whole agent, not just the agent program. Indeed, the embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment. \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n\nconsciousness—the machine has to be aware of its own mental states and actions.\n\nphenomenology, or the study of direct experience: the machine has to actually feel emotions. \nOthers focus on intentionality—that is, the question of whether the machine’s purported beliefs, desires, and\n other representations are actually “about” some- thing in the real world.\n\nPhilosophical efforts to solve this mind–body problem are directly relevant to the question of whether machines could have real minds.\n\nhe monist theory of mind, often called physicalism, avoids this problem by asserting the mind is not separate from the body—that mental states are physical states.\n\nintentional states. These are states, such as believing, knowing, desiring, fearing, and so on, that refer to some aspect of the external world. \n\nThe “wide content” view interprets it from the point of view of an omniscient outside observer with access to the whole situation, who can distinguish differences in the world. \n\nNarrow content, on the other hand, considers only the brain state.\n\nThe theory of functionalism says that a mental state is any intermediate causal condition between input and output.\n\nintuition pump: it amplifies one’s prior intuitions, so biological naturalists are more convinced of their positions, and functionalists are convinced only that axiom 3 is unsupported, or that in general Searle’s argument is unconvincing. \n\nexplanatory gap has led some philosophers to conclude that humans are simply incapable of forming a proper understanding of their own consciousness.\n\ninverted spectrum thought experiment, which the subjective experience of per- son X when seeing red objects is the same experience that the rest of us experience when seeing green objects, and vice versa.\n\nThe technical term for the intrinsic nature of experiences is qualia\n\n\nThere are three possible conclusions:\n1. The causal mechanisms of consciousness that generate these kinds of outputs in normal brains are still operating in the electronic version, which is therefore conscious.\n2. The conscious mental events in the normal brain have no causal connection to behavior, and are missing from the electronic brain, which is therefore not conscious.\n3. The experiment is impossible, and therefore speculation about it is meaningless.\nAlthough we cannot rule out the second possibility, it reduces consciousness to what philoso- phers call an epiphenomenal role\n\n\n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n\nagent function that maps any given percept sequence to an action.\n\nthe agent function for an artificial agent will be implemented by an agent program. \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nA rational agent is one that does the right thing—conceptually speaking, every entry in the table for the agent function is filled out correctly.\n\nperformance measure that evaluates any given sequence of environment states.\n\nRationality\n\nFor each possible percept sequence, a rational agent should select an action that is ex- pected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n• The performance measure that defines the criterion of success.\n• The agent’s prior knowledge of the environment. • The actions that the agent can perform.\n• The agent’s percept sequence to date\n\n An omniscient agent knows the actual outcome of its actions and can act accordingly;\n\n Doing actions in order to modify future percepts—sometimes called information gather\n\n exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts, we say that the agent lacks autonomy. \n\n \n\n## AIMA 2.3 The Nature of Environments\n\nPEAS: performance measure, the environment, and the agent’s actuators and sensors.\n\nsoftware agents:::softbot Web site operator designed to scan Internet news sources and show the interesting items to its users\n\n A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action; relevance, in turn, depends on the performance measure\n\n communication often emerges as a rational behavior in multiagent environments; in some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability.\n\n If the next state of the environment is completely deter- mined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic.\n\n uncertain if it is not fully observable or not deterministic.\n\n a nondeterministic environment is one in which actions are characterized by their possible outcomes, but no probabilities are attached to them. \n\n In an episodic task environment, the agent’s experience is divided into atomic episodes\n\n  Episodic environments are much simpler than sequential environments because the agent does not need to think ahead.\n\n   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 semidynamic.\n\n   In a known environment, the outcomes (or outcome probabilities if the environment is stochastic) for all actions are given.\n\n   It is quite possible for a known environment to be partially observable—for example, in solitaire card games, I know the rules but am still unable to see the cards that have not yet been turned over. \n\n   environment generator for each environment class that selects particular environments (with certain likelihoods) in which to run the agent.\n\n  \n\n\n\n## AIMA 2.4 The Structure of Agents\n \n\nagent = architecture + program .\n\nThe lookup table will contain 􏰂Tt = 1 |P|t entries.\n\nThe daunting size of these tables (the number of atoms in the observable universe is less than 1080) means that (a) no physical agent in this universe will have the space to store the table, (b) the designer would not have time to create the table, (c) no agent could ever learn all the right table entries from its experience, and (d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries.\n\n• Simple reflex agents;\n• Model-based reflex agents; • Goal-based agents; and\n• Utility-based agents.\n\nsimple reflex agent. These agents select actions on the basis of the current percept, ignoring the rest of the percept history\n\nEscape from infinite loops is possible if the agent can randomize its actions.\n\n\nModel-based reflex agents\nThe most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now. \nThat is, the agent should maintain some sort of internal state that depends on the percept history \n\n First, we need some information about how the world evolves independently of the agent—for example, that an overtaking car generally will be closer behind than it was a moment ago. \n Second, we need some information about how the agent’s own actions affect the world—\n\n  implemented in simple Boolean circuits or in complete scientific theories—is called a model of the world. An agent that uses such a model is called a model-based agent.\n\n\nGoal-based agents\nn other words, as well as a current state description, the agent needs some sort of goal information that describes situations that are desirable\nSearch  and planning  to find goal\n\nUtility-based agents\nn agent’s utility function is essentially an internalization of the performance measure. \nIf the internal utility function and the external performance measure are in agreement, \nthen an agent that chooses actions to maximize its utility will be rational according to the external performance measure\n\nFirst, when there are conflicting goals, only some of which can be achieved (for example, speed and safety),\n the utility function specifies the appropriate tradeoff. \nSecond, when there are several goals that the agent can aim for, none of which can be achieved with certainty,\n utility provides a way in which the likelihood of success can be weighed against the importance of the goals.\n\n Learning agents::: creating state-of-the-art systems.Learning in intelligent agents can be summarized as a process of modification of each component of the agent to bring \n the components into closer agreement with the available feedback information, \n thereby improv- ing the overall performance of the agent.\n\n\n\n\n## Module 1 Lecture Notes\n \n learning element, which is re- sponsible for making improvements, and the performance element, which is responsible for selecting external actions.\n\n 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 he performance standard distinguishes part of the incoming percept as a reward (or penalty) that provides direct feedback on the quality of the agent’s behavior\n\n atomic, factored, and structured.\n\n atomic representation each state of the world is indivisible—it has no internal structure. search and game-playing, Hidden Markov models, and Markov decision processes \n\n  A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value.\n  factored representations, including constraint satisfaction algorithms ,propositional logic, planning, Bayesian networks, and the machine learning \n\n  Structured representations underlie relational databases and first-order logic , first-order probability models, knowledge-based learning \n\n  the axis along which atomic, factored, and structured repre- sentations lie is the axis of increasing expressiveness.\n  \n  easoning and learning become more complex as the expressive power of the representation increases.\n   To gain the benefits of expressive representations while avoiding their drawbacks, \n   intelligent systems for the real world may need to operate at all points along the axis simultaneously.\n\n\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\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",
        "\n",
        "All data treated as objects\n",
        "An object is deleted (by garbage collection) once unreachable.\n",
        "\n",
        "Strong Typing\n",
        "Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
        "that type (eg. “foo” + 2) type(object) isinstance(object, type)\n",
        "\n",
        "Java: static typing\n",
        "Variables can only refer to objects of a declared type\n",
        "int x = 2\n",
        "String y = \"foo\"\n",
        "  Methods use type signatures to enforce contracts\n",
        "  public static void main(String[] args)\n",
        "o Python: dynamic typing\n",
        "Variables come into existence when first assigned.\n",
        ">>> x = \"foo\"\n",
        ">>> x = 2\n",
        "\n",
        "print(\"%s can speak %d languages\" % (\"C3PO\", 6000000)) --- Immutable (String)\n",
        "\n",
        " \"_\".join(words)\n",
        "\n",
        " d = {'user' : 'R2D2', 'pswd': 1234}----Dictionary ;;;  d.keys() ;;;d.values()   ;;;;  d.items()\n",
        "\n",
        " \n",
        "\n",
        " defaultdict automatically initializes nonexistent dictionary values\n",
        "\n",
        " from collections import Counter d = Counter()\n",
        "\n",
        "d['a']\n",
        "\n",
        "0 //op\n",
        "\n",
        " d['dog'] += 10\n",
        "\n",
        " d['dog']\n",
        "\n",
        " 10//op\n",
        "\n",
        "\n",
        " The return type is a tuple\n",
        "\n",
        "  print_everything(*lst)\n",
        "\n",
        "\n",
        "  **kwargs ---Suppose you want to accept a variable number of keyword arguments to your function.\n",
        "  my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)\n",
        "\n",
        "\n",
        "  def myfun(positional, *args, **kwargs):\n",
        "    print(positional)\n",
        "    if args:\n",
        "        print(args)\n",
        "    if kwargs:\n",
        "        print(kwargs)\n",
        "\n",
        "        \n",
        "\n",
        "\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": 42,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 650
        },
        "outputId": "af6103a6-2137-4e5f-fbf6-b60ea9cd2ee6"
      },
      "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": 43,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n\nAll data treated as objects\nAn object is deleted (by garbage collection) once unreachable.\n\nStrong Typing\nEvery object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2) type(object) isinstance(object, type)\n\nJava: static typing\nVariables can only refer to objects of a declared type\nint x = 2\nString y = \"foo\"\n  Methods use type signatures to enforce contracts\n  public static void main(String[] args)\no Python: dynamic typing\nVariables come into existence when first assigned.\n>>> x = \"foo\"\n>>> x = 2\n\nprint(\"%s can speak %d languages\" % (\"C3PO\", 6000000)) --- Immutable (String)\n\n \"_\".join(words)\n\n d = {'user' : 'R2D2', 'pswd': 1234}----Dictionary ;;;  d.keys() ;;;d.values()   ;;;;  d.items()\n\n \n\n defaultdict automatically initializes nonexistent dictionary values\n\n from collections import Counter d = Counter()\n\nd['a']\n\n0 //op\n\n d['dog'] += 10\n\n d['dog']\n\n 10//op\n\n\n The return type is a tuple\n\n  print_everything(*lst)\n\n\n  **kwargs ---Suppose you want to accept a variable number of keyword arguments to your function.\n  my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)\n\n\n  def myfun(positional, *args, **kwargs):\n    print(positional)\n    if args:\n        print(args)\n    if kwargs:\n        print(kwargs)\n\n        \n\n\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 = \"\"\" Goal formulation is the first step in problem defination.\n",
        "Problem formulation is the process of deciding what actions and states to consider, given a goal.\n",
        "\n",
        "while the agent is executing the solution sequence it ignores its percepts when choosing an action---Control theorists call this an open-loop system,\n",
        "\n",
        "A problem can be defined formally by five components:\n",
        "\n",
        "The initial state \n",
        "A description of the possible actions available to the agent.\n",
        "A description of what each action does; the formal name for this is the transition model, successor to refer to any state reachable from a given state by a single action\n",
        "A path in the state space is a sequence of states connected by a sequence of actions.\n",
        "goal test, which determines whether a given state is a goal state. \n",
        "A path cost function that assigns a numeric cost to each path.\n",
        "\n",
        "The process of removing detail from a representation is called abstraction.\n",
        "\n",
        "\n",
        "function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action persistent: seq, an action sequence, initially empty\n",
        "state, some description of the current world state goal, a goal, initially null\n",
        "problem, a problem formulation\n",
        "state ← UPDATE-STATE(state,percept) if seq is empty then\n",
        "goal ← FORMULATE-GOAL(state)\n",
        "problem ←FORMULATE-PROBLEM(state,goal) seq ← SEARCH(problem)\n",
        "if seq = failure then return a null action\n",
        "action ← FIRST(seq) seq ← REST(seq) return action\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "A larger environment with n locations has n · 2n states.\n",
        "\n",
        "8-puzzle belongs to the family of sliding-block puzzles,--np complete\n",
        "\n",
        "n-queens family, ::An incremental formulation,  A complete-state formulation \n",
        "\n",
        " traveling salesperson problem (TSP) : np-hard \n",
        "\n",
        "\n",
        "Criterion\n",
        "          Breadth-      Uniform-     Depth-     Depth-lim     Iterative-deep    Bidirectional (if applicable)\n",
        "Complete?   Yes           Yes         No.        No               Yes.                      Yes\n",
        "Time.       O(b^d)    O(b1+⌊C∗/ε⌋)    O(b^m)     O(b^l)               O(b^d)              O(b^d/2)\n",
        "Space       O(b^d)    O(b1+⌊C∗/ε⌋)    O(bm)     O(bl)               O(bd)               O(bd/2)\n",
        "Optimal?    Yes           Yes         No.        No                 Yes.                      Yes\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "\n",
        "function TREE-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\n",
        "loop do\n",
        "if the frontier is empty then return failure\n",
        "choose a leaf node and remove it from the frontier\n",
        "if the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier\n",
        "\n",
        "\n",
        "function GRAPH-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\n",
        "initialize the explored set to be empty\n",
        "loop do\n",
        "if the frontier is empty then return failure\n",
        "choose a leaf node and remove it from the frontier\n",
        "if the node contains a goal state then return the corresponding solution add the node to the explored set\n",
        "expand the chosen node, adding the resulting nodes to the frontier\n",
        "only if not in the frontier or explored set\n",
        "\n",
        "\n",
        "we have a structure that contains four components\n",
        "• n.STATE:\n",
        "• n.PARENT: \n",
        "• n.ACTION: \n",
        "• n.PATH-COST: g(n), of the path from the initial state to the node,\n",
        "\n",
        "the next node to expand according to its preferred strategy\n",
        "\n",
        "evaluate an algorithm’s performance in four ways:\n",
        "• Completeness:  • Optimality:  • Time complexity: • Space complexity:\n",
        "\n",
        "complexity\n",
        "b, the branching ;;; d, the depth of the shallowest goal node ;;;;m, the maximum length of any path in the state space;;;\n",
        "\n",
        "total cost, which combines the search cost and the path cost of the solution found\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS: complete (provided the branching factor b is finite))\n",
        "\n",
        "breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node.\n",
        "\n",
        "O(bd): time ans space complexity\n",
        "\n",
        "Uniform-cost search:\n",
        "\n",
        "expands the node n with the lowest path cost g(n).\n",
        "\n",
        "priority queue ordered by g\n",
        "\n",
        "Diff between bfs and UCS:\n",
        "\n",
        "goal test is applied to a node when it is selected for expansion rather than when it is first generated.\n",
        "\n",
        "The second difference is that a test is added in case a better path is found to a node currently on the frontier.\n",
        "\n",
        "optimal,Completeness is guaranteed provided the cost of every step exceeds some small positive constant ε. h does not care about the number of steps a path has, but only about their total cost. \n",
        "Therefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions\n",
        "\n",
        "time and space:  O(b^(1+\u0004C∗/ε)\u0005),\n",
        "\n",
        "DFS:\n",
        "\n",
        "The graph-search version, which avoids repeated states and re- dundant paths, is complete in finite state spaces because it will eventually expand every node. \n",
        "The tree-search version, on the other hand, is not complete\n",
        "\n",
        " both versions are nonoptimal. \n",
        "\n",
        " all of the O(b^m) nodes in the search tree, where m is the maximum depth of any node;\n",
        "\n",
        " For a state space with branching factor b and maximum depth m, depth-first search requires storage of only O(bm) nodes.\n",
        "\n",
        " Depth limited search :\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "\n",
        " Depth-limited search will also be nonoptimal if we choose l > d. Its time complexity is O(b^l) and its space complexity is O(bl). Depth-first search can be viewed as a special case of depth-limited search with l = ∞.\n",
        "function DEPTH-LIMITED-SEARCH(problem,limit) returns a solution, or failure/cutoff return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit)\n",
        "function RECURSIVE-DLS(node,problem,limit) returns a solution, or failure/cutoff if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\n",
        "else if limit = 0 then return cutoff\n",
        "else\n",
        "cutoff occurred?←false\n",
        "for each action in problem.ACTIONS(node.STATE) do\n",
        "child ←CHILD-NODE(problem,node,action) result←RECURSIVE-DLS(child,problem,limit −1) if result = cutoff then cutoff occurred ? ← true\n",
        "else if result ̸= failure then return result\n",
        "if cutoff occurred? then return cutoff else return failure\n",
        "\n",
        "\n",
        "depth-limited search can terminate with two kinds of failure: the standard failure value indicates no solution; the cutoff value indicates no solution within the depth limit.\n",
        "\n",
        "\n",
        "Iterative deepening search\n",
        "\n",
        "function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure fordepth =0to∞do\n",
        "result ←DEPTH-LIMITED-SEARCH(problem,depth) if result ̸= cutoff then return result\n",
        "\n",
        "memory requirements are modest: O(bd) to be precise.  and time complexity of O(b^d)\n",
        "\n",
        "In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.\n",
        "\n",
        "increasing path-cost limits instead of increasing depth limits. The resulting algorithm, called iterative lengthening search, \n",
        "\n",
        "\n",
        "Bidirectional search\n",
        "\n",
        "The idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal\n",
        "\n",
        "b^d/2 + b^d/2  - time and space (This space requirement is the most significant weakness of bidirectional se)\n",
        "\n",
        "Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect;\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",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1d455bf6-4731-4517-cc8a-bc8b63bb0525"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Goal formulation is the first step in problem defination.\nProblem formulation is the process of deciding what actions and states to consider, given a goal.\n\nwhile the agent is executing the solution sequence it ignores its percepts when choosing an action---Control theorists call this an open-loop system,\n\nA problem can be defined formally by five components:\n\nThe initial state \nA description of the possible actions available to the agent.\nA description of what each action does; the formal name for this is the transition model, successor to refer to any state reachable from a given state by a single action\nA path in the state space is a sequence of states connected by a sequence of actions.\ngoal test, which determines whether a given state is a goal state. \nA path cost function that assigns a numeric cost to each path.\n\nThe process of removing detail from a representation is called abstraction.\n\n\nfunction SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action persistent: seq, an action sequence, initially empty\nstate, some description of the current world state goal, a goal, initially null\nproblem, a problem formulation\nstate ← UPDATE-STATE(state,percept) if seq is empty then\ngoal ← FORMULATE-GOAL(state)\nproblem ←FORMULATE-PROBLEM(state,goal) seq ← SEARCH(problem)\nif seq = failure then return a null action\naction ← FIRST(seq) seq ← REST(seq) return action\n\n\n## AIMA Chapter 3.2 Example Problems\n \nA larger environment with n locations has n · 2n states.\n\n8-puzzle belongs to the family of sliding-block puzzles,--np complete\n\nn-queens family, ::An incremental formulation,  A complete-state formulation \n\n traveling salesperson problem (TSP) : np-hard \n\n\nCriterion\n          Breadth-      Uniform-     Depth-     Depth-lim     Iterative-deep    Bidirectional (if applicable)\nComplete?   Yes           Yes         No.        No               Yes.                      Yes\nTime.       O(b^d)    O(b1+⌊C∗/ε⌋)    O(b^m)     O(b^l)               O(b^d)              O(b^d/2)\nSpace       O(b^d)    O(b1+⌊C∗/ε⌋)    O(bm)     O(bl)               O(bd)               O(bd/2)\nOptimal?    Yes           Yes         No.        No                 Yes.                      Yes\n\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n\nfunction TREE-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier\n\n\nfunction GRAPH-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\ninitialize the explored set to be empty\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution add the node to the explored set\nexpand the chosen node, adding the resulting nodes to the frontier\nonly if not in the frontier or explored set\n\n\nwe have a structure that contains four components\n• n.STATE:\n• n.PARENT: \n• n.ACTION: \n• n.PATH-COST: g(n), of the path from the initial state to the node,\n\nthe next node to expand according to its preferred strategy\n\nevaluate an algorithm’s performance in four ways:\n• Completeness:  • Optimality:  • Time complexity: • Space complexity:\n\ncomplexity\nb, the branching ;;; d, the depth of the shallowest goal node ;;;;m, the maximum length of any path in the state space;;;\n\ntotal cost, which combines the search cost and the path cost of the solution found\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS: complete (provided the branching factor b is finite))\n\nbreadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node.\n\nO(bd): time ans space complexity\n\nUniform-cost search:\n\nexpands the node n with the lowest path cost g(n).\n\npriority queue ordered by g\n\nDiff between bfs and UCS:\n\ngoal test is applied to a node when it is selected for expansion rather than when it is first generated.\n\nThe second difference is that a test is added in case a better path is found to a node currently on the frontier.\n\noptimal,Completeness is guaranteed provided the cost of every step exceeds some small positive constant ε. h does not care about the number of steps a path has, but only about their total cost. \nTherefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions\n\ntime and space:  O(b^(1+\u0004C∗/ε)\u0005),\n\nDFS:\n\nThe graph-search version, which avoids repeated states and re- dundant paths, is complete in finite state spaces because it will eventually expand every node. \nThe tree-search version, on the other hand, is not complete\n\n both versions are nonoptimal. \n\n all of the O(b^m) nodes in the search tree, where m is the maximum depth of any node;\n\n For a state space with branching factor b and maximum depth m, depth-first search requires storage of only O(bm) nodes.\n\n Depth limited search :\n\n\n\n\n\n\n## Module 3 Lecture Notes\n \n\n Depth-limited search will also be nonoptimal if we choose l > d. Its time complexity is O(b^l) and its space complexity is O(bl). Depth-first search can be viewed as a special case of depth-limited search with l = ∞.\nfunction DEPTH-LIMITED-SEARCH(problem,limit) returns a solution, or failure/cutoff return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit)\nfunction RECURSIVE-DLS(node,problem,limit) returns a solution, or failure/cutoff if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\nelse if limit = 0 then return cutoff\nelse\ncutoff occurred?←false\nfor each action in problem.ACTIONS(node.STATE) do\nchild ←CHILD-NODE(problem,node,action) result←RECURSIVE-DLS(child,problem,limit −1) if result = cutoff then cutoff occurred ? ← true\nelse if result ̸= failure then return result\nif cutoff occurred? then return cutoff else return failure\n\n\ndepth-limited search can terminate with two kinds of failure: the standard failure value indicates no solution; the cutoff value indicates no solution within the depth limit.\n\n\nIterative deepening search\n\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure fordepth =0to∞do\nresult ←DEPTH-LIMITED-SEARCH(problem,depth) if result ̸= cutoff then return result\n\nmemory requirements are modest: O(bd) to be precise.  and time complexity of O(b^d)\n\nIn general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.\n\nincreasing path-cost limits instead of increasing depth limits. The resulting algorithm, called iterative lengthening search, \n\n\nBidirectional search\n\nThe idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal\n\nb^d/2 + b^d/2  - time and space (This space requirement is the most significant weakness of bidirectional se)\n\nBidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect;\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 = \"\"\" \n",
        "\n",
        "best-first search\n",
        "\n",
        "The implementation of best-first graph search is identical to that for uniform-cost search \n",
        "\n",
        "TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f(n)\n",
        "\n",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n",
        "\n",
        "Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly.\n",
        "heuristic function; that is, f (n) = h(n).\n",
        "\n",
        "Greedy best-first tree search is also incomplete even in a finite state space, much like depth-first search\n",
        "\n",
        "worst-case time and space complexity for the tree version is O(b^m), where m is the maximum depth of the search space.\n",
        "\n",
        "A* search:\n",
        "\n",
        "It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:\n",
        "\n",
        "both complete and optimal. \n",
        " A∗ expands no nodes with f(n) > C∗\n",
        " A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaran- teed to expand fewer nodes than A∗\n",
        "\n",
        "An admissible heuristic is one that never overestimates the cost to reach the goal.\n",
        "Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.\n",
        "\n",
        "A heuristic h(n) is consistent if, for every node n and every successor n'\u0002 of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n\u0002' plus the estimated cost of reaching the goal from n'\u0002:\n",
        "h(n) ≤ c(n, a, n'\u0002) + h(n'\u0002) . (Triangle inequality)\n",
        "\n",
        "\n",
        "tree-search version of A∗ is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent.\n",
        "\n",
        "A∗ selects a node n for expansion, the optimal path to that node has been found.\n",
        "\n",
        "W\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "\n",
        "The effect of heuristic accuracy on performance\n",
        "effective branching factor b∗. \n",
        "\n",
        "A well- designed heuristic would have a value of b∗ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\n",
        "\n",
        " h2(n) ≥ h1(n). We thus say that h2 dominates h1. Domination translates directly into efficiency:\n",
        "\n",
        " A problem with fewer restrictions on the actions is called a relaxed problem.\n",
        "\n",
        "the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "Furthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n",
        "\n",
        "A program called ABSOLVER can generate heuristics automatically from problem def- initions, using the “relaxed problem” method \n",
        "\n",
        "The idea behind pattern databases is to store these exact solution costs for every pos- sible subproblem instance\n",
        "\n",
        "That is, we record not the total cost of solving the 1-2- 3-4 subproblem, but just the number of moves involving 1-2-3-4. \n",
        "Then it is easy to see that the sum of the two costs is still a lower bound on the cost of solving the entire problem. \n",
        "This is the idea behind disjoint pattern databases.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" ith uniform-cost search (A∗ search using h(n) = 0), the bands will be “circular” around the start state.\n",
        " With more accurate heuristics, the bands will stretch toward the goal state and become more narrowly focused around the optimal path.\n",
        "\n",
        " O(b^(εd)) = O((b^ε)^d), so the effective branching factor (defined more formally in the next section) is b^ε.\n",
        "\n",
        " Because it keeps all generated nodes in memory (as do all GRAPH-SEARCH algorithms), A∗ usually runs out of space long before it runs out of time. \n",
        " For this reason, A∗ is not practical for many large-scale prob- lems.\n",
        "\n",
        "\n",
        "reduce memory requirements for A∗:: iterative-deepening A∗ (IDA∗) \n",
        "\n",
        "Recursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the operation of standard best-first search, but using only linear space\n",
        "\n",
        "RBFS is somewhat more efficient than IDA∗, but still suffers from excessive node re- generation.  RBFS is an optimal algorithm \n",
        "\n",
        "it depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded.\n",
        "\n",
        "IDA∗ and RBFS suffer from using too little memory. Because they forget most of what they have done, both algorithms may end up reex- panding the same states many times ove\n",
        "\n",
        "\n",
        "MA∗ (memory-bounded A∗) and SMA∗ (simplified MA∗).\n",
        "\n",
        "SMA∗ is complete if there is any reachable solution—that is, if d, the depth of the shallowest goal node, is less than the memory size (expressed in nodes).\n",
        " It is optimal if any optimal solution is reachable; otherwise, it returns the best reachable solution. \n",
        " In practical terms, SMA∗ is a fairly robust choice for finding optimal solutions, particularly when the state space is a graph, step costs are not uniform, \n",
        " and node generation is expensive compared to the overhead of maintaining the frontier and the explored set.\n",
        "\n",
        "\n",
        "metalevel state space.::Each state in a metalevel state space captures the internal (computational) state of a program that is searching in an object-level state space \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b09f8c73-1e4b-4b52-ff38-070afc5456a6"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n\nbest-first search\n\nThe implementation of best-first graph search is identical to that for uniform-cost search \n\nTREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f(n)\n\nh(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n\nGreedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly.\nheuristic function; that is, f (n) = h(n).\n\nGreedy best-first tree search is also incomplete even in a finite state space, much like depth-first search\n\nworst-case time and space complexity for the tree version is O(b^m), where m is the maximum depth of the search space.\n\nA* search:\n\nIt evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:\n\nboth complete and optimal. \n A∗ expands no nodes with f(n) > C∗\n A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaran- teed to expand fewer nodes than A∗\n\nAn admissible heuristic is one that never overestimates the cost to reach the goal.\nAdmissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.\n\nA heuristic h(n) is consistent if, for every node n and every successor n'\u0002 of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n\u0002' plus the estimated cost of reaching the goal from n'\u0002:\nh(n) ≤ c(n, a, n'\u0002) + h(n'\u0002) . (Triangle inequality)\n\n\ntree-search version of A∗ is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent.\n\nA∗ selects a node n for expansion, the optimal path to that node has been found.\n\nW\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n\nThe effect of heuristic accuracy on performance\neffective branching factor b∗. \n\nA well- designed heuristic would have a value of b∗ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\n\n h2(n) ≥ h1(n). We thus say that h2 dominates h1. Domination translates directly into efficiency:\n\n A problem with fewer restrictions on the actions is called a relaxed problem.\n\nthe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nFurthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n\nA program called ABSOLVER can generate heuristics automatically from problem def- initions, using the “relaxed problem” method \n\nThe idea behind pattern databases is to store these exact solution costs for every pos- sible subproblem instance\n\nThat is, we record not the total cost of solving the 1-2- 3-4 subproblem, but just the number of moves involving 1-2-3-4. \nThen it is easy to see that the sum of the two costs is still a lower bound on the cost of solving the entire problem. \nThis is the idea behind disjoint pattern databases.\n\n\n\n\n## Module 4 Lecture Notes\n ith uniform-cost search (A∗ search using h(n) = 0), the bands will be “circular” around the start state.\n With more accurate heuristics, the bands will stretch toward the goal state and become more narrowly focused around the optimal path.\n\n O(b^(εd)) = O((b^ε)^d), so the effective branching factor (defined more formally in the next section) is b^ε.\n\n Because it keeps all generated nodes in memory (as do all GRAPH-SEARCH algorithms), A∗ usually runs out of space long before it runs out of time. \n For this reason, A∗ is not practical for many large-scale prob- lems.\n\n\nreduce memory requirements for A∗:: iterative-deepening A∗ (IDA∗) \n\nRecursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the operation of standard best-first search, but using only linear space\n\nRBFS is somewhat more efficient than IDA∗, but still suffers from excessive node re- generation.  RBFS is an optimal algorithm \n\nit depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded.\n\nIDA∗ and RBFS suffer from using too little memory. Because they forget most of what they have done, both algorithms may end up reex- panding the same states many times ove\n\n\nMA∗ (memory-bounded A∗) and SMA∗ (simplified MA∗).\n\nSMA∗ is complete if there is any reachable solution—that is, if d, the depth of the shallowest goal node, is less than the memory size (expressed in nodes).\n It is optimal if any optimal solution is reachable; otherwise, it returns the best reachable solution. \n In practical terms, SMA∗ is a fairly robust choice for finding optimal solutions, particularly when the state space is a graph, step costs are not uniform, \n and node generation is expensive compared to the overhead of maintaining the frontier and the explored set.\n\n\nmetalevel state space.::Each state in a metalevel state space captures the internal (computational) state of a program that is searching in an object-level state space \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "deterministic, turn-taking, two-player, zero-sum games of perfect information (such as chess). Strategic:\n",
        "\n",
        "Pruning allows us to ignore portions of the search tree that make no difference to the final choice, and heuristic\n",
        "\n",
        "evaluation functions allow us to approximate the true utility of a state without doing a complete search.\n",
        "\n",
        "A game can be formally defined as a kind of search problem with the following elements:\n",
        "• S0: The initial state, which specifies how the game is set up at the start.\n",
        "• PLAYER(s): Defines which player has the move in a state.\n",
        "• ACTIONS(s): Returns the set of legal moves in a state.\n",
        "• RESULT(s,a): The transition model, which defines the result of a move.\n",
        "• TERMINAL-TEST(s): A terminal test, which is true when the game is over and false\n",
        "otherwise. States where the game has ended are called terminal states.\n",
        "• UTILIT Y (s, p): A utility function (also called an objective function or payoff function),\n",
        "defines the final numeric value for a game that ends in terminal state s for a player p.\n",
        "\n",
        "A zero-sum game is (confusingly) defined as one where the total payoff to all players\n",
        "is the same for every instance of the game.\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "The minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game.\n",
        "\n",
        "minimax algorithm performs a complete depth-first exploration of the game tree.\n",
        "\n",
        "If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). The space complexity is O(bm).\n",
        "\n",
        "For terminal states, this vector gives the utility of the state from each player’s viewpoint. \n",
        "\n",
        "def min-value(state):\n",
        "   if the state is a terminal state:\n",
        "        return the state’s utility\n",
        "   initialize v = +∞\n",
        "   for each successor of state:\n",
        "v = min(v, max-value(successor)) return v\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "The problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree.\n",
        "\n",
        "α = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.\n",
        "β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN.\n",
        "\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined.\n",
        "\n",
        " alpha–beta needs to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\n",
        "\n",
        "\n",
        "function ALPHA-BETA-SEARCH(state) returns an action v ←MAX-VALUE(state,−∞,+∞)\n",
        "return the action in ACTIONS(state) with value v\n",
        "\n",
        "function MAX-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← −∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MAX(v, MIN-VALUE(RESULT(s,a), α, β)) ifv ≥ βthenreturnv\n",
        "α←MAX(α, v)\n",
        "return v\n",
        "\n",
        "function MIN-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← +∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MIN(v, MAX-VALUE(RESULT(s,a) , α, β)) ifv ≤ αthenreturnv\n",
        "β ← MIN(β, v)\n",
        "return v\n",
        "\n",
        "One way to gain information from the current move is with iterative deepening search.\n",
        "The best moves are often called killer moves and to try them first is called the killer move heuristic.\n",
        "\n",
        "In many games, repeated states occur frequently because of transpo- sitions—different permutations of the move sequence that end up in the same position.\n",
        "The hash table of previously seen positions is traditionally called a transposition table;\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_4 =\"\"\" \n",
        "programs should cut off the search earlier and apply a heuristic evaluation function to states in the search,\n",
        "\n",
        "replace the utility function by a heuristic evaluation function EVAL, which estimates the position’s utility, \n",
        "and replace the terminal test by a cutoff test that decides when to apply EVAL.\n",
        "\n",
        "H-MINIMAX(s,d) = \n",
        "⎨ EVAL(s) if CUTOFF-TEST(s,d)\n",
        "⎩ maxa∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MAX \n",
        "mina∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MIN.\n",
        "\n",
        "An evaluation function returns an estimate of the expected utility of the game from a given position\n",
        "\n",
        "First, the evaluation function should order the terminal states in the same way as the true utility function: \n",
        "states that are wins must evaluate better than draws, which in turn must be better than losses.\n",
        " Otherwise, an agent using the evaluation function might err even if it can see ahead all the way to the end of the game.\n",
        "Second, the computation must not take too long! (The whole point is to search faster.) \n",
        "Third, for nonterminal states, the evaluation function should be strongly correlated with the actual chances of winning.\n",
        "\n",
        "\n",
        "apply iterative deepening to alpha beta for cutoff test. Iterative also helps in ordering\n",
        "\n",
        "The evaluation function should be applied only to positions that are quiescent—that is, unlikely to exhibit wild swings in value in the near future.\n",
        "\n",
        "This extra search is called a quiescence search; sometimes it is restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position.\n",
        "\n",
        "horizon effect== 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 delaying tactics\n",
        "\n",
        "(Type -B )forward pruning : beam search: consider only a “beam” of the n best moves (according to the evaluation function) rather than considering all possible moves.\n",
        "\n",
        "PROBCUT, or probabilistic cut, algorithm:  It computes this probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (α, β)\n",
        "\n",
        "Type B Strategy, i.e. deep but narrow search\n",
        "\n",
        "A , as proposed by Claude Shannon, explores a wide but shallow portion of the tree\n",
        "\n",
        "For games with a large search space, it is not feasible to search the whole tree. As such, we have to make tradeoffs about what part of the tree to search\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "stochastic games:\n",
        "\n",
        "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",
        "A game tree in backgammon must include chance nodes in addition to M A X and M I N nodes.\n",
        "\n",
        "def exp-value(state):\n",
        "  initialize v = 0\n",
        "  for each successor of state:\n",
        "p = probability(successor)\n",
        "   v += p *\n",
        "value(successor)\n",
        "return v\n",
        "\n",
        "This leads us to generalize the minimax value for deterministic games to an expecti- minimax value for games with chance nodes.\n",
        "\n",
        "It turns out that to avoid this sensitivity, the evaluation function must be a positive linear transformation of the probability of winning from a position\n",
        "\n",
        "Because expectiminimax is also considering all the possible dice-roll sequences, it will take O(b^mn^m), where n is the number of distinct rolls.\n",
        "\n",
        "alpha–beta pruning : has upper and lower bounds.  say that all utility values are between −2 and +2;\n",
        "then the value of leaf nodes is bounded, and in turn we can place an upper bound on the value of a chance node without looking at all its children\n",
        "\n",
        "Monte Carlo simulation to evaluate a position. Start with an alpha–beta (or other) search algorithm.\n",
        "From a start position, have the algorithm play thousands of games against itself, using random dice rolls. \n",
        "eg: backgammon, the resulting win percentage has been shown to be a good approximation of the value of the position, even if the algorithm has an imperfect heuristic and is searching only a few plies.\n",
        "For games with dice, this type of simulation is called a rollout.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "Decision theory, in its simplest form, deals with choosing among actions based on the desir- ability of their immediate outcomes;\n",
        "\n",
        "The agent’s preferences are captured by a utility function, U (s)\n",
        "\n",
        "The expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n",
        "\n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n",
        "action = argmax EU (a|e)\n",
        "\n",
        "f 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",
        "chapter16_2 = \"\"\"\n",
        "Constraints on rational preferences:\n",
        "\n",
        " Orderability: Exactlyoneof(A≻B),(B≻A), or(A∼B)holds.\n",
        "\n",
        "  Transitivity: (A≻B)∧(B≻C) ⇒ (A≻C).\n",
        "\n",
        "   Continuity: A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n",
        "\n",
        "   Substitutability: A∼B ⇒ [p,A; 1−p,C]∼[p,B;1−p,C].\n",
        "\n",
        "    Monotonicity: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n",
        "\n",
        "    Decomposability: [p,A; 1−p,[q,B; 1−q,C]]∼[p,A; (1−p)q,B; (1−p)(1−q),C].\n",
        "\n",
        "  Existence of Utility Function: U(A)>U(B) ⇔ A≻B U(A)=U(B) ⇔ A∼B\n",
        "\n",
        "  Expected Utility of a Lottery: U([p1,S1;...;pn,Sn]) =piU(Si) \n",
        "\n",
        "  As in game-playing, in a deterministic environment an agent just needs 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 = \"\"\"\n",
        " build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation,\n",
        "\n",
        " Normalized utilities use a scale with u = 0 and u = 1.\n",
        "\n",
        " Given a utility scale between u and u⊥, we can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [p, u ; (1 − p), u⊥ ].\n",
        "\n",
        " Some attempts have been made to find out the value that people place on their own lives. One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n",
        "\n",
        " Another measure is the QALY, or quality-adjusted life year. Patients with a disability are willing to accept a shorter life expectancy to be restored to full health. For example, kidney patients on average are indifferent between living two years on a dialysis machine and one year at full health.\n",
        "\n",
        "\n",
        "I\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "\n",
        "Most card games (e.g. Hearts, Bridge, etc.) and Scrabble Stochastic, not deterministic\n",
        "Not fully observable: lacking in perfect information\n",
        "o Real-time strategy games\n",
        "Continuous rather than discrete\n",
        "No pause between actions, don’t take turns\n",
        "o Cooperative games\n",
        "\n",
        "Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n",
        "\n",
        "\n",
        "t will usually be the case that an agent prefers more money to less, all other things being equal. We say that the agent exhibits a monotonic preference for more money.\n",
        "\n",
        "Assuming the coin is fair, the expected monetary value (EMV) of the gamble is 1 ($0) 2\n",
        " + 1 ($2,500,000) = $1,250,000, which is more than the original $1,000,000. \n",
        "\n",
        " That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. \n",
        "\n",
        " On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking.\n",
        "\n",
        " The rational way to choose the best action, a∗, is to maximize expected utility: a∗ = argmax EU (a|e) .\n",
        "\n",
        " This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse \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.\n",
        "\n",
        " n other words, there is no utility function that is consistent with these choices. One explanation for the apparently irrational preferences is the certainty effect \n",
        "\n",
        " People know they would experience regret if they gave up a certain reward (B) for an 80% chance at a higher reward and then lost.\n",
        "\n",
        " . It seems that people have ambiguity aversion\n",
        "\n",
        " exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect. \n",
        "\n",
        "  skew upward the customer’s estimate of the value of all wines and make the $55 bottle seem like a bargain. This is called the anchoring effect.\n",
        "\n",
        "  The evidence for human irrationality is also questioned by researchers in the field of evo- lutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal num- bers.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "120d781b-47d9-4beb-d33c-986b03394cd2"
      },
      "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.4 IMPERFECT REAL-TIME DECISIONS\", chapter5_4),\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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \ndeterministic, turn-taking, two-player, zero-sum games of perfect information (such as chess). Strategic:\n\nPruning allows us to ignore portions of the search tree that make no difference to the final choice, and heuristic\n\nevaluation functions allow us to approximate the true utility of a state without doing a complete search.\n\nA game can be formally defined as a kind of search problem with the following elements:\n• S0: The initial state, which specifies how the game is set up at the start.\n• PLAYER(s): Defines which player has the move in a state.\n• ACTIONS(s): Returns the set of legal moves in a state.\n• RESULT(s,a): The transition model, which defines the result of a move.\n• TERMINAL-TEST(s): A terminal test, which is true when the game is over and false\notherwise. States where the game has ended are called terminal states.\n• UTILIT Y (s, p): A utility function (also called an objective function or payoff function),\ndefines the final numeric value for a game that ends in terminal state s for a player p.\n\nA zero-sum game is (confusingly) defined as one where the total payoff to all players\nis the same for every instance of the game.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nThe minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game.\n\nminimax algorithm performs a complete depth-first exploration of the game tree.\n\nIf the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). The space complexity is O(bm).\n\nFor terminal states, this vector gives the utility of the state from each player’s viewpoint. \n\ndef min-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = +∞\n   for each successor of state:\nv = min(v, max-value(successor)) return v\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nThe problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree.\n\nα = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.\nβ = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN.\n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined.\n\n alpha–beta needs to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\n\n\nfunction ALPHA-BETA-SEARCH(state) returns an action v ←MAX-VALUE(state,−∞,+∞)\nreturn the action in ACTIONS(state) with value v\n\nfunction MAX-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s,a), α, β)) ifv ≥ βthenreturnv\nα←MAX(α, v)\nreturn v\n\nfunction MIN-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← +∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s,a) , α, β)) ifv ≤ αthenreturnv\nβ ← MIN(β, v)\nreturn v\n\nOne way to gain information from the current move is with iterative deepening search.\nThe best moves are often called killer moves and to try them first is called the killer move heuristic.\n\nIn many games, repeated states occur frequently because of transpo- sitions—different permutations of the move sequence that end up in the same position.\nThe hash table of previously seen positions is traditionally called a transposition table;\n\n\n\n## AIMA Chapter 5.4 IMPERFECT REAL-TIME DECISIONS\n \nprograms should cut off the search earlier and apply a heuristic evaluation function to states in the search,\n\nreplace the utility function by a heuristic evaluation function EVAL, which estimates the position’s utility, \nand replace the terminal test by a cutoff test that decides when to apply EVAL.\n\nH-MINIMAX(s,d) = \n⎨ EVAL(s) if CUTOFF-TEST(s,d)\n⎩ maxa∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MAX \nmina∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MIN.\n\nAn evaluation function returns an estimate of the expected utility of the game from a given position\n\nFirst, the evaluation function should order the terminal states in the same way as the true utility function: \nstates that are wins must evaluate better than draws, which in turn must be better than losses.\n Otherwise, an agent using the evaluation function might err even if it can see ahead all the way to the end of the game.\nSecond, the computation must not take too long! (The whole point is to search faster.) \nThird, for nonterminal states, the evaluation function should be strongly correlated with the actual chances of winning.\n\n\napply iterative deepening to alpha beta for cutoff test. Iterative also helps in ordering\n\nThe evaluation function should be applied only to positions that are quiescent—that is, unlikely to exhibit wild swings in value in the near future.\n\nThis extra search is called a quiescence search; sometimes it is restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position.\n\nhorizon effect== 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 delaying tactics\n\n(Type -B )forward pruning : beam search: consider only a “beam” of the n best moves (according to the evaluation function) rather than considering all possible moves.\n\nPROBCUT, or probabilistic cut, algorithm:  It computes this probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (α, β)\n\nType B Strategy, i.e. deep but narrow search\n\nA , as proposed by Claude Shannon, explores a wide but shallow portion of the tree\n\nFor games with a large search space, it is not feasible to search the whole tree. As such, we have to make tradeoffs about what part of the tree to search\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nstochastic games:\n\nExplicit randomness: rolling dice\n\nUnpredictable opponents: the opponent isn’t optimal\n\nActions can fail: when moving a robot, wheels might slip\n\nA game tree in backgammon must include chance nodes in addition to M A X and M I N nodes.\n\ndef exp-value(state):\n  initialize v = 0\n  for each successor of state:\np = probability(successor)\n   v += p *\nvalue(successor)\nreturn v\n\nThis leads us to generalize the minimax value for deterministic games to an expecti- minimax value for games with chance nodes.\n\nIt turns out that to avoid this sensitivity, the evaluation function must be a positive linear transformation of the probability of winning from a position\n\nBecause expectiminimax is also considering all the possible dice-roll sequences, it will take O(b^mn^m), where n is the number of distinct rolls.\n\nalpha–beta pruning : has upper and lower bounds.  say that all utility values are between −2 and +2;\nthen the value of leaf nodes is bounded, and in turn we can place an upper bound on the value of a chance node without looking at all its children\n\nMonte Carlo simulation to evaluate a position. Start with an alpha–beta (or other) search algorithm.\nFrom a start position, have the algorithm play thousands of games against itself, using random dice rolls. \neg: backgammon, the resulting win percentage has been shown to be a good approximation of the value of the position, even if the algorithm has an imperfect heuristic and is searching only a few plies.\nFor games with dice, this type of simulation is called a rollout.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory, in its simplest form, deals with choosing among actions based on the desir- ability of their immediate outcomes;\n\nThe agent’s preferences are captured by a utility function, U (s)\n\nThe expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\naction = argmax EU (a|e)\n\nf 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## AIMA Chapter 16.2 The Basis of Utility Theory\n\nConstraints on rational preferences:\n\n Orderability: Exactlyoneof(A≻B),(B≻A), or(A∼B)holds.\n\n  Transitivity: (A≻B)∧(B≻C) ⇒ (A≻C).\n\n   Continuity: A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n\n   Substitutability: A∼B ⇒ [p,A; 1−p,C]∼[p,B;1−p,C].\n\n    Monotonicity: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n\n    Decomposability: [p,A; 1−p,[q,B; 1−q,C]]∼[p,A; (1−p)q,B; (1−p)(1−q),C].\n\n  Existence of Utility Function: U(A)>U(B) ⇔ A≻B U(A)=U(B) ⇔ A∼B\n\n  Expected Utility of a Lottery: U([p1,S1;...;pn,Sn]) =piU(Si) \n\n  As in game-playing, in a deterministic environment an agent just needs 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\n build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation,\n\n Normalized utilities use a scale with u = 0 and u = 1.\n\n Given a utility scale between u and u⊥, we can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [p, u ; (1 − p), u⊥ ].\n\n Some attempts have been made to find out the value that people place on their own lives. One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n\n Another measure is the QALY, or quality-adjusted life year. Patients with a disability are willing to accept a shorter life expectancy to be restored to full health. For example, kidney patients on average are indifferent between living two years on a dialysis machine and one year at full health.\n\n\nI\n\n \n\n## Module 5 Lecture Notes\n\n\nMost card games (e.g. Hearts, Bridge, etc.) and Scrabble Stochastic, not deterministic\nNot fully observable: lacking in perfect information\no Real-time strategy games\nContinuous rather than discrete\nNo pause between actions, don’t take turns\no Cooperative games\n\nValues should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n\n\nt will usually be the case that an agent prefers more money to less, all other things being equal. We say that the agent exhibits a monotonic preference for more money.\n\nAssuming the coin is fair, the expected monetary value (EMV) of the gamble is 1 ($0) 2\n + 1 ($2,500,000) = $1,250,000, which is more than the original $1,000,000. \n\n That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. \n\n On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking.\n\n The rational way to choose the best action, a∗, is to maximize expected utility: a∗ = argmax EU (a|e) .\n\n This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse \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.\n\n n other words, there is no utility function that is consistent with these choices. One explanation for the apparently irrational preferences is the certainty effect \n\n People know they would experience regret if they gave up a certain reward (B) for an 80% chance at a higher reward and then lost.\n\n . It seems that people have ambiguity aversion\n\n exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect. \n\n  skew upward the customer’s estimate of the value of all wines and make the $55 bottle seem like a bargain. This is called the anchoring effect.\n\n  The evidence for human irrationality is also questioned by researchers in the field of evo- lutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal num- bers.\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 = \"\"\"We use a factored representation for each state: a set of variables, each of which has a value.\n",
        "A problem is solved when each variable has a value that satisfies all the constraints on the variable.\n",
        "A problem described this way is called a constraint satisfaction problem,\n",
        "A constraint satisfaction problem consists of three components, X, D, and C :\n",
        "X is a set of variables, {X1,...,Xn}.\n",
        "D is a set of domains, {D1, . . . , Dn}, one for each variable.\\n\n",
        "C is a set of constraints that specify allowable combinations of values.\\n\n",
        "Each state in a CSP is defined by an assignment of values.\\n\n",
        "precedence constraints - one task must happen before the other task \\n\n",
        "disjunctive constraint to say that Axle and Axle must not\\n\n",
        "overlap in time; either one comes first or the other does\\n\n",
        "unary constraint, which restricts the value of a single variable.\n",
        "\n",
        "constraint hypergraph,\\\n",
        "A hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent n-ary constraints.\n",
        "\n",
        "First, it is easier and less error-prone to write the problem description using Alldiff .\n",
        "Second, it is possible to design special-purpose inference algorithms for global constraints that are not available for a set of more primitive constraints.\n",
        "\n",
        "preference constraints - CSPs with preferences can be solved with optimization search methods, either path-based or local\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "In CSPs there is a choice: an algorithm can search (choose a new variable assignment from several possibilities) or\\\n",
        " do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable,\\\n",
        "  which in turn can reduce the legal values for another variable, and so on\n",
        "\n",
        "\n",
        "local consistency. If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an arc,\\\n",
        " then the process of enforcing local con- sistency 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. \n",
        "\n",
        "function AC-3(csp) :\n",
        "returns false if an inconsistency is found and true otherwise \n",
        "inputs: csp, a binary CSP with components (X, D, C)\n",
        "local variables: queue, a queue of arcs, initially all the arcs in csp\n",
        "while queue is not empty do\n",
        "  (Xi, Xj)←REMOVE-FIRST(queue) if REVISE(csp, Xi, Xj) then\n",
        "  if size of Di = 0 then return false\n",
        "  for each Xk in Xi.NEIGHBORS - {Xj} do\n",
        "      add (Xk, Xi) to queue return true\n",
        "\n",
        "function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi revised ← false\n",
        "  for each x in Di do\n",
        "    if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then delete x from Di\n",
        "revised ← true\n",
        "return revised\n",
        "\n",
        "\n",
        "arc consistency is called AC-3\n",
        "\n",
        "consistency of an arc can be done in O(d2) time, so we get O(cd3) total worst-case time.\n",
        "\n",
        "TIME COMPLEXITY FOR STRONGLY K-CONSISTENT: We are guaranteed to find a solution in time O(n^2d). \n",
        "\n",
        "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "\n",
        "Of course, there is no free lunch: any algorithm for establishing n-consistency must take time exponential in n in the worst case.\\\n",
        " Worse, n-consistency also requires space that is exponential in n.\n",
        "\n",
        " resource constraint, sometimes called the atmost constraint. eg: 10 ppl are required to do the job\n",
        "\n",
        "domains are represented by upper and lower bounds and are managed by bounds propagation. EG: moving of lot of ppl\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "\n",
        "CSPs cannot be solved by inference alone; there comes a time when we must search for a solution\n",
        "\n",
        "CSPs are commutative because when assigning values to variables, we reach the same partial assignment regardless of order.\n",
        "\n",
        "function BACKTRACKING-SEARCH(csp) returns a solution, or failure return BACKTRACK({ }, csp)\n",
        "\n",
        "function BACKTRACK(assignment,csp) returns a solution, or failure\n",
        "\n",
        "if assignment is complete then return assignment\n",
        "var ← SELECT-UNASSIGNED-VARIABLE(csp)\n",
        "\n",
        "for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do\n",
        "ifvalueisconsistentwithassignment then add {var = value} to assignment inferences ←INFERENCE(csp,var,value) if inferences ̸= failure then\n",
        "add inferences to assignment\n",
        "result ← BACKTRACK(assignment, csp) if result ̸= failure then\n",
        "return result\n",
        "remove {var = value} and inferences from assignment\n",
        "\n",
        "The term backtracking search is used for a depth-first search\n",
        "\n",
        "BACKTRACKING-SEARCH keeps only a single representation of a state and alters that representation rather than creating new ones,\n",
        "\n",
        "This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum- remaining-values (MRV) heuristic. \n",
        "It also has been called the “most constrained variable” or “fail-first” heuristic, \n",
        "the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \n",
        "\n",
        "The MRV heuristic usually performs better than a random or static ordering, \n",
        "\n",
        " degree heuristic ==It attempts to reduce the branching factor on future choices by selecting the vari- able that is involved in the largest number of constraints on other unassigned variables. \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local search algorithms turn out to be effective in solving many CSPs.\n",
        "They use a complete-state formulation: the initial state assigns a value to every variable, and the search changes the value of one variable at a time.\n",
        "\n",
        "\n",
        "min-conflicts ==the minimum number of conflicts with other variables—the \n",
        "\n",
        "function MIN-CONFLICTS(csp,max steps) returns a solution or failure \n",
        "inputs: csp, a constraint satisfaction problem\n",
        "max steps, the number of steps allowed before giving up\n",
        "current ← an initial complete assignment for csp fori =1tomax steps do\n",
        "if current is a solution for csp then return current\n",
        "var ← a randomly chosen conflicted variable from csp.VARIABLES\n",
        "value ←the value v for var that minimizes CONFLICTS(var,v,current,csp) set var = value in current\n",
        "return failure\n",
        "\n",
        "\n",
        "Plateau search—allowing side- ways moves to another state with the same score—can help local search find its way off this plateau. \n",
        "This wandering on the plateau can be directed with tabu search: \n",
        "keeping a small list of recently visited states and forbidding the algorithm to return to those states. \n",
        "Simulated annealing can also be used to escape from plateaux.\n",
        "\n",
        "\n",
        "constraint weighting, can help concentrate the search on the important constraints.The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment\n",
        "\n",
        "\n",
        "Another advantage of local search is that it can be used in an online setting when the problem changes.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "\n",
        "Independence can be ascertained simply by finding connected components\n",
        "\n",
        "Hence, the total work is O(d^cn/c), which is linear in n(divided into c parts); without the decomposition, the total work is O(dn), which is exponential in n. \n",
        "\n",
        "The key is a new notion of consistency, called directed arc consistency or DAC. A CSP is defined to be directed arc-consistent under an ordering of variables X1 , X2 , . . . , Xn if and only if every Xi is arc-consistent with each Xj forj>i.\n",
        "\n",
        "There are two primary ways to do this, one based on removing nodes and one based on collapsing nodes together.\n",
        "\n",
        "The first approach involves assigning values to some variables so that the remaining variables form a tree.\n",
        "\n",
        "cutset conditioning; ===Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset. \n",
        "\n",
        "tree decomposition== subproblems.\n",
        "\n",
        "\n",
        "• Every variable in the original problem appears in at least one of the subproblems.\n",
        "• If two variables are connected by a constraint in the original problem, they must appear\n",
        "together (along with the constraint) in at least one of the subproblems.\n",
        "• If a variable appears in two subproblems in the tree, it must appear in every subproblem\n",
        "along the path connecting those subproblems.\n",
        "\n",
        "\n",
        "tree width of the graph itself is defined to be the minimum tree width among all its tree decompositions.\n",
        "If a graph has tree width w and we are given the corresponding tree decomposition, then the problem can be solved in O(nd^(w+1)) time. \n",
        "\n",
        "CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n",
        "\n",
        "For example, on the Australia map we know that WA, NT , and SA must all have different colors, but there are 3! = 6 ways to assign the three colors to these three regions. This is called value symmetry. \n",
        "We would like to reduce the search space by a factor of n! by breaking the symmetry. \n",
        "We do this by introducing a symmetry-breaking constraint.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space\n",
        "\n",
        "CSPs are specialized for identification problems\n",
        "\n",
        "\n",
        "All nodes can be connected to every other node,\n",
        "so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\n",
        "o If there are d values, checking arc (i,j) takes O(d2) time\n",
        "o Each arc (i,j) can only be inserted into the queue d times o Worst case complexity: O(n^2d^3)\n",
        "(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd3))\n",
        "\n",
        "MRV heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker.\n",
        "\n",
        "least-constraining-value heuristic  prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n",
        "\n",
        "\n",
        "Why should variable selection be fail-first, but value selection be fail-last? \n",
        "It turns out that, for a wide variety of problems, a variable ordering that chooses a variable with the minimum number of remaining values helps minimize the number of nodes in the search tree by pruning larger parts of the tree earlier. \n",
        "For value ordering, the trick is that we only need one solution; therefore it makes sense to look for the most likely values first. \n",
        "If we wanted to enumerate all solutions rather than just find one, then value ordering would be irrelevant.\n",
        "\n",
        "\n",
        "forward checking.== Whenever a vari- able X is assigned, the forward-checking process establishes arc consistency for it:\n",
        "\n",
        "MAC (for Maintaining Arc Consistency (MAC))==  all Xj that are unassigned variables that are neighbors of Xi. it uses constraint propogation.\n",
        "\n",
        "Looking backward == This is to maintain a conflict set.\n",
        "\n",
        "The backjumping method backtracks to the most recent assignment in the conflict set\n",
        "\n",
        "conflict-directed backjumping. == go to the location of original conflict. \n",
        "\n",
        "When the search arrives at a contradiction, we know that some subset of the conflict set is responsible for the problem.\n",
        "Constraint learning == finding a minimum set of variables from the conflict set that causes the problem. \n",
        "This set of variables, along with their corresponding values, is called a no-good. \n",
        "\n",
        "No-goods can be effectively used by forward checking or by backjumping.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "32502f20-ed3e-4d9c-dbf4-2e8c1be1cb23"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nWe use a factored representation for each state: a set of variables, each of which has a value.\nA problem is solved when each variable has a value that satisfies all the constraints on the variable.\nA problem described this way is called a constraint satisfaction problem,\nA constraint satisfaction problem consists of three components, X, D, and C :\nX is a set of variables, {X1,...,Xn}.\nD is a set of domains, {D1, . . . , Dn}, one for each variable.\n\nC is a set of constraints that specify allowable combinations of values.\n\nEach state in a CSP is defined by an assignment of values.\n\nprecedence constraints - one task must happen before the other task \n\ndisjunctive constraint to say that Axle and Axle must not\n\noverlap in time; either one comes first or the other does\n\nunary constraint, which restricts the value of a single variable.\n\nconstraint hypergraph,A hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent n-ary constraints.\n\nFirst, it is easier and less error-prone to write the problem description using Alldiff .\nSecond, it is possible to design special-purpose inference algorithms for global constraints that are not available for a set of more primitive constraints.\n\npreference constraints - CSPs with preferences can be solved with optimization search methods, either path-based or local\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nIn CSPs there is a choice: an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable,  which in turn can reduce the legal values for another variable, and so on\n\n\nlocal consistency. If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an arc, then the process of enforcing local con- sistency 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. \n\nfunction AC-3(csp) :\nreturns false if an inconsistency is found and true otherwise \ninputs: csp, a binary CSP with components (X, D, C)\nlocal variables: queue, a queue of arcs, initially all the arcs in csp\nwhile queue is not empty do\n  (Xi, Xj)←REMOVE-FIRST(queue) if REVISE(csp, Xi, Xj) then\n  if size of Di = 0 then return false\n  for each Xk in Xi.NEIGHBORS - {Xj} do\n      add (Xk, Xi) to queue return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi revised ← false\n  for each x in Di do\n    if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then delete x from Di\nrevised ← true\nreturn revised\n\n\narc consistency is called AC-3\n\nconsistency of an arc can be done in O(d2) time, so we get O(cd3) total worst-case time.\n\nTIME COMPLEXITY FOR STRONGLY K-CONSISTENT: We are guaranteed to find a solution in time O(n^2d). \n\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n\nOf course, there is no free lunch: any algorithm for establishing n-consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in n.\n\n resource constraint, sometimes called the atmost constraint. eg: 10 ppl are required to do the job\n\ndomains are represented by upper and lower bounds and are managed by bounds propagation. EG: moving of lot of ppl\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n\nCSPs cannot be solved by inference alone; there comes a time when we must search for a solution\n\nCSPs are commutative because when assigning values to variables, we reach the same partial assignment regardless of order.\n\nfunction BACKTRACKING-SEARCH(csp) returns a solution, or failure return BACKTRACK({ }, csp)\n\nfunction BACKTRACK(assignment,csp) returns a solution, or failure\n\nif assignment is complete then return assignment\nvar ← SELECT-UNASSIGNED-VARIABLE(csp)\n\nfor each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do\nifvalueisconsistentwithassignment then add {var = value} to assignment inferences ←INFERENCE(csp,var,value) if inferences ̸= failure then\nadd inferences to assignment\nresult ← BACKTRACK(assignment, csp) if result ̸= failure then\nreturn result\nremove {var = value} and inferences from assignment\n\nThe term backtracking search is used for a depth-first search\n\nBACKTRACKING-SEARCH keeps only a single representation of a state and alters that representation rather than creating new ones,\n\nThis intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum- remaining-values (MRV) heuristic. \nIt also has been called the “most constrained variable” or “fail-first” heuristic, \nthe latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \n\nThe MRV heuristic usually performs better than a random or static ordering, \n\n degree heuristic ==It attempts to reduce the branching factor on future choices by selecting the vari- able that is involved in the largest number of constraints on other unassigned variables. \n\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algorithms turn out to be effective in solving many CSPs.\nThey use a complete-state formulation: the initial state assigns a value to every variable, and the search changes the value of one variable at a time.\n\n\nmin-conflicts ==the minimum number of conflicts with other variables—the \n\nfunction MIN-CONFLICTS(csp,max steps) returns a solution or failure \ninputs: csp, a constraint satisfaction problem\nmax steps, the number of steps allowed before giving up\ncurrent ← an initial complete assignment for csp fori =1tomax steps do\nif current is a solution for csp then return current\nvar ← a randomly chosen conflicted variable from csp.VARIABLES\nvalue ←the value v for var that minimizes CONFLICTS(var,v,current,csp) set var = value in current\nreturn failure\n\n\nPlateau search—allowing side- ways moves to another state with the same score—can help local search find its way off this plateau. \nThis wandering on the plateau can be directed with tabu search: \nkeeping a small list of recently visited states and forbidding the algorithm to return to those states. \nSimulated annealing can also be used to escape from plateaux.\n\n\nconstraint weighting, can help concentrate the search on the important constraints.The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment\n\n\nAnother advantage of local search is that it can be used in an online setting when the problem changes.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n\nIndependence can be ascertained simply by finding connected components\n\nHence, the total work is O(d^cn/c), which is linear in n(divided into c parts); without the decomposition, the total work is O(dn), which is exponential in n. \n\nThe key is a new notion of consistency, called directed arc consistency or DAC. A CSP is defined to be directed arc-consistent under an ordering of variables X1 , X2 , . . . , Xn if and only if every Xi is arc-consistent with each Xj forj>i.\n\nThere are two primary ways to do this, one based on removing nodes and one based on collapsing nodes together.\n\nThe first approach involves assigning values to some variables so that the remaining variables form a tree.\n\ncutset conditioning; ===Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset. \n\ntree decomposition== subproblems.\n\n\n• Every variable in the original problem appears in at least one of the subproblems.\n• If two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the subproblems.\n• If a variable appears in two subproblems in the tree, it must appear in every subproblem\nalong the path connecting those subproblems.\n\n\ntree width of the graph itself is defined to be the minimum tree width among all its tree decompositions.\nIf a graph has tree width w and we are given the corresponding tree decomposition, then the problem can be solved in O(nd^(w+1)) time. \n\nCSPs with constraint graphs of bounded tree width are solvable in polynomial time\n\nFor example, on the Australia map we know that WA, NT , and SA must all have different colors, but there are 3! = 6 ways to assign the three colors to these three regions. This is called value symmetry. \nWe would like to reduce the search space by a factor of n! by breaking the symmetry. \nWe do this by introducing a symmetry-breaking constraint.\n\n\n\n## Module 6 Lecture Notes\n \nAssumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space\n\nCSPs are specialized for identification problems\n\n\nAll nodes can be connected to every other node,\nso each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\no If there are d values, checking arc (i,j) takes O(d2) time\no Each arc (i,j) can only be inserted into the queue d times o Worst case complexity: O(n^2d^3)\n(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd3))\n\nMRV heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker.\n\nleast-constraining-value heuristic  prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n\n\nWhy should variable selection be fail-first, but value selection be fail-last? \nIt turns out that, for a wide variety of problems, a variable ordering that chooses a variable with the minimum number of remaining values helps minimize the number of nodes in the search tree by pruning larger parts of the tree earlier. \nFor value ordering, the trick is that we only need one solution; therefore it makes sense to look for the most likely values first. \nIf we wanted to enumerate all solutions rather than just find one, then value ordering would be irrelevant.\n\n\nforward checking.== Whenever a vari- able X is assigned, the forward-checking process establishes arc consistency for it:\n\nMAC (for Maintaining Arc Consistency (MAC))==  all Xj that are unassigned variables that are neighbors of Xi. it uses constraint propogation.\n\nLooking backward == This is to maintain a conflict set.\n\nThe backjumping method backtracks to the most recent assignment in the conflict set\n\nconflict-directed backjumping. == go to the location of original conflict. \n\nWhen the search arrives at a contradiction, we know that some subset of the conflict set is responsible for the problem.\nConstraint learning == finding a minimum set of variables from the conflict set that causes the problem. \nThis set of variables, along with their corresponding values, is called a no-good. \n\nNo-goods can be effectively used by forward checking or by backjumping.\n\n\n\n\n\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 = \"\"\" \n",
        "The central component of a knowledge-based agent is its knowledge base, or KB.A knowl- edge base is a set of sentences or axiom\n",
        "\n",
        " inference—that is, deriving new sentences from old. ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously.\n",
        "\n",
        " knowledge level, where we need specify only what the agent knows and what its goals are, in order to fix its behavior\n",
        "\n",
        " A knowledge-based agent can be built simply by TELLing it what it needs to know. Starting with an empty knowledge base, \n",
        " the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. \n",
        " This is called the declarative ap- proach to system building\n",
        "\n",
        " he procedural approach encodes desired behaviors directly as program code.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "iscrete, static, and single-agent.It is partially observable.It is sequential, because rewards may come only after many actions are taken. \n",
        "\n",
        "known; or we could say that the transition model itself is unknown because the agent doesn’t know which Forward actions are fatal—in which case, \n",
        "discovering the locations of pits and wumpus completes the agent’s knowledge of the transition model.\n",
        "\n",
        "\n",
        " conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "entences 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",
        "If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.\n",
        "\n",
        "the relation of logical entailment between sentences—the idea that a sentence fol- lows logically from another sentence. eg: α |= β\n",
        "\n",
        "α |= β if and only if M(α)⊆M(β) .\n",
        "\n",
        "model checking, because it enu- merates all possible models to check that α is true in all models in which KB is true, that is, that M(KB) ⊆ M(α).\n",
        "\n",
        "An inference algorithm that derives only entailed sentences is called sound or truth- preserving. \n",
        "\n",
        "completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. \n",
        "\n",
        " grounding—the connection between logical reasoning processes and the real environment in which the agent exists. \n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\n",
        "\n",
        "⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- ditional). \n",
        "Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent is ¬W2,2. \n",
        "Implications are also known as rules or if–then statements. \n",
        "The implication symbol is sometimes written in other books as ⊃ or →.\n",
        "\n",
        "OPERATOR PRECEDENCE::: ¬,∧,∨,⇒,⇔\n",
        "\n",
        "The biconditional, P ⇔ Q, is true whenever both P ⇒ Q and Q ⇒ P are true. In English, this is often written as “P if and only if Q.” \n",
        "\n",
        "If KB and α contain n symbols in all, then there are 2^n models.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "\n",
        "theorem proving—applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n",
        "\n",
        "logical equivalence: two sen- tences α and β are logically equivalent if they are true in the same set of models. We write this as α ≡ β.\n",
        "α≡β ifandonlyif α|=βandβ|=α.\n",
        "\n",
        " validity: A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.\n",
        " by proving that (α ⇒ β) is equivalent to True.\n",
        "\n",
        " satisfiability. A sentence is satisfiable if it is true in, or satisfied by, some model.\n",
        "\n",
        " the SAT problem—was the first problem proved to be NP-complete.\n",
        "\n",
        "Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively, α is satisfiable iff ¬α is not valid. We also have the following useful result:\n",
        "α |= β if and only if the sentence (α ∧ ¬β) is unsatisfiable.\n",
        "\n",
        "It is also called proof by refutation or proof by contradiction. One assumes a sentence β to be false and shows that this leads to a contradiction with known axioms α. \n",
        "This contradiction is exactly what is meant by saying that the sentence (α ∧ ¬β) is unsatisfiable.\n",
        "\n",
        "\n",
        "The best-known rule is called Modus Ponens α ⇒ β, α === β\n",
        "\n",
        " And-Elimination, which says that, from a conjunction, any of the conjuncts can be inferred:α∧β ==α\n",
        "\n",
        " By considering the possible truth values of α and β, one can show easily that Modus Ponens and And-Elimination are sound once and for all.\n",
        "\n",
        " The equivalence for biconditional elimination yields the two inference rules α ⇔ β and (α ⇒ β) ∧ (β ⇒ α) .\n",
        "    (α ⇒ β)∧(β ⇒ α) α ⇔ β\n",
        "\n",
        "     search algorithms  are used\n",
        "\n",
        "monotonicity, which says that the set of en- tailed sentences can only increase as information is added to the knowledge base.8 For any sentences α and β,\n",
        "if KB|=α then KB∧β|=α.\n",
        "\n",
        "resolution, that yields a complete inference algorithm when coupled with any complete search algorithm.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "The forward-chaining algorithm PL-FC-ENTAILS?(KB,q) determines if a single proposi- tion symbol q—the query—is entailed by a knowledge base of definite clauses.\n",
        "\n",
        "It is easy to see that forward chaining is sound: every inference is essentially an appli- cation of Modus Ponens. \n",
        "\n",
        "Forward chaining is also complete: every entailed atomic sentence will be derived. \n",
        "\n",
        "\n",
        "data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n",
        "\n",
        "Backward chaining is a form of goal-directed reasoning.\n",
        "\n",
        "Often, the cost of backward chaining is much less than linear in the size of the knowledge base, because the process touches only relevant facts.\n",
        "\n",
        " The algorithm is essentially identical to the AND-OR-GRAPH-SEARCH algorithm\n",
        "\n",
        "\n",
        " This theorem is proved by demonstrating its contrapositive: if the closure RC(S) does not\n",
        "\n",
        "contain the empty clause, then S is satisfiable. In fact, we can construct a model for S with\n",
        "suitable truth values for P1 , . . . , Pk . The construction procedure is as follows: \n",
        "For i from 1 to k,\n",
        "– If a clause in RC (S) contains the literal ¬Pi and all its other literals are false under the assignment chosen for P1, . . . , Pi−1, then assign false to Pi.\n",
        "– Otherwise, assign true to Pi.\n",
        "nference procedures based on resolution work by using the principle of proof by contradic- tion. That is, to show that KB |= α, we show that (KB ∧ ¬α) is unsatisfiable\n",
        "\n",
        " The empty clause—a disjunction of no disjuncts—is equivalent to False because a disjunction is true only if at least one of its disjuncts is true. \n",
        " \n",
        "\n",
        " PL-RESOLUTION is complete. To do this, we introduce the resolution closure RC (S) of a set of clauses S, which is the set of all clauses derivable by repeated application of the resolution rule to clauses in S or their derivatives.\n",
        " \n",
        " The completeness theorem for resolution in propositional logic is called the ground resolution theorem:\n",
        "If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n",
        "\n",
        "\n",
        "One such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.\n",
        "\n",
        "Horn clause, which is a disjunction of literals of which at most one is positive.\n",
        "\n",
        "So all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n",
        "\n",
        "Advantage of Definite Clauses :\n",
        "\n",
        "Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal. \n",
        "\n",
        "A sentence consisting of a single positive literal, such as L1,1, is called a fact. \n",
        "\n",
        "In Horn form, the premise is called the body and the conclusion is called the head\n",
        "\n",
        "Inference with Horn clauses can be done through the forward-chaining and backward- chaining algorithms.This type of inference is the basis for logic programming,\n",
        "\n",
        "Deciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 61,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ac21aa2a-cec6-4d78-9427-4182fd7773f4"
      },
      "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": 62,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nThe central component of a knowledge-based agent is its knowledge base, or KB.A knowl- edge base is a set of sentences or axiom\n\n inference—that is, deriving new sentences from old. ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously.\n\n knowledge level, where we need specify only what the agent knows and what its goals are, in order to fix its behavior\n\n A knowledge-based agent can be built simply by TELLing it what it needs to know. Starting with an empty knowledge base, \n the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. \n This is called the declarative ap- proach to system building\n\n he procedural approach encodes desired behaviors directly as program code.\n\n\n\n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \niscrete, static, and single-agent.It is partially observable.It is sequential, because rewards may come only after many actions are taken. \n\nknown; or we could say that the transition model itself is unknown because the agent doesn’t know which Forward actions are fatal—in which case, \ndiscovering the locations of pits and wumpus completes the agent’s knowledge of the transition model.\n\n\n conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n \n\n## AIMA Chapter 7.3 Logic\n\nentences 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\nIf a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.\n\nthe relation of logical entailment between sentences—the idea that a sentence fol- lows logically from another sentence. eg: α |= β\n\nα |= β if and only if M(α)⊆M(β) .\n\nmodel checking, because it enu- merates all possible models to check that α is true in all models in which KB is true, that is, that M(KB) ⊆ M(α).\n\nAn inference algorithm that derives only entailed sentences is called sound or truth- preserving. \n\ncompleteness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. \n\n grounding—the connection between logical reasoning processes and the real environment in which the agent exists. \n\n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nThe syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\n\n⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- ditional). \nIts premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent is ¬W2,2. \nImplications are also known as rules or if–then statements. \nThe implication symbol is sometimes written in other books as ⊃ or →.\n\nOPERATOR PRECEDENCE::: ¬,∧,∨,⇒,⇔\n\nThe biconditional, P ⇔ Q, is true whenever both P ⇒ Q and Q ⇒ P are true. In English, this is often written as “P if and only if Q.” \n\nIf KB and α contain n symbols in all, then there are 2^n models.\n\n\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\ntheorem proving—applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n\nlogical equivalence: two sen- tences α and β are logically equivalent if they are true in the same set of models. We write this as α ≡ β.\nα≡β ifandonlyif α|=βandβ|=α.\n\n validity: A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.\n by proving that (α ⇒ β) is equivalent to True.\n\n satisfiability. A sentence is satisfiable if it is true in, or satisfied by, some model.\n\n the SAT problem—was the first problem proved to be NP-complete.\n\nValidity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively, α is satisfiable iff ¬α is not valid. We also have the following useful result:\nα |= β if and only if the sentence (α ∧ ¬β) is unsatisfiable.\n\nIt is also called proof by refutation or proof by contradiction. One assumes a sentence β to be false and shows that this leads to a contradiction with known axioms α. \nThis contradiction is exactly what is meant by saying that the sentence (α ∧ ¬β) is unsatisfiable.\n\n\nThe best-known rule is called Modus Ponens α ⇒ β, α === β\n\n And-Elimination, which says that, from a conjunction, any of the conjuncts can be inferred:α∧β ==α\n\n By considering the possible truth values of α and β, one can show easily that Modus Ponens and And-Elimination are sound once and for all.\n\n The equivalence for biconditional elimination yields the two inference rules α ⇔ β and (α ⇒ β) ∧ (β ⇒ α) .\n    (α ⇒ β)∧(β ⇒ α) α ⇔ β\n\n     search algorithms  are used\n\nmonotonicity, which says that the set of en- tailed sentences can only increase as information is added to the knowledge base.8 For any sentences α and β,\nif KB|=α then KB∧β|=α.\n\nresolution, that yields a complete inference algorithm when coupled with any complete search algorithm.\n\n\n\n\n\n\n \n \n\n## Module 7 Lecture Notes\n \n\nThe forward-chaining algorithm PL-FC-ENTAILS?(KB,q) determines if a single proposi- tion symbol q—the query—is entailed by a knowledge base of definite clauses.\n\nIt is easy to see that forward chaining is sound: every inference is essentially an appli- cation of Modus Ponens. \n\nForward chaining is also complete: every entailed atomic sentence will be derived. \n\n\ndata-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n\nBackward chaining is a form of goal-directed reasoning.\n\nOften, the cost of backward chaining is much less than linear in the size of the knowledge base, because the process touches only relevant facts.\n\n The algorithm is essentially identical to the AND-OR-GRAPH-SEARCH algorithm\n\n\n This theorem is proved by demonstrating its contrapositive: if the closure RC(S) does not\n\ncontain the empty clause, then S is satisfiable. In fact, we can construct a model for S with\nsuitable truth values for P1 , . . . , Pk . The construction procedure is as follows: \nFor i from 1 to k,\n– If a clause in RC (S) contains the literal ¬Pi and all its other literals are false under the assignment chosen for P1, . . . , Pi−1, then assign false to Pi.\n– Otherwise, assign true to Pi.\nnference procedures based on resolution work by using the principle of proof by contradic- tion. That is, to show that KB |= α, we show that (KB ∧ ¬α) is unsatisfiable\n\n The empty clause—a disjunction of no disjuncts—is equivalent to False because a disjunction is true only if at least one of its disjuncts is true. \n \n\n PL-RESOLUTION is complete. To do this, we introduce the resolution closure RC (S) of a set of clauses S, which is the set of all clauses derivable by repeated application of the resolution rule to clauses in S or their derivatives.\n \n The completeness theorem for resolution in propositional logic is called the ground resolution theorem:\nIf a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n\nOne such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.\n\nHorn clause, which is a disjunction of literals of which at most one is positive.\n\nSo all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n\nAdvantage of Definite Clauses :\n\nEvery definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal. \n\nA sentence consisting of a single positive literal, such as L1,1, is called a fact. \n\nIn Horn form, the premise is called the body and the conclusion is called the head\n\nInference with Horn clauses can be done through the forward-chaining and backward- chaining algorithms.This type of inference is the basis for logic programming,\n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base\n \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "00493bc9-e80f-4d06-eee5-0af46a48bcd3"
      },
      "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": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n• natural language processing to enable it to communicate successfully in English;\n• knowledge representation to store what it knows or hears;\n• automated reasoning to use the stored information to answer questions and to draw new conclusions;\n• machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nWe need to get inside the actual workings of human minds.\nthrough introspection—trying to catch our own thoughts as they go by;\nthrough psychological experiments—observing a person in action;\nand through brain imaging—observing the brain in action\n\ncognitive science brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind.\nThese laws of thought were supposed to govern the operation of the mind; their study initiated the field called logic.\n\nFirst, it is not easy to take informal knowledge and state it in the formal terms required by logical notation, \nparticularly when the knowledge is less than 100% certain.\nSecond, there is a big difference between solving a problem “in principle” and solving it in practice.\n\nAn agent is just something that acts (agent comes from the Latin agere, to do). Of course, all computer programs do something, \nbut computer agents are expected to do more: operate autonomously, perceive their environment, persist over a prolonged time period, adapt to change, and create and pursue goals. \nA rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n \nThe rational-agent approach has two advantages over the other approaches. \nFirst, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. \nSecond, it is more amenable to scientific development than are approaches based on human behavior or human thought.\n \n \n\n## AIMA Chapter 27.1 The Limits of AI\n \n\nthe assertion that machines could act as if they were intelligent is called the weak AI hypothesis by philosophers, \nand the assertion that machines that do so are actually thinking (not just simulating thinking) is called the strong AI hypothesis.\n\nPhilosophers such as J. R. Lucas (1961) have claimed that this theorem shows that machines are mentally inferior to humans, because machines are formal systems that are limited by the incompleteness theore\n\nGo ̈del’s incompleteness theorem applies only to formal systems that are powerful enough to do arithmetic.\n\nSecond, an agent should not be too ashamed that it cannot establish the truth of some sentence while other agents can. Consider the sentence\n\neven if we grant that computers have limitations on what they can prove, there is no evidence that humans are immune from those limitations. \n\nThe inability to capture everything in a set of logical rules is called the qualification problem in AI.\n\nGood Old-Fashioned AI,” or GOFAI,\n\no understand how human (or other animal) agents work, we have to consider the whole agent, not just the agent program. Indeed, the embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment. \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n\nconsciousness—the machine has to be aware of its own mental states and actions.\n\nphenomenology, or the study of direct experience: the machine has to actually feel emotions. \nOthers focus on intentionality—that is, the question of whether the machine’s purported beliefs, desires, and\n other representations are actually “about” some- thing in the real world.\n\nPhilosophical efforts to solve this mind–body problem are directly relevant to the question of whether machines could have real minds.\n\nhe monist theory of mind, often called physicalism, avoids this problem by asserting the mind is not separate from the body—that mental states are physical states.\n\nintentional states. These are states, such as believing, knowing, desiring, fearing, and so on, that refer to some aspect of the external world. \n\nThe “wide content” view interprets it from the point of view of an omniscient outside observer with access to the whole situation, who can distinguish differences in the world. \n\nNarrow content, on the other hand, considers only the brain state.\n\nThe theory of functionalism says that a mental state is any intermediate causal condition between input and output.\n\nintuition pump: it amplifies one’s prior intuitions, so biological naturalists are more convinced of their positions, and functionalists are convinced only that axiom 3 is unsupported, or that in general Searle’s argument is unconvincing. \n\nexplanatory gap has led some philosophers to conclude that humans are simply incapable of forming a proper understanding of their own consciousness.\n\ninverted spectrum thought experiment, which the subjective experience of per- son X when seeing red objects is the same experience that the rest of us experience when seeing green objects, and vice versa.\n\nThe technical term for the intrinsic nature of experiences is qualia\n\n\nThere are three possible conclusions:\n1. The causal mechanisms of consciousness that generate these kinds of outputs in normal brains are still operating in the electronic version, which is therefore conscious.\n2. The conscious mental events in the normal brain have no causal connection to behavior, and are missing from the electronic brain, which is therefore not conscious.\n3. The experiment is impossible, and therefore speculation about it is meaningless.\nAlthough we cannot rule out the second possibility, it reduces consciousness to what philoso- phers call an epiphenomenal role\n\n\n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n\nagent function that maps any given percept sequence to an action.\n\nthe agent function for an artificial agent will be implemented by an agent program. \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nA rational agent is one that does the right thing—conceptually speaking, every entry in the table for the agent function is filled out correctly.\n\nperformance measure that evaluates any given sequence of environment states.\n\nRationality\n\nFor each possible percept sequence, a rational agent should select an action that is ex- pected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n• The performance measure that defines the criterion of success.\n• The agent’s prior knowledge of the environment. • The actions that the agent can perform.\n• The agent’s percept sequence to date\n\n An omniscient agent knows the actual outcome of its actions and can act accordingly;\n\n Doing actions in order to modify future percepts—sometimes called information gather\n\n exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts, we say that the agent lacks autonomy. \n\n \n\n## AIMA 2.3 The Nature of Environments\n\nPEAS: performance measure, the environment, and the agent’s actuators and sensors.\n\nsoftware agents:::softbot Web site operator designed to scan Internet news sources and show the interesting items to its users\n\n A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action; relevance, in turn, depends on the performance measure\n\n communication often emerges as a rational behavior in multiagent environments; in some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability.\n\n If the next state of the environment is completely deter- mined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic.\n\n uncertain if it is not fully observable or not deterministic.\n\n a nondeterministic environment is one in which actions are characterized by their possible outcomes, but no probabilities are attached to them. \n\n In an episodic task environment, the agent’s experience is divided into atomic episodes\n\n  Episodic environments are much simpler than sequential environments because the agent does not need to think ahead.\n\n   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 semidynamic.\n\n   In a known environment, the outcomes (or outcome probabilities if the environment is stochastic) for all actions are given.\n\n   It is quite possible for a known environment to be partially observable—for example, in solitaire card games, I know the rules but am still unable to see the cards that have not yet been turned over. \n\n   environment generator for each environment class that selects particular environments (with certain likelihoods) in which to run the agent.\n\n  \n\n\n\n## AIMA 2.4 The Structure of Agents\n \n\nagent = architecture + program .\n\nThe lookup table will contain 􏰂Tt = 1 |P|t entries.\n\nThe daunting size of these tables (the number of atoms in the observable universe is less than 1080) means that (a) no physical agent in this universe will have the space to store the table, (b) the designer would not have time to create the table, (c) no agent could ever learn all the right table entries from its experience, and (d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries.\n\n• Simple reflex agents;\n• Model-based reflex agents; • Goal-based agents; and\n• Utility-based agents.\n\nsimple reflex agent. These agents select actions on the basis of the current percept, ignoring the rest of the percept history\n\nEscape from infinite loops is possible if the agent can randomize its actions.\n\n\nModel-based reflex agents\nThe most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now. \nThat is, the agent should maintain some sort of internal state that depends on the percept history \n\n First, we need some information about how the world evolves independently of the agent—for example, that an overtaking car generally will be closer behind than it was a moment ago. \n Second, we need some information about how the agent’s own actions affect the world—\n\n  implemented in simple Boolean circuits or in complete scientific theories—is called a model of the world. An agent that uses such a model is called a model-based agent.\n\n\nGoal-based agents\nn other words, as well as a current state description, the agent needs some sort of goal information that describes situations that are desirable\nSearch  and planning  to find goal\n\nUtility-based agents\nn agent’s utility function is essentially an internalization of the performance measure. \nIf the internal utility function and the external performance measure are in agreement, \nthen an agent that chooses actions to maximize its utility will be rational according to the external performance measure\n\nFirst, when there are conflicting goals, only some of which can be achieved (for example, speed and safety),\n the utility function specifies the appropriate tradeoff. \nSecond, when there are several goals that the agent can aim for, none of which can be achieved with certainty,\n utility provides a way in which the likelihood of success can be weighed against the importance of the goals.\n\n Learning agents::: creating state-of-the-art systems.Learning in intelligent agents can be summarized as a process of modification of each component of the agent to bring \n the components into closer agreement with the available feedback information, \n thereby improv- ing the overall performance of the agent.\n\n\n\n\n## Module 1 Lecture Notes\n \n learning element, which is re- sponsible for making improvements, and the performance element, which is responsible for selecting external actions.\n\n 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 he performance standard distinguishes part of the incoming percept as a reward (or penalty) that provides direct feedback on the quality of the agent’s behavior\n\n atomic, factored, and structured.\n\n atomic representation each state of the world is indivisible—it has no internal structure. search and game-playing, Hidden Markov models, and Markov decision processes \n\n  A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value.\n  factored representations, including constraint satisfaction algorithms ,propositional logic, planning, Bayesian networks, and the machine learning \n\n  Structured representations underlie relational databases and first-order logic , first-order probability models, knowledge-based learning \n\n  the axis along which atomic, factored, and structured repre- sentations lie is the axis of increasing expressiveness.\n  \n  easoning and learning become more complex as the expressive power of the representation increases.\n   To gain the benefits of expressive representations while avoiding their drawbacks, \n   intelligent systems for the real world may need to operate at all points along the axis simultaneously.\n\n\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n\nAll data treated as objects\nAn object is deleted (by garbage collection) once unreachable.\n\nStrong Typing\nEvery object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2) type(object) isinstance(object, type)\n\nJava: static typing\nVariables can only refer to objects of a declared type\nint x = 2\nString y = \"foo\"\n  Methods use type signatures to enforce contracts\n  public static void main(String[] args)\no Python: dynamic typing\nVariables come into existence when first assigned.\n>>> x = \"foo\"\n>>> x = 2\n\nprint(\"%s can speak %d languages\" % (\"C3PO\", 6000000)) --- Immutable (String)\n\n \"_\".join(words)\n\n d = {'user' : 'R2D2', 'pswd': 1234}----Dictionary ;;;  d.keys() ;;;d.values()   ;;;;  d.items()\n\n \n\n defaultdict automatically initializes nonexistent dictionary values\n\n from collections import Counter d = Counter()\n\nd['a']\n\n0 //op\n\n d['dog'] += 10\n\n d['dog']\n\n 10//op\n\n\n The return type is a tuple\n\n  print_everything(*lst)\n\n\n  **kwargs ---Suppose you want to accept a variable number of keyword arguments to your function.\n  my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)\n\n\n  def myfun(positional, *args, **kwargs):\n    print(positional)\n    if args:\n        print(args)\n    if kwargs:\n        print(kwargs)\n\n        \n\n\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 Goal formulation is the first step in problem defination.\nProblem formulation is the process of deciding what actions and states to consider, given a goal.\n\nwhile the agent is executing the solution sequence it ignores its percepts when choosing an action---Control theorists call this an open-loop system,\n\nA problem can be defined formally by five components:\n\nThe initial state \nA description of the possible actions available to the agent.\nA description of what each action does; the formal name for this is the transition model, successor to refer to any state reachable from a given state by a single action\nA path in the state space is a sequence of states connected by a sequence of actions.\ngoal test, which determines whether a given state is a goal state. \nA path cost function that assigns a numeric cost to each path.\n\nThe process of removing detail from a representation is called abstraction.\n\n\nfunction SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action persistent: seq, an action sequence, initially empty\nstate, some description of the current world state goal, a goal, initially null\nproblem, a problem formulation\nstate ← UPDATE-STATE(state,percept) if seq is empty then\ngoal ← FORMULATE-GOAL(state)\nproblem ←FORMULATE-PROBLEM(state,goal) seq ← SEARCH(problem)\nif seq = failure then return a null action\naction ← FIRST(seq) seq ← REST(seq) return action\n\n\n## AIMA Chapter 3.2 Example Problems\n \nA larger environment with n locations has n · 2n states.\n\n8-puzzle belongs to the family of sliding-block puzzles,--np complete\n\nn-queens family, ::An incremental formulation,  A complete-state formulation \n\n traveling salesperson problem (TSP) : np-hard \n\n\nCriterion\n          Breadth-      Uniform-     Depth-     Depth-lim     Iterative-deep    Bidirectional (if applicable)\nComplete?   Yes           Yes         No.        No               Yes.                      Yes\nTime.       O(b^d)    O(b1+⌊C∗/ε⌋)    O(b^m)     O(b^l)               O(b^d)              O(b^d/2)\nSpace       O(b^d)    O(b1+⌊C∗/ε⌋)    O(bm)     O(bl)               O(bd)               O(bd/2)\nOptimal?    Yes           Yes         No.        No                 Yes.                      Yes\n\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n\nfunction TREE-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier\n\n\nfunction GRAPH-SEARCH(problem) returns a solution, or failure initialize the frontier using the initial state of problem\ninitialize the explored set to be empty\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution add the node to the explored set\nexpand the chosen node, adding the resulting nodes to the frontier\nonly if not in the frontier or explored set\n\n\nwe have a structure that contains four components\n• n.STATE:\n• n.PARENT: \n• n.ACTION: \n• n.PATH-COST: g(n), of the path from the initial state to the node,\n\nthe next node to expand according to its preferred strategy\n\nevaluate an algorithm’s performance in four ways:\n• Completeness:  • Optimality:  • Time complexity: • Space complexity:\n\ncomplexity\nb, the branching ;;; d, the depth of the shallowest goal node ;;;;m, the maximum length of any path in the state space;;;\n\ntotal cost, which combines the search cost and the path cost of the solution found\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS: complete (provided the branching factor b is finite))\n\nbreadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node.\n\nO(bd): time ans space complexity\n\nUniform-cost search:\n\nexpands the node n with the lowest path cost g(n).\n\npriority queue ordered by g\n\nDiff between bfs and UCS:\n\ngoal test is applied to a node when it is selected for expansion rather than when it is first generated.\n\nThe second difference is that a test is added in case a better path is found to a node currently on the frontier.\n\noptimal,Completeness is guaranteed provided the cost of every step exceeds some small positive constant ε. h does not care about the number of steps a path has, but only about their total cost. \nTherefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions\n\ntime and space:  O(b^(1+\u0004C∗/ε)\u0005),\n\nDFS:\n\nThe graph-search version, which avoids repeated states and re- dundant paths, is complete in finite state spaces because it will eventually expand every node. \nThe tree-search version, on the other hand, is not complete\n\n both versions are nonoptimal. \n\n all of the O(b^m) nodes in the search tree, where m is the maximum depth of any node;\n\n For a state space with branching factor b and maximum depth m, depth-first search requires storage of only O(bm) nodes.\n\n Depth limited search :\n\n\n\n\n\n\n## Module 3 Lecture Notes\n \n\n Depth-limited search will also be nonoptimal if we choose l > d. Its time complexity is O(b^l) and its space complexity is O(bl). Depth-first search can be viewed as a special case of depth-limited search with l = ∞.\nfunction DEPTH-LIMITED-SEARCH(problem,limit) returns a solution, or failure/cutoff return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit)\nfunction RECURSIVE-DLS(node,problem,limit) returns a solution, or failure/cutoff if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\nelse if limit = 0 then return cutoff\nelse\ncutoff occurred?←false\nfor each action in problem.ACTIONS(node.STATE) do\nchild ←CHILD-NODE(problem,node,action) result←RECURSIVE-DLS(child,problem,limit −1) if result = cutoff then cutoff occurred ? ← true\nelse if result ̸= failure then return result\nif cutoff occurred? then return cutoff else return failure\n\n\ndepth-limited search can terminate with two kinds of failure: the standard failure value indicates no solution; the cutoff value indicates no solution within the depth limit.\n\n\nIterative deepening search\n\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure fordepth =0to∞do\nresult ←DEPTH-LIMITED-SEARCH(problem,depth) if result ̸= cutoff then return result\n\nmemory requirements are modest: O(bd) to be precise.  and time complexity of O(b^d)\n\nIn general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.\n\nincreasing path-cost limits instead of increasing depth limits. The resulting algorithm, called iterative lengthening search, \n\n\nBidirectional search\n\nThe idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal\n\nb^d/2 + b^d/2  - time and space (This space requirement is the most significant weakness of bidirectional se)\n\nBidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect;\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 \n\nbest-first search\n\nThe implementation of best-first graph search is identical to that for uniform-cost search \n\nTREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f(n)\n\nh(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n\nGreedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly.\nheuristic function; that is, f (n) = h(n).\n\nGreedy best-first tree search is also incomplete even in a finite state space, much like depth-first search\n\nworst-case time and space complexity for the tree version is O(b^m), where m is the maximum depth of the search space.\n\nA* search:\n\nIt evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:\n\nboth complete and optimal. \n A∗ expands no nodes with f(n) > C∗\n A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaran- teed to expand fewer nodes than A∗\n\nAn admissible heuristic is one that never overestimates the cost to reach the goal.\nAdmissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.\n\nA heuristic h(n) is consistent if, for every node n and every successor n'\u0002 of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n\u0002' plus the estimated cost of reaching the goal from n'\u0002:\nh(n) ≤ c(n, a, n'\u0002) + h(n'\u0002) . (Triangle inequality)\n\n\ntree-search version of A∗ is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent.\n\nA∗ selects a node n for expansion, the optimal path to that node has been found.\n\nW\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n\nThe effect of heuristic accuracy on performance\neffective branching factor b∗. \n\nA well- designed heuristic would have a value of b∗ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\n\n h2(n) ≥ h1(n). We thus say that h2 dominates h1. Domination translates directly into efficiency:\n\n A problem with fewer restrictions on the actions is called a relaxed problem.\n\nthe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nFurthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n\nA program called ABSOLVER can generate heuristics automatically from problem def- initions, using the “relaxed problem” method \n\nThe idea behind pattern databases is to store these exact solution costs for every pos- sible subproblem instance\n\nThat is, we record not the total cost of solving the 1-2- 3-4 subproblem, but just the number of moves involving 1-2-3-4. \nThen it is easy to see that the sum of the two costs is still a lower bound on the cost of solving the entire problem. \nThis is the idea behind disjoint pattern databases.\n\n\n\n\n## Module 4 Lecture Notes\n ith uniform-cost search (A∗ search using h(n) = 0), the bands will be “circular” around the start state.\n With more accurate heuristics, the bands will stretch toward the goal state and become more narrowly focused around the optimal path.\n\n O(b^(εd)) = O((b^ε)^d), so the effective branching factor (defined more formally in the next section) is b^ε.\n\n Because it keeps all generated nodes in memory (as do all GRAPH-SEARCH algorithms), A∗ usually runs out of space long before it runs out of time. \n For this reason, A∗ is not practical for many large-scale prob- lems.\n\n\nreduce memory requirements for A∗:: iterative-deepening A∗ (IDA∗) \n\nRecursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the operation of standard best-first search, but using only linear space\n\nRBFS is somewhat more efficient than IDA∗, but still suffers from excessive node re- generation.  RBFS is an optimal algorithm \n\nit depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded.\n\nIDA∗ and RBFS suffer from using too little memory. Because they forget most of what they have done, both algorithms may end up reex- panding the same states many times ove\n\n\nMA∗ (memory-bounded A∗) and SMA∗ (simplified MA∗).\n\nSMA∗ is complete if there is any reachable solution—that is, if d, the depth of the shallowest goal node, is less than the memory size (expressed in nodes).\n It is optimal if any optimal solution is reachable; otherwise, it returns the best reachable solution. \n In practical terms, SMA∗ is a fairly robust choice for finding optimal solutions, particularly when the state space is a graph, step costs are not uniform, \n and node generation is expensive compared to the overhead of maintaining the frontier and the explored set.\n\n\nmetalevel state space.::Each state in a metalevel state space captures the internal (computational) state of a program that is searching in an object-level state space \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 \ndeterministic, turn-taking, two-player, zero-sum games of perfect information (such as chess). Strategic:\n\nPruning allows us to ignore portions of the search tree that make no difference to the final choice, and heuristic\n\nevaluation functions allow us to approximate the true utility of a state without doing a complete search.\n\nA game can be formally defined as a kind of search problem with the following elements:\n• S0: The initial state, which specifies how the game is set up at the start.\n• PLAYER(s): Defines which player has the move in a state.\n• ACTIONS(s): Returns the set of legal moves in a state.\n• RESULT(s,a): The transition model, which defines the result of a move.\n• TERMINAL-TEST(s): A terminal test, which is true when the game is over and false\notherwise. States where the game has ended are called terminal states.\n• UTILIT Y (s, p): A utility function (also called an objective function or payoff function),\ndefines the final numeric value for a game that ends in terminal state s for a player p.\n\nA zero-sum game is (confusingly) defined as one where the total payoff to all players\nis the same for every instance of the game.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nThe minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game.\n\nminimax algorithm performs a complete depth-first exploration of the game tree.\n\nIf the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). The space complexity is O(bm).\n\nFor terminal states, this vector gives the utility of the state from each player’s viewpoint. \n\ndef min-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = +∞\n   for each successor of state:\nv = min(v, max-value(successor)) return v\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nThe problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree.\n\nα = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.\nβ = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN.\n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined.\n\n alpha–beta needs to examine only O(b^(m/2)) nodes to pick the best move, instead of O(b^m) for minimax.\n\n\nfunction ALPHA-BETA-SEARCH(state) returns an action v ←MAX-VALUE(state,−∞,+∞)\nreturn the action in ACTIONS(state) with value v\n\nfunction MAX-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s,a), α, β)) ifv ≥ βthenreturnv\nα←MAX(α, v)\nreturn v\n\nfunction MIN-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← +∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s,a) , α, β)) ifv ≤ αthenreturnv\nβ ← MIN(β, v)\nreturn v\n\nOne way to gain information from the current move is with iterative deepening search.\nThe best moves are often called killer moves and to try them first is called the killer move heuristic.\n\nIn many games, repeated states occur frequently because of transpo- sitions—different permutations of the move sequence that end up in the same position.\nThe hash table of previously seen positions is traditionally called a transposition table;\n\n\n\n## AIMA Chapter 5.4 IMPERFECT REAL-TIME DECISIONS\n \nprograms should cut off the search earlier and apply a heuristic evaluation function to states in the search,\n\nreplace the utility function by a heuristic evaluation function EVAL, which estimates the position’s utility, \nand replace the terminal test by a cutoff test that decides when to apply EVAL.\n\nH-MINIMAX(s,d) = \n⎨ EVAL(s) if CUTOFF-TEST(s,d)\n⎩ maxa∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MAX \nmina∈Actions(s) H-MINIMAX(RESULT(s, a), d + 1)  if PLAYER(s) = MIN.\n\nAn evaluation function returns an estimate of the expected utility of the game from a given position\n\nFirst, the evaluation function should order the terminal states in the same way as the true utility function: \nstates that are wins must evaluate better than draws, which in turn must be better than losses.\n Otherwise, an agent using the evaluation function might err even if it can see ahead all the way to the end of the game.\nSecond, the computation must not take too long! (The whole point is to search faster.) \nThird, for nonterminal states, the evaluation function should be strongly correlated with the actual chances of winning.\n\n\napply iterative deepening to alpha beta for cutoff test. Iterative also helps in ordering\n\nThe evaluation function should be applied only to positions that are quiescent—that is, unlikely to exhibit wild swings in value in the near future.\n\nThis extra search is called a quiescence search; sometimes it is restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position.\n\nhorizon effect== 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 delaying tactics\n\n(Type -B )forward pruning : beam search: consider only a “beam” of the n best moves (according to the evaluation function) rather than considering all possible moves.\n\nPROBCUT, or probabilistic cut, algorithm:  It computes this probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (α, β)\n\nType B Strategy, i.e. deep but narrow search\n\nA , as proposed by Claude Shannon, explores a wide but shallow portion of the tree\n\nFor games with a large search space, it is not feasible to search the whole tree. As such, we have to make tradeoffs about what part of the tree to search\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nstochastic games:\n\nExplicit randomness: rolling dice\n\nUnpredictable opponents: the opponent isn’t optimal\n\nActions can fail: when moving a robot, wheels might slip\n\nA game tree in backgammon must include chance nodes in addition to M A X and M I N nodes.\n\ndef exp-value(state):\n  initialize v = 0\n  for each successor of state:\np = probability(successor)\n   v += p *\nvalue(successor)\nreturn v\n\nThis leads us to generalize the minimax value for deterministic games to an expecti- minimax value for games with chance nodes.\n\nIt turns out that to avoid this sensitivity, the evaluation function must be a positive linear transformation of the probability of winning from a position\n\nBecause expectiminimax is also considering all the possible dice-roll sequences, it will take O(b^mn^m), where n is the number of distinct rolls.\n\nalpha–beta pruning : has upper and lower bounds.  say that all utility values are between −2 and +2;\nthen the value of leaf nodes is bounded, and in turn we can place an upper bound on the value of a chance node without looking at all its children\n\nMonte Carlo simulation to evaluate a position. Start with an alpha–beta (or other) search algorithm.\nFrom a start position, have the algorithm play thousands of games against itself, using random dice rolls. \neg: backgammon, the resulting win percentage has been shown to be a good approximation of the value of the position, even if the algorithm has an imperfect heuristic and is searching only a few plies.\nFor games with dice, this type of simulation is called a rollout.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory, in its simplest form, deals with choosing among actions based on the desir- ability of their immediate outcomes;\n\nThe agent’s preferences are captured by a utility function, U (s)\n\nThe expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\naction = argmax EU (a|e)\n\nf 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## AIMA Chapter 16.2 The Basis of Utility Theory\n\nConstraints on rational preferences:\n\n Orderability: Exactlyoneof(A≻B),(B≻A), or(A∼B)holds.\n\n  Transitivity: (A≻B)∧(B≻C) ⇒ (A≻C).\n\n   Continuity: A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n\n   Substitutability: A∼B ⇒ [p,A; 1−p,C]∼[p,B;1−p,C].\n\n    Monotonicity: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n\n    Decomposability: [p,A; 1−p,[q,B; 1−q,C]]∼[p,A; (1−p)q,B; (1−p)(1−q),C].\n\n  Existence of Utility Function: U(A)>U(B) ⇔ A≻B U(A)=U(B) ⇔ A∼B\n\n  Expected Utility of a Lottery: U([p1,S1;...;pn,Sn]) =piU(Si) \n\n  As in game-playing, in a deterministic environment an agent just needs 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\n build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation,\n\n Normalized utilities use a scale with u = 0 and u = 1.\n\n Given a utility scale between u and u⊥, we can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [p, u ; (1 − p), u⊥ ].\n\n Some attempts have been made to find out the value that people place on their own lives. One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n\n Another measure is the QALY, or quality-adjusted life year. Patients with a disability are willing to accept a shorter life expectancy to be restored to full health. For example, kidney patients on average are indifferent between living two years on a dialysis machine and one year at full health.\n\n\nI\n\n \n\n## Module 5 Lecture Notes\n\n\nMost card games (e.g. Hearts, Bridge, etc.) and Scrabble Stochastic, not deterministic\nNot fully observable: lacking in perfect information\no Real-time strategy games\nContinuous rather than discrete\nNo pause between actions, don’t take turns\no Cooperative games\n\nValues should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n\n\nt will usually be the case that an agent prefers more money to less, all other things being equal. We say that the agent exhibits a monotonic preference for more money.\n\nAssuming the coin is fair, the expected monetary value (EMV) of the gamble is 1 ($0) 2\n + 1 ($2,500,000) = $1,250,000, which is more than the original $1,000,000. \n\n That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. \n\n On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking.\n\n The rational way to choose the best action, a∗, is to maximize expected utility: a∗ = argmax EU (a|e) .\n\n This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse \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.\n\n n other words, there is no utility function that is consistent with these choices. One explanation for the apparently irrational preferences is the certainty effect \n\n People know they would experience regret if they gave up a certain reward (B) for an 80% chance at a higher reward and then lost.\n\n . It seems that people have ambiguity aversion\n\n exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect. \n\n  skew upward the customer’s estimate of the value of all wines and make the $55 bottle seem like a bargain. This is called the anchoring effect.\n\n  The evidence for human irrationality is also questioned by researchers in the field of evo- lutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal num- bers.\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\nWe use a factored representation for each state: a set of variables, each of which has a value.\nA problem is solved when each variable has a value that satisfies all the constraints on the variable.\nA problem described this way is called a constraint satisfaction problem,\nA constraint satisfaction problem consists of three components, X, D, and C :\nX is a set of variables, {X1,...,Xn}.\nD is a set of domains, {D1, . . . , Dn}, one for each variable.\n\nC is a set of constraints that specify allowable combinations of values.\n\nEach state in a CSP is defined by an assignment of values.\n\nprecedence constraints - one task must happen before the other task \n\ndisjunctive constraint to say that Axle and Axle must not\n\noverlap in time; either one comes first or the other does\n\nunary constraint, which restricts the value of a single variable.\n\nconstraint hypergraph,A hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent n-ary constraints.\n\nFirst, it is easier and less error-prone to write the problem description using Alldiff .\nSecond, it is possible to design special-purpose inference algorithms for global constraints that are not available for a set of more primitive constraints.\n\npreference constraints - CSPs with preferences can be solved with optimization search methods, either path-based or local\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nIn CSPs there is a choice: an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable,  which in turn can reduce the legal values for another variable, and so on\n\n\nlocal consistency. If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an arc, then the process of enforcing local con- sistency 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. \n\nfunction AC-3(csp) :\nreturns false if an inconsistency is found and true otherwise \ninputs: csp, a binary CSP with components (X, D, C)\nlocal variables: queue, a queue of arcs, initially all the arcs in csp\nwhile queue is not empty do\n  (Xi, Xj)←REMOVE-FIRST(queue) if REVISE(csp, Xi, Xj) then\n  if size of Di = 0 then return false\n  for each Xk in Xi.NEIGHBORS - {Xj} do\n      add (Xk, Xi) to queue return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi revised ← false\n  for each x in Di do\n    if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then delete x from Di\nrevised ← true\nreturn revised\n\n\narc consistency is called AC-3\n\nconsistency of an arc can be done in O(d2) time, so we get O(cd3) total worst-case time.\n\nTIME COMPLEXITY FOR STRONGLY K-CONSISTENT: We are guaranteed to find a solution in time O(n^2d). \n\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n\nOf course, there is no free lunch: any algorithm for establishing n-consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in n.\n\n resource constraint, sometimes called the atmost constraint. eg: 10 ppl are required to do the job\n\ndomains are represented by upper and lower bounds and are managed by bounds propagation. EG: moving of lot of ppl\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n\nCSPs cannot be solved by inference alone; there comes a time when we must search for a solution\n\nCSPs are commutative because when assigning values to variables, we reach the same partial assignment regardless of order.\n\nfunction BACKTRACKING-SEARCH(csp) returns a solution, or failure return BACKTRACK({ }, csp)\n\nfunction BACKTRACK(assignment,csp) returns a solution, or failure\n\nif assignment is complete then return assignment\nvar ← SELECT-UNASSIGNED-VARIABLE(csp)\n\nfor each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do\nifvalueisconsistentwithassignment then add {var = value} to assignment inferences ←INFERENCE(csp,var,value) if inferences ̸= failure then\nadd inferences to assignment\nresult ← BACKTRACK(assignment, csp) if result ̸= failure then\nreturn result\nremove {var = value} and inferences from assignment\n\nThe term backtracking search is used for a depth-first search\n\nBACKTRACKING-SEARCH keeps only a single representation of a state and alters that representation rather than creating new ones,\n\nThis intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum- remaining-values (MRV) heuristic. \nIt also has been called the “most constrained variable” or “fail-first” heuristic, \nthe latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \n\nThe MRV heuristic usually performs better than a random or static ordering, \n\n degree heuristic ==It attempts to reduce the branching factor on future choices by selecting the vari- able that is involved in the largest number of constraints on other unassigned variables. \n\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algorithms turn out to be effective in solving many CSPs.\nThey use a complete-state formulation: the initial state assigns a value to every variable, and the search changes the value of one variable at a time.\n\n\nmin-conflicts ==the minimum number of conflicts with other variables—the \n\nfunction MIN-CONFLICTS(csp,max steps) returns a solution or failure \ninputs: csp, a constraint satisfaction problem\nmax steps, the number of steps allowed before giving up\ncurrent ← an initial complete assignment for csp fori =1tomax steps do\nif current is a solution for csp then return current\nvar ← a randomly chosen conflicted variable from csp.VARIABLES\nvalue ←the value v for var that minimizes CONFLICTS(var,v,current,csp) set var = value in current\nreturn failure\n\n\nPlateau search—allowing side- ways moves to another state with the same score—can help local search find its way off this plateau. \nThis wandering on the plateau can be directed with tabu search: \nkeeping a small list of recently visited states and forbidding the algorithm to return to those states. \nSimulated annealing can also be used to escape from plateaux.\n\n\nconstraint weighting, can help concentrate the search on the important constraints.The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment\n\n\nAnother advantage of local search is that it can be used in an online setting when the problem changes.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n\nIndependence can be ascertained simply by finding connected components\n\nHence, the total work is O(d^cn/c), which is linear in n(divided into c parts); without the decomposition, the total work is O(dn), which is exponential in n. \n\nThe key is a new notion of consistency, called directed arc consistency or DAC. A CSP is defined to be directed arc-consistent under an ordering of variables X1 , X2 , . . . , Xn if and only if every Xi is arc-consistent with each Xj forj>i.\n\nThere are two primary ways to do this, one based on removing nodes and one based on collapsing nodes together.\n\nThe first approach involves assigning values to some variables so that the remaining variables form a tree.\n\ncutset conditioning; ===Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset. \n\ntree decomposition== subproblems.\n\n\n• Every variable in the original problem appears in at least one of the subproblems.\n• If two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the subproblems.\n• If a variable appears in two subproblems in the tree, it must appear in every subproblem\nalong the path connecting those subproblems.\n\n\ntree width of the graph itself is defined to be the minimum tree width among all its tree decompositions.\nIf a graph has tree width w and we are given the corresponding tree decomposition, then the problem can be solved in O(nd^(w+1)) time. \n\nCSPs with constraint graphs of bounded tree width are solvable in polynomial time\n\nFor example, on the Australia map we know that WA, NT , and SA must all have different colors, but there are 3! = 6 ways to assign the three colors to these three regions. This is called value symmetry. \nWe would like to reduce the search space by a factor of n! by breaking the symmetry. \nWe do this by introducing a symmetry-breaking constraint.\n\n\n\n## Module 6 Lecture Notes\n \nAssumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space\n\nCSPs are specialized for identification problems\n\n\nAll nodes can be connected to every other node,\nso each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\no If there are d values, checking arc (i,j) takes O(d2) time\no Each arc (i,j) can only be inserted into the queue d times o Worst case complexity: O(n^2d^3)\n(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd3))\n\nMRV heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker.\n\nleast-constraining-value heuristic  prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n\n\nWhy should variable selection be fail-first, but value selection be fail-last? \nIt turns out that, for a wide variety of problems, a variable ordering that chooses a variable with the minimum number of remaining values helps minimize the number of nodes in the search tree by pruning larger parts of the tree earlier. \nFor value ordering, the trick is that we only need one solution; therefore it makes sense to look for the most likely values first. \nIf we wanted to enumerate all solutions rather than just find one, then value ordering would be irrelevant.\n\n\nforward checking.== Whenever a vari- able X is assigned, the forward-checking process establishes arc consistency for it:\n\nMAC (for Maintaining Arc Consistency (MAC))==  all Xj that are unassigned variables that are neighbors of Xi. it uses constraint propogation.\n\nLooking backward == This is to maintain a conflict set.\n\nThe backjumping method backtracks to the most recent assignment in the conflict set\n\nconflict-directed backjumping. == go to the location of original conflict. \n\nWhen the search arrives at a contradiction, we know that some subset of the conflict set is responsible for the problem.\nConstraint learning == finding a minimum set of variables from the conflict set that causes the problem. \nThis set of variables, along with their corresponding values, is called a no-good. \n\nNo-goods can be effectively used by forward checking or by backjumping.\n\n\n\n\n\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 \nThe central component of a knowledge-based agent is its knowledge base, or KB.A knowl- edge base is a set of sentences or axiom\n\n inference—that is, deriving new sentences from old. ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously.\n\n knowledge level, where we need specify only what the agent knows and what its goals are, in order to fix its behavior\n\n A knowledge-based agent can be built simply by TELLing it what it needs to know. Starting with an empty knowledge base, \n the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. \n This is called the declarative ap- proach to system building\n\n he procedural approach encodes desired behaviors directly as program code.\n\n\n\n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \niscrete, static, and single-agent.It is partially observable.It is sequential, because rewards may come only after many actions are taken. \n\nknown; or we could say that the transition model itself is unknown because the agent doesn’t know which Forward actions are fatal—in which case, \ndiscovering the locations of pits and wumpus completes the agent’s knowledge of the transition model.\n\n\n conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n \n\n## AIMA Chapter 7.3 Logic\n\nentences 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\nIf a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.\n\nthe relation of logical entailment between sentences—the idea that a sentence fol- lows logically from another sentence. eg: α |= β\n\nα |= β if and only if M(α)⊆M(β) .\n\nmodel checking, because it enu- merates all possible models to check that α is true in all models in which KB is true, that is, that M(KB) ⊆ M(α).\n\nAn inference algorithm that derives only entailed sentences is called sound or truth- preserving. \n\ncompleteness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. \n\n grounding—the connection between logical reasoning processes and the real environment in which the agent exists. \n\n\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nThe syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\n\n⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- ditional). \nIts premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent is ¬W2,2. \nImplications are also known as rules or if–then statements. \nThe implication symbol is sometimes written in other books as ⊃ or →.\n\nOPERATOR PRECEDENCE::: ¬,∧,∨,⇒,⇔\n\nThe biconditional, P ⇔ Q, is true whenever both P ⇒ Q and Q ⇒ P are true. In English, this is often written as “P if and only if Q.” \n\nIf KB and α contain n symbols in all, then there are 2^n models.\n\n\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\ntheorem proving—applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n\nlogical equivalence: two sen- tences α and β are logically equivalent if they are true in the same set of models. We write this as α ≡ β.\nα≡β ifandonlyif α|=βandβ|=α.\n\n validity: A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.\n by proving that (α ⇒ β) is equivalent to True.\n\n satisfiability. A sentence is satisfiable if it is true in, or satisfied by, some model.\n\n the SAT problem—was the first problem proved to be NP-complete.\n\nValidity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively, α is satisfiable iff ¬α is not valid. We also have the following useful result:\nα |= β if and only if the sentence (α ∧ ¬β) is unsatisfiable.\n\nIt is also called proof by refutation or proof by contradiction. One assumes a sentence β to be false and shows that this leads to a contradiction with known axioms α. \nThis contradiction is exactly what is meant by saying that the sentence (α ∧ ¬β) is unsatisfiable.\n\n\nThe best-known rule is called Modus Ponens α ⇒ β, α === β\n\n And-Elimination, which says that, from a conjunction, any of the conjuncts can be inferred:α∧β ==α\n\n By considering the possible truth values of α and β, one can show easily that Modus Ponens and And-Elimination are sound once and for all.\n\n The equivalence for biconditional elimination yields the two inference rules α ⇔ β and (α ⇒ β) ∧ (β ⇒ α) .\n    (α ⇒ β)∧(β ⇒ α) α ⇔ β\n\n     search algorithms  are used\n\nmonotonicity, which says that the set of en- tailed sentences can only increase as information is added to the knowledge base.8 For any sentences α and β,\nif KB|=α then KB∧β|=α.\n\nresolution, that yields a complete inference algorithm when coupled with any complete search algorithm.\n\n\n\n\n\n\n \n \n\n## Module 7 Lecture Notes\n \n\nThe forward-chaining algorithm PL-FC-ENTAILS?(KB,q) determines if a single proposi- tion symbol q—the query—is entailed by a knowledge base of definite clauses.\n\nIt is easy to see that forward chaining is sound: every inference is essentially an appli- cation of Modus Ponens. \n\nForward chaining is also complete: every entailed atomic sentence will be derived. \n\n\ndata-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n\nBackward chaining is a form of goal-directed reasoning.\n\nOften, the cost of backward chaining is much less than linear in the size of the knowledge base, because the process touches only relevant facts.\n\n The algorithm is essentially identical to the AND-OR-GRAPH-SEARCH algorithm\n\n\n This theorem is proved by demonstrating its contrapositive: if the closure RC(S) does not\n\ncontain the empty clause, then S is satisfiable. In fact, we can construct a model for S with\nsuitable truth values for P1 , . . . , Pk . The construction procedure is as follows: \nFor i from 1 to k,\n– If a clause in RC (S) contains the literal ¬Pi and all its other literals are false under the assignment chosen for P1, . . . , Pi−1, then assign false to Pi.\n– Otherwise, assign true to Pi.\nnference procedures based on resolution work by using the principle of proof by contradic- tion. That is, to show that KB |= α, we show that (KB ∧ ¬α) is unsatisfiable\n\n The empty clause—a disjunction of no disjuncts—is equivalent to False because a disjunction is true only if at least one of its disjuncts is true. \n \n\n PL-RESOLUTION is complete. To do this, we introduce the resolution closure RC (S) of a set of clauses S, which is the set of all clauses derivable by repeated application of the resolution rule to clauses in S or their derivatives.\n \n The completeness theorem for resolution in propositional logic is called the ground resolution theorem:\nIf a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n\nOne such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.\n\nHorn clause, which is a disjunction of literals of which at most one is positive.\n\nSo all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n\nAdvantage of Definite Clauses :\n\nEvery definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal. \n\nA sentence consisting of a single positive literal, such as L1,1, is called a fact. \n\nIn Horn form, the premise is called the body and the conclusion is called the head\n\nInference with Horn clauses can be done through the forward-chaining and backward- chaining algorithms.This type of inference is the basis for logic programming,\n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base\n \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}