{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ray's 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": "ef31220f-7700-4ee0-d935-a535c3f2f61b"
      },
      "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": null,
      "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": "3a741ce9-776f-4ebf-c056-230356c00639"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "244a9679-2c47-484a-93a5-55993e9f9a90"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"AI definition: fidelity to human performance vs rationality(doing \n",
        "the right thing). Intelligence: a property of internal thought process and \n",
        "reasoning vs. intelligent behavior. 4 dimensions: human vs. rational and thought \n",
        "vs. behavior. 1)Acting humanly: the Turing test approach. A computer passes the \n",
        "test if a human interrogator cannot tell whether it comes from a person. The \n",
        "computer needs capabilities: natural lanugage processing for successful communication, \n",
        "knowledge representation to store knowledge, automated reasoning to answer questions\n",
        "and draw conclusions, and machien learning to adapt to new circumstances and to \n",
        "detect patterns. The total Turing test requires interaction with objects and people,\n",
        "so needs computer vision and robotics. 2) Thinking humanly: the cognitive modeling \n",
        "approach. Three ways to learn about human though: introspection(catch one's own \n",
        "thoughts), psychological experiments(observe a person), brain imaging(observe the \n",
        "brain). 3)Think rationally: Aristotle provided pattern to derive correct conclusion \n",
        "from correct premises(logic). Logic requires knowledge of the world that is certain \n",
        "while theory of probability fills uncertainty. 4) Acting rationally: \n",
        "Agent is something that acts. A rational agent is one that acts to achieve the\n",
        "best outcome or the best expected outcome when there is uncertainty. SOMETIMES making\n",
        "correct inferences is part of being a rational agent. Skills in the Turing test\n",
        "allow an agent to act rationally. Knowledge representation and reasoning enable \n",
        "agents to reach good decisions. Rational-agent to AI has two advantages: more\n",
        "general than the \"laws of thought\" approach, not just correct inference and more\n",
        "amenable to scientific development(rationality well defined mathematically). AI\n",
        "has focused on the study and construction of agents that do the right thing. The\n",
        "right thing is defined by the objective provided to the agent. This is the\n",
        "standard model. Perfect rationality is not feasible, so refine standard model to\n",
        "accomplish limited rationality. 5) Real world hard to specify the objective correctly\n",
        "and completely. Value alignment problem is the problem of achieving agreement between\n",
        "our true preferences and the input objective. We want agents that are provably \n",
        "benefitial to humans.\"\"\" \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 = \"\"\" John Searle: weak AI are machines that act as if they were intelligent,\n",
        "strong AI are machines that are actually consciously thinking, not just simulating\n",
        "thinking. Strong AI is \"human-level' AI or 'general AI', referring to programs that\n",
        "can solve an arbitrarily wide vareity of tasks, including novel ones, and as well as\n",
        "a human. 1) Turing's 'arguement from informality of behavior' says that human behavior\n",
        "is far too complex to be captured by any formal set of rules. Hubert Dreyfus and \n",
        "Stuart Dreyfus and Kenneth Sayre criticized Good Old-Fashioned AI, the simplest\n",
        "logical agent，difficult to capture every contingency of appropriate behavior in \n",
        "a set of necessary and sufficient logical rules, this is 'qualification problem'. \n",
        "Probabilistic reasoning system is good at open-ended domains, and deep learning\n",
        "systems do well on informal tasks. The embodied cognition approach claims that it\n",
        "makes no sense to consider the brain separately: cognition takes place within a\n",
        "body, system as a whole. 2) The 'argument from disability' claims that 'a machine\n",
        "can never do X'. 3) Turing and Godel proved that certain mathematical questions \n",
        "are in principle unanswerable by particular formal systems. Godel's incompleteness\n",
        "theorem: for formal axiomatic framework F, sentence G(F) can't have 1. G(F) is a \n",
        "sentence of F and can't be proved within F and 2. If F is consistent, then G(F) is\n",
        "true. Lucas claimed that machines are mentally inferior to humans. 4) The Turing test:\n",
        "a program to have a conversation via typed messages with an interrogator for five\n",
        "minutes. Machine passes if he fools the interrogator 30% of the time. ELIZA program,\n",
        "Mgonz, Natachata, cyberlove. 2014, Eugene Goostman a new internet chatbot fooled\n",
        "33% of the untrained amateur judges by pretending himself to be a Ukrainian boy.\n",
        "\"\"\"\n",
        "\n",
        "chapter27_2 = \"\"\" 0) Philosophers claim that machines are not actually thinking,\n",
        "but would be a only a simulation of thinking. Turing: we don't have direct evidence\n",
        "about the internal mental states of other humans. Turing said that polite convention\n",
        "should be extended to machines that 'everyone thinks'. 1) John Searle rejects the \n",
        "polite convention and proposes the famous Chinese rom. A person that understands\n",
        "English only generate fluent, intelligent Chinese responses through following the\n",
        "instructions in the rule book and finding symbols. Computers generate no understanding.\n",
        "Searle is a proponent of biological naturalism (mental states are high-level emergent\n",
        "features that are caused by low-level physical processes in the neurons) and neurons\n",
        "have 'it' but transistors do not. But cells don't understand either. 2) Consciousness\n",
        "is the awareness of the outside world, and of the self, and the subjective experience\n",
        "of living. Intrinsic nature of experiences is qualia.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment\n",
        "through sensors and acting upon that environment through actuators. The term percept\n",
        "refers to the content an agent's sensors are perceiving. An agent's percept sequence\n",
        "is the complete history of everything the agent has ever perceived. An agent's choice\n",
        "of action at any given instant can depend on its built-in knowledge and on the entire\n",
        "percept sequence observed to date, but not on anything it hasn't perceived. An agent's\n",
        "behavior is described by the agent function that maps any given percept sequence to\n",
        "an action. An external characterization of the agent is a \"truth table\"(my term) \n",
        "with all possible percept sequences as input. Internally, the agent function for \n",
        "an artificial agent will be implemented by an agent program. The agent function \n",
        "is an abstract mathematical description; the agent program is a concrete \n",
        "implementation, running within some physical system.  \"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" A rational agent is one that does the right thing. 1) \n",
        "Consequentialism: we evaluate an agent's behavior by its consequences. When an agent\n",
        "is placed in an environment, it generates a sequence of actions according to the \n",
        "percepts it receives. This sequence of actions causes the environment to go through\n",
        "a sequence of states. If the sequence is desirable, then the agent has performed\n",
        "well. The notion of desirability is captured by a performance measure that evaluates\n",
        "any given sequence of environment states. Norbert Wiener warned that we should ensure\n",
        "'the purpose put into the machine is the purpose which we really desire'. As a general\n",
        "rule, it is better to design performance measures according to what one actually\n",
        "wants to be achieved in the environment, rather than according to how one thinks\n",
        "the agent should bahave. 2) What is rational at any given time depends on four things:\n",
        "1> the performance measure that defines the criterion of success 2> The agent's\n",
        "prior knowledge of the environment 3> The actions that the agent can perform 4>\n",
        "The agent's percept sequence to date. Definition of a rational agent: For each\n",
        "possible percept sequence, a rational agent should select an action that is expected\n",
        "to maximize its performance measure, given the evidence provided by the percept\n",
        "sequence and whatever built-in knolwedge the agent has. If the geography is unknown,\n",
        "the agent will need to explore it. 3) Distinguish between rationality and omniscience.\n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly;\n",
        "but omniscience is impossible in reality. Rationality is not the same as perfection.\n",
        "Rationality maximizes expected performance, while perfection maximizes actual\n",
        "performance. The rational choice depends only on the percept sequence to date,\n",
        "so rationality doesn't require omniscience. However, it is not rational to cross\n",
        "the road before looking both ways (uninformative percept sequence), and a rational\n",
        "agent should choose \"looking both way\" action before crossing because looking maximizes\n",
        "the expected performance. Doing actions in order to modify future percepts is \n",
        "information gathering. Exploration in an unknown environment is also information\n",
        "gathering. Rational agent needs to gather information and also learn as much as\n",
        "possible from its percept sequences. Learning is the process of modifying and\n",
        "augmenting its configuration. To the extent that an agent relies on the prior\n",
        "knowledge of its designer raher than on its own percepts and learning processses,\n",
        " we say that the agent lacks autonomy. \n",
        " \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" 0) Task environments are the 'problems' to which rational agents\n",
        "are the 'solutions'. The nature of the task environment directly affects the\n",
        "appropriate design for the agent program. 1) The heading of the task environment\n",
        "is described by PEAS(performance, environment, actuator, sensor). 2) Dimensions of\n",
        "the task environments. 1. fully observable vs. partially observable. If an agent's\n",
        "sensors give it access to the complete state of the environment at each point in\n",
        "life, then we say that the task environment is fully observable. A task environment\n",
        "is effectively fully observable if the sensors detect all aspects that are relevant\n",
        "to the choice of action; relevance depends on the performance measure. An agent doesn't\n",
        "need to maintain any internal state to keep track of the world in foe. An environment\n",
        "might be partially observable because of noisy and inaccurate sensors. If an agent\n",
        "has no sensors at all, then the environment is unobservable. But the agent's goal\n",
        "may still be accomplished. 2. single-agent vs. multiagent. Multiagent is whether B's\n",
        "behavior is best described as maximizing a performance measure whose value depends\n",
        "on A's behavior. Chess is a competitive multiagent environment. Driving is a \n",
        "cooperative multiagent(safe) and partially competitive environment(parking). 3> \n",
        "deterministic vs. nondeterministic: If the next state of the environment is \n",
        "completely determined by the current state and the action executed by the agent, \n",
        "the environment is deterministic. Fully observable and deterministic doesn't have\n",
        "uncertainty. However, partially observable can be nondeterministic. Stochastic is\n",
        "a synonym for nondeterministic, but a model is stochastic if it explicitly deals\n",
        "with probabilities. 4> episodic vs. sequential. In an episodic task environment,\n",
        "the agent's experience is divided into atomic episodes. In each episode the agent\n",
        "receives a percept then performs a single action. the next episode doesn't depend\n",
        "on the actions taken in previous episodes. Classification tasks are episodic. In\n",
        "sequential environments, the current decision could affect all future decisions.\n",
        "5> static vs. dynamic: If the environment can change while an agent is deliberating,\n",
        "then it is dynamic for the agents, static otherwise. If the environment doesn't \n",
        "change with the passage of time but the agent's performance score does, then it is\n",
        "semidynamic. 6> discrete vs. continues. Applies to the state of the environment,\n",
        "to the way time is handled, and to the percepts and actions of the agent. Chess is\n",
        "discrete, driving is continuous. 7> known vs. unknown. The distinction refers to\n",
        "the agent's state of knowledge about the laws of physics of the environment. In a\n",
        "known environment, the outcomes or outcome probabilities for all actions are given.\n",
        "A known environment can be partially observable: card games. An unknown environment\n",
        "can be fully observable: video games(entire game state but doesn't know the effect\n",
        "of buttons until try them). \"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\" The job of AI is to design an agent program that implements the \n",
        "agent function—the mapping from percepts to actions. The agent architecture is\n",
        "computing device with physical sensors and actuators. agent = architecture + program. \n",
        "1) The agent programs take the current percept as input from the sensors and return an action to the \n",
        "actuators. Notice the difference between the agent program, which takes the current \n",
        "percept as input, and the agent function, which may depend on the entire percept history.\n",
        "2) Simple reflex agents select actions on the basis of the current \n",
        "percept, ignoring the rest of the percept history. Condition/situation-action\n",
        "rule is if-then. Escape from infinite loops is possible if \n",
        "the agent can randomize its actions. 3) Model-based reflex agents: To handle partial\n",
        "observable: The agent should maintain some sort of internal state that depends \n",
        "on the percept history. \n",
        "First, we need the effects of the agent’s actions and how the \n",
        "world evolves independently of the agent, which is the transition model of the \n",
        "world. Second, we need some information about how the state of the \n",
        "world is reflected in the agent’s percepts, which is the sensor model. Together, \n",
        "the transition model and sensor model create a model-based agent that keep track of the state \n",
        "of the world by updating its internal states.\n",
        "4) Goal-based agents. As well as a current state description, the agent needs \n",
        "some sort of goal information that describes situations that are desirable. Search\n",
        "and planning require AI to find action sequences that achieve the agent's goal. \n",
        "5) Utility-based agents. An agent’s utility function is essentially an \n",
        "internalization of the performance \n",
        "measure. A rational utility-based agent chooses the action that maximizes the \n",
        "expected utility of the action outcomes. A model-free utility-based agent can learn \n",
        "what action is best in a particular situation without ever learning exactly how \n",
        "that action changes the environment.\n",
        "6) Learning agent. Learning allows the agent to operate in initially unknown environments \n",
        "and to become more competent than its initial knowledge alone might allow. A learning \n",
        "agent can be divided into four conceptual components. Learning element makes improvements.\n",
        "The performance element selects external actions. critic. The problem generator \n",
        "suggests actions that leads to new and informative experiences.\n",
        "7) In an atomic representation each state of the world is indivisible without \n",
        "internal structures. A factored representation splits up each state into a fixed \n",
        "set of variables or attributes, each of which can have a value. In a structured\n",
        "representation, objects and relationships can be described explicitly. Relational \n",
        "database, first-order logic and probability models. AFS has increasing expressiveness.\n",
        "A localist representation has one-on-one mapping between concepts and memory locations.\n",
        "A distributed representation is otherwise.\n",
        " \"\"\"\n",
        "\n",
        "#500\n",
        "print(\"The length in words is\", len(chapter2_4.split(' ')))\n",
        "#3000\n",
        "print(\"The length in characters is\", len(chapter2_4))\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Descartes Principle of dualism – that the mind or thinking \n",
        "self is essentially incorporeal or spiritual – that the mind exists separately from \n",
        "the body: \"if a foot or arm or any other part of the body is cut off, nothing has \n",
        "thereby taken away from the mind.\" “I think, therefore I am.\" Rene Descartes wondered \n",
        "if he could know for sure that others who looked and behaved like him weren’t in \n",
        "fact automata. Bodies of people and animals are nothing more than complex machines, \n",
        "the bones, muscles and organs could be replaced with cogs, pistons and cams. “if \n",
        "there were machines bearing the image of our bodies, and capable of imitating our \n",
        "actions. For example, if touched in a particular place it may demand what we wish \n",
        "to say to it; if in another it may cry out that it is hurt. However there would \n",
        "be two tests to know that they were not really men.”... They could never use properly \n",
        "use language. Alan Turing \"I propose to consider the question, 'Can machines think?'\" \n",
        "Because \"thinking\" is difficult to define, Turing chooses to \"replace the question \n",
        "by another, which is closely related to it and is expressed in relatively unambiguous\n",
        "words.\" Turing's new question is: \"Are there imaginable digital computers which \n",
        "would do well in the imitation game?\" A human evaluator would judge text-based \n",
        "conversations between a human and a machine designed to generate human-like responses. \n",
        "If the evaluator cannot reliably tell the machine from the human, the machine passes \n",
        "the test. The test results do not depend on the ability to give correct answers \n",
        "to questions, only how closely one's answers resemble those a human would give.\n",
        "John Searle The Chinese room Is the Turing Test a good test of whether machines \n",
        "possess intelligence? No, because the appearance of being a good conversational \n",
        "participant is achievable through simple symbol manipulation. Searle contends that \n",
        "the application of rules to input symbols is not true intelligence. Searle contrasts \n",
        "strong AI with weak AI. In strong AI, the computer really is a mind in the sense \n",
        "that it can be literally said to understand and have other cognitive states. In \n",
        "weak AI, computers just simulate thought, their seeming understanding isn't real \n",
        "understanding. He argues that (biological) brains cause minds.\n",
        "Daniel Dennett wrote a short story called “Where Am I?” where he describes being \n",
        "recruited by the Pentagon to have his brain removed from his body and connected \n",
        "via radio links attaching his severed nerves. Body is sent on a secret mission to \n",
        "diffuse bomb without radiation harming brain. His body is destroyed by the radiation, \n",
        "but his consciousness continues in the vat. The scientists restore him in a new \n",
        "body. Then it is revealed that constructed a computer duplicate of my brain, reproducing \n",
        "both the complete information-processing structure and the computational speed of \n",
        "my brain in a giant computer program. His brain in a vat is processing symbols. \n",
        "What makes this different than a computer processing symbols? An agent is anything that \n",
        "perceives its environment through sensors and can act on its environment through actuators\n",
        "A percept is the agent’s perceptual inputs at any given instance. An agent is specified \n",
        "by an agent function f:P -> a that maps a sequence of percept vectors P to an action \n",
        "a from a set A: P = [p0, p1, ... pt], A = {a0, a1, ... ak}. An agent is anything \n",
        "that can be viewed as perceiving its environment through sensors and acting upon \n",
        "that environment. A rational agent is an agent that perceives its environment \n",
        "and behaves rationally Rational behavior: doing the right thing. AI is usually concerned \n",
        "with Consequentialism. We evaluate an agent’s behavior by its consequences. Rational \n",
        "choice theory is a framework for understanding social and economic behavior. The \n",
        "basic premise is that aggregate social behavior results from the behavior of individual \n",
        "actors, each of whom is making their individual decisions. It assumes that individuals \n",
        "have preferences and choose the alternative that they prefer. We define a performance \n",
        "measure: An objective criterion for success of an agent's behavior; given the evidence \n",
        "provided by the percept sequence. It is better to design performance measures according \n",
        "to what you want to be achieved in the environment, rather than how you think the agent \n",
        "should behave. Initial Rational Agent: For each possible percept sequence P, a rational agent \n",
        "selects an action a to maximize its performance measure. Ideal agent: maximizes \n",
        "actual performance, but needs to be omniscient. Usually impossible, Rationality \n",
        "not equal to Guaranteed Success. Computational limitations make complete rationality \n",
        "unachievable. Revised Rational Agent:  For each possible percept sequence P, a rational \n",
        "agent selects an action a that maximizes the expected value of its performance measure.\n",
        "It doesn’t have to know what the actual outcome will be. To design a rational agent \n",
        "we need to specify a task environment • a problem specification for which the agent is a solution\n",
        "Note that A rational agent is not guaranteed to find optimal solutions. An agent’s \n",
        "choice of action at a given instant depends on its percept sequence but not future \n",
        "perceptual inputs. Randomized behavior can be rational in some environments!!!\"\"\"\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",
        "\"agent function\": \"specifies the action taken by the agent in response to any percept sequence\",\n",
        "\"performance measure\": \"evaluates the behavior of the agent in an environment\",\n",
        "\"rational agent\": \"maximize the expected value of the performance measure, given the percept sequence it has seen so far\", \n",
        "\"utility\" : \"the quality of being useful\",\n",
        "\"task environment\" : \" includes the performance measure, the external environment, the actuators, and the sensors\",\n",
        "\"agent program\": \"implementation of the agent function\",\n",
        "\"simple reflex agents\": \"respond directly to percepts\", \n",
        "\"model-based reflex agents\": \"maintain internal state to track aspects of the world that are not evident in the current percept\",\n",
        "\"goal-based agents\": \"act to achieve their goals\",\n",
        "\"utility-based agents\": \"try to maximize their own expected “happiness” \",\n",
        "\"percept\" : \"the content an agent's sensors are perceiving\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 432\n",
            "The length in characters is 2929\n"
          ]
        }
      ]
    },
    {
      "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": "54fa68f8-5b4a-4fdd-bedb-f8c0f963e883"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI definition: fidelity to human performance vs rationality(doing \nthe right thing). Intelligence: a property of internal thought process and \nreasoning vs. intelligent behavior. 4 dimensions: human vs. rational and thought \nvs. behavior. 1)Acting humanly: the Turing test approach. A computer passes the \ntest if a human interrogator cannot tell whether it comes from a person. The \ncomputer needs capabilities: natural lanugage processing for successful communication, \nknowledge representation to store knowledge, automated reasoning to answer questions\nand draw conclusions, and machien learning to adapt to new circumstances and to \ndetect patterns. The total Turing test requires interaction with objects and people,\nso needs computer vision and robotics. 2) Thinking humanly: the cognitive modeling \napproach. Three ways to learn about human though: introspection(catch one's own \nthoughts), psychological experiments(observe a person), brain imaging(observe the \nbrain). 3)Think rationally: Aristotle provided pattern to derive correct conclusion \nfrom correct premises(logic). Logic requires knowledge of the world that is certain \nwhile theory of probability fills uncertainty. 4) Acting rationally: \nAgent is something that acts. A rational agent is one that acts to achieve the\nbest outcome or the best expected outcome when there is uncertainty. SOMETIMES making\ncorrect inferences is part of being a rational agent. Skills in the Turing test\nallow an agent to act rationally. Knowledge representation and reasoning enable \nagents to reach good decisions. Rational-agent to AI has two advantages: more\ngeneral than the \"laws of thought\" approach, not just correct inference and more\namenable to scientific development(rationality well defined mathematically). AI\nhas focused on the study and construction of agents that do the right thing. The\nright thing is defined by the objective provided to the agent. This is the\nstandard model. Perfect rationality is not feasible, so refine standard model to\naccomplish limited rationality. 5) Real world hard to specify the objective correctly\nand completely. Value alignment problem is the problem of achieving agreement between\nour true preferences and the input objective. We want agents that are provably \nbenefitial to humans.\n\n## AIMA Chapter 27.1 The Limits of AI\n John Searle: weak AI are machines that act as if they were intelligent,\nstrong AI are machines that are actually consciously thinking, not just simulating\nthinking. Strong AI is \"human-level' AI or 'general AI', referring to programs that\ncan solve an arbitrarily wide vareity of tasks, including novel ones, and as well as\na human. 1) Turing's 'arguement from informality of behavior' says that human behavior\nis far too complex to be captured by any formal set of rules. Hubert Dreyfus and \nStuart Dreyfus and Kenneth Sayre criticized Good Old-Fashioned AI, the simplest\nlogical agent，difficult to capture every contingency of appropriate behavior in \na set of necessary and sufficient logical rules, this is 'qualification problem'. \nProbabilistic reasoning system is good at open-ended domains, and deep learning\nsystems do well on informal tasks. The embodied cognition approach claims that it\nmakes no sense to consider the brain separately: cognition takes place within a\nbody, system as a whole. 2) The 'argument from disability' claims that 'a machine\ncan never do X'. 3) Turing and Godel proved that certain mathematical questions \nare in principle unanswerable by particular formal systems. Godel's incompleteness\ntheorem: for formal axiomatic framework F, sentence G(F) can't have 1. G(F) is a \nsentence of F and can't be proved within F and 2. If F is consistent, then G(F) is\ntrue. Lucas claimed that machines are mentally inferior to humans. 4) The Turing test:\na program to have a conversation via typed messages with an interrogator for five\nminutes. Machine passes if he fools the interrogator 30% of the time. ELIZA program,\nMgonz, Natachata, cyberlove. 2014, Eugene Goostman a new internet chatbot fooled\n33% of the untrained amateur judges by pretending himself to be a Ukrainian boy.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n 0) Philosophers claim that machines are not actually thinking,\nbut would be a only a simulation of thinking. Turing: we don't have direct evidence\nabout the internal mental states of other humans. Turing said that polite convention\nshould be extended to machines that 'everyone thinks'. 1) John Searle rejects the \npolite convention and proposes the famous Chinese rom. A person that understands\nEnglish only generate fluent, intelligent Chinese responses through following the\ninstructions in the rule book and finding symbols. Computers generate no understanding.\nSearle is a proponent of biological naturalism (mental states are high-level emergent\nfeatures that are caused by low-level physical processes in the neurons) and neurons\nhave 'it' but transistors do not. But cells don't understand either. 2) Consciousness\nis the awareness of the outside world, and of the self, and the subjective experience\nof living. Intrinsic nature of experiences is qualia.\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment\nthrough sensors and acting upon that environment through actuators. The term percept\nrefers to the content an agent's sensors are perceiving. An agent's percept sequence\nis the complete history of everything the agent has ever perceived. An agent's choice\nof action at any given instant can depend on its built-in knowledge and on the entire\npercept sequence observed to date, but not on anything it hasn't perceived. An agent's\nbehavior is described by the agent function that maps any given percept sequence to\nan action. An external characterization of the agent is a \"truth table\"(my term) \nwith all possible percept sequences as input. Internally, the agent function for \nan artificial agent will be implemented by an agent program. The agent function \nis an abstract mathematical description; the agent program is a concrete \nimplementation, running within some physical system.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing. 1) \nConsequentialism: we evaluate an agent's behavior by its consequences. When an agent\nis placed in an environment, it generates a sequence of actions according to the \npercepts it receives. This sequence of actions causes the environment to go through\na sequence of states. If the sequence is desirable, then the agent has performed\nwell. The notion of desirability is captured by a performance measure that evaluates\nany given sequence of environment states. Norbert Wiener warned that we should ensure\n'the purpose put into the machine is the purpose which we really desire'. As a general\nrule, it is better to design performance measures according to what one actually\nwants to be achieved in the environment, rather than according to how one thinks\nthe agent should bahave. 2) What is rational at any given time depends on four things:\n1> the performance measure that defines the criterion of success 2> The agent's\nprior knowledge of the environment 3> The actions that the agent can perform 4>\nThe agent's percept sequence to date. Definition of a rational agent: For each\npossible percept sequence, a rational agent should select an action that is expected\nto maximize its performance measure, given the evidence provided by the percept\nsequence and whatever built-in knolwedge the agent has. If the geography is unknown,\nthe agent will need to explore it. 3) Distinguish between rationality and omniscience.\nAn omniscient agent knows the actual outcome of its actions and can act accordingly;\nbut omniscience is impossible in reality. Rationality is not the same as perfection.\nRationality maximizes expected performance, while perfection maximizes actual\nperformance. The rational choice depends only on the percept sequence to date,\nso rationality doesn't require omniscience. However, it is not rational to cross\nthe road before looking both ways (uninformative percept sequence), and a rational\nagent should choose \"looking both way\" action before crossing because looking maximizes\nthe expected performance. Doing actions in order to modify future percepts is \ninformation gathering. Exploration in an unknown environment is also information\ngathering. Rational agent needs to gather information and also learn as much as\npossible from its percept sequences. Learning is the process of modifying and\naugmenting its configuration. To the extent that an agent relies on the prior\nknowledge of its designer raher than on its own percepts and learning processses,\n we say that the agent lacks autonomy. \n \n\n## AIMA 2.3 The Nature of Environments\n 0) Task environments are the 'problems' to which rational agents\nare the 'solutions'. The nature of the task environment directly affects the\nappropriate design for the agent program. 1) The heading of the task environment\nis described by PEAS(performance, environment, actuator, sensor). 2) Dimensions of\nthe task environments. 1. fully observable vs. partially observable. If an agent's\nsensors give it access to the complete state of the environment at each point in\nlife, then we say that the task environment is fully observable. A task environment\nis effectively fully observable if the sensors detect all aspects that are relevant\nto the choice of action; relevance depends on the performance measure. An agent doesn't\nneed to maintain any internal state to keep track of the world in foe. An environment\nmight be partially observable because of noisy and inaccurate sensors. If an agent\nhas no sensors at all, then the environment is unobservable. But the agent's goal\nmay still be accomplished. 2. single-agent vs. multiagent. Multiagent is whether B's\nbehavior is best described as maximizing a performance measure whose value depends\non A's behavior. Chess is a competitive multiagent environment. Driving is a \ncooperative multiagent(safe) and partially competitive environment(parking). 3> \ndeterministic vs. nondeterministic: If the next state of the environment is \ncompletely determined by the current state and the action executed by the agent, \nthe environment is deterministic. Fully observable and deterministic doesn't have\nuncertainty. However, partially observable can be nondeterministic. Stochastic is\na synonym for nondeterministic, but a model is stochastic if it explicitly deals\nwith probabilities. 4> episodic vs. sequential. In an episodic task environment,\nthe agent's experience is divided into atomic episodes. In each episode the agent\nreceives a percept then performs a single action. the next episode doesn't depend\non the actions taken in previous episodes. Classification tasks are episodic. In\nsequential environments, the current decision could affect all future decisions.\n5> static vs. dynamic: If the environment can change while an agent is deliberating,\nthen it is dynamic for the agents, static otherwise. If the environment doesn't \nchange with the passage of time but the agent's performance score does, then it is\nsemidynamic. 6> discrete vs. continues. Applies to the state of the environment,\nto the way time is handled, and to the percepts and actions of the agent. Chess is\ndiscrete, driving is continuous. 7> known vs. unknown. The distinction refers to\nthe agent's state of knowledge about the laws of physics of the environment. In a\nknown environment, the outcomes or outcome probabilities for all actions are given.\nA known environment can be partially observable: card games. An unknown environment\ncan be fully observable: video games(entire game state but doesn't know the effect\nof buttons until try them). \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the \nagent function—the mapping from percepts to actions. The agent architecture is\ncomputing device with physical sensors and actuators. agent = architecture + program. \n1) The agent programs take the current percept as input from the sensors and return an action to the \nactuators. Notice the difference between the agent program, which takes the current \npercept as input, and the agent function, which may depend on the entire percept history.\n2) Simple reflex agents select actions on the basis of the current \npercept, ignoring the rest of the percept history. Condition/situation-action\nrule is if-then. Escape from infinite loops is possible if \nthe agent can randomize its actions. 3) Model-based reflex agents: To handle partial\nobservable: The agent should maintain some sort of internal state that depends \non the percept history. \nFirst, we need the effects of the agent’s actions and how the \nworld evolves independently of the agent, which is the transition model of the \nworld. Second, we need some information about how the state of the \nworld is reflected in the agent’s percepts, which is the sensor model. Together, \nthe transition model and sensor model create a model-based agent that keep track of the state \nof the world by updating its internal states.\n4) Goal-based agents. As well as a current state description, the agent needs \nsome sort of goal information that describes situations that are desirable. Search\nand planning require AI to find action sequences that achieve the agent's goal. \n5) Utility-based agents. An agent’s utility function is essentially an \ninternalization of the performance \nmeasure. A rational utility-based agent chooses the action that maximizes the \nexpected utility of the action outcomes. A model-free utility-based agent can learn \nwhat action is best in a particular situation without ever learning exactly how \nthat action changes the environment.\n6) Learning agent. Learning allows the agent to operate in initially unknown environments \nand to become more competent than its initial knowledge alone might allow. A learning \nagent can be divided into four conceptual components. Learning element makes improvements.\nThe performance element selects external actions. critic. The problem generator \nsuggests actions that leads to new and informative experiences.\n7) In an atomic representation each state of the world is indivisible without \ninternal structures. A factored representation splits up each state into a fixed \nset of variables or attributes, each of which can have a value. In a structured\nrepresentation, objects and relationships can be described explicitly. Relational \ndatabase, first-order logic and probability models. AFS has increasing expressiveness.\nA localist representation has one-on-one mapping between concepts and memory locations.\nA distributed representation is otherwise.\n \n\n## Module 1 Lecture Notes\n Descartes Principle of dualism – that the mind or thinking \nself is essentially incorporeal or spiritual – that the mind exists separately from \nthe body: \"if a foot or arm or any other part of the body is cut off, nothing has \nthereby taken away from the mind.\" “I think, therefore I am.\" Rene Descartes wondered \nif he could know for sure that others who looked and behaved like him weren’t in \nfact automata. Bodies of people and animals are nothing more than complex machines, \nthe bones, muscles and organs could be replaced with cogs, pistons and cams. “if \nthere were machines bearing the image of our bodies, and capable of imitating our \nactions. For example, if touched in a particular place it may demand what we wish \nto say to it; if in another it may cry out that it is hurt. However there would \nbe two tests to know that they were not really men.”... They could never use properly \nuse language. Alan Turing \"I propose to consider the question, 'Can machines think?'\" \nBecause \"thinking\" is difficult to define, Turing chooses to \"replace the question \nby another, which is closely related to it and is expressed in relatively unambiguous\nwords.\" Turing's new question is: \"Are there imaginable digital computers which \nwould do well in the imitation game?\" A human evaluator would judge text-based \nconversations between a human and a machine designed to generate human-like responses. \nIf the evaluator cannot reliably tell the machine from the human, the machine passes \nthe test. The test results do not depend on the ability to give correct answers \nto questions, only how closely one's answers resemble those a human would give.\nJohn Searle The Chinese room Is the Turing Test a good test of whether machines \npossess intelligence? No, because the appearance of being a good conversational \nparticipant is achievable through simple symbol manipulation. Searle contends that \nthe application of rules to input symbols is not true intelligence. Searle contrasts \nstrong AI with weak AI. In strong AI, the computer really is a mind in the sense \nthat it can be literally said to understand and have other cognitive states. In \nweak AI, computers just simulate thought, their seeming understanding isn't real \nunderstanding. He argues that (biological) brains cause minds.\nDaniel Dennett wrote a short story called “Where Am I?” where he describes being \nrecruited by the Pentagon to have his brain removed from his body and connected \nvia radio links attaching his severed nerves. Body is sent on a secret mission to \ndiffuse bomb without radiation harming brain. His body is destroyed by the radiation, \nbut his consciousness continues in the vat. The scientists restore him in a new \nbody. Then it is revealed that constructed a computer duplicate of my brain, reproducing \nboth the complete information-processing structure and the computational speed of \nmy brain in a giant computer program. His brain in a vat is processing symbols. \nWhat makes this different than a computer processing symbols? An agent is anything that \nperceives its environment through sensors and can act on its environment through actuators\nA percept is the agent’s perceptual inputs at any given instance. An agent is specified \nby an agent function f:P -> a that maps a sequence of percept vectors P to an action \na from a set A: P = [p0, p1, ... pt], A = {a0, a1, ... ak}. An agent is anything \nthat can be viewed as perceiving its environment through sensors and acting upon \nthat environment. A rational agent is an agent that perceives its environment \nand behaves rationally Rational behavior: doing the right thing. AI is usually concerned \nwith Consequentialism. We evaluate an agent’s behavior by its consequences. Rational \nchoice theory is a framework for understanding social and economic behavior. The \nbasic premise is that aggregate social behavior results from the behavior of individual \nactors, each of whom is making their individual decisions. It assumes that individuals \nhave preferences and choose the alternative that they prefer. We define a performance \nmeasure: An objective criterion for success of an agent's behavior; given the evidence \nprovided by the percept sequence. It is better to design performance measures according \nto what you want to be achieved in the environment, rather than how you think the agent \nshould behave. Initial Rational Agent: For each possible percept sequence P, a rational agent \nselects an action a to maximize its performance measure. Ideal agent: maximizes \nactual performance, but needs to be omniscient. Usually impossible, Rationality \nnot equal to Guaranteed Success. Computational limitations make complete rationality \nunachievable. Revised Rational Agent:  For each possible percept sequence P, a rational \nagent selects an action a that maximizes the expected value of its performance measure.\nIt doesn’t have to know what the actual outcome will be. To design a rational agent \nwe need to specify a task environment • a problem specification for which the agent is a solution\nNote that A rational agent is not guaranteed to find optimal solutions. An agent’s \nchoice of action at a given instant depends on its percept sequence but not future \nperceptual inputs. Randomized behavior can be rational in some environments!!!\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Agent function** - specifies the action taken by the agent in response to any percept sequence\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Rational agent** - maximize the expected value of the performance measure, given the percept sequence it has seen so far\n* **Utility** - the quality of being useful\n* **Task environment** -  includes the performance measure, the external environment, the actuators, and the sensors\n* **Agent program** - implementation of the agent function\n* **Simple reflex agents** - respond directly to percepts\n* **Model-based reflex agents** - maintain internal state to track aspects of the world that are not evident in the current percept\n* **Goal-based agents** - act to achieve their goals\n* **Utility-based agents** - try to maximize their own expected “happiness” \n* **Percept** - the content an agent's sensors are perceiving\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",
        "Every bold has two underscores before and two underscores after.\n",
        "Fast development: Concise, intuitive syntax that is whitespace, delimited Garbage \n",
        "collected. Portable: Programs run on major platforms without change. Various built-in \n",
        "types: lists, dictionaries, sets: useful for AI. Large collection of support libraries: \n",
        "NumPy for Matlab like programming, Pandas for data analysis, \n",
        "Sklearn for machine learning, Pytorch and TensorFlow for deep learning\n",
        "REPL ENVIRONMENT Read-Evaluate-Print loop. \n",
        "All data treated as objects. An object is deleted (by garbage collection) once unreachable.\n",
        "Strong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible \n",
        "with that type (eg. “foo” + 2) type(object) isinstance(object, type)/\n",
        "Examples of Types: int, float, str, tuple, dict, list, bool: True, False, \n",
        "None, generator, function. static typing: Variables can only refer to objects of \n",
        "a declared type. dynamic typing: Variables come into existence when first assigned.\n",
        "Type of the variable is determined automatically. If assigned again, type is updated.\n",
        "Functions have no type signatures. However, type errors can only be caught at runtime.\n",
        "strings are immutable. is checks whether variables point to the same object while\n",
        "== checks whether variables point to objects of the same value. lists are mutable.\n",
        "Use [:] to get a shallow copy of any sequence. Tuple is immutable but can contain\n",
        "mixed types including collection types. negative index is looking from right, starting\n",
        "from -1 as the rightmost. Slicing returns copy of a subsequence. 1:-1 is the same as\n",
        "1:len(n)-1. insert can be used on list (idx, ele). index, count, and remove on list\n",
        "with ele as input. list.sort() is sort, list.sort(a) is sort with function a,\n",
        "sort(list) returns a sorted copy. a.join([b, c, d]) = 'bacad' where bcd are strings.\n",
        "capitalize is upper first letter. upper is upper every. strip is to remove a substring.\n",
        "Dictionaries are unordered & work by hashing, so keys must be immutable.\n",
        "Constant average time add, lookup, update. keys(), values(), items() \n",
        "Python allows you to multiple values in the type of tuple. Python doesn’t allow \n",
        "function overloading like Java does, two functions can't have the same name. \n",
        "But operator overloading is possible. Non-default argument should always precede \n",
        "default arguments; otherwise, it reports SyntaxError. Functions can be called with \n",
        "arguments out of order. Suppose you want to accept a variable number of non-keyword \n",
        "arguments to your function. Use *args as the function input and *lst if lst is the\n",
        "actual input. def print_everything(*args): print(args), can do print('a', 'b')\n",
        "args is a tuple of arguments passed to the fn.\n",
        "and lst = ['a', 'b'] print(*lst) Suppose you want to accept a variable number of \n",
        "arguments to your function. def print_keyword_args(**kwargs): # kwargs is a dict \n",
        "of the keyword args passed to the fn. print_keyword_args(a = 'b', c = 'd') yields\n",
        "{'a': 'b', 'c': 'd'}. Same as dict = {'a': 'b', 'c': 'd'} and print_keyword_args(**dict)\n",
        "Python uses dynamic scope Function sees the most current value of variables\n",
        "Functions are “first-class” objects, First class object is an entity that can be \n",
        "dynamically created, destroyed, passed to a function, returned as a value, and have \n",
        "all the rights as other variables in the programming language have.\n",
        "Functions are “first-class citizens”, Pass functions as arguments to other functions, \n",
        "Return functions as the values from other functions, Assign functions to variables or \n",
        "store them in data structures. Higher order functions: take functions as input\n",
        "A class can extend the definition of another class\n",
        "Allows use (or extension) of methods and attributes already defined in the\n",
        "previous one.\n",
        "New class: subclass. Original: parent, ancestor or superclass\n",
        "To define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition.\n",
        "class cs_Student(Student):\n",
        "Python has no ‘extends’ keyword like Java. Multiple inheritance is supported.\n",
        "Constructors: __init__ Must be done explicitly.\n",
        "To redefine a method of the parent class, include a new definition using the same\n",
        "name in the subclass.\n",
        "The old code in the parent class won’t get executed.\n",
        "To execute the method in the parent class in addition to new code for some method, \n",
        "explicitly call the parent’s version of the method.\n",
        "parentClass.methodName(self, a, b)\n",
        "The only time you ever explicitly pass self as an argument is when\n",
        "calling a method of an ancestor.\n",
        "myOwnSubClass.methodName(a, b)\n",
        "Magic Methods allow user-defined classes to behave like built in types\n",
        "You can implement operator overloading with magic methods\n",
        "__init__, __len__, __copy__, __cmp__, __add__, __neg__\n",
        "The interpreter sets the __name__ variable to have a value \"__main__\" for the source \n",
        "file that is being executed on the command line.\n",
        "Python doesn’t have a built-in main method, so there is no def main(). Instead, \n",
        "it uses this syntax to define a main method: if __name__ == '__main__':\n",
        "Duck typing establishes suitability of an object by determining presence of methods Does it swim like a duck and quack like a duck? It’s a duck\n",
        "Not to be confused with ‘rubber duck debugging’\n",
        "lst1 = [('a', 1), ('b', 2), ('c', 'hi’)] lst2 = ['x', 'a', 6]\n",
        "d = { k: v for k,v in lst1 } s = { x for x in lst2 }\n",
        "k = [1,2,3], i = iter(k), next(i), i.__next__(), i.next() same\n",
        "no hasnext() method. \n",
        "generator: uses yield in function, automatically return a generator when called.\n",
        "gen.__next__(), next(get), gen.__next__()\n",
        "problems: 1> 'abc' = 'a'+'b'+'c' = '',join(['a','b','c'])='%s%s%s'%('a', 'b', 'c')\n",
        "but not [x for x in 'abc'], not sum(['a','b','c']). 2> function inside a class is\n",
        "called method. 3> list can have different types of things. Can have [None,   ]\n",
        "or a list of functions or [_ for _ in [1, 2, 3]]. 4> Can't assign tuple values.\n",
        "5> A hash function is any function that can be used to map data of arbitrary size \n",
        "to fixed-size values. 6> Some mathematical operations can be performed on a string.\n",
        "7> A Python tuple can also be created without using parentheses. a = b, c, d is tuple\n",
        "8> A function can take an unlimited number of arguments and return multiple values.\n",
        "Python return default value if no return value. Python supports nested functions.\n",
        "9> 1 to 100 is [i for i in range(1, 101)]\n",
        "10> assigning slicing doesn't change original.\n",
        "11> {\"a\": 3, \"b\": 2, [1,2]: 2}. first_two = set(); first_two.add(\"one\"); \n",
        "first_two.remove(\"two\"). {\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4}. \n",
        "a = '123'; a[1] = '1'. b = (1, 2, 3); b[1] = 1 all return error.\n",
        "d = ({ }, { }); d[1][1] = 1 is ok. \n",
        "12> x = [(x, y) for x in [1,2,3] for y in [1,2,3]], len(x) = 9.\n",
        "\"\"\"\n",
        "\n",
        "# print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n",
        "# print(\"The length in characters is\", len(module2_lecture_notes))\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"A mutable object can be changed after it's created\",\n",
        "}"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 974
        },
        "outputId": "c0a3df26-75c1-416c-dc27-4d2ab3d585d1"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nEvery bold has two underscores before and two underscores after.\nFast development: Concise, intuitive syntax that is whitespace, delimited Garbage \ncollected. Portable: Programs run on major platforms without change. Various built-in \ntypes: lists, dictionaries, sets: useful for AI. Large collection of support libraries: \nNumPy for Matlab like programming, Pandas for data analysis, \nSklearn for machine learning, Pytorch and TensorFlow for deep learning\nREPL ENVIRONMENT Read-Evaluate-Print loop. \nAll data treated as objects. An object is deleted (by garbage collection) once unreachable.\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible \nwith that type (eg. “foo” + 2) type(object) isinstance(object, type)/\nExamples of Types: int, float, str, tuple, dict, list, bool: True, False, \nNone, generator, function. static typing: Variables can only refer to objects of \na declared type. dynamic typing: Variables come into existence when first assigned.\nType of the variable is determined automatically. If assigned again, type is updated.\nFunctions have no type signatures. However, type errors can only be caught at runtime.\nstrings are immutable. is checks whether variables point to the same object while\n== checks whether variables point to objects of the same value. lists are mutable.\nUse [:] to get a shallow copy of any sequence. Tuple is immutable but can contain\nmixed types including collection types. negative index is looking from right, starting\nfrom -1 as the rightmost. Slicing returns copy of a subsequence. 1:-1 is the same as\n1:len(n)-1. insert can be used on list (idx, ele). index, count, and remove on list\nwith ele as input. list.sort() is sort, list.sort(a) is sort with function a,\nsort(list) returns a sorted copy. a.join([b, c, d]) = 'bacad' where bcd are strings.\ncapitalize is upper first letter. upper is upper every. strip is to remove a substring.\nDictionaries are unordered & work by hashing, so keys must be immutable.\nConstant average time add, lookup, update. keys(), values(), items() \nPython allows you to multiple values in the type of tuple. Python doesn’t allow \nfunction overloading like Java does, two functions can't have the same name. \nBut operator overloading is possible. Non-default argument should always precede \ndefault arguments; otherwise, it reports SyntaxError. Functions can be called with \narguments out of order. Suppose you want to accept a variable number of non-keyword \narguments to your function. Use *args as the function input and *lst if lst is the\nactual input. def print_everything(*args): print(args), can do print('a', 'b')\nargs is a tuple of arguments passed to the fn.\nand lst = ['a', 'b'] print(*lst) Suppose you want to accept a variable number of \narguments to your function. def print_keyword_args(**kwargs): # kwargs is a dict \nof the keyword args passed to the fn. print_keyword_args(a = 'b', c = 'd') yields\n{'a': 'b', 'c': 'd'}. Same as dict = {'a': 'b', 'c': 'd'} and print_keyword_args(**dict)\nPython uses dynamic scope Function sees the most current value of variables\nFunctions are “first-class” objects, First class object is an entity that can be \ndynamically created, destroyed, passed to a function, returned as a value, and have \nall the rights as other variables in the programming language have.\nFunctions are “first-class citizens”, Pass functions as arguments to other functions, \nReturn functions as the values from other functions, Assign functions to variables or \nstore them in data structures. Higher order functions: take functions as input\nA class can extend the definition of another class\nAllows use (or extension) of methods and attributes already defined in the\nprevious one.\nNew class: subclass. Original: parent, ancestor or superclass\nTo define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition.\nclass cs_Student(Student):\nPython has no ‘extends’ keyword like Java. Multiple inheritance is supported.\nConstructors: __init__ Must be done explicitly.\nTo redefine a method of the parent class, include a new definition using the same\nname in the subclass.\nThe old code in the parent class won’t get executed.\nTo execute the method in the parent class in addition to new code for some method, \nexplicitly call the parent’s version of the method.\nparentClass.methodName(self, a, b)\nThe only time you ever explicitly pass self as an argument is when\ncalling a method of an ancestor.\nmyOwnSubClass.methodName(a, b)\nMagic Methods allow user-defined classes to behave like built in types\nYou can implement operator overloading with magic methods\n__init__, __len__, __copy__, __cmp__, __add__, __neg__\nThe interpreter sets the __name__ variable to have a value \"__main__\" for the source \nfile that is being executed on the command line.\nPython doesn’t have a built-in main method, so there is no def main(). Instead, \nit uses this syntax to define a main method: if __name__ == '__main__':\nDuck typing establishes suitability of an object by determining presence of methods Does it swim like a duck and quack like a duck? It’s a duck\nNot to be confused with ‘rubber duck debugging’\nlst1 = [('a', 1), ('b', 2), ('c', 'hi’)] lst2 = ['x', 'a', 6]\nd = { k: v for k,v in lst1 } s = { x for x in lst2 }\nk = [1,2,3], i = iter(k), next(i), i.__next__(), i.next() same\nno hasnext() method. \ngenerator: uses yield in function, automatically return a generator when called.\ngen.__next__(), next(get), gen.__next__()\nproblems: 1> 'abc' = 'a'+'b'+'c' = '',join(['a','b','c'])='%s%s%s'%('a', 'b', 'c')\nbut not [x for x in 'abc'], not sum(['a','b','c']). 2> function inside a class is\ncalled method. 3> list can have different types of things. Can have [None,   ]\nor a list of functions or [_ for _ in [1, 2, 3]]. 4> Can't assign tuple values.\n5> A hash function is any function that can be used to map data of arbitrary size \nto fixed-size values. 6> Some mathematical operations can be performed on a string.\n7> A Python tuple can also be created without using parentheses. a = b, c, d is tuple\n8> A function can take an unlimited number of arguments and return multiple values.\nPython return default value if no return value. Python supports nested functions.\n9> 1 to 100 is [i for i in range(1, 101)]\n10> assigning slicing doesn't change original.\n11> {\"a\": 3, \"b\": 2, [1,2]: 2}. first_two = set(); first_two.add(\"one\"); \nfirst_two.remove(\"two\"). {\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4}. \na = '123'; a[1] = '1'. b = (1, 2, 3); b[1] = 1 all return error.\nd = ({ }, { }); d[1][1] = 1 is ok. \n12> x = [(x, y) for x in [1,2,3] for y in [1,2,3]], len(x) = 9.\n\n\n## Module 2 Definitions\n* **Mutability** - A mutable object can be changed after it's created\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cfb19ea6-8673-4e90-c515-4af5db9f9023"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" GOAL FORMULATION: Goals organize behavior by limiting the objectives \n",
        "and hence the actions to be considered. PROBLEM FORMULATION: The agent devises a \n",
        "description of the states and actions necessary to reach the goal—an abstract model \n",
        "of the relevant part of the world. SEARCH: Before taking any action in the real \n",
        "world, the agent simulates sequences of actions in its model, searching until it \n",
        "finds a sequence of actions that reaches the goal. EXECUTION: The agent can now \n",
        "execute the actions in the solution, one at a time. 1) In a fully observable, deterministic, \n",
        "known environment, the solution to any problem is a fixed sequence of actions. If\n",
        "not, the agent would be safer using a closed-loop approach that monitors the percepts. \n",
        "a solution would be a branching strategy that recommends different future actions \n",
        "depending on what percepts arrive. A search problem: A set of possible states that \n",
        "the environment can be in. We call this the state space. The initial state that \n",
        "the agent starts in. A set of one or more goal states. The actions available to the agent.\n",
        "An action is applicable in state s if it can be executed in s. A transition model, \n",
        "which describes what each action does. An action cost function that reflects its \n",
        "own performance measure. Graph: states are vertices, actions are edges. 2) Model is\n",
        "an abstract mathematical description. The abstraction is valid if we can elaborate \n",
        "any abstract solution into a solution in the more detailed world. The abstraction \n",
        "is useful if carrying out each of the actions in the solution is easier than the \n",
        "original problem. The choice of a good abstraction thus involves removing as much \n",
        "detail as possible while retaining validity and ensuring that the abstract actions \n",
        "are easy to carry out.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is intended to illustrate or exercise various \n",
        "problem-solving methods. It can be given a concise, exact description and hence is \n",
        "suitable as a benchmark for researchers to compare the performance of algorithms. \n",
        "A real-world problem, such as robot navigation, is one whose solutions people actually \n",
        "use, and whose formulation is idiosyncratic, not standardized. 1) Absolute/egocentric\n",
        "actions: action in absolute direction or direction perceived by onself. 2) real-world\n",
        "example: STATES: Each state obviously includes a location (e.g., an airport) and the current time. \n",
        "Furthermore, because the cost of an action (a flight segment) may depend on previous\n",
        "segments, their fare bases, and their status as domestic or international, the \n",
        "state must record extra information about these “historical” aspects. INITIAL STATE: \n",
        "The user’s home airport. ACTIONS: Take any flight from the current location, in \n",
        "any seat class, leaving after the current time, leaving enough time for within-airport \n",
        "transfer if needed. TRANSITION MODEL: The state resulting from taking a flight will \n",
        "have the flight’s destination as the new location and the flight’s arrival time as the new time.\n",
        "GOAL STATE: A destination city. Sometimes the goal can be more complex, such as \n",
        "“arrive at the destination on a nonstop flight.” ACTION COST: A combination of \n",
        "monetary cost, waiting time, flight time, customs and immigration procedures, seat \n",
        "quality, time of day, type of airplane, frequent-flyer reward points, and so on. \n",
        "Robot navigation is a generalization of the route-finding problem described earlier. \n",
        "Rather than following distinct paths (such as the roads in Romania), a robot can \n",
        "roam around, in effect making its own paths. \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" A search algorithm takes a search problem as input and returns \n",
        "a solution, or an indication of failure. In a search tree, each node corresponds \n",
        "to a state in the state space and the edges in the search tree correspond to actions. \n",
        "The root of the tree corresponds to the initial state of the problem. It is important \n",
        "to understand the distinction between the state space and the search tree. The state \n",
        "space describes the (possibly infinite) set of states in the world, and the actions \n",
        "that allow transitions from one state to another. The search tree describes paths \n",
        "between these states, reaching towards the goal. The search tree may have multiple \n",
        "paths to (and thus multiple nodes for) any given state, but each node in the tree \n",
        "has a unique path back to the root (as in all trees). The frontier of the search \n",
        "tree is a set of unexpanded nodes. 1) best-first search expands a node with minimum \n",
        "value of some evaluation function f(n). 2) data structure of node: 4 components,\n",
        "state, parent, action, path-cost. frontier queue can be priority queue (best-first), \n",
        "FIFO queue (BFS), and LIFO queue (dfs). Reached states can be hashed table. \n",
        "3) A cycle is a special case of a redundant path. We call a search algorithm a \n",
        "graph search if it checks for redundant paths and a tree-like search if it does \n",
        "not check. Best-first-Search is graph search, more memory but faster. 4) performance\n",
        "measure: 1> completeness: if the algorithm guaranteed to find a solution when \n",
        "there is one. 2> COST OPTIMALITY: if it finds a solution with the lowest path cost \n",
        "of all solutions. 3> Time complexity 4> space complexity. To be complete, a search \n",
        "algorithm must be systematic in the way it explores an infinite state space, making \n",
        "sure it can eventually reach any state that is connected to the initial state. Depth d\n",
        "is the number of actions in an optimal solution. he branching factor b is the number \n",
        "of successors of a node that need to be considered\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" 1) When all actions have the same cost, an appropriate strategy \n",
        "is breadth-first search, in which the root node is expanded first, then all the \n",
        "successors of the root node are expanded next, then their successors, and so on. \n",
        "This is a systematic search strategy that is therefore complete even on infinite \n",
        "state spaces. We could implement breadth-first search as a call to BEST-FIRST-SEARCH \n",
        "where the evaluation function is the depth of the node—that is, the number of \n",
        "actions it takes to reach the node. Need FIFO and early goal test, checking a node\n",
        "is goal before adding to queue. Complete and optimal, TC and SC are O(b^d). 2) Dijkstra's\n",
        "or uniform cost. The complexity of uniform-cost search is characterized in terms C,\n",
        "the cost of the optimal solution, and e, a lower bound on the cost of each action, \n",
        "with Then the algorithm’s worst-case time and TC and SC are O(b^(1+floor(C*/e))).\n",
        "Notice that floor(C*/e) = d when all costs are equal. 3) DFS always expands the \n",
        "deepest node in the frontier first, f(n) is the negative of depth. It's implemented\n",
        "as a tree search. It is not systematic in infinite state spaces so incomplete. It\n",
        "can get stuck in cycle/infinite loop. DFS requires smaller memory and no reached table.\n",
        "MC is O(bm) where m is the maximum depth of the tree. Backtracking search uses less\n",
        "memory because only one successor is generated, and remembers where the next successor\n",
        "is. It reduces to O(m), but need to specify how to undo. 4) depth limited and iterative\n",
        "deepening search is a version of depth-first search in which we supply a depth limit L, \n",
        "and treat all nodes at depth as if they had no successors. TC is O(b^L) and SC is\n",
        "O(b*L), but poor choice of L will make it incomplete. Uses tree-like search so have\n",
        "to eliminate cycles by limiting depth. Memory req is O(b*d) when there is a solution and\n",
        "O(b*m) when no solution. It's optimal when all actions have the same cost and complete\n",
        "on finite acyclic state spaces. TC is O(b^d) when there is solution and O(b^m) otherwise.\n",
        "In general, iterative deepening is the preferred uninformed search method when \n",
        "the search state space is larger than can fit in memory and the depth of the \n",
        "solution is not known. 5) bidirectional simultaneously searches forward from the \n",
        "initial state and backwards from the goal state(s), hoping that the two searches \n",
        "will meet. For this to work, we need to keep track of two frontiers and two tables \n",
        "of reached states, and we need to be able to reason backwards. 6) Completeness:\n",
        "BFS, uniform cost, iterative deepening, bidirectional. Optimal: Same as completeness.\n",
        "Time: BFS is O(b^d), UC is O(b^(1+floor(C*/e))), DFS is O(b^m), Depth-limited is\n",
        "O(b^l), ID is O(b^d), bidirectional is O(b^(d/2)). Space: BFS is O(b^d), UC is \n",
        "O(b^(1+floor(C*/e))), DFS is O(b*m), DL is O(b*l), ID is O(b*d), bidirectional is\n",
        "O(b^(d/2)). Bidirectional here uses BF or UC. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" 0> A search method is uninformed if it only has access \n",
        "to the problem definition. 1> In a fully observable, deterministic, known environment, \n",
        "the solution to any problem is a fixed sequence of actions. 2> The state space is\n",
        "the set of possible states of the environment. 3> The initial state and goal states\n",
        "are needed when defining a search problem. 4> A solution to a search problem is a \n",
        "path through the state space from the intial state to a goal state. 5> A state space,\n",
        "initial state, goal state, actions, transition model, action cost function are required\n",
        "to define a search problem. 5> In a search problem, an optimal solution has the \n",
        "lowest path cost among all solutions. 6> A search algorithm is graph search if it \n",
        "checks for redundant paths, tree search if it doesn't. 7> Graph search is faster than\n",
        "tree search but uses mores space. 8> Search algorithms are typically judged based on\n",
        "completeness, cost optimality, time complexity, and space complexity. 9> A search \n",
        "algorithm is complete if the algorithm is guaranteed to find a solution if there \n",
        "is one, and to correctly report failure when there is not. 10> A search algorithm \n",
        "is cost optimal when it is guaranteed to find the solution with the lowest path \n",
        "cost of all solutions. 11> Time complexity is how long it takes for an algorithm \n",
        "to find a solution. 12> Space complexity is how much memory it takes for an algorithm \n",
        "to run. 13> In uninformed search, best-first search expands nodes according to an \n",
        "evaluation function. 14> Breadth-first search expands the node which is shallowest.\n",
        "15> BFS is optimal when unit cost 16> uniform expands with lowest g(n) 17> DFS\n",
        "expands nodes which is deepest. DLs expands nodes which is deepest and within a \n",
        "depth bound. 17> Iterative deepening search expands the node according to depth-limited \n",
        "search with increasing depth bounds. 18> Bidirectional search expands nodes around \n",
        "the initial state and the goal. Slide: A simple reflex agent is one that selects \n",
        "an action based only on the current percept. It ignores the rest of the percept \n",
        "history. A problem-solving agent must plan ahead. The computational process that \n",
        "it undertakes is called search. It will consider a sequence of actions that form \n",
        "a path to a goal state. Such a sequence is called a solution.\n",
        "The properties of the task environments change the types of solutions that we \n",
        "need. If an environment is: Fully observable, Deterministic, Known environment.\n",
        "The solution to any problem in such an environment is a fixed sequence of actions.\n",
        "In environments that are partially observable or nondeterministic, the solution \n",
        "must recommend different future actions depending on the what percepts it receives. \n",
        "This could be in the form of a branching strategy. Holiday setting: Formulate goal:\n",
        "Be in Bucharest Formulate search problem: States: various cities, Actions: drive \n",
        "between cities, Performance measure: minimize travel time / distance, Find solution:\n",
        "Sequence of cities. Real world is absurdly complex. State space must be abstracted \n",
        "for problem solving. Tree Search: Generalized algorithm to solve search problems\n",
        "Enumerate in some order all possible paths from the initial state. States do not \n",
        "have parents, children, depth or path cost, but nodes representing states do!\n",
        "BFS is optimal if cost = 1 per step!!! Use BFS If there are possibly infinite paths \n",
        "in your search space. Preferable to use DFS if you are working with restricted memory.\n",
        "Dijkstra is a uniform-cost search without a goal. Uniform-cost search is optimal.\n",
        "Not all moves are equal in path cost. Depth-first search doesn't have much lower \n",
        "space complexity than iterative deepening. Depth-first search is incomplete.\n",
        "\"\"\"\n",
        "\n",
        "# print(\"The length in words is\", len(module3_lecture_notes.split(' ')))\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",
        "\"component of problem\" : \"the state space, the initial state, a set of actions, a transition model, a set of goal states, and an action cost function\",\n",
        "\"abstraction\": \"the process of removing detail from a representation\",\n",
        "\"problem environment representation\": \"a state space graph\",\n",
        "\"solution\": \"a sequence of actions from the initial state to a goal state\",\n",
        "\"optimal solution\": \"the solution with the lowest path cost among all solutions.\",\n",
        "\"solution in PER\": \"a path through the state space from the initial state to a goal state\",\n",
        "\"search algorithm representation\": \"treating states and actions as atomic and without internal structure\",\n",
        "\"search algorithm judgement\": \"basis of completeness, cost optimality, time complexity, and space complexity\",\n",
        "\"uninformed search methods\": \"has access only to the problem definition\",\n",
        "\"best-first search\": \"selects nodes for expansion using an evaluation function\",\n",
        "\"breadth-first search\": \"expands the shallowest nodes first, complete, optimal if unit cost, but exponential SC\",\n",
        "\"uniform-cost search\": \"expands the node with lowest path cost g(n), optimal for general action costs\",\n",
        "\"depth-first search\": \"expands the deepest unexpanded node first, incomplete, suboptimal, linear SC\",\n",
        "\"depth-limited search\": \"adds a depth bound to dfs\",\n",
        "\"iterative deepening search\": \"calls dfs with increasing depth limits until goal is reached. complete acyclic, optimal unit action costs.\",\n",
        "\"bidirectional search\": \"expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet, optimal\",\n",
        "\"the search problem\": \"the process of looking for a sequence of actions that reaches the goal\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 47,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 585\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "556eb071-d24b-49c3-8eb3-7022c3e38703"
      },
      "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": 48,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'component of problem' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n GOAL FORMULATION: Goals organize behavior by limiting the objectives \nand hence the actions to be considered. PROBLEM FORMULATION: The agent devises a \ndescription of the states and actions necessary to reach the goal—an abstract model \nof the relevant part of the world. SEARCH: Before taking any action in the real \nworld, the agent simulates sequences of actions in its model, searching until it \nfinds a sequence of actions that reaches the goal. EXECUTION: The agent can now \nexecute the actions in the solution, one at a time. 1) In a fully observable, deterministic, \nknown environment, the solution to any problem is a fixed sequence of actions. If\nnot, the agent would be safer using a closed-loop approach that monitors the percepts. \na solution would be a branching strategy that recommends different future actions \ndepending on what percepts arrive. A search problem: A set of possible states that \nthe environment can be in. We call this the state space. The initial state that \nthe agent starts in. A set of one or more goal states. The actions available to the agent.\nAn action is applicable in state s if it can be executed in s. A transition model, \nwhich describes what each action does. An action cost function that reflects its \nown performance measure. Graph: states are vertices, actions are edges. 2) Model is\nan abstract mathematical description. The abstraction is valid if we can elaborate \nany abstract solution into a solution in the more detailed world. The abstraction \nis useful if carrying out each of the actions in the solution is easier than the \noriginal problem. The choice of a good abstraction thus involves removing as much \ndetail as possible while retaining validity and ensuring that the abstract actions \nare easy to carry out.\n\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various \nproblem-solving methods. It can be given a concise, exact description and hence is \nsuitable as a benchmark for researchers to compare the performance of algorithms. \nA real-world problem, such as robot navigation, is one whose solutions people actually \nuse, and whose formulation is idiosyncratic, not standardized. 1) Absolute/egocentric\nactions: action in absolute direction or direction perceived by onself. 2) real-world\nexample: STATES: Each state obviously includes a location (e.g., an airport) and the current time. \nFurthermore, because the cost of an action (a flight segment) may depend on previous\nsegments, their fare bases, and their status as domestic or international, the \nstate must record extra information about these “historical” aspects. INITIAL STATE: \nThe user’s home airport. ACTIONS: Take any flight from the current location, in \nany seat class, leaving after the current time, leaving enough time for within-airport \ntransfer if needed. TRANSITION MODEL: The state resulting from taking a flight will \nhave the flight’s destination as the new location and the flight’s arrival time as the new time.\nGOAL STATE: A destination city. Sometimes the goal can be more complex, such as \n“arrive at the destination on a nonstop flight.” ACTION COST: A combination of \nmonetary cost, waiting time, flight time, customs and immigration procedures, seat \nquality, time of day, type of airplane, frequent-flyer reward points, and so on. \nRobot navigation is a generalization of the route-finding problem described earlier. \nRather than following distinct paths (such as the roads in Romania), a robot can \nroam around, in effect making its own paths. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns \na solution, or an indication of failure. In a search tree, each node corresponds \nto a state in the state space and the edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem. It is important \nto understand the distinction between the state space and the search tree. The state \nspace describes the (possibly infinite) set of states in the world, and the actions \nthat allow transitions from one state to another. The search tree describes paths \nbetween these states, reaching towards the goal. The search tree may have multiple \npaths to (and thus multiple nodes for) any given state, but each node in the tree \nhas a unique path back to the root (as in all trees). The frontier of the search \ntree is a set of unexpanded nodes. 1) best-first search expands a node with minimum \nvalue of some evaluation function f(n). 2) data structure of node: 4 components,\nstate, parent, action, path-cost. frontier queue can be priority queue (best-first), \nFIFO queue (BFS), and LIFO queue (dfs). Reached states can be hashed table. \n3) A cycle is a special case of a redundant path. We call a search algorithm a \ngraph search if it checks for redundant paths and a tree-like search if it does \nnot check. Best-first-Search is graph search, more memory but faster. 4) performance\nmeasure: 1> completeness: if the algorithm guaranteed to find a solution when \nthere is one. 2> COST OPTIMALITY: if it finds a solution with the lowest path cost \nof all solutions. 3> Time complexity 4> space complexity. To be complete, a search \nalgorithm must be systematic in the way it explores an infinite state space, making \nsure it can eventually reach any state that is connected to the initial state. Depth d\nis the number of actions in an optimal solution. he branching factor b is the number \nof successors of a node that need to be considered\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n 1) When all actions have the same cost, an appropriate strategy \nis breadth-first search, in which the root node is expanded first, then all the \nsuccessors of the root node are expanded next, then their successors, and so on. \nThis is a systematic search strategy that is therefore complete even on infinite \nstate spaces. We could implement breadth-first search as a call to BEST-FIRST-SEARCH \nwhere the evaluation function is the depth of the node—that is, the number of \nactions it takes to reach the node. Need FIFO and early goal test, checking a node\nis goal before adding to queue. Complete and optimal, TC and SC are O(b^d). 2) Dijkstra's\nor uniform cost. The complexity of uniform-cost search is characterized in terms C,\nthe cost of the optimal solution, and e, a lower bound on the cost of each action, \nwith Then the algorithm’s worst-case time and TC and SC are O(b^(1+floor(C*/e))).\nNotice that floor(C*/e) = d when all costs are equal. 3) DFS always expands the \ndeepest node in the frontier first, f(n) is the negative of depth. It's implemented\nas a tree search. It is not systematic in infinite state spaces so incomplete. It\ncan get stuck in cycle/infinite loop. DFS requires smaller memory and no reached table.\nMC is O(bm) where m is the maximum depth of the tree. Backtracking search uses less\nmemory because only one successor is generated, and remembers where the next successor\nis. It reduces to O(m), but need to specify how to undo. 4) depth limited and iterative\ndeepening search is a version of depth-first search in which we supply a depth limit L, \nand treat all nodes at depth as if they had no successors. TC is O(b^L) and SC is\nO(b*L), but poor choice of L will make it incomplete. Uses tree-like search so have\nto eliminate cycles by limiting depth. Memory req is O(b*d) when there is a solution and\nO(b*m) when no solution. It's optimal when all actions have the same cost and complete\non finite acyclic state spaces. TC is O(b^d) when there is solution and O(b^m) otherwise.\nIn general, iterative deepening is the preferred uninformed search method when \nthe search state space is larger than can fit in memory and the depth of the \nsolution is not known. 5) bidirectional simultaneously searches forward from the \ninitial state and backwards from the goal state(s), hoping that the two searches \nwill meet. For this to work, we need to keep track of two frontiers and two tables \nof reached states, and we need to be able to reason backwards. 6) Completeness:\nBFS, uniform cost, iterative deepening, bidirectional. Optimal: Same as completeness.\nTime: BFS is O(b^d), UC is O(b^(1+floor(C*/e))), DFS is O(b^m), Depth-limited is\nO(b^l), ID is O(b^d), bidirectional is O(b^(d/2)). Space: BFS is O(b^d), UC is \nO(b^(1+floor(C*/e))), DFS is O(b*m), DL is O(b*l), ID is O(b*d), bidirectional is\nO(b^(d/2)). Bidirectional here uses BF or UC. \n\n## Module 3 Lecture Notes\n 0> A search method is uninformed if it only has access \nto the problem definition. 1> In a fully observable, deterministic, known environment, \nthe solution to any problem is a fixed sequence of actions. 2> The state space is\nthe set of possible states of the environment. 3> The initial state and goal states\nare needed when defining a search problem. 4> A solution to a search problem is a \npath through the state space from the intial state to a goal state. 5> A state space,\ninitial state, goal state, actions, transition model, action cost function are required\nto define a search problem. 5> In a search problem, an optimal solution has the \nlowest path cost among all solutions. 6> A search algorithm is graph search if it \nchecks for redundant paths, tree search if it doesn't. 7> Graph search is faster than\ntree search but uses mores space. 8> Search algorithms are typically judged based on\ncompleteness, cost optimality, time complexity, and space complexity. 9> A search \nalgorithm is complete if the algorithm is guaranteed to find a solution if there \nis one, and to correctly report failure when there is not. 10> A search algorithm \nis cost optimal when it is guaranteed to find the solution with the lowest path \ncost of all solutions. 11> Time complexity is how long it takes for an algorithm \nto find a solution. 12> Space complexity is how much memory it takes for an algorithm \nto run. 13> In uninformed search, best-first search expands nodes according to an \nevaluation function. 14> Breadth-first search expands the node which is shallowest.\n15> BFS is optimal when unit cost 16> uniform expands with lowest g(n) 17> DFS\nexpands nodes which is deepest. DLs expands nodes which is deepest and within a \ndepth bound. 17> Iterative deepening search expands the node according to depth-limited \nsearch with increasing depth bounds. 18> Bidirectional search expands nodes around \nthe initial state and the goal. Slide: A simple reflex agent is one that selects \nan action based only on the current percept. It ignores the rest of the percept \nhistory. A problem-solving agent must plan ahead. The computational process that \nit undertakes is called search. It will consider a sequence of actions that form \na path to a goal state. Such a sequence is called a solution.\nThe properties of the task environments change the types of solutions that we \nneed. If an environment is: Fully observable, Deterministic, Known environment.\nThe solution to any problem in such an environment is a fixed sequence of actions.\nIn environments that are partially observable or nondeterministic, the solution \nmust recommend different future actions depending on the what percepts it receives. \nThis could be in the form of a branching strategy. Holiday setting: Formulate goal:\nBe in Bucharest Formulate search problem: States: various cities, Actions: drive \nbetween cities, Performance measure: minimize travel time / distance, Find solution:\nSequence of cities. Real world is absurdly complex. State space must be abstracted \nfor problem solving. Tree Search: Generalized algorithm to solve search problems\nEnumerate in some order all possible paths from the initial state. States do not \nhave parents, children, depth or path cost, but nodes representing states do!\nBFS is optimal if cost = 1 per step!!! Use BFS If there are possibly infinite paths \nin your search space. Preferable to use DFS if you are working with restricted memory.\nDijkstra is a uniform-cost search without a goal. Uniform-cost search is optimal.\nNot all moves are equal in path cost. Depth-first search doesn't have much lower \nspace complexity than iterative deepening. Depth-first search is incomplete.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Component of problem** - the state space, the initial state, a set of actions, a transition model, a set of goal states, and an action cost function\n* **Abstraction** - the process of removing detail from a representation\n* **Problem environment representation** - a state space graph\n* **Solution** - a sequence of actions from the initial state to a goal state\n* **Optimal solution** - the solution with the lowest path cost among all solutions.\n* **Solution in per** - a path through the state space from the initial state to a goal state\n* **Search algorithm representation** - treating states and actions as atomic and without internal structure\n* **Search algorithm judgement** - basis of completeness, cost optimality, time complexity, and space complexity\n* **Uninformed search methods** - has access only to the problem definition\n* **Best-first search** - selects nodes for expansion using an evaluation function\n* **Breadth-first search** - expands the shallowest nodes first, complete, optimal if unit cost, but exponential SC\n* **Uniform-cost search** - expands the node with lowest path cost g(n), optimal for general action costs\n* **Depth-first search** - expands the deepest unexpanded node first, incomplete, suboptimal, linear SC\n* **Depth-limited search** - adds a depth bound to dfs\n* **Iterative deepening search** - calls dfs with increasing depth limits until goal is reached. complete acyclic, optimal unit action costs.\n* **Bidirectional search** - expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet, optimal\n* **The search problem** - the process of looking for a sequence of actions that reaches the goal\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ad22f604-010d-4ed7-a8da-d028a5a05d7e"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "\n",
        "chapter3_5 = \"\"\" A heuristic function h(n) is the estimated cost of the cheapest\n",
        "path from the state at node n to a goal state. 1) Greedy best-first search is a \n",
        "form of best-first search that expands first the node with the lowest value, so\n",
        "the evaluation function f(n) = h(n). Greedy best-first graph search is complete \n",
        "in finite state spaces, but not in infinite ones. The worst-case time and space \n",
        "complexity is O(abs(V)). With a good heuristic function, however, the complexity \n",
        "can be reduced substantially, on certain problems reaching O(b*m). 2) A heuristic \n",
        "is consistent if, for every node and every successor of \n",
        "generated by an action h(n) leq c(n, a, n')+h(n'). Consistency is stronger than\n",
        "admissibility, so every consistent heuristic is admissible. 3) Draw contours in\n",
        "the state space. A* expands all nodes that can be reached from the initial state \n",
        "on a path where every node on the path has, so surely expanded nodes.\n",
        "A* with a consistent heuristic is optimally efficient in the sense that any algorithm \n",
        "that extends search paths from the initial state, and uses the same heuristic \n",
        "information, must expand all nodes that are surely expanded by A*. A* is efficient \n",
        "because it prunes away search tree nodes that are not necessary for finding an optimal \n",
        "solution. 4) Satisficing solutions are suboptimal but good enough. Weighted A* search\n",
        "uses f(n) = g(n) + W * h(n) with W > 1. Find solution between C* and W*C*, usually\n",
        "close to C*. A* is g+h, uniform is g, gbf is h. In bounded-cost search, we look \n",
        "for a solution whose cost is less than some constant And in unbounded-cost search, \n",
        "we accept a solution of any cost, as long as we can find it quickly. Speedy search, \n",
        "which is a version of greedy best-first search that uses as a heuristic the estimated \n",
        "number of actions required to reach a goal, regardless of the cost of those actions.\n",
        "5) memory is frontier and reached. 1> keep a state in only one of the two places.\n",
        "2> remove states from reached when we can prove that they are no longer needed. \n",
        "Beam search limits the size of the frontier. The easiest approach is to keep only \n",
        "the nodes with the best f-scores, discarding any other expanded nodes. Incomplete \n",
        "and suboptimal, but good memory and the fast execution. Iterative-deepening A* \n",
        "search (IDA*) is to A* what iterative-deepening search is to depth-first: IDA* \n",
        "gives us the benefits of A* without the requirement to keep all reached states \n",
        "in memory, at a cost of visiting some states multiple times. Recursive best-first \n",
        "search attempts to mimic the operation of standard best-first search, but using \n",
        "only linear space. RBFS is somewhat more efficient than IDA*. SMA* proceeds just \n",
        "like A*, expanding the best leaf until memory is full. At this point, it cannot \n",
        "add a new node to the search tree without dropping an old one. SMA* always drops \n",
        "the worst leaf node—the one with the highest -value.5) bidirectional \n",
        "A* doesn't produce optimal\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\" 1) effective branching factor b* . N+1=1+b* +(b* )^2..+(b* )^d.\n",
        "Well designed heuristic should have b* close to 1. Effective depth is the actual depth\n",
        "a search performs, which is less than d. When one heuristic dominates another, meaning\n",
        "h2(n)>h1(n), h2 is always better than h1 and expands less nodes. 2) relaxed graph\n",
        "creates a supergraph of the origianl set space because it adds in more edges. So\n",
        "always admissible.Just pick the maximum admissible function out of all the choices.\n",
        "3) Admissible heuristics can be derived from a subproblem. Pattern databases store\n",
        "the exact solution costs for every possible subproblem. Disjoint pattern databases\n",
        "divide the problems up such that each move affects only one subproblem. 4) Precompute\n",
        "of some optimal path costs. Choose a few landmark points. min abs(C* (n, L)+C* (goal, L))\n",
        "Add shortcuts the artificial, edges in the graph that define an optimal multi-action path. \n",
        "Differential heuristic = max abs(C* (n, L)-C* (goal, L)) for landmark L beyond the goal.\n",
        "Each state in a metalevel state space captures the internal (computational) state \n",
        "of a program that is searching in an ordinary state space such as the map of Romania.\n",
        "(To keep the two concepts separate, we call the map of Romania an object-level state space.) \n",
        "a metalevel learning algorithm can learn from these experiences to avoid \n",
        "exploring unpromising subtrees. The goal of learning is to minimize the total cost\n",
        " of problem solving, trading off computational expense and path cost. 6) Another way\n",
        " is to learn from experience. “Experience” here means solving lots of 8-puzzles, \n",
        " for instance. Each optimal solution to an 8-puzzle problem provides an example \n",
        " (goal, path) pair. From these examples, a learning algorithm can be used to \n",
        " construct a function that can (with luck) approximate the true path cost for \n",
        " other states that arise during search. Most of these approaches learn an imperfect \n",
        " approximation to the heuristic function, and thus risk inadmissibility. This leads \n",
        " to an inevitable tradeoff between learning time, search run time, and solution cost. \n",
        " \"\"\"\n",
        "\n",
        "#500\n",
        "print(\"The length in words is\", len(chapter3_6.split(' ')))\n",
        "#3000\n",
        "print(\"The length in characters is\", len(chapter3_6))\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" 1> A search method is uninformed if it only has access \n",
        "to the problem definition. 2> Max can't simply search for a single sequence of events \n",
        "from an initial state to a winning terminal state before the game begins because\n",
        "the best possible move made by MAX at any point in time will depend on the previous \n",
        "move made by MIN. 3> A search method is informed if it has access to the problem \n",
        "definition and a heuristic function, h(n). 4> The heuristic function h(n) estimates\n",
        "the cost of a solution from a node n. 5> Greedy best-first search expands nodes \n",
        "with minimal h(n). 6> The biggest problem with A* is the space complexity。\n",
        "7> A* is complete and optimal. 8> An admissible heuristic is one that never overestimates \n",
        "the cost to reach a goal. 9> IDA* is iterative deepening A* search. 10> RBFS is\n",
        "recursive best-first search. 11> IDA*, SMA*, and RBFS are optimal search algorithms \n",
        "which are more space efficient than A*. 12> Beam search limits the size of the frontier,\n",
        "so suboptimal and incomplete but runs faster than complete search. 13> Weighted A*\n",
        "is not optimal but complete, expands fewer nodes than A*.\n",
        "Uniform-cost search (UCS) is a tree search algorithm used for traversing or searching \n",
        "a weighted tree, tree structure, or graph. UCS is the extension of BF-search and \n",
        "expands node with lowest path cost. frontier is priority queue ordered by g(n).\n",
        "Subtle but significant difference from BFS: Tests if a node is a goal state when \n",
        "it is selected for expansion, not when it is added to the frontier. Updates a node \n",
        "on the frontier if a better path to the same state is found. So always enqueues \n",
        "a node before checking whether it is a goal. BFS has circle contour, UCS has cost\n",
        "contours. Best-first search selects node for expansion with minimal evaluation function f(n) \n",
        "where f(n) is some function that includes estimate heuristic h(n) of the remaining \n",
        "distance to goal. Best-first uses priority queue. Greedy best-first search: f(n) = h(n)\n",
        "Expands the node that is estimated to be closest to goal and completely ignores \n",
        "g(n): the cost to get to n. \n",
        "A* search expands nodes with minimal f(n) = g(n) + h(n) where g(n) is the path cost from the \n",
        "initial state to node and is the estimated cost of the shortest path from to a \n",
        "goal state. Key idea: avoid expanding paths that are already expensive, but expand most\n",
        "promising first. g(n) the actual cost (so far) to reach the node. h(n) estimated \n",
        "cost to get from the node to the goal. f(n) estimated total cost of path through \n",
        "n to goal. An admissible heuristic is one that never overestimates the cost to \n",
        "reach a goal, therefore optimistic. With an admissible heuristic, A* is \n",
        "cost-optimal. \"\"\"\n",
        "\n",
        "#500\n",
        "print(\"The length in words is\", len(module4_lecture_notes.split(' ')))\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search methods\": \"has access to a heuristic function that estimates the cost of a solution from current node\",\n",
        "\"greedy best-first search\": \"expands nodes with minimal h(n), not optimal but often efficient\",\n",
        "\"A* search\": \"expands nodes with minimal f(n), complete and optimal when h(n) is admissible\",\n",
        "\"bidirectional A* search\": \"sometimes more efficient than A* search\", \n",
        "\"iterative deepening A* search\": \"iterative deepening version of A* that addresses SC issue\", \n",
        "\"recursive best-first search and simpliffied memory-bound A*\" : \"robust, optimal search algorithms that use limited amounts of memory\",\n",
        "\"beam search\": \" puts a limit on the size of the frontier, incomplete and suboptimal but faster\",\n",
        "\"WEIGHTED A*\": \"search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 328\n",
            "The length in characters is 2092\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "311bab30-f52c-43f9-e8c9-09ab41a5cafb"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A heuristic function h(n) is the estimated cost of the cheapest\npath from the state at node n to a goal state. 1) Greedy best-first search is a \nform of best-first search that expands first the node with the lowest value, so\nthe evaluation function f(n) = h(n). Greedy best-first graph search is complete \nin finite state spaces, but not in infinite ones. The worst-case time and space \ncomplexity is O(abs(V)). With a good heuristic function, however, the complexity \ncan be reduced substantially, on certain problems reaching O(b*m). 2) A heuristic \nis consistent if, for every node and every successor of \ngenerated by an action h(n) leq c(n, a, n')+h(n'). Consistency is stronger than\nadmissibility, so every consistent heuristic is admissible. 3) Draw contours in\nthe state space. A* expands all nodes that can be reached from the initial state \non a path where every node on the path has, so surely expanded nodes.\nA* with a consistent heuristic is optimally efficient in the sense that any algorithm \nthat extends search paths from the initial state, and uses the same heuristic \ninformation, must expand all nodes that are surely expanded by A*. A* is efficient \nbecause it prunes away search tree nodes that are not necessary for finding an optimal \nsolution. 4) Satisficing solutions are suboptimal but good enough. Weighted A* search\nuses f(n) = g(n) + W * h(n) with W > 1. Find solution between C* and W*C*, usually\nclose to C*. A* is g+h, uniform is g, gbf is h. In bounded-cost search, we look \nfor a solution whose cost is less than some constant And in unbounded-cost search, \nwe accept a solution of any cost, as long as we can find it quickly. Speedy search, \nwhich is a version of greedy best-first search that uses as a heuristic the estimated \nnumber of actions required to reach a goal, regardless of the cost of those actions.\n5) memory is frontier and reached. 1> keep a state in only one of the two places.\n2> remove states from reached when we can prove that they are no longer needed. \nBeam search limits the size of the frontier. The easiest approach is to keep only \nthe nodes with the best f-scores, discarding any other expanded nodes. Incomplete \nand suboptimal, but good memory and the fast execution. Iterative-deepening A* \nsearch (IDA*) is to A* what iterative-deepening search is to depth-first: IDA* \ngives us the benefits of A* without the requirement to keep all reached states \nin memory, at a cost of visiting some states multiple times. Recursive best-first \nsearch attempts to mimic the operation of standard best-first search, but using \nonly linear space. RBFS is somewhat more efficient than IDA*. SMA* proceeds just \nlike A*, expanding the best leaf until memory is full. At this point, it cannot \nadd a new node to the search tree without dropping an old one. SMA* always drops \nthe worst leaf node—the one with the highest -value.5) bidirectional \nA* doesn't produce optimal\n\n## AIMA Chapter 3.6 Heuristic Functions\n 1) effective branching factor b* . N+1=1+b* +(b* )^2..+(b* )^d.\nWell designed heuristic should have b* close to 1. Effective depth is the actual depth\na search performs, which is less than d. When one heuristic dominates another, meaning\nh2(n)>h1(n), h2 is always better than h1 and expands less nodes. 2) relaxed graph\ncreates a supergraph of the origianl set space because it adds in more edges. So\nalways admissible.Just pick the maximum admissible function out of all the choices.\n3) Admissible heuristics can be derived from a subproblem. Pattern databases store\nthe exact solution costs for every possible subproblem. Disjoint pattern databases\ndivide the problems up such that each move affects only one subproblem. 4) Precompute\nof some optimal path costs. Choose a few landmark points. min abs(C* (n, L)+C* (goal, L))\nAdd shortcuts the artificial, edges in the graph that define an optimal multi-action path. \nDifferential heuristic = max abs(C* (n, L)-C* (goal, L)) for landmark L beyond the goal.\nEach state in a metalevel state space captures the internal (computational) state \nof a program that is searching in an ordinary state space such as the map of Romania.\n(To keep the two concepts separate, we call the map of Romania an object-level state space.) \na metalevel learning algorithm can learn from these experiences to avoid \nexploring unpromising subtrees. The goal of learning is to minimize the total cost\n of problem solving, trading off computational expense and path cost. 6) Another way\n is to learn from experience. “Experience” here means solving lots of 8-puzzles, \n for instance. Each optimal solution to an 8-puzzle problem provides an example \n (goal, path) pair. From these examples, a learning algorithm can be used to \n construct a function that can (with luck) approximate the true path cost for \n other states that arise during search. Most of these approaches learn an imperfect \n approximation to the heuristic function, and thus risk inadmissibility. This leads \n to an inevitable tradeoff between learning time, search run time, and solution cost. \n \n\n## Module 4 Lecture Notes\n 1> A search method is uninformed if it only has access \nto the problem definition. 2> Max can't simply search for a single sequence of events \nfrom an initial state to a winning terminal state before the game begins because\nthe best possible move made by MAX at any point in time will depend on the previous \nmove made by MIN. 3> A search method is informed if it has access to the problem \ndefinition and a heuristic function, h(n). 4> The heuristic function h(n) estimates\nthe cost of a solution from a node n. 5> Greedy best-first search expands nodes \nwith minimal h(n). 6> The biggest problem with A* is the space complexity。\n7> A* is complete and optimal. 8> An admissible heuristic is one that never overestimates \nthe cost to reach a goal. 9> IDA* is iterative deepening A* search. 10> RBFS is\nrecursive best-first search. 11> IDA*, SMA*, and RBFS are optimal search algorithms \nwhich are more space efficient than A*. 12> Beam search limits the size of the frontier,\nso suboptimal and incomplete but runs faster than complete search. 13> Weighted A*\nis not optimal but complete, expands fewer nodes than A*. 13>\n\nA* search expands nodes with minimal f(n) = g(n) + h(n) where g(n) is the path cost from the \ninitial state to node and is the estimated cost of the shortest path from to a \ngoal state. An admissible heuristic is one that never overestimates the cost to \nreach a goal, therefore optimistic. With an admissible heuristic, A* is \ncost-optimal. \n\n## Module 4 Definitions\n* **Informed search methods** - has access to a heuristic function that estimates the cost of a solution from current node\n* **Greedy best-first search** - expands nodes with minimal h(n), not optimal but often efficient\n* **A* search** - expands nodes with minimal f(n), complete and optimal when h(n) is admissible\n* **Bidirectional a* search** - sometimes more efficient than A* search\n* **Iterative deepening a* search** - iterative deepening version of A* that addresses SC issue\n* **Recursive best-first search and simpliffied memory-bound a*** - robust, optimal search algorithms that use limited amounts of memory\n* **Beam search** -  puts a limit on the size of the frontier, incomplete and suboptimal but faster\n* **Weighted a*** - search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b04d14ae-f0d6-49ac-d259-d73778be3e19"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Competitive environments, in which two or more agents have conflicting \n",
        "goals, giving rise to adversarial search problems. stance 1: the aggregate as \n",
        "an economy, allowing us to do things like predict that increasing demand will cause \n",
        "prices to rise, without having to predict the action of any individual agent. \n",
        "stance 2: adversarial agents as just a part of the environment—a part that makes \n",
        "the environment nondeterministic. stance 3: explicitly model the adversarial agents \n",
        "with the techniques of adversarial game-tree search. We do stance 3. Define the state \n",
        "space graph—a graph where the vertices are states, the edges are moves and a state \n",
        "might be reached by multiple paths. Define the complete game tree as a search tree \n",
        "that follows every sequence of moves all the way to a terminal state.  \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" 0) The minimax value is the utility at a terminal state, the \n",
        "maximum for max and minimum for min. The minimax value assumes that both players \n",
        "play optimally. 1) Minimax search is a recursive algorithm that proceeds all the \n",
        "way down to the leaves of the tree and then backs up the minimax values through \n",
        "the tree as the recursion unwinds. The minimax algorithm performs a complete \n",
        "depth-first exploration of the game tree. 2) Multi-agent: each player chooses their\n",
        "max value. 3) Pruning eliminates the examination of some states. alpha is the value\n",
        "of the best choice we have found so far at any choice point along the path for MAX.\n",
        "beta the value of the best choice we have found so far at any choice point along \n",
        "the path for MIN. 4) depends on order, so try to first examine the successors that \n",
        "are likely to be best. perfect: O(b^(m/2)) instead of O(b^m) for minimax. Iterative \n",
        "deepening record the ranking of moves then try killer moves (best moves). In game \n",
        "tree search, repeated states can occur because of transpositions—different permutations \n",
        "of the move sequence that end up in the same position, and the problem can be \n",
        "addressed with a transposition table that caches the heuristic value of states.\n",
        "Strategies when there are too m any states: Type A strategy considers all possible \n",
        "moves to a certain depth in the search tree, and then uses a heuristic evaluation \n",
        "function to estimate the utility of states at that depth. It explores a wide but \n",
        "shallow portion of the tree. A Type B strategy ignores moves that look bad, and \n",
        "follows promising lines “as far as possible.” It explores a deep but narrow portion \n",
        "of the tree.\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" 1) Heuristic alpha-beta tree search estimates a nonterminal state's\n",
        "utility and replace the terminal test by a cutoff test. The heuristic eval(s, p)\n",
        "returns an estimate of the expected utility of state s to player p at a depth level\n",
        "that is cutoff. For terminal states: eval(s,p) = utility(s,p). For nonterminal:\n",
        "eval is between loss and win utility. A reasonable evaluation is the expected value.\n",
        "Material value is defined to have feature values for different objects in game.\n",
        "Evaluation would be a linear combination of material values(king is 5, pawn is 1).\n",
        "2) The evaluation function should be applied only to positions that are quiescent,\n",
        "positions in which there is no pending move (such as a capturing the queen) that \n",
        "would wildly swing the evaluation. The horizon effect is more difficult to eliminate. \n",
        "It arises when the program is facing an opponent’s move that causes serious damage \n",
        "and is ultimately unavoidable, but can be temporarily avoided by the use of \n",
        "delaying tactics. One strategy to mitigate the horizon effect is to allow singular \n",
        "extensions, moves that are “clearly better” than all other moves in a given position, \n",
        "even when the search would normally be cut off at that point. 3) Alpha–beta pruning \n",
        "prunes branches of the tree that can have no effect on the final evaluation, but \n",
        "forward pruning prunes moves that appear to be poor moves, but might possibly be \n",
        "good ones. Thus, the strategy saves computation time at the risk of making an error.\n",
        "In Shannon’s terms, this is a Type B strategy. Beam search: only n best moves, but\n",
        "very dangerous. The PROBCUT, or probabilistic cut, algorithm is a forward-pruning \n",
        "version of alpha–beta search that uses statistics gained from prior experience to \n",
        "lessen the chance that the best move will be pruned. Another technique, late move \n",
        "reduction, works under the assumption that move ordering has been done well, and \n",
        "therefore moves that appear later in the list of possible moves are less likely \n",
        "to be good moves. But rather than pruning them away completely, we just reduce the \n",
        "depth to which we search these moves, thereby saving time. 4) Near the end of the \n",
        "game there are again fewer possible positions, and thus it is easier to do lookup. \n",
        "But here it is the computer that has the expertise: computer analysis of endgames \n",
        "goes far beyond human abilities. Novice humans can win a king-and-rook-versus-king \n",
        "(KRK) endgame by following a few simple rules. Other endings, such as king, bishop, \n",
        "and knight versus king (KBNK), are difficult to master and have no succinct strategy \n",
        "description. A computer, on the other hand, can completely solve the endgame by \n",
        "producing a policy, which is a mapping from every possible state to the best move \n",
        "in that state. Then the computer can play perfectly by looking up the right move \n",
        "in this table. The table is constructed by retrograde minimax search: start by \n",
        "considering all ways to place the KBNK pieces on the board. Then do reverse moves. \"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" Stochastic games bring us a little closer to the unpredictability \n",
        "of real life by including a random element. A game tree in backgammon must include \n",
        "chance nodes in addition to MAX and MIN nodes. The branches leading from each chance \n",
        "node denote the possible dice rolls; each branch is labeled with the roll and its \n",
        "probability. We can only calculate the expected value of a position: the average \n",
        "over all possible outcomes of the chance nodes. The expectiminimax value for games \n",
        "with chance nodes, a generalization of the minimax value for deterministic games.\n",
        "1) Expectiminimax takes O(b^m* n^m) compared to minimax that takes O(b^m) where n\n",
        "is the number of possible outcomes. Alpha–beta pruning can be applied to game \n",
        "trees with chance nodes.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" A goal-based agent has a binary distinction between good (goal) \n",
        "and bad (non-goal) states, while a decision-theoretic agent assigns a continuous \n",
        "range of values to states, and thus can more easily choose a better state even \n",
        "when no best state is available. A decision network/influence diagram extends Bayesian \n",
        "networks by incorporating actions and utilities. An agent here has P(s) to each\n",
        "possible current state s. The agent's preferences are captured by a utility function\n",
        "U(s), and we can compute the expected utility value of each action. The principle \n",
        "of maximum expected utility (MEU) says that a rational agent should choose the \n",
        "action that maximizes the agent’s expected utility. Estimating the probability distribution\n",
        "requires perception, learning, knowledge representation, and inference. Computing\n",
        "requires a causal model of the world. Consider the environments that could lead \n",
        "to an agent having a given percept history, and consider the different agents that \n",
        "we could design. If an agent acts so as to maximize a utility function that correctly \n",
        "reflects the performance measure, then the agent will achieve the highest possible \n",
        "performance score (averaged over all the possible environments). This is the \n",
        "central justification for the MEU principle itself. While the claim may seem \n",
        "tautological, it does in fact embody a very important transition from the external \n",
        "performance measure to an internal utility function. The performance measure gives \n",
        "a score for a history—a sequence of states. Thus it is applied retrospectively after \n",
        "an agent completes a sequence of actions. The utility function applies to the very \n",
        "next state, so it can be used to guide actions step by step. \"\"\"\n",
        "\n",
        "\n",
        "chapter16_2 = \"\"\" A lottery L = [P1, S1; P2, S2; ... Pn, Sn] where S is an outcome\n",
        "and P is a probability. Orderability states that the agent should prefer one lottery\n",
        "over another. Transitivity exists in orderability of preference. Continuity: If lottery\n",
        "A > B > C, exists P such that the agent is indifferent between B and [p, A; 1-p, C].\n",
        "Substitutability: if the agent is indifferent between A and B, [p, A; 1-p, C] ~ \n",
        "[p, B; 1-p, C]. Monotonicity: A>B and p>q, we have [p, A; 1-p, B] > [q, A; 1-q, B].\n",
        "Decomposability: Decomposability: [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B;\n",
        "(1-p)(1-q), C]. 2) Exist a utility function such that U(A) = U(B) when indifferent,\n",
        "U(A) > U(B) when A > B. Utility of a lottery is the linear combination of probability\n",
        "times the utility of each S. In a deterministic environment an agent needs only \n",
        "a preference ranking on states—the numbers don’t matter. This is called a value \n",
        "function or ordinal utility function. \"\"\"\n",
        "\n",
        "\n",
        "chapter16_3 = \"\"\" Preference elicitation, involves presenting choices to the human \n",
        "and using the observed preferences to pin down the underlying utility function.\n",
        "Normalized utilities use a scale that utility of best is 1 and utility of worst \n",
        "is 0. standard lottery is [p, 1; 1-p, 0]. Currently several agencies of the U.S. \n",
        "government use the [value of a statistical \n",
        "life] to determine the costs and benefits of regulations and interventions. One \n",
        "common “currency” used in medical and safety analysis is the micromort, a one in \n",
        "a million chance of death. Another measure is the quality-adjusted life \n",
        "year. Patients are willing to accept a shorter life expectancy to avoid a disability.\n",
        "2) It will usually be the case that an agent prefers more money to less, all other \n",
        "things being equal. We say that the agent exhibits a monotonic preference for more money. \n",
        "When the expected monetary value of the gamble is more than the original, but that\n",
        "does not mean accepting the gamble is a better decision. To determine what to do, \n",
        "we need to assign utilities to the outcome states. Utility is not directly proportional \n",
        "to monetary value, because the utility for your first million is very high, whereas \n",
        "the utility for an additional million is smaller. In a pioneering study of actual \n",
        "utility functions, Grayson found that the utility of money was almost exactly \n",
        "proportional to the logarithm of the amount. For U(L) < U(S-EMV(L)), agents with curves of this \n",
        "shape are risk-averse: they prefer a sure thing with a payoff that is less than \n",
        "the expected monetary value of a gamble. On the other hand, in the “desperate” \n",
        "region at large negative wealth, the behavior is risk-seeking. The value an agent \n",
        "will accept in lieu of a lottery is called the certainty equivalent of the lottery.\n",
        "The difference between the EMV of a lottery and its certainty equivalent is called \n",
        "the insurance premium. Risk aversion is the basis for the insurance industry, because \n",
        "it means that insurance premiums are positive. Notice that for small changes in \n",
        "wealth relative to the current wealth, almost any curve will be approximately linear. \n",
        "An agent that has a linear curve is said to be risk-neutral.\n",
        "3) bias = E[E[f]-E[f]_true). P(max(X1 < X...Xk < X))=F(x)^k. p(x) is the derivative\n",
        "of F(x)^k. This tendency for the estimated expected utility of the best choice to \n",
        "be too high is called the optimizer’s curse. 4) Decision theory is a normative theory: \n",
        "it describes how a rational agent should act. A descriptive theory, on the other hand, \n",
        "describes how actual agents really do act. One explanation for the apparently irrational \n",
        "preferences is the certainty effect people are strongly attracted to gains that are certain. \n",
        "Peo want ambituity aversion: wants deterministic. The framing effect is 90% survival\n",
        "rate over 10% death rate. The anchoring effect is to sell 50box water when there is\n",
        "another 100box water.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" 1> The minimax algorithm uses a depth-first approach.\n",
        "2> The time complexity of the minimax algorithm is O(b^m) where b is the number of\n",
        "legal moves at each node and m is the maximum depth of the tree. 3> Games differ\n",
        "from search because games have multiple agents. 4> A state where a game ends is called \n",
        "a terminal state. 5> A utility function U(s) gives the payoff for each player in \n",
        "terminal state s. 6> The minimax search algorthim solves perfect information, zero-sum\n",
        "games. 7> Minimax evaluates nodes in the same order as DFS. 8> Minimax evaluates \n",
        "each node as the value of the best terminal state reach by both player playing optimally.\n",
        "The current player tries to maximize the score and the other player tries to minimize \n",
        "it. 9> Alpha-beta pruning is more efficient that minimax because it eliminates provably \n",
        "irrelevant subtrees. 10> The running time of alpha-beta pruning is impacted by the \n",
        "order in which we examine nodes. 11> Alpha-beta pruning has optimal time complexity\n",
        "O(b^(m/2)) and worst time complexity O(b^m). 12> A Type A Strategy, as proposed by \n",
        "Claude Shannon, explores a wide but shallow portion of the tree. 13> A Type B Strategy, \n",
        "as proposed by Claude Shannon, explores a deep but narrow portion of the tree.\n",
        "14> Type A and Type B are useful because for games with a large search space, it \n",
        "is not feasible to search the whole tree. As such, we have to make tradeoffs about \n",
        "what part of the tree to search. 15> Heuristic alpha-beta search replaces the utility \n",
        "function with an evaluation function that estimates the value of non-terminal nodes. \n",
        "16> In heuristic alpha-beta pruning, the terminal test is replaced with a cutoff\n",
        "test that decides when to cut off the search. 17> The evaluation function should \n",
        "be applied only to positions that are quiescent. 18> A move is quiescent if there \n",
        "is no pending move that would wildly swing the valuation. 19> Forward pruning\n",
        "prunes moves that appear to be bad moves. Beam search is forward pruning. FP is\n",
        "type B strategy. 20> MCTS works by playing the game to the end while randomly selecting \n",
        "moves. MCTS evaluates an action by repeatedly playing the game from that state and \n",
        "taking the average of the results. 21> Expectiminimax is used to handle games of\n",
        "chance. 22> In minimax search, the value of a node is the optimal value of its children.\n",
        "23> Set of terminal states, a utility function, the initial state, and the set of \n",
        "legal moves that a player can make are required to define a game. The Waltz/Mackworth \n",
        "\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(module5_lecture_notes.split(' ')))\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"a synonym for fully observable\",  \n",
        "\"zero-sum\": \"what is good for one player is just as bad for the other\",\n",
        "\"move\": \"a synonym for action\",\n",
        "\"position\": \"a synonym for state\",\n",
        "\"horizontal effect\": \"facing an opponent’s move that causes serious and unavoidable damage that can be temporarily avoided\",\n",
        "\"game\": \"initial state, legal actions at each state, result of action, terminal test, and utility function\",\n",
        "\"initial state\": \"how the board is set up\",\n",
        "\"heuristic evaluation function\": \"estimates the utility of a state\",\n",
        "\"expectiminimax\": \"an extension to the minimax algorithm that evaluates a chance node by weighted average\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 55,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 422\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "558c3fbb-0e63-40d3-9178-81747c73309f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 56,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Competitive environments, in which two or more agents have conflicting \ngoals, giving rise to adversarial search problems. stance 1: the aggregate as \nan economy, allowing us to do things like predict that increasing demand will cause \nprices to rise, without having to predict the action of any individual agent. \nstance 2: adversarial agents as just a part of the environment—a part that makes \nthe environment nondeterministic. stance 3: explicitly model the adversarial agents \nwith the techniques of adversarial game-tree search. We do stance 3. Define the state \nspace graph—a graph where the vertices are states, the edges are moves and a state \nmight be reached by multiple paths. Define the complete game tree as a search tree \nthat follows every sequence of moves all the way to a terminal state.  \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n 0) The minimax value is the utility at a terminal state, the \nmaximum for max and minimum for min. The minimax value assumes that both players \nplay optimally. 1) Minimax search is a recursive algorithm that proceeds all the \nway down to the leaves of the tree and then backs up the minimax values through \nthe tree as the recursion unwinds. The minimax algorithm performs a complete \ndepth-first exploration of the game tree. 2) Multi-agent: each player chooses their\nmax value. 3) Pruning eliminates the examination of some states. alpha is the value\nof the best choice we have found so far at any choice point along the path for MAX.\nbeta the value of the best choice we have found so far at any choice point along \nthe path for MIN. 4) depends on order, so try to first examine the successors that \nare likely to be best. perfect: O(b^(m/2)) instead of O(b^m) for minimax. Iterative \ndeepening record the ranking of moves then try killer moves (best moves). In game \ntree search, repeated states can occur because of transpositions—different permutations \nof the move sequence that end up in the same position, and the problem can be \naddressed with a transposition table that caches the heuristic value of states.\nStrategies when there are too m any states: Type A strategy considers all possible \nmoves to a certain depth in the search tree, and then uses a heuristic evaluation \nfunction to estimate the utility of states at that depth. It explores a wide but \nshallow portion of the tree. A Type B strategy ignores moves that look bad, and \nfollows promising lines “as far as possible.” It explores a deep but narrow portion \nof the tree.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n 1) Heuristic alpha-beta tree search estimates a nonterminal state's\nutility and replace the terminal test by a cutoff test. The heuristic eval(s, p)\nreturns an estimate of the expected utility of state s to player p at a depth level\nthat is cutoff. For terminal states: eval(s,p) = utility(s,p). For nonterminal:\neval is between loss and win utility. A reasonable evaluation is the expected value.\nMaterial value is defined to have feature values for different objects in game.\nEvaluation would be a linear combination of material values(king is 5, pawn is 1).\n2) The evaluation function should be applied only to positions that are quiescent,\npositions in which there is no pending move (such as a capturing the queen) that \nwould wildly swing the evaluation. The horizon effect is more difficult to eliminate. \nIt arises when the program is facing an opponent’s move that causes serious damage \nand is ultimately unavoidable, but can be temporarily avoided by the use of \ndelaying tactics. One strategy to mitigate the horizon effect is to allow singular \nextensions, moves that are “clearly better” than all other moves in a given position, \neven when the search would normally be cut off at that point. 3) Alpha–beta pruning \nprunes branches of the tree that can have no effect on the final evaluation, but \nforward pruning prunes moves that appear to be poor moves, but might possibly be \ngood ones. Thus, the strategy saves computation time at the risk of making an error.\nIn Shannon’s terms, this is a Type B strategy. Beam search: only n best moves, but\nvery dangerous. The PROBCUT, or probabilistic cut, algorithm is a forward-pruning \nversion of alpha–beta search that uses statistics gained from prior experience to \nlessen the chance that the best move will be pruned. Another technique, late move \nreduction, works under the assumption that move ordering has been done well, and \ntherefore moves that appear later in the list of possible moves are less likely \nto be good moves. But rather than pruning them away completely, we just reduce the \ndepth to which we search these moves, thereby saving time. 4) Near the end of the \ngame there are again fewer possible positions, and thus it is easier to do lookup. \nBut here it is the computer that has the expertise: computer analysis of endgames \ngoes far beyond human abilities. Novice humans can win a king-and-rook-versus-king \n(KRK) endgame by following a few simple rules. Other endings, such as king, bishop, \nand knight versus king (KBNK), are difficult to master and have no succinct strategy \ndescription. A computer, on the other hand, can completely solve the endgame by \nproducing a policy, which is a mapping from every possible state to the best move \nin that state. Then the computer can play perfectly by looking up the right move \nin this table. The table is constructed by retrograde minimax search: start by \nconsidering all ways to place the KBNK pieces on the board. Then do reverse moves. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability \nof real life by including a random element. A game tree in backgammon must include \nchance nodes in addition to MAX and MIN nodes. The branches leading from each chance \nnode denote the possible dice rolls; each branch is labeled with the roll and its \nprobability. We can only calculate the expected value of a position: the average \nover all possible outcomes of the chance nodes. The expectiminimax value for games \nwith chance nodes, a generalization of the minimax value for deterministic games.\n1) Expectiminimax takes O(b^m* n^m) compared to minimax that takes O(b^m) where n\nis the number of possible outcomes. Alpha–beta pruning can be applied to game \ntrees with chance nodes.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n A goal-based agent has a binary distinction between good (goal) \nand bad (non-goal) states, while a decision-theoretic agent assigns a continuous \nrange of values to states, and thus can more easily choose a better state even \nwhen no best state is available. A decision network/influence diagram extends Bayesian \nnetworks by incorporating actions and utilities. An agent here has P(s) to each\npossible current state s. The agent's preferences are captured by a utility function\nU(s), and we can compute the expected utility value of each action. The principle \nof maximum expected utility (MEU) says that a rational agent should choose the \naction that maximizes the agent’s expected utility. Estimating the probability distribution\nrequires perception, learning, knowledge representation, and inference. Computing\nrequires a causal model of the world. Consider the environments that could lead \nto an agent having a given percept history, and consider the different agents that \nwe could design. If an agent acts so as to maximize a utility function that correctly \nreflects the performance measure, then the agent will achieve the highest possible \nperformance score (averaged over all the possible environments). This is the \ncentral justification for the MEU principle itself. While the claim may seem \ntautological, it does in fact embody a very important transition from the external \nperformance measure to an internal utility function. The performance measure gives \na score for a history—a sequence of states. Thus it is applied retrospectively after \nan agent completes a sequence of actions. The utility function applies to the very \nnext state, so it can be used to guide actions step by step. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n A lottery L = [P1, S1; P2, S2; ... Pn, Sn] where S is an outcome\nand P is a probability. Orderability states that the agent should prefer one lottery\nover another. Transitivity exists in orderability of preference. Continuity: If lottery\nA > B > C, exists P such that the agent is indifferent between B and [p, A; 1-p, C].\nSubstitutability: if the agent is indifferent between A and B, [p, A; 1-p, C] ~ \n[p, B; 1-p, C]. Monotonicity: A>B and p>q, we have [p, A; 1-p, B] > [q, A; 1-q, B].\nDecomposability: Decomposability: [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B;\n(1-p)(1-q), C]. 2) Exist a utility function such that U(A) = U(B) when indifferent,\nU(A) > U(B) when A > B. Utility of a lottery is the linear combination of probability\ntimes the utility of each S. In a deterministic environment an agent needs only \na preference ranking on states—the numbers don’t matter. This is called a value \nfunction or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation, involves presenting choices to the human \nand using the observed preferences to pin down the underlying utility function.\nNormalized utilities use a scale that utility of best is 1 and utility of worst \nis 0. standard lottery is [p, 1; 1-p, 0]. Currently several agencies of the U.S. \ngovernment use the [value of a statistical \nlife] to determine the costs and benefits of regulations and interventions. One \ncommon “currency” used in medical and safety analysis is the micromort, a one in \na million chance of death. Another measure is the quality-adjusted life \nyear. Patients are willing to accept a shorter life expectancy to avoid a disability.\n2) It will usually be the case that an agent prefers more money to less, all other \nthings being equal. We say that the agent exhibits a monotonic preference for more money. \nWhen the expected monetary value of the gamble is more than the original, but that\ndoes not mean accepting the gamble is a better decision. To determine what to do, \nwe need to assign utilities to the outcome states. Utility is not directly proportional \nto monetary value, because the utility for your first million is very high, whereas \nthe utility for an additional million is smaller. In a pioneering study of actual \nutility functions, Grayson found that the utility of money was almost exactly \nproportional to the logarithm of the amount. For U(L) < U(S-EMV(L)), agents with curves of this \nshape are risk-averse: they prefer a sure thing with a payoff that is less than \nthe expected monetary value of a gamble. On the other hand, in the “desperate” \nregion at large negative wealth, the behavior is risk-seeking. The value an agent \nwill accept in lieu of a lottery is called the certainty equivalent of the lottery.\nThe difference between the EMV of a lottery and its certainty equivalent is called \nthe insurance premium. Risk aversion is the basis for the insurance industry, because \nit means that insurance premiums are positive. Notice that for small changes in \nwealth relative to the current wealth, almost any curve will be approximately linear. \nAn agent that has a linear curve is said to be risk-neutral.\n3) bias = E[E[f]-E[f]_true). P(max(X1 < X...Xk < X))=F(x)^k. p(x) is the derivative\nof F(x)^k. This tendency for the estimated expected utility of the best choice to \nbe too high is called the optimizer’s curse. 4) Decision theory is a normative theory: \nit describes how a rational agent should act. A descriptive theory, on the other hand, \ndescribes how actual agents really do act. One explanation for the apparently irrational \npreferences is the certainty effect people are strongly attracted to gains that are certain. \nPeo want ambituity aversion: wants deterministic. The framing effect is 90% survival\nrate over 10% death rate. The anchoring effect is to sell 50box water when there is\nanother 100box water.\n\n\n## Module 5 Lecture Notes\n 1> The minimax algorithm uses a depth-first approach.\n2> The time complexity of the minimax algorithm is O(b^m) where b is the number of\nlegal moves at each node and m is the maximum depth of the tree. 3> Games differ\nfrom search because games have multiple agents. 4> A state where a game ends is called \na terminal state. 5> A utility function U(s) gives the payoff for each player in \nterminal state s. 6> The minimax search algorthim solves perfect information, zero-sum\ngames. 7> Minimax evaluates nodes in the same order as DFS. 8> Minimax evaluates \neach node as the value of the best terminal state reach by both player playing optimally.\nThe current player tries to maximize the score and the other player tries to minimize \nit. 9> Alpha-beta pruning is more efficient that minimax because it eliminates provably \nirrelevant subtrees. 10> The running time of alpha-beta pruning is impacted by the \norder in which we examine nodes. 11> Alpha-beta pruning has optimal time complexity\nO(b^(m/2)) and worst time complexity O(b^m). 12> A Type A Strategy, as proposed by \nClaude Shannon, explores a wide but shallow portion of the tree. 13> A Type B Strategy, \nas proposed by Claude Shannon, explores a deep but narrow portion of the tree.\n14> Type A and Type B are useful because for games with a large search space, it \nis not feasible to search the whole tree. As such, we have to make tradeoffs about \nwhat part of the tree to search. 15> Heuristic alpha-beta search replaces the utility \nfunction with an evaluation function that estimates the value of non-terminal nodes. \n16> In heuristic alpha-beta pruning, the terminal test is replaced with a cutoff\ntest that decides when to cut off the search. 17> The evaluation function should \nbe applied only to positions that are quiescent. 18> A move is quiescent if there \nis no pending move that would wildly swing the valuation. 19> Forward pruning\nprunes moves that appear to be bad moves. Beam search is forward pruning. FP is\ntype B strategy. 20> MCTS works by playing the game to the end while randomly selecting \nmoves. MCTS evaluates an action by repeatedly playing the game from that state and \ntaking the average of the results. 21> Expectiminimax is used to handle games of\nchance. 22> In minimax search, the value of a node is the optimal value of its children.\n23> Set of terminal states, a utility function, the initial state, and the set of \nlegal moves that a player can make are required to define a game. The Waltz/Mackworth \n\n\n## Module 5 Definitions\n* **Perfect information** - a synonym for fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Move** - a synonym for action\n* **Position** - a synonym for state\n* **Horizontal effect** - facing an opponent’s move that causes serious and unavoidable damage that can be temporarily avoided\n* **Game** - initial state, legal actions at each state, result of action, terminal test, and utility function\n* **Initial state** - how the board is set up\n* **Heuristic evaluation function** - estimates the utility of a state\n* **Expectiminimax** - an extension to the minimax algorithm that evaluates a chance node by weighted average\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3ee09393-3543-4d0d-ac28-7c3c76134e12"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "\n",
        "chapter6_1 = \"\"\" CSP search algorithms take advantage of the structure of states \n",
        "and use general rather than domain-specific heuristics to enable the solution of \n",
        "complex problems. CSPs have the additional advantage that the actions and transition \n",
        "model can be deduced from the problem description. 0) An assignment of values to\n",
        "variables is {Xi = vi, Xj = vj...} where vi is in domain Di for Xi. 1) Visualize \n",
        "CSP as a constraint graph with nodes corresponding to variables of the problem and \n",
        "edges cnnecting two variables as constraints. 2) precedence constraints is one has \n",
        "to be earlier than other. disjunctive constraint is that two can't overlap. \n",
        "3) The simplest kind of CSP involves variables that have discrete, finite domains.\n",
        "A discrete domain can be infinite, such as the set of integers or strings. Special \n",
        "solution algorithms exist for linear constraints on integer variables in which each \n",
        "variable appears only in linear form. It can be shown that no algorithm exists for \n",
        "solving general nonlinear constraints on integer variables—the problem is undecidable.\n",
        "The best-known category of continuous-domain CSPs is that of linear programming \n",
        "problems, where constraints must be linear equalities or inequalities. Linear \n",
        "programming problems can be solved in time polynomial in the number of variables.\n",
        "Binary CSP can be represented as a constraint graph. Cryptarithmetic can be represented\n",
        "as aconstraint hypergraph consists of ordinary nodes and hypernodes that represent\n",
        "n-th order constraints. We could transform any CSP into one with only binary constraints—which \n",
        "certainly makes the life of the algorithm designer simpler. Another way to convert \n",
        "an -ary CSP to a binary one is the dual graph transformation: create a new graph \n",
        "in which there will be one variable for each constraint in the original graph, and \n",
        "one binary constraint for each pair of constraints in the original graph that share \n",
        "variables. Many real-world CSPs include preference constraints indicating which \n",
        "solutions are preferred. Preference constraints can often be encoded as costs on \n",
        "individual variable assignments. With this formulation, CSPs with preferences can \n",
        "be solved with optimization search methods, either path-based or local. We call \n",
        "such a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" 0) A CSP algorithm can do a specific type of inference called \n",
        "constraint propagation: using the constraints to reduce the number of legal values \n",
        "for a variable, which in turn can reduce the legal values for another variable, and so on.\n",
        "Constraint propagation may be intertwined with search, or it may be done as a preprocessing \n",
        "step, before search starts. The key idea is enforcing local consistency. 1) A single \n",
        "variable (corresponding to a node in the CSP graph) is node-consistent if all the \n",
        "values in the variable’s domain satisfy the variable’s unary constraints. \n",
        "2) A variable in a CSP is arc-consistent1 if every value in its domain satisfies \n",
        "the variable’s binary constraints. A graph is arc-consistent if every variable is\n",
        "arc-consistent withe very other variable. We have AC3 with total worst-case time of \n",
        "O(c*d^3) where d is the maximal domain size and c is the number of binary constraints.\n",
        "Checking consistency of 1 arc is O(d^2) time, and it can be deleted d times. \n",
        "3) Path consistency tightens the binary constraints by using implicit constraints \n",
        "that are inferred by looking at triples of variables. 4) A CSP is k-consistent if, \n",
        "for any set of variables and for any consistent assignment to those variables, a \n",
        "consistent value can always be assigned to any th variable.A CSP is strongly k-consistent \n",
        "if it is (k-1)-consistent and is also (k-2)-consistent, (k-3)-consistent, all the \n",
        "way down to 1-consistent. 5) global constraint: \n",
        "This leads to the following simple algorithm: First, remove any variable in the \n",
        "constraint that has a singleton domain, and delete that variable’s value from the \n",
        "domains of the remaining variables. Repeat as long as there are singleton variables. \n",
        "If at any point an empty domain is produced or there are more variables than domain \n",
        "values left, then an inconsistency has been detected. Resource constraint/atmost \n",
        "constraint in scheduling problems. Resource-limited problems domains are represented \n",
        "by upper and lower bounds and are managed by bounds propagation. We say that a CSP \n",
        "is bounds-consistent if for every variable , and for both the lower- bound and upper-bound \n",
        "values of X, there exists some value Y of that satisfies the constraint between X and \n",
        "Y for every variable Y. \"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" 0) Sometimes we can finish the constraint propagation process and \n",
        "still have variables with multiple possible values. In that case we have to search \n",
        "for a solution using standard depth-limited search. A problem is commutative if \n",
        "the order of application of any given set of actions does not matter. Leaves reduce\n",
        "from n!* d^n to d^n. BACKTRACKING-SEARCH keeps only a single representation of a \n",
        "state (assignment) and alters that representation rather than creating new ones.\n",
        "1) Backtracking can choose unassigned static ordering and randomly, but neither\n",
        "is optimal. The minimum-remaining-values (MRV) heuristic or the “most constrained \n",
        "variable” or “fail-first” heuristic performs better. Pick a variable that is most \n",
        "likely to cause a failure soon, thereby pruning the search tree.Once a variable has been selected, \n",
        "the algorithm must decide on the order in which to examine its values. The \n",
        "least-constraining-value heuristic is effective for this. It prefers the value \n",
        "that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
        "2) forward checking establishes arc consistency whenever a variable is assigned.\n",
        "The maintaining arc consistency algorithm detects inconsistencies by starting\n",
        "with all (Y, X) archs. MAC is stricltly more powerful than forward checking.\n",
        "3) Chronological backtracking refers to the most recent decision point being revisited.\n",
        "The conflic t set is a set of assignments that are in conflict with some value for some variable.\n",
        "The backjumping method backtracks to the most recent assignment in the conflict set\n",
        "and jump over previous assigned value. A backjumping algorithm that uses conflict \n",
        "sets defined in this way is called conflict-directed backjumping. Constraint learning \n",
        "is the idea of finding a minimum set of variables from the conflict set that causes \n",
        "the problem. This set of variables, along with their corresponding values, is called \n",
        "a no-good. We then record the no-good, either by adding a new constraint to the CSP \n",
        "to forbid this combination of assignments or by keeping a separate cache of no-goods.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter6_4 = \"\"\" Local search algorithms use a complete-state formulation where\n",
        "each state assigns a value to each variable, and the search changes the value of \n",
        "one variable at a time. Select the value that results in the minimum number of \n",
        "conflicts with other variables—the min-conflicts heuristic. The runtime of min-conflicts \n",
        "is roughly independent of problem size after initial assignment. The landscape of \n",
        "a CSP under the min- conflicts heuristic usually has a series of plateaus. There \n",
        "may be millions of variable assignments that are only one conflict away from a solution.\n",
        "Plateau search—allowing sideways moves to another state with the same score—can help local \n",
        "search find its way off this plateau. This wandering on the plateau can be directed \n",
        "with a technique called tabu search: keeping a small list of recently visited states \n",
        "and forbidding the algorithm to return to those states. Simulated annealing can \n",
        "also be used to escape from plateaus. Another technique called constraint weighting \n",
        "aims to concentrate the search on the important constraints. Each constraint is \n",
        "given a numeric weight, initially all 1. At each step of the search, the algorithm \n",
        "chooses a variable/value pair to change that will result in the lowest total weight \n",
        "of all violated constraints. The weights are then adjusted by incrementing the weight \n",
        "of each constraint that is violated by the current assignment. This has two benefits: \n",
        "it adds topography to plateaus, making sure that it is possible to improve from \n",
        "the current state, and it also adds learning: over time the difficult constraints \n",
        "are assigned higher weights. Another advantage of local search is that it can be \n",
        "used in an online setting when the problem changes. \"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\" 0) Divide the problem into independent subproblems so that combining\n",
        "subsolutions yields a solution. Independence can be ascertained simply by finding \n",
        "connected components of the constraint graph. n variables in total, c variables in\n",
        "subproblems, d size of domain. O(d^n) is reduced to O(d^c* n/c), which is linear\n",
        "to n versus exponential to n. A CSP is defined to be directional arc-consistent \n",
        "under an ordering of variables X1 to Xn if and only if every Xi is arc-consistent \n",
        "with each Xj for j > i. To solve a tree-structured CSP, first pick any variable \n",
        "to be the root of the tree, and choose an ordering of the variables such that each \n",
        "variable appears after its parent in the tree. Such an ordering is called a topological \n",
        "sort. Any tree with nodes has n-1 edges, so we can make this graph directed arc-consistent \n",
        "in O(n) steps, each of which must compare up to possible domain values for two \n",
        "variables, for a total time of O(n* d^2). Once we have a directed arc-consistent \n",
        "graph, we can just march down the list of variables and choose any remaining value. \n",
        "That means we won’t have to backtrack; we can move linearly through the variables.\n",
        "1) Cutset conditioning involves assigning values to some variables so that the \n",
        "remaining variables form a tree. Need to try various assigned values. Cycle cutset S\n",
        "is a subset of the CSP's variables that the CG becomes a tree after the removal \n",
        "of S. For each valid assignment in S, remove inconsistent values and solve. If the\n",
        "cycle cutset has size c, the total runtime is O(d^c* (n-c)* d^2). Efficient when c is small.\n",
        "2) Tree decomposition of the constraint graph is a transformation of the original graph \n",
        "into a tree where each node in the tree consists of a set of variables. Every variable in \n",
        "the original problem appears in at least one of the tree nodes. If two variables are connected \n",
        "by a constraint in the original problem, they must appear together (along with the \n",
        "constraint) in at least one of the tree nodes. If a variable appears in two nodes \n",
        "in the tree, it must appear in every node along the path connecting those nodes.\n",
        "Once a tree-structure graph is obtained, can solve in O(n* d^2) time when n is the\n",
        "number of tree nodes and d is the size of the largest domain. Efficient when d is\n",
        "small. The tree width of a tree decomposition of a graph is one less than the size \n",
        "of the largest node; the tree width of the graph itself is defined to be the minimum \n",
        "width among all its tree decompositions. If a graph has tree width then the problem \n",
        "can be solved in O(n* d^(w+1)) time. NP-hard to find smallest cycle cutset and smallest \n",
        "tree width. But tree decomposition is faster!!!! Cycle-cutset approach has linear memory \n",
        "while tree decomposition requires memory exponential in w. Symmetry-breaking constraint\n",
        "breaks value symmetry by assigning an order.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" 1> 6.3.2 MAC is a way of interleaving search and inference.\n",
        "AC-3 is pure inference. MAC runs while assigning variables in backtracking search. \n",
        "Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. \n",
        "Then, it runs identically to AC-3. 2> Cutset conditioning is used to reduce a general \n",
        "CSP to a tree structured one. 3> Solving a tree-structued CSP takes linear time in\n",
        "the number of variables. 4> In forward checking, whenever a variable X is assigned, \n",
        "we establish arc consistency for X. 5> The key idea behind inference in CSPs is\n",
        "enforcing local consistency. 6> Tree decomposition subproblems are efficient if \n",
        "the tree width of the constraint graph is small. 7> MAC stands for maintaining arc\n",
        "consistency. 8> Solving an arbitrary CSP takes exponential time in the number of\n",
        "variables. 9> Tree decomposition is faster than cutset conditioning. Whenever you \n",
        "have a cycle-cutset of size cc, there is also a tree of width w<c+1. 10> AC3 is \n",
        "an algorithm for enforcing arch consistency. 11> Cutset conditioning can be executed \n",
        "in linear memory, while tree decomposition requries memory exponential in the tree \n",
        "width w. 12> Node consistency is k-consistency for k = 1. 13> Backtracking search is\n",
        "a form of depth-first search. 14> MAC recursively propogrates constraints, whereas \n",
        "forward checking does not.If we assign X, forward checking makes all the arcs incident \n",
        "on X consistent. MAC does this, and if the domain of a variable Y changes, does the \n",
        "same for Y. 15> AC3: Place all the arcs in a queue. Pop arcs. For each arc, remove \n",
        "inconsistent values. If we change the values of a node, add its arcs to the queue. \n",
        "Terminate when the queue is empty. 16> In CSP solvers, inference techniques use\n",
        "constraints to rule out variable assignment. 17> Tree decomposition techniques transform \n",
        "the CSP into a tree of subproblems. 18> CSP differ from search problems: In search \n",
        "problems, states are black boxes with a transition model to move between boxes. \n",
        "In CSPs, the agent can see inside the states and move between states accordingly.\n",
        "19> CSPs can rule out variable assignments using search or inference. 20> In CSP \n",
        "solvers, inference techniques use constraints to rule out variable assignment.\n",
        "21> A CSP is k-consistent if, for any set of k-1 variables and for any consistent \n",
        "assignment to those variables, a consistent value can always be assigned to any \n",
        "kth variable. 22> Backtracking occurs when no legal assignment can be found for\n",
        "a variable. 23> MRV heuristic stands for Minimum Remaining Value and chooses the \n",
        "variable with the fewest 'legal' values. 24> The degree heuristic chooses the variable \n",
        "with the largest number of constraints. 25> The least constraining value heuristic \n",
        "chooses the value that rules out the fewest values for neighboring variables.\n",
        "26> constraint learning records the conflicts as they are encountered in the search \n",
        "in order to avoid the same conflict later. 27> Cutset conditioning is efficient \n",
        "if a small cutset can be found. However, in general, it is no more efficient than \n",
        "solving a CSP directly. There is no free-lunch in solving CSPs indirectly.\n",
        "Constraint Propagation Algorithm: 1. Assign every node in the constraint graph a \n",
        "set of all possible values. 2. Repeat until there is no change in the set of values \n",
        "associated with any node: 3. For each node i: For each neighboring node j in the picture:\n",
        "Remove any value from i which is not arc consistent with j.\n",
        "AC-3\n",
        "function AC-3(csp) return the CSP, possibly with reduced domains inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\n",
        "local variables: queue, a queue of arcs initially the arcs in csp while queue is not empty do\n",
        "(Xi, Xj) ¬ queue.pop()\n",
        "if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n",
        "for each Xk in NEIGHBORS[Xi ] – {Xj} do add (Xk, Xi) to queue\n",
        "  function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value removed ¬ false\n",
        "for each x in DOMAIN[Xi] do\n",
        "if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n",
        "then delete x from DOMAIN[Xi]; removed is true return removed.\n",
        "AC-3: Worst Case Complexity Analysis\n",
        "o 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(n2)\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(n2d3)\n",
        "(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3))\n",
        "\"\"\"\n",
        "print(\"The length in words is\", len(module6_lecture_notes.split(' ')))\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP_slide\" : \"consists of finite set of variables, nonempty domain of possible values, and finite set of constraints\",\n",
        "\"relation\": \"defines value that those variables can take on\",\n",
        "\"consistent/legal assignment\": \"an assignement that does not violate any constraints\",\n",
        "\"complete assignment\": \"an assignment in which every variable is assigned a value\",\n",
        "\"partial assignment\": \"an assignment that leaves some variables unassigned\",\n",
        "\"partial solution\": \"a partial assignment that is consistent\",\n",
        "\"unary constraint\": \"restricts the value of a single variable\",\n",
        "\"binary constraint\": \"relate two variables\",\n",
        "\"binary CSP\": \"one with only unary and binary constraints\",\n",
        "\"ternary constraint\": \"relate three variables\",\n",
        "\"global constraint\": \"a constraint involving an arbitrary number of variables\",\n",
        "\"CSP\": \"represent a state with a set of variable/value pairs and represent the conditions for a solution by a set of constraints on the variables.\",\n",
        "\"minimum-remaining-values and degree heuristics\": \"domain-independent methods for deciding which variable to choose next in a backtracking search.\",\n",
        "\"least- constraining-value heuristic\": \"helps in deciding which value to try first for a given variable\",\n",
        "\"backtracking\": \"occurs when no legal assignment can be found for a variable.\",\n",
        "\"Conflict-directed backjumping\": \"backtracks directly to the source of the problem\",\n",
        "\"Constraint learning\": \"records the conflicts as they are encountered during search in order to avoid the same conflict later in the search\",\n",
        "\"min-conflicts heuristic\": \"used by local search and applied to constraint satisfaction problems with great success.\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 58,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 738\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7a8263fe-cfc9-49a5-a8d9-96f8c150dc00"
      },
      "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": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'CSP' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP search algorithms take advantage of the structure of states \nand use general rather than domain-specific heuristics to enable the solution of \ncomplex problems. CSPs have the additional advantage that the actions and transition \nmodel can be deduced from the problem description. 0) An assignment of values to\nvariables is {Xi = vi, Xj = vj...} where vi is in domain Di for Xi. 1) Visualize \nCSP as a constraint graph with nodes corresponding to variables of the problem and \nedges cnnecting two variables as constraints. 2) precedence constraints is one has \nto be earlier than other. disjunctive constraint is that two can't overlap. \n3) The simplest kind of CSP involves variables that have discrete, finite domains.\nA discrete domain can be infinite, such as the set of integers or strings. Special \nsolution algorithms exist for linear constraints on integer variables in which each \nvariable appears only in linear form. It can be shown that no algorithm exists for \nsolving general nonlinear constraints on integer variables—the problem is undecidable.\nThe best-known category of continuous-domain CSPs is that of linear programming \nproblems, where constraints must be linear equalities or inequalities. Linear \nprogramming problems can be solved in time polynomial in the number of variables.\nBinary CSP can be represented as a constraint graph. Cryptarithmetic can be represented\nas aconstraint hypergraph consists of ordinary nodes and hypernodes that represent\nn-th order constraints. We could transform any CSP into one with only binary constraints—which \ncertainly makes the life of the algorithm designer simpler. Another way to convert \nan -ary CSP to a binary one is the dual graph transformation: create a new graph \nin which there will be one variable for each constraint in the original graph, and \none binary constraint for each pair of constraints in the original graph that share \nvariables. Many real-world CSPs include preference constraints indicating which \nsolutions are preferred. Preference constraints can often be encoded as costs on \nindividual variable assignments. With this formulation, CSPs with preferences can \nbe solved with optimization search methods, either path-based or local. We call \nsuch a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 0) A CSP algorithm can do a specific type of inference called \nconstraint propagation: using the constraints to reduce the number of legal values \nfor a variable, which in turn can reduce the legal values for another variable, and so on.\nConstraint propagation may be intertwined with search, or it may be done as a preprocessing \nstep, before search starts. The key idea is enforcing local consistency. 1) A single \nvariable (corresponding to a node in the CSP graph) is node-consistent if all the \nvalues in the variable’s domain satisfy the variable’s unary constraints. \n2) A variable in a CSP is arc-consistent1 if every value in its domain satisfies \nthe variable’s binary constraints. A graph is arc-consistent if every variable is\narc-consistent withe very other variable. We have AC3 with total worst-case time of \nO(c*d^3) where d is the maximal domain size and c is the number of binary constraints.\nChecking consistency of 1 arc is O(d^2) time, and it can be deleted d times. \n3) Path consistency tightens the binary constraints by using implicit constraints \nthat are inferred by looking at triples of variables. 4) A CSP is k-consistent if, \nfor any set of variables and for any consistent assignment to those variables, a \nconsistent value can always be assigned to any th variable.A CSP is strongly k-consistent \nif it is (k-1)-consistent and is also (k-2)-consistent, (k-3)-consistent, all the \nway down to 1-consistent. 5) global constraint: \nThis leads to the following simple algorithm: First, remove any variable in the \nconstraint that has a singleton domain, and delete that variable’s value from the \ndomains of the remaining variables. Repeat as long as there are singleton variables. \nIf at any point an empty domain is produced or there are more variables than domain \nvalues left, then an inconsistency has been detected. Resource constraint/atmost \nconstraint in scheduling problems. Resource-limited problems domains are represented \nby upper and lower bounds and are managed by bounds propagation. We say that a CSP \nis bounds-consistent if for every variable , and for both the lower- bound and upper-bound \nvalues of X, there exists some value Y of that satisfies the constraint between X and \nY for every variable Y. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n 0) Sometimes we can finish the constraint propagation process and \nstill have variables with multiple possible values. In that case we have to search \nfor a solution using standard depth-limited search. A problem is commutative if \nthe order of application of any given set of actions does not matter. Leaves reduce\nfrom n!* d^n to d^n. BACKTRACKING-SEARCH keeps only a single representation of a \nstate (assignment) and alters that representation rather than creating new ones.\n1) Backtracking can choose unassigned static ordering and randomly, but neither\nis optimal. The minimum-remaining-values (MRV) heuristic or the “most constrained \nvariable” or “fail-first” heuristic performs better. Pick a variable that is most \nlikely to cause a failure soon, thereby pruning the search tree.Once a variable has been selected, \nthe algorithm must decide on the order in which to examine its values. The \nleast-constraining-value heuristic is effective for this. It prefers the value \nthat rules out the fewest choices for the neighboring variables in the constraint graph.\n2) forward checking establishes arc consistency whenever a variable is assigned.\nThe maintaining arc consistency algorithm detects inconsistencies by starting\nwith all (Y, X) archs. MAC is stricltly more powerful than forward checking.\n3) Chronological backtracking refers to the most recent decision point being revisited.\nThe conflic t set is a set of assignments that are in conflict with some value for some variable.\nThe backjumping method backtracks to the most recent assignment in the conflict set\nand jump over previous assigned value. A backjumping algorithm that uses conflict \nsets defined in this way is called conflict-directed backjumping. Constraint learning \nis the idea of finding a minimum set of variables from the conflict set that causes \nthe problem. This set of variables, along with their corresponding values, is called \na no-good. We then record the no-good, either by adding a new constraint to the CSP \nto forbid this combination of assignments or by keeping a separate cache of no-goods.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms use a complete-state formulation where\neach state assigns a value to each variable, and the search changes the value of \none variable at a time. Select the value that results in the minimum number of \nconflicts with other variables—the min-conflicts heuristic. The runtime of min-conflicts \nis roughly independent of problem size after initial assignment. The landscape of \na CSP under the min- conflicts heuristic usually has a series of plateaus. There \nmay be millions of variable assignments that are only one conflict away from a solution.\nPlateau search—allowing sideways moves to another state with the same score—can help local \nsearch find its way off this plateau. This wandering on the plateau can be directed \nwith a technique called tabu search: keeping a small list of recently visited states \nand forbidding the algorithm to return to those states. Simulated annealing can \nalso be used to escape from plateaus. Another technique called constraint weighting \naims to concentrate the search on the important constraints. Each constraint is \ngiven a numeric weight, initially all 1. At each step of the search, the algorithm \nchooses a variable/value pair to change that will result in the lowest total weight \nof all violated constraints. The weights are then adjusted by incrementing the weight \nof each constraint that is violated by the current assignment. This has two benefits: \nit adds topography to plateaus, making sure that it is possible to improve from \nthe current state, and it also adds learning: over time the difficult constraints \nare assigned higher weights. Another advantage of local search is that it can be \nused in an online setting when the problem changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n 0) Divide the problem into independent subproblems so that combining\nsubsolutions yields a solution. Independence can be ascertained simply by finding \nconnected components of the constraint graph. n variables in total, c variables in\nsubproblems, d size of domain. O(d^n) is reduced to O(d^c* n/c), which is linear\nto n versus exponential to n. A CSP is defined to be directional arc-consistent \nunder an ordering of variables X1 to Xn if and only if every Xi is arc-consistent \nwith each Xj for j > i. To solve a tree-structured CSP, first pick any variable \nto be the root of the tree, and choose an ordering of the variables such that each \nvariable appears after its parent in the tree. Such an ordering is called a topological \nsort. Any tree with nodes has n-1 edges, so we can make this graph directed arc-consistent \nin O(n) steps, each of which must compare up to possible domain values for two \nvariables, for a total time of O(n* d^2). Once we have a directed arc-consistent \ngraph, we can just march down the list of variables and choose any remaining value. \nThat means we won’t have to backtrack; we can move linearly through the variables.\n1) Cutset conditioning involves assigning values to some variables so that the \nremaining variables form a tree. Need to try various assigned values. Cycle cutset S\nis a subset of the CSP's variables that the CG becomes a tree after the removal \nof S. For each valid assignment in S, remove inconsistent values and solve. If the\ncycle cutset has size c, the total runtime is O(d^c* (n-c)* d^2). Efficient when c is small.\n2) Tree decomposition of the constraint graph is a transformation of the original graph \ninto a tree where each node in the tree consists of a set of variables. Every variable in \nthe original problem appears in at least one of the tree nodes. If two variables are connected \nby a constraint in the original problem, they must appear together (along with the \nconstraint) in at least one of the tree nodes. If a variable appears in two nodes \nin the tree, it must appear in every node along the path connecting those nodes.\nOnce a tree-structure graph is obtained, can solve in O(n* d^2) time when n is the\nnumber of tree nodes and d is the size of the largest domain. Efficient when d is\nsmall. The tree width of a tree decomposition of a graph is one less than the size \nof the largest node; the tree width of the graph itself is defined to be the minimum \nwidth among all its tree decompositions. If a graph has tree width then the problem \ncan be solved in O(n* d^(w+1)) time. NP-hard to find smallest cycle cutset and smallest \ntree width. But tree decomposition is faster!!!! Cycle-cutset approach has linear memory \nwhile tree decomposition requires memory exponential in w. Symmetry-breaking constraint\nbreaks value symmetry by assigning an order.\n\n\n## Module 6 Lecture Notes\n 1> 6.3.2 MAC is a way of interleaving search and inference.\nAC-3 is pure inference. MAC runs while assigning variables in backtracking search. \nInstead of queueing all arcs, MAC only queues arcs incident on the assigned variable. \nThen, it runs identically to AC-3. 2> Cutset conditioning is used to reduce a general \nCSP to a tree structured one. 3> Solving a tree-structued CSP takes linear time in\nthe number of variables. 4> In forward checking, whenever a variable X is assigned, \nwe establish arc consistency for X. 5> The key idea behind inference in CSPs is\nenforcing local consistency. 6> Tree decomposition subproblems are efficient if \nthe tree width of the constraint graph is small. 7> MAC stands for maintaining arc\nconsistency. 8> Solving an arbitrary CSP takes exponential time in the number of\nvariables. 9> Tree decomposition is faster than cutset conditioning. Whenever you \nhave a cycle-cutset of size cc, there is also a tree of width w<c+1. 10> AC3 is \nan algorithm for enforcing arch consistency. 11> Cutset conditioning can be executed \nin linear memory, while tree decomposition requries memory exponential in the tree \nwidth w. 12> Node consistency is k-consistency for k = 1. 13> Backtracking search is\na form of depth-first search. 14> MAC recursively propogrates constraints, whereas \nforward checking does not.If we assign X, forward checking makes all the arcs incident \non X consistent. MAC does this, and if the domain of a variable Y changes, does the \nsame for Y. 15> AC3: Place all the arcs in a queue. Pop arcs. For each arc, remove \ninconsistent values. If we change the values of a node, add its arcs to the queue. \nTerminate when the queue is empty. 16> In CSP solvers, inference techniques use\nconstraints to rule out variable assignment. 17> Tree decomposition techniques transform \nthe CSP into a tree of subproblems. 18> CSP differ from search problems: In search \nproblems, states are black boxes with a transition model to move between boxes. \nIn CSPs, the agent can see inside the states and move between states accordingly.\n19> CSPs can rule out variable assignments using search or inference. 20> In CSP \nsolvers, inference techniques use constraints to rule out variable assignment.\n21> A CSP is k-consistent if, for any set of k-1 variables and for any consistent \nassignment to those variables, a consistent value can always be assigned to any \nkth variable. 22> Backtracking occurs when no legal assignment can be found for\na variable. 23> MRV heuristic stands for Minimum Remaining Value and chooses the \nvariable with the fewest 'legal' values. 24> The degree heuristic chooses the variable \nwith the largest number of constraints. 25> The least constraining value heuristic \nchooses the value that rules out the fewest values for neighboring variables.\n26> constraint learning records the conflicts as they are encountered in the search \nin order to avoid the same conflict later. 27> Cutset conditioning is efficient \nif a small cutset can be found. However, in general, it is no more efficient than \nsolving a CSP directly. There is no free-lunch in solving CSPs indirectly.\nConstraint Propagation Algorithm: 1. Assign every node in the constraint graph a \nset of all possible values. 2. Repeat until there is no change in the set of values \nassociated with any node: 3. For each node i: For each neighboring node j in the picture:\nRemove any value from i which is not arc consistent with j.\nAC-3\nfunction AC-3(csp) return the CSP, possibly with reduced domains inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\nlocal variables: queue, a queue of arcs initially the arcs in csp while queue is not empty do\n(Xi, Xj) ¬ queue.pop()\nif REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\nfor each Xk in NEIGHBORS[Xi ] – {Xj} do add (Xk, Xi) to queue\n  function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value removed ¬ false\nfor each x in DOMAIN[Xi] do\nif no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\nthen delete x from DOMAIN[Xi]; removed is true return removed.\nAC-3: Worst Case Complexity Analysis\no All 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(n2)\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(n2d3)\n(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3))\n\n\n## Module 6 Definitions\n* **Csp_slide** - consists of finite set of variables, nonempty domain of possible values, and finite set of constraints\n* **Relation** - defines value that those variables can take on\n* **Consistent/legal assignment** - an assignement that does not violate any constraints\n* **Complete assignment** - an assignment in which every variable is assigned a value\n* **Partial assignment** - an assignment that leaves some variables unassigned\n* **Partial solution** - a partial assignment that is consistent\n* **Unary constraint** - restricts the value of a single variable\n* **Binary constraint** - relate two variables\n* **Binary csp** - one with only unary and binary constraints\n* **Ternary constraint** - relate three variables\n* **Global constraint** - a constraint involving an arbitrary number of variables\n* **Csp** - represent a state with a set of variable/value pairs and represent the conditions for a solution by a set of constraints on the variables.\n* **Minimum-remaining-values and degree heuristics** - domain-independent methods for deciding which variable to choose next in a backtracking search.\n* **Least- constraining-value heuristic** - helps in deciding which value to try first for a given variable\n* **Backtracking** - occurs when no legal assignment can be found for a variable.\n* **Conflict-directed backjumping** - backtracks directly to the source of the problem\n* **Constraint learning** - records the conflicts as they are encountered during search in order to avoid the same conflict later in the search\n* **Min-conflicts heuristic** - used by local search and applied to constraint satisfaction problems with great success.\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 = \"\"\" In AI, knowledge-based agents use a process of reasoning over an \n",
        "internal representation of knowledge to decide what actions to take. The central \n",
        "component of a knowledge-based agent is its knowledge base. A knowledge base is \n",
        "a set of sentences. Each sentence is expressed in a language called a knowledge \n",
        "representation language and represents some assertion about the world. When the \n",
        "sentence is taken as being given without being derived from other sentences, we \n",
        "call it an axiom. The standard names for these operations are add is TELL and query \n",
        "is ASK, respectively. Both operations may involve inference—that is, deriving new \n",
        "sentences from old. Inference must obey the requirement that when one ASKs a question \n",
        "of the knowledge base, the answer should follow from what has been told (or TELLed) \n",
        "to the knowledge base previously. knowledge level is where we need specify only \n",
        "what the agent knows and what its goals are, in order to determine its behavior.\n",
        "The knowledge level is independent of the implementation level. Starting with an \n",
        "empty knowledge base, the agent designer can TELL sentences one by one until the \n",
        "agent knows how to operate in its environment. This is called the declarative approach \n",
        "to system building. In contrast, the procedural approach encodes desired behaviors \n",
        "directly as program code.\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" PERFORMANCE MEASURE: for climbing out of the cave with the gold,\n",
        "for falling into a pit or being eaten by the wumpus, for each action taken, and\n",
        "for using up the arrow. The game ends either when the agent dies or when the agent \n",
        "climbs out of the cave.\n",
        "ENVIRONMENT: A grid of rooms, with walls surrounding the grid. The agent always \n",
        "starts in the square labeled [1,1], facing to the east. The locations of the gold \n",
        "and the wumpus are chosen randomly, with a uniform distribution, from the squares \n",
        "other than the start square. In addition, each square other than the start can be \n",
        "a pit, with probability 0.2.\n",
        "ACTUATORS: The agent can move Forward, TurnLeft by 90, or TurnRight by 90. The agent \n",
        "dies a miserable death if it enters a square containing a pit or a live wumpus. \n",
        "(It is safe, albeit smelly, to enter a square with a dead wumpus.) If an agent tries \n",
        "to move forward and bumps into a wall, then the agent does not move. The action Grab can be\n",
        "used to pick up the gold if it is in the same square as the agent. The action Shoot \n",
        "can be used to fire an arrow in a straight line in the direction the agent is facing. \n",
        "The arrow continues until it either hits (and hence kills) the wumpus or hits a wall. \n",
        "The agent has only one arrow, so only the first Shoot action has any effect. Finally, \n",
        "the action Climb can be used to climb out of the cave, but only from square [1,1].\n",
        "SENSORS: The agent has five sensors, each of which gives a single bit of information:\n",
        "‐ In the squares directly (not diagonally) adjacent to the wumpus, the agent will perceive\n",
        "a Stench.\n",
        "‐ In the squares directly adjacent to a pit, the agent will perceive a Breeze.\n",
        "‐ In the square where the gold is, the agent will perceive a Glitter.\n",
        "‐ When an agent walks into a wall, it will perceive a Bump.\n",
        "‐ When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.\n",
        "The percepts will be given to the agent program in the form of a list of five symbols; for \n",
        "example, if there is a stench and a breeze, but no glitter, bump, or scream, the agent \n",
        "program will get [Stench,Breeze,None,None,None]. \"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\" Knowledge bases consist of sentences. These sentences are expressed \n",
        "according to the syntax of the representation language, which specifies all the \n",
        "sentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic.\n",
        "A logic must also define the semantics, or meaning, of sentences. The semantics \n",
        "defines the truth of each sentence with respect to each possible world. In standard \n",
        "logics, every sentence must be either true or false in each possible world. \n",
        "If a sentence is true in model m, we say that m satisfies a or sometimes m is a model \n",
        "of a. We use the notation M(a) to mean the set of all models of a. The relation of \n",
        "logical entailment between sentences is the idea that a sentence follows logically \n",
        "from another sentence. formal definition of entailment: β⊨α if and only if in every \n",
        "model in which beta is true, alpha is also true. β⊨α if and only M(beta) is a subset\n",
        "of M(alpha). beta is the stronger assertion and can be x = 0. alpha can by xy = 0.\n",
        "An inference algorithm that derives only entailed sentences is called sound or truth-preserving. \n",
        "Soundness is a highly desirable property. An unsound inference procedure essentially \n",
        "makes things up as it goes along. The property of completeness is also desirable: \n",
        "an inference algorithm is complete if it can derive any sentence that is entailed. \n",
        "The final issue to consider is grounding—the connection between logical reasoning \n",
        "processes and the real environment in which the agent exists.  \"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" 1) The syntax of propositional logic defines the allowable sentences. \n",
        "The atomic sentences consist of a single proposition symbol. Complex sentences are \n",
        "constructed from simpler sentences, using parentheses and operators called logical \n",
        "connectives. A literal is either an atomic sentence (a positive literal) or a negated \n",
        "atomic sentence (a negative literal). AND is conjunction with conjuncts as its parts.\n",
        "OR is disjunction with disjunts as its parts. Implication sign has premise/antecedent\n",
        "and conclusion/consequent. Implications are also known as rules or if–then statements.\n",
        "Biconditional is if and only if. 2) A model sets the truth value, true or false, for\n",
        "every propositional symbol. The rules can also be expressed with truth tables that \n",
        "specify the truth value of a complex sentence for each possible assignment of truth \n",
        "values to its components\"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" Theorem proving—applying rules of inference directly to the sentences \n",
        "in our knowledge base to construct a proof of the desired sentence without consulting models.\n",
        "If the number of models is large but the length of the proof is short, then theorem \n",
        "proving can be more efficient than model checking. 1) inference rule: a -> b and a\n",
        "can get b. elimination rule: a and b can get a. bidirectional is two inference rules.\n",
        "2) resolution: given a1 or a2 or a3 or a4, not a2 or not a4, we have a1 or a3.\n",
        "given a1 or a2, not a1 or not a3, we have a2 or not a3, but reduce only a1 at this time,\n",
        "can't reduce two things at a time. More: given a1 or a2 or a3, not a2 or a5, a6, have\n",
        "a1 or a3 or a5 or a6. CNF: or in clauses, clauses connected by and, not on literals.\n",
        "a and not a should be discarded becuase it is an empty clause. Any complementary \n",
        "literals appear in the same cluase should be discarded. Ground resolution theorem:\n",
        "If a set of clauses is unsatisfiable, then the resolution closure of those clauses\n",
        "contains the empty clause. 3) Horn clauses are closed under resolution. Resolve two\n",
        "horn clauses yields a Horn clause. 1> Every definite clause can be written as an implication \n",
        "whose premise is a conjunction of positive literals and whose conclusion is a single \n",
        "positive literal. In Horn form, the premise is called the body and the conclusion \n",
        "is called the head. Fact is a sentence consisting of a single positive literal.\n",
        "2> Inference with Horn clauses can be done through the forward-chaining and \n",
        "backward-chaining algorithms. 3> Deciding entailment with Horn clauses can be done \n",
        "in time that is linear in the size of the knowledge base—a pleasant surprise.\n",
        "Horn form: definite clause not a or not b or c is implication a and b is c. \n",
        "4) The forward-chaining algorithm determines if a single proposition is entailed\n",
        "by a knowledge base of definite cluases. Forward chaining is sound and complete.\n",
        "Forward chaining is an example of the general concept of data-driven reasoning—that \n",
        "is, reasoning in which the focus of attention starts with the known data. \n",
        "The backward-chaining algorithm, as its name suggests, works backward from the \n",
        "query. If the query q is known to be true, then no work is needed. Otherwise, the \n",
        "algorithm finds those implications in the knowledge base whose conclusion is q. \n",
        "If all the premises of one of those implications can be proved true (by backward \n",
        "chaining), then is true. Backward chaining is a form of goal-directed reasoning. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "Conjunctive Normal Form (CNF)\n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n",
        "1> Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n",
        "2> Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n",
        "3> Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "4> Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n",
        "The sentence is now in CNF!\n",
        "Resolution Algorithm\n",
        "Inference procedures based on resolution work using the principle of proof by contradiction.\n",
        "To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\n",
        "First, convert (KB ⋀ ¬𝛂) into CNF\n",
        "Then apply the resolution rule to the resulting clauses.\n",
        "Resolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\n",
        "Continue the process until one of two things happens:\n",
        "There are no new clauses that can be added. In this case, the KB does not entail 𝛂 Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n",
        "The resolution algorithm is complete! This makes is a very important inference method.\n",
        "However, we don’t always need the full power of resolution. Some KBs are formulated in a more restrictive form which enables them to use more efficient inference algorithms.\n",
        "Definite clause – disjunction of literals where exactly one is positive\n",
        "Horn clause – disjunction of literals where at most one is positive\n",
        "This includes definite clauses\n",
        "And clauses with no positive literals\n",
        "Horn clauses are closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\n",
        "KBs with only definite clauses\n",
        "1> Every definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal.\n",
        "¬ L1,1 ⋁ ¬ Breeze ⋁ B1,1 can be written as the implication L1,1 ⋀ Breeze ⟹ B1,1\n",
        "2> Inference with Horn clauses can be done through the forward-chaining and\n",
        "backward-chaining algorithms\n",
        "3> Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n",
        "Forward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
        "Backward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose\n",
        "conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
        "Backward chaining is a form of goal-directed reasoning.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"wumpus world\" : \"a cave consisting of rooms connected by passageways\",\n",
        "\"syntax_book\": \"the structure of sentences\",\n",
        "\"semantics_book2\": \"the way in which the truth of sentences is determined\", \n",
        "\"semantics_book1\" : \"meaning of sentences\", \n",
        "\"model\" : \"mathematical abstraction of possible worlds\",\n",
        "\"grounding\": \"the connection between logical reasoning processes and the real environment in which the agent exists\",\n",
        "\"literal\": \"either an atomic sentence or a negated atomic sentence\",\n",
        "\"logical equivalence\": \"two sentences are logically equivalent if they are true in the same set of models\",\n",
        "\"logical equivalence\": \"two sentences are equivalent if and only if each of them entails the other\",\n",
        "\"validity\": \"A sentence is valid if it si true in all models\",\n",
        "\"satisfiability\": \"A sentence is satisfiable if it is true in some model\",\n",
        "\"definite clause\": \"a disjunction of literals with exactly one positive\",\n",
        "\"horn clause\": \"a disjunction of literals with at most one positive\",\n",
        "\"goal clause\": \"a disjunction of literals with at no positive\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f64d519c-ce4b-4d6e-959a-00c13037164e"
      },
      "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": 65,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n In AI, knowledge-based agents use a process of reasoning over an \ninternal representation of knowledge to decide what actions to take. The central \ncomponent of a knowledge-based agent is its knowledge base. A knowledge base is \na set of sentences. Each sentence is expressed in a language called a knowledge \nrepresentation language and represents some assertion about the world. When the \nsentence is taken as being given without being derived from other sentences, we \ncall it an axiom. The standard names for these operations are add is TELL and query \nis ASK, respectively. Both operations may involve inference—that is, deriving new \nsentences from old. Inference must obey the requirement that when one ASKs a question \nof the knowledge base, the answer should follow from what has been told (or TELLed) \nto the knowledge base previously. knowledge level is where we need specify only \nwhat the agent knows and what its goals are, in order to determine its behavior.\nThe knowledge level is independent of the implementation level. Starting with an \nempty knowledge base, the agent designer can TELL sentences one by one until the \nagent knows how to operate in its environment. This is called the declarative approach \nto system building. In contrast, the procedural approach encodes desired behaviors \ndirectly as program code.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PERFORMANCE MEASURE: for climbing out of the cave with the gold,\nfor falling into a pit or being eaten by the wumpus, for each action taken, and\nfor using up the arrow. The game ends either when the agent dies or when the agent \nclimbs out of the cave.\nENVIRONMENT: A grid of rooms, with walls surrounding the grid. The agent always \nstarts in the square labeled [1,1], facing to the east. The locations of the gold \nand the wumpus are chosen randomly, with a uniform distribution, from the squares \nother than the start square. In addition, each square other than the start can be \na pit, with probability 0.2.\nACTUATORS: The agent can move Forward, TurnLeft by 90, or TurnRight by 90. The agent \ndies a miserable death if it enters a square containing a pit or a live wumpus. \n(It is safe, albeit smelly, to enter a square with a dead wumpus.) If an agent tries \nto move forward and bumps into a wall, then the agent does not move. The action Grab can be\nused to pick up the gold if it is in the same square as the agent. The action Shoot \ncan be used to fire an arrow in a straight line in the direction the agent is facing. \nThe arrow continues until it either hits (and hence kills) the wumpus or hits a wall. \nThe agent has only one arrow, so only the first Shoot action has any effect. Finally, \nthe action Climb can be used to climb out of the cave, but only from square [1,1].\nSENSORS: The agent has five sensors, each of which gives a single bit of information:\n‐ In the squares directly (not diagonally) adjacent to the wumpus, the agent will perceive\na Stench.\n‐ In the squares directly adjacent to a pit, the agent will perceive a Breeze.\n‐ In the square where the gold is, the agent will perceive a Glitter.\n‐ When an agent walks into a wall, it will perceive a Bump.\n‐ When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.\nThe percepts will be given to the agent program in the form of a list of five symbols; for \nexample, if there is a stench and a breeze, but no glitter, bump, or scream, the agent \nprogram will get [Stench,Breeze,None,None,None]. \n\n## AIMA Chapter 7.3 Logic\n Knowledge bases consist of sentences. These sentences are expressed \naccording to the syntax of the representation language, which specifies all the \nsentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic.\nA logic must also define the semantics, or meaning, of sentences. The semantics \ndefines the truth of each sentence with respect to each possible world. In standard \nlogics, every sentence must be either true or false in each possible world. \nIf a sentence is true in model m, we say that m satisfies a or sometimes m is a model \nof a. We use the notation M(a) to mean the set of all models of a. The relation of \nlogical entailment between sentences is the idea that a sentence follows logically \nfrom another sentence. formal definition of entailment: β⊨α if and only if in every \nmodel in which beta is true, alpha is also true. β⊨α if and only M(beta) is a subset\nof M(alpha). beta is the stronger assertion and can be x = 0. alpha can by xy = 0.\nAn inference algorithm that derives only entailed sentences is called sound or truth-preserving. \nSoundness is a highly desirable property. An unsound inference procedure essentially \nmakes things up as it goes along. The property of completeness is also desirable: \nan inference algorithm is complete if it can derive any sentence that is entailed. \nThe final issue to consider is grounding—the connection between logical reasoning \nprocesses and the real environment in which the agent exists.  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 1) The syntax of propositional logic defines the allowable sentences. \nThe atomic sentences consist of a single proposition symbol. Complex sentences are \nconstructed from simpler sentences, using parentheses and operators called logical \nconnectives. A literal is either an atomic sentence (a positive literal) or a negated \natomic sentence (a negative literal). AND is conjunction with conjuncts as its parts.\nOR is disjunction with disjunts as its parts. Implication sign has premise/antecedent\nand conclusion/consequent. Implications are also known as rules or if–then statements.\nBiconditional is if and only if. 2) A model sets the truth value, true or false, for\nevery propositional symbol. The rules can also be expressed with truth tables that \nspecify the truth value of a complex sentence for each possible assignment of truth \nvalues to its components\n\n## AIMA 7.5 Propositional Theorem Proving\n Theorem proving—applying rules of inference directly to the sentences \nin our knowledge base to construct a proof of the desired sentence without consulting models.\nIf the number of models is large but the length of the proof is short, then theorem \nproving can be more efficient than model checking. 1) inference rule: a -> b and a\ncan get b. elimination rule: a and b can get a. bidirectional is two inference rules.\n2) resolution: given a1 or a2 or a3 or a4, not a2 or not a4, we have a1 or a3.\ngiven a1 or a2, not a1 or not a3, we have a2 or not a3, but reduce only a1 at this time,\ncan't reduce two things at a time. More: given a1 or a2 or a3, not a2 or a5, a6, have\na1 or a3 or a5 or a6. CNF: or in clauses, clauses connected by and, not on literals.\na and not a should be discarded becuase it is an empty clause. Any complementary \nliterals appear in the same cluase should be discarded. Ground resolution theorem:\nIf a set of clauses is unsatisfiable, then the resolution closure of those clauses\ncontains the empty clause. 3) Horn clauses are closed under resolution. Resolve two\nhorn clauses yields a Horn clause. 1> Every definite clause can be written as an implication \nwhose premise is a conjunction of positive literals and whose conclusion is a single \npositive literal. In Horn form, the premise is called the body and the conclusion \nis called the head. Fact is a sentence consisting of a single positive literal.\n2> Inference with Horn clauses can be done through the forward-chaining and \nbackward-chaining algorithms. 3> Deciding entailment with Horn clauses can be done \nin time that is linear in the size of the knowledge base—a pleasant surprise.\nHorn form: definite clause not a or not b or c is implication a and b is c. \n4) The forward-chaining algorithm determines if a single proposition is entailed\nby a knowledge base of definite cluases. Forward chaining is sound and complete.\nForward chaining is an example of the general concept of data-driven reasoning—that \nis, reasoning in which the focus of attention starts with the known data. \nThe backward-chaining algorithm, as its name suggests, works backward from the \nquery. If the query q is known to be true, then no work is needed. Otherwise, the \nalgorithm finds those implications in the knowledge base whose conclusion is q. \nIf all the premises of one of those implications can be proved true (by backward \nchaining), then is true. Backward chaining is a form of goal-directed reasoning. \n\n## Module 7 Lecture Notes\n \nConjunctive Normal Form (CNF)\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n1> Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n2> Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n3> Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4> Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\nThe sentence is now in CNF!\nResolution Algorithm\nInference procedures based on resolution work using the principle of proof by contradiction.\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\nFirst, convert (KB ⋀ ¬𝛂) into CNF\nThen apply the resolution rule to the resulting clauses.\nResolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\nContinue the process until one of two things happens:\nThere are no new clauses that can be added. In this case, the KB does not entail 𝛂 Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\nThe resolution algorithm is complete! This makes is a very important inference method.\nHowever, we don’t always need the full power of resolution. Some KBs are formulated in a more restrictive form which enables them to use more efficient inference algorithms.\nDefinite clause – disjunction of literals where exactly one is positive\nHorn clause – disjunction of literals where at most one is positive\nThis includes definite clauses\nAnd clauses with no positive literals\nHorn clauses are closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\nKBs with only definite clauses\n1> Every definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal.\n¬ L1,1 ⋁ ¬ Breeze ⋁ B1,1 can be written as the implication L1,1 ⋀ Breeze ⟹ B1,1\n2> Inference with Horn clauses can be done through the forward-chaining and\nbackward-chaining algorithms\n3> Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\nForward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\nBackward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\nBackward chaining is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Wumpus world** - a cave consisting of rooms connected by passageways\n* **Syntax_book** - the structure of sentences\n* **Semantics_book2** - the way in which the truth of sentences is determined\n* **Semantics_book1** - meaning of sentences\n* **Model** - mathematical abstraction of possible worlds\n* **Grounding** - the connection between logical reasoning processes and the real environment in which the agent exists\n* **Literal** - either an atomic sentence or a negated atomic sentence\n* **Logical equivalence** - two sentences are equivalent if and only if each of them entails the other\n* **Validity** - A sentence is valid if it si true in all models\n* **Satisfiability** - A sentence is satisfiable if it is true in some model\n* **Definite clause** - a disjunction of literals with exactly one positive\n* **Horn clause** - a disjunction of literals with at most one positive\n* **Goal clause** - a disjunction of literals with at no positive\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": "e9b09784-df5d-4bba-95d8-850936c66cce"
      },
      "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": 66,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI definition: fidelity to human performance vs rationality(doing \nthe right thing). Intelligence: a property of internal thought process and \nreasoning vs. intelligent behavior. 4 dimensions: human vs. rational and thought \nvs. behavior. 1)Acting humanly: the Turing test approach. A computer passes the \ntest if a human interrogator cannot tell whether it comes from a person. The \ncomputer needs capabilities: natural lanugage processing for successful communication, \nknowledge representation to store knowledge, automated reasoning to answer questions\nand draw conclusions, and machien learning to adapt to new circumstances and to \ndetect patterns. The total Turing test requires interaction with objects and people,\nso needs computer vision and robotics. 2) Thinking humanly: the cognitive modeling \napproach. Three ways to learn about human though: introspection(catch one's own \nthoughts), psychological experiments(observe a person), brain imaging(observe the \nbrain). 3)Think rationally: Aristotle provided pattern to derive correct conclusion \nfrom correct premises(logic). Logic requires knowledge of the world that is certain \nwhile theory of probability fills uncertainty. 4) Acting rationally: \nAgent is something that acts. A rational agent is one that acts to achieve the\nbest outcome or the best expected outcome when there is uncertainty. SOMETIMES making\ncorrect inferences is part of being a rational agent. Skills in the Turing test\nallow an agent to act rationally. Knowledge representation and reasoning enable \nagents to reach good decisions. Rational-agent to AI has two advantages: more\ngeneral than the \"laws of thought\" approach, not just correct inference and more\namenable to scientific development(rationality well defined mathematically). AI\nhas focused on the study and construction of agents that do the right thing. The\nright thing is defined by the objective provided to the agent. This is the\nstandard model. Perfect rationality is not feasible, so refine standard model to\naccomplish limited rationality. 5) Real world hard to specify the objective correctly\nand completely. Value alignment problem is the problem of achieving agreement between\nour true preferences and the input objective. We want agents that are provably \nbenefitial to humans.\n\n## AIMA Chapter 27.1 The Limits of AI\n John Searle: weak AI are machines that act as if they were intelligent,\nstrong AI are machines that are actually consciously thinking, not just simulating\nthinking. Strong AI is \"human-level' AI or 'general AI', referring to programs that\ncan solve an arbitrarily wide vareity of tasks, including novel ones, and as well as\na human. 1) Turing's 'arguement from informality of behavior' says that human behavior\nis far too complex to be captured by any formal set of rules. Hubert Dreyfus and \nStuart Dreyfus and Kenneth Sayre criticized Good Old-Fashioned AI, the simplest\nlogical agent，difficult to capture every contingency of appropriate behavior in \na set of necessary and sufficient logical rules, this is 'qualification problem'. \nProbabilistic reasoning system is good at open-ended domains, and deep learning\nsystems do well on informal tasks. The embodied cognition approach claims that it\nmakes no sense to consider the brain separately: cognition takes place within a\nbody, system as a whole. 2) The 'argument from disability' claims that 'a machine\ncan never do X'. 3) Turing and Godel proved that certain mathematical questions \nare in principle unanswerable by particular formal systems. Godel's incompleteness\ntheorem: for formal axiomatic framework F, sentence G(F) can't have 1. G(F) is a \nsentence of F and can't be proved within F and 2. If F is consistent, then G(F) is\ntrue. Lucas claimed that machines are mentally inferior to humans. 4) The Turing test:\na program to have a conversation via typed messages with an interrogator for five\nminutes. Machine passes if he fools the interrogator 30% of the time. ELIZA program,\nMgonz, Natachata, cyberlove. 2014, Eugene Goostman a new internet chatbot fooled\n33% of the untrained amateur judges by pretending himself to be a Ukrainian boy.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n 0) Philosophers claim that machines are not actually thinking,\nbut would be a only a simulation of thinking. Turing: we don't have direct evidence\nabout the internal mental states of other humans. Turing said that polite convention\nshould be extended to machines that 'everyone thinks'. 1) John Searle rejects the \npolite convention and proposes the famous Chinese rom. A person that understands\nEnglish only generate fluent, intelligent Chinese responses through following the\ninstructions in the rule book and finding symbols. Computers generate no understanding.\nSearle is a proponent of biological naturalism (mental states are high-level emergent\nfeatures that are caused by low-level physical processes in the neurons) and neurons\nhave 'it' but transistors do not. But cells don't understand either. 2) Consciousness\nis the awareness of the outside world, and of the self, and the subjective experience\nof living. Intrinsic nature of experiences is qualia.\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment\nthrough sensors and acting upon that environment through actuators. The term percept\nrefers to the content an agent's sensors are perceiving. An agent's percept sequence\nis the complete history of everything the agent has ever perceived. An agent's choice\nof action at any given instant can depend on its built-in knowledge and on the entire\npercept sequence observed to date, but not on anything it hasn't perceived. An agent's\nbehavior is described by the agent function that maps any given percept sequence to\nan action. An external characterization of the agent is a \"truth table\"(my term) \nwith all possible percept sequences as input. Internally, the agent function for \nan artificial agent will be implemented by an agent program. The agent function \nis an abstract mathematical description; the agent program is a concrete \nimplementation, running within some physical system.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing. 1) \nConsequentialism: we evaluate an agent's behavior by its consequences. When an agent\nis placed in an environment, it generates a sequence of actions according to the \npercepts it receives. This sequence of actions causes the environment to go through\na sequence of states. If the sequence is desirable, then the agent has performed\nwell. The notion of desirability is captured by a performance measure that evaluates\nany given sequence of environment states. Norbert Wiener warned that we should ensure\n'the purpose put into the machine is the purpose which we really desire'. As a general\nrule, it is better to design performance measures according to what one actually\nwants to be achieved in the environment, rather than according to how one thinks\nthe agent should bahave. 2) What is rational at any given time depends on four things:\n1> the performance measure that defines the criterion of success 2> The agent's\nprior knowledge of the environment 3> The actions that the agent can perform 4>\nThe agent's percept sequence to date. Definition of a rational agent: For each\npossible percept sequence, a rational agent should select an action that is expected\nto maximize its performance measure, given the evidence provided by the percept\nsequence and whatever built-in knolwedge the agent has. If the geography is unknown,\nthe agent will need to explore it. 3) Distinguish between rationality and omniscience.\nAn omniscient agent knows the actual outcome of its actions and can act accordingly;\nbut omniscience is impossible in reality. Rationality is not the same as perfection.\nRationality maximizes expected performance, while perfection maximizes actual\nperformance. The rational choice depends only on the percept sequence to date,\nso rationality doesn't require omniscience. However, it is not rational to cross\nthe road before looking both ways (uninformative percept sequence), and a rational\nagent should choose \"looking both way\" action before crossing because looking maximizes\nthe expected performance. Doing actions in order to modify future percepts is \ninformation gathering. Exploration in an unknown environment is also information\ngathering. Rational agent needs to gather information and also learn as much as\npossible from its percept sequences. Learning is the process of modifying and\naugmenting its configuration. To the extent that an agent relies on the prior\nknowledge of its designer raher than on its own percepts and learning processses,\n we say that the agent lacks autonomy. \n \n\n## AIMA 2.3 The Nature of Environments\n 0) Task environments are the 'problems' to which rational agents\nare the 'solutions'. The nature of the task environment directly affects the\nappropriate design for the agent program. 1) The heading of the task environment\nis described by PEAS(performance, environment, actuator, sensor). 2) Dimensions of\nthe task environments. 1. fully observable vs. partially observable. If an agent's\nsensors give it access to the complete state of the environment at each point in\nlife, then we say that the task environment is fully observable. A task environment\nis effectively fully observable if the sensors detect all aspects that are relevant\nto the choice of action; relevance depends on the performance measure. An agent doesn't\nneed to maintain any internal state to keep track of the world in foe. An environment\nmight be partially observable because of noisy and inaccurate sensors. If an agent\nhas no sensors at all, then the environment is unobservable. But the agent's goal\nmay still be accomplished. 2. single-agent vs. multiagent. Multiagent is whether B's\nbehavior is best described as maximizing a performance measure whose value depends\non A's behavior. Chess is a competitive multiagent environment. Driving is a \ncooperative multiagent(safe) and partially competitive environment(parking). 3> \ndeterministic vs. nondeterministic: If the next state of the environment is \ncompletely determined by the current state and the action executed by the agent, \nthe environment is deterministic. Fully observable and deterministic doesn't have\nuncertainty. However, partially observable can be nondeterministic. Stochastic is\na synonym for nondeterministic, but a model is stochastic if it explicitly deals\nwith probabilities. 4> episodic vs. sequential. In an episodic task environment,\nthe agent's experience is divided into atomic episodes. In each episode the agent\nreceives a percept then performs a single action. the next episode doesn't depend\non the actions taken in previous episodes. Classification tasks are episodic. In\nsequential environments, the current decision could affect all future decisions.\n5> static vs. dynamic: If the environment can change while an agent is deliberating,\nthen it is dynamic for the agents, static otherwise. If the environment doesn't \nchange with the passage of time but the agent's performance score does, then it is\nsemidynamic. 6> discrete vs. continues. Applies to the state of the environment,\nto the way time is handled, and to the percepts and actions of the agent. Chess is\ndiscrete, driving is continuous. 7> known vs. unknown. The distinction refers to\nthe agent's state of knowledge about the laws of physics of the environment. In a\nknown environment, the outcomes or outcome probabilities for all actions are given.\nA known environment can be partially observable: card games. An unknown environment\ncan be fully observable: video games(entire game state but doesn't know the effect\nof buttons until try them). \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the \nagent function—the mapping from percepts to actions. The agent architecture is\ncomputing device with physical sensors and actuators. agent = architecture + program. \n1) The agent programs take the current percept as input from the sensors and return an action to the \nactuators. Notice the difference between the agent program, which takes the current \npercept as input, and the agent function, which may depend on the entire percept history.\n2) Simple reflex agents select actions on the basis of the current \npercept, ignoring the rest of the percept history. Condition/situation-action\nrule is if-then. Escape from infinite loops is possible if \nthe agent can randomize its actions. 3) Model-based reflex agents: To handle partial\nobservable: The agent should maintain some sort of internal state that depends \non the percept history. \nFirst, we need the effects of the agent’s actions and how the \nworld evolves independently of the agent, which is the transition model of the \nworld. Second, we need some information about how the state of the \nworld is reflected in the agent’s percepts, which is the sensor model. Together, \nthe transition model and sensor model create a model-based agent that keep track of the state \nof the world by updating its internal states.\n4) Goal-based agents. As well as a current state description, the agent needs \nsome sort of goal information that describes situations that are desirable. Search\nand planning require AI to find action sequences that achieve the agent's goal. \n5) Utility-based agents. An agent’s utility function is essentially an \ninternalization of the performance \nmeasure. A rational utility-based agent chooses the action that maximizes the \nexpected utility of the action outcomes. A model-free utility-based agent can learn \nwhat action is best in a particular situation without ever learning exactly how \nthat action changes the environment.\n6) Learning agent. Learning allows the agent to operate in initially unknown environments \nand to become more competent than its initial knowledge alone might allow. A learning \nagent can be divided into four conceptual components. Learning element makes improvements.\nThe performance element selects external actions. critic. The problem generator \nsuggests actions that leads to new and informative experiences.\n7) In an atomic representation each state of the world is indivisible without \ninternal structures. A factored representation splits up each state into a fixed \nset of variables or attributes, each of which can have a value. In a structured\nrepresentation, objects and relationships can be described explicitly. Relational \ndatabase, first-order logic and probability models. AFS has increasing expressiveness.\nA localist representation has one-on-one mapping between concepts and memory locations.\nA distributed representation is otherwise.\n \n\n## Module 1 Lecture Notes\n Descartes Principle of dualism – that the mind or thinking \nself is essentially incorporeal or spiritual – that the mind exists separately from \nthe body: \"if a foot or arm or any other part of the body is cut off, nothing has \nthereby taken away from the mind.\" “I think, therefore I am.\" Rene Descartes wondered \nif he could know for sure that others who looked and behaved like him weren’t in \nfact automata. Bodies of people and animals are nothing more than complex machines, \nthe bones, muscles and organs could be replaced with cogs, pistons and cams. “if \nthere were machines bearing the image of our bodies, and capable of imitating our \nactions. For example, if touched in a particular place it may demand what we wish \nto say to it; if in another it may cry out that it is hurt. However there would \nbe two tests to know that they were not really men.”... They could never use properly \nuse language. Alan Turing \"I propose to consider the question, 'Can machines think?'\" \nBecause \"thinking\" is difficult to define, Turing chooses to \"replace the question \nby another, which is closely related to it and is expressed in relatively unambiguous\nwords.\" Turing's new question is: \"Are there imaginable digital computers which \nwould do well in the imitation game?\" A human evaluator would judge text-based \nconversations between a human and a machine designed to generate human-like responses. \nIf the evaluator cannot reliably tell the machine from the human, the machine passes \nthe test. The test results do not depend on the ability to give correct answers \nto questions, only how closely one's answers resemble those a human would give.\nJohn Searle The Chinese room Is the Turing Test a good test of whether machines \npossess intelligence? No, because the appearance of being a good conversational \nparticipant is achievable through simple symbol manipulation. Searle contends that \nthe application of rules to input symbols is not true intelligence. Searle contrasts \nstrong AI with weak AI. In strong AI, the computer really is a mind in the sense \nthat it can be literally said to understand and have other cognitive states. In \nweak AI, computers just simulate thought, their seeming understanding isn't real \nunderstanding. He argues that (biological) brains cause minds.\nDaniel Dennett wrote a short story called “Where Am I?” where he describes being \nrecruited by the Pentagon to have his brain removed from his body and connected \nvia radio links attaching his severed nerves. Body is sent on a secret mission to \ndiffuse bomb without radiation harming brain. His body is destroyed by the radiation, \nbut his consciousness continues in the vat. The scientists restore him in a new \nbody. Then it is revealed that constructed a computer duplicate of my brain, reproducing \nboth the complete information-processing structure and the computational speed of \nmy brain in a giant computer program. His brain in a vat is processing symbols. \nWhat makes this different than a computer processing symbols? An agent is anything that \nperceives its environment through sensors and can act on its environment through actuators\nA percept is the agent’s perceptual inputs at any given instance. An agent is specified \nby an agent function f:P -> a that maps a sequence of percept vectors P to an action \na from a set A: P = [p0, p1, ... pt], A = {a0, a1, ... ak}. An agent is anything \nthat can be viewed as perceiving its environment through sensors and acting upon \nthat environment. A rational agent is an agent that perceives its environment \nand behaves rationally Rational behavior: doing the right thing. AI is usually concerned \nwith Consequentialism. We evaluate an agent’s behavior by its consequences. Rational \nchoice theory is a framework for understanding social and economic behavior. The \nbasic premise is that aggregate social behavior results from the behavior of individual \nactors, each of whom is making their individual decisions. It assumes that individuals \nhave preferences and choose the alternative that they prefer. We define a performance \nmeasure: An objective criterion for success of an agent's behavior; given the evidence \nprovided by the percept sequence. It is better to design performance measures according \nto what you want to be achieved in the environment, rather than how you think the agent \nshould behave. Initial Rational Agent: For each possible percept sequence P, a rational agent \nselects an action a to maximize its performance measure. Ideal agent: maximizes \nactual performance, but needs to be omniscient. Usually impossible, Rationality \nnot equal to Guaranteed Success. Computational limitations make complete rationality \nunachievable. Revised Rational Agent:  For each possible percept sequence P, a rational \nagent selects an action a that maximizes the expected value of its performance measure.\nIt doesn’t have to know what the actual outcome will be. To design a rational agent \nwe need to specify a task environment • a problem specification for which the agent is a solution\nNote that A rational agent is not guaranteed to find optimal solutions. An agent’s \nchoice of action at a given instant depends on its percept sequence but not future \nperceptual inputs. Randomized behavior can be rational in some environments!!!\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Agent function** - specifies the action taken by the agent in response to any percept sequence\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Rational agent** - maximize the expected value of the performance measure, given the percept sequence it has seen so far\n* **Utility** - the quality of being useful\n* **Task environment** -  includes the performance measure, the external environment, the actuators, and the sensors\n* **Agent program** - implementation of the agent function\n* **Simple reflex agents** - respond directly to percepts\n* **Model-based reflex agents** - maintain internal state to track aspects of the world that are not evident in the current percept\n* **Goal-based agents** - act to achieve their goals\n* **Utility-based agents** - try to maximize their own expected “happiness” \n* **Percept** - the content an agent's sensors are perceiving\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nEvery bold has two underscores before and two underscores after.\nFast development: Concise, intuitive syntax that is whitespace, delimited Garbage \ncollected. Portable: Programs run on major platforms without change. Various built-in \ntypes: lists, dictionaries, sets: useful for AI. Large collection of support libraries: \nNumPy for Matlab like programming, Pandas for data analysis, \nSklearn for machine learning, Pytorch and TensorFlow for deep learning\nREPL ENVIRONMENT Read-Evaluate-Print loop. \nAll data treated as objects. An object is deleted (by garbage collection) once unreachable.\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible \nwith that type (eg. “foo” + 2) type(object) isinstance(object, type)/\nExamples of Types: int, float, str, tuple, dict, list, bool: True, False, \nNone, generator, function. static typing: Variables can only refer to objects of \na declared type. dynamic typing: Variables come into existence when first assigned.\nType of the variable is determined automatically. If assigned again, type is updated.\nFunctions have no type signatures. However, type errors can only be caught at runtime.\nstrings are immutable. is checks whether variables point to the same object while\n== checks whether variables point to objects of the same value. lists are mutable.\nUse [:] to get a shallow copy of any sequence. Tuple is immutable but can contain\nmixed types including collection types. negative index is looking from right, starting\nfrom -1 as the rightmost. Slicing returns copy of a subsequence. 1:-1 is the same as\n1:len(n)-1. insert can be used on list (idx, ele). index, count, and remove on list\nwith ele as input. list.sort() is sort, list.sort(a) is sort with function a,\nsort(list) returns a sorted copy. a.join([b, c, d]) = 'bacad' where bcd are strings.\ncapitalize is upper first letter. upper is upper every. strip is to remove a substring.\nDictionaries are unordered & work by hashing, so keys must be immutable.\nConstant average time add, lookup, update. keys(), values(), items() \nPython allows you to multiple values in the type of tuple. Python doesn’t allow \nfunction overloading like Java does, two functions can't have the same name. \nBut operator overloading is possible. Non-default argument should always precede \ndefault arguments; otherwise, it reports SyntaxError. Functions can be called with \narguments out of order. Suppose you want to accept a variable number of non-keyword \narguments to your function. Use *args as the function input and *lst if lst is the\nactual input. def print_everything(*args): print(args), can do print('a', 'b')\nargs is a tuple of arguments passed to the fn.\nand lst = ['a', 'b'] print(*lst) Suppose you want to accept a variable number of \narguments to your function. def print_keyword_args(**kwargs): # kwargs is a dict \nof the keyword args passed to the fn. print_keyword_args(a = 'b', c = 'd') yields\n{'a': 'b', 'c': 'd'}. Same as dict = {'a': 'b', 'c': 'd'} and print_keyword_args(**dict)\nPython uses dynamic scope Function sees the most current value of variables\nFunctions are “first-class” objects, First class object is an entity that can be \ndynamically created, destroyed, passed to a function, returned as a value, and have \nall the rights as other variables in the programming language have.\nFunctions are “first-class citizens”, Pass functions as arguments to other functions, \nReturn functions as the values from other functions, Assign functions to variables or \nstore them in data structures. Higher order functions: take functions as input\nA class can extend the definition of another class\nAllows use (or extension) of methods and attributes already defined in the\nprevious one.\nNew class: subclass. Original: parent, ancestor or superclass\nTo define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition.\nclass cs_Student(Student):\nPython has no ‘extends’ keyword like Java. Multiple inheritance is supported.\nConstructors: __init__ Must be done explicitly.\nTo redefine a method of the parent class, include a new definition using the same\nname in the subclass.\nThe old code in the parent class won’t get executed.\nTo execute the method in the parent class in addition to new code for some method, \nexplicitly call the parent’s version of the method.\nparentClass.methodName(self, a, b)\nThe only time you ever explicitly pass self as an argument is when\ncalling a method of an ancestor.\nmyOwnSubClass.methodName(a, b)\nMagic Methods allow user-defined classes to behave like built in types\nYou can implement operator overloading with magic methods\n__init__, __len__, __copy__, __cmp__, __add__, __neg__\nThe interpreter sets the __name__ variable to have a value \"__main__\" for the source \nfile that is being executed on the command line.\nPython doesn’t have a built-in main method, so there is no def main(). Instead, \nit uses this syntax to define a main method: if __name__ == '__main__':\nDuck typing establishes suitability of an object by determining presence of methods Does it swim like a duck and quack like a duck? It’s a duck\nNot to be confused with ‘rubber duck debugging’\nlst1 = [('a', 1), ('b', 2), ('c', 'hi’)] lst2 = ['x', 'a', 6]\nd = { k: v for k,v in lst1 } s = { x for x in lst2 }\nk = [1,2,3], i = iter(k), next(i), i.__next__(), i.next() same\nno hasnext() method. \ngenerator: uses yield in function, automatically return a generator when called.\ngen.__next__(), next(get), gen.__next__()\nproblems: 1> 'abc' = 'a'+'b'+'c' = '',join(['a','b','c'])='%s%s%s'%('a', 'b', 'c')\nbut not [x for x in 'abc'], not sum(['a','b','c']). 2> function inside a class is\ncalled method. 3> list can have different types of things. Can have [None,   ]\nor a list of functions or [_ for _ in [1, 2, 3]]. 4> Can't assign tuple values.\n5> A hash function is any function that can be used to map data of arbitrary size \nto fixed-size values. 6> Some mathematical operations can be performed on a string.\n7> A Python tuple can also be created without using parentheses. a = b, c, d is tuple\n8> A function can take an unlimited number of arguments and return multiple values.\nPython return default value if no return value. Python supports nested functions.\n9> 1 to 100 is [i for i in range(1, 101)]\n10> assigning slicing doesn't change original.\n11> {\"a\": 3, \"b\": 2, [1,2]: 2}. first_two = set(); first_two.add(\"one\"); \nfirst_two.remove(\"two\"). {\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4}. \na = '123'; a[1] = '1'. b = (1, 2, 3); b[1] = 1 all return error.\nd = ({ }, { }); d[1][1] = 1 is ok. \n12> x = [(x, y) for x in [1,2,3] for y in [1,2,3]], len(x) = 9.\n\n\n## Module 2 Definitions\n* **Mutability** - A mutable object can be changed after it's created\n\n\n## WARNING: Your definition of 'component of problem' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n GOAL FORMULATION: Goals organize behavior by limiting the objectives \nand hence the actions to be considered. PROBLEM FORMULATION: The agent devises a \ndescription of the states and actions necessary to reach the goal—an abstract model \nof the relevant part of the world. SEARCH: Before taking any action in the real \nworld, the agent simulates sequences of actions in its model, searching until it \nfinds a sequence of actions that reaches the goal. EXECUTION: The agent can now \nexecute the actions in the solution, one at a time. 1) In a fully observable, deterministic, \nknown environment, the solution to any problem is a fixed sequence of actions. If\nnot, the agent would be safer using a closed-loop approach that monitors the percepts. \na solution would be a branching strategy that recommends different future actions \ndepending on what percepts arrive. A search problem: A set of possible states that \nthe environment can be in. We call this the state space. The initial state that \nthe agent starts in. A set of one or more goal states. The actions available to the agent.\nAn action is applicable in state s if it can be executed in s. A transition model, \nwhich describes what each action does. An action cost function that reflects its \nown performance measure. Graph: states are vertices, actions are edges. 2) Model is\nan abstract mathematical description. The abstraction is valid if we can elaborate \nany abstract solution into a solution in the more detailed world. The abstraction \nis useful if carrying out each of the actions in the solution is easier than the \noriginal problem. The choice of a good abstraction thus involves removing as much \ndetail as possible while retaining validity and ensuring that the abstract actions \nare easy to carry out.\n\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various \nproblem-solving methods. It can be given a concise, exact description and hence is \nsuitable as a benchmark for researchers to compare the performance of algorithms. \nA real-world problem, such as robot navigation, is one whose solutions people actually \nuse, and whose formulation is idiosyncratic, not standardized. 1) Absolute/egocentric\nactions: action in absolute direction or direction perceived by onself. 2) real-world\nexample: STATES: Each state obviously includes a location (e.g., an airport) and the current time. \nFurthermore, because the cost of an action (a flight segment) may depend on previous\nsegments, their fare bases, and their status as domestic or international, the \nstate must record extra information about these “historical” aspects. INITIAL STATE: \nThe user’s home airport. ACTIONS: Take any flight from the current location, in \nany seat class, leaving after the current time, leaving enough time for within-airport \ntransfer if needed. TRANSITION MODEL: The state resulting from taking a flight will \nhave the flight’s destination as the new location and the flight’s arrival time as the new time.\nGOAL STATE: A destination city. Sometimes the goal can be more complex, such as \n“arrive at the destination on a nonstop flight.” ACTION COST: A combination of \nmonetary cost, waiting time, flight time, customs and immigration procedures, seat \nquality, time of day, type of airplane, frequent-flyer reward points, and so on. \nRobot navigation is a generalization of the route-finding problem described earlier. \nRather than following distinct paths (such as the roads in Romania), a robot can \nroam around, in effect making its own paths. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns \na solution, or an indication of failure. In a search tree, each node corresponds \nto a state in the state space and the edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem. It is important \nto understand the distinction between the state space and the search tree. The state \nspace describes the (possibly infinite) set of states in the world, and the actions \nthat allow transitions from one state to another. The search tree describes paths \nbetween these states, reaching towards the goal. The search tree may have multiple \npaths to (and thus multiple nodes for) any given state, but each node in the tree \nhas a unique path back to the root (as in all trees). The frontier of the search \ntree is a set of unexpanded nodes. 1) best-first search expands a node with minimum \nvalue of some evaluation function f(n). 2) data structure of node: 4 components,\nstate, parent, action, path-cost. frontier queue can be priority queue (best-first), \nFIFO queue (BFS), and LIFO queue (dfs). Reached states can be hashed table. \n3) A cycle is a special case of a redundant path. We call a search algorithm a \ngraph search if it checks for redundant paths and a tree-like search if it does \nnot check. Best-first-Search is graph search, more memory but faster. 4) performance\nmeasure: 1> completeness: if the algorithm guaranteed to find a solution when \nthere is one. 2> COST OPTIMALITY: if it finds a solution with the lowest path cost \nof all solutions. 3> Time complexity 4> space complexity. To be complete, a search \nalgorithm must be systematic in the way it explores an infinite state space, making \nsure it can eventually reach any state that is connected to the initial state. Depth d\nis the number of actions in an optimal solution. he branching factor b is the number \nof successors of a node that need to be considered\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n 1) When all actions have the same cost, an appropriate strategy \nis breadth-first search, in which the root node is expanded first, then all the \nsuccessors of the root node are expanded next, then their successors, and so on. \nThis is a systematic search strategy that is therefore complete even on infinite \nstate spaces. We could implement breadth-first search as a call to BEST-FIRST-SEARCH \nwhere the evaluation function is the depth of the node—that is, the number of \nactions it takes to reach the node. Need FIFO and early goal test, checking a node\nis goal before adding to queue. Complete and optimal, TC and SC are O(b^d). 2) Dijkstra's\nor uniform cost. The complexity of uniform-cost search is characterized in terms C,\nthe cost of the optimal solution, and e, a lower bound on the cost of each action, \nwith Then the algorithm’s worst-case time and TC and SC are O(b^(1+floor(C*/e))).\nNotice that floor(C*/e) = d when all costs are equal. 3) DFS always expands the \ndeepest node in the frontier first, f(n) is the negative of depth. It's implemented\nas a tree search. It is not systematic in infinite state spaces so incomplete. It\ncan get stuck in cycle/infinite loop. DFS requires smaller memory and no reached table.\nMC is O(bm) where m is the maximum depth of the tree. Backtracking search uses less\nmemory because only one successor is generated, and remembers where the next successor\nis. It reduces to O(m), but need to specify how to undo. 4) depth limited and iterative\ndeepening search is a version of depth-first search in which we supply a depth limit L, \nand treat all nodes at depth as if they had no successors. TC is O(b^L) and SC is\nO(b*L), but poor choice of L will make it incomplete. Uses tree-like search so have\nto eliminate cycles by limiting depth. Memory req is O(b*d) when there is a solution and\nO(b*m) when no solution. It's optimal when all actions have the same cost and complete\non finite acyclic state spaces. TC is O(b^d) when there is solution and O(b^m) otherwise.\nIn general, iterative deepening is the preferred uninformed search method when \nthe search state space is larger than can fit in memory and the depth of the \nsolution is not known. 5) bidirectional simultaneously searches forward from the \ninitial state and backwards from the goal state(s), hoping that the two searches \nwill meet. For this to work, we need to keep track of two frontiers and two tables \nof reached states, and we need to be able to reason backwards. 6) Completeness:\nBFS, uniform cost, iterative deepening, bidirectional. Optimal: Same as completeness.\nTime: BFS is O(b^d), UC is O(b^(1+floor(C*/e))), DFS is O(b^m), Depth-limited is\nO(b^l), ID is O(b^d), bidirectional is O(b^(d/2)). Space: BFS is O(b^d), UC is \nO(b^(1+floor(C*/e))), DFS is O(b*m), DL is O(b*l), ID is O(b*d), bidirectional is\nO(b^(d/2)). Bidirectional here uses BF or UC. \n\n## Module 3 Lecture Notes\n 0> A search method is uninformed if it only has access \nto the problem definition. 1> In a fully observable, deterministic, known environment, \nthe solution to any problem is a fixed sequence of actions. 2> The state space is\nthe set of possible states of the environment. 3> The initial state and goal states\nare needed when defining a search problem. 4> A solution to a search problem is a \npath through the state space from the intial state to a goal state. 5> A state space,\ninitial state, goal state, actions, transition model, action cost function are required\nto define a search problem. 5> In a search problem, an optimal solution has the \nlowest path cost among all solutions. 6> A search algorithm is graph search if it \nchecks for redundant paths, tree search if it doesn't. 7> Graph search is faster than\ntree search but uses mores space. 8> Search algorithms are typically judged based on\ncompleteness, cost optimality, time complexity, and space complexity. 9> A search \nalgorithm is complete if the algorithm is guaranteed to find a solution if there \nis one, and to correctly report failure when there is not. 10> A search algorithm \nis cost optimal when it is guaranteed to find the solution with the lowest path \ncost of all solutions. 11> Time complexity is how long it takes for an algorithm \nto find a solution. 12> Space complexity is how much memory it takes for an algorithm \nto run. 13> In uninformed search, best-first search expands nodes according to an \nevaluation function. 14> Breadth-first search expands the node which is shallowest.\n15> BFS is optimal when unit cost 16> uniform expands with lowest g(n) 17> DFS\nexpands nodes which is deepest. DLs expands nodes which is deepest and within a \ndepth bound. 17> Iterative deepening search expands the node according to depth-limited \nsearch with increasing depth bounds. 18> Bidirectional search expands nodes around \nthe initial state and the goal. Slide: A simple reflex agent is one that selects \nan action based only on the current percept. It ignores the rest of the percept \nhistory. A problem-solving agent must plan ahead. The computational process that \nit undertakes is called search. It will consider a sequence of actions that form \na path to a goal state. Such a sequence is called a solution.\nThe properties of the task environments change the types of solutions that we \nneed. If an environment is: Fully observable, Deterministic, Known environment.\nThe solution to any problem in such an environment is a fixed sequence of actions.\nIn environments that are partially observable or nondeterministic, the solution \nmust recommend different future actions depending on the what percepts it receives. \nThis could be in the form of a branching strategy. Holiday setting: Formulate goal:\nBe in Bucharest Formulate search problem: States: various cities, Actions: drive \nbetween cities, Performance measure: minimize travel time / distance, Find solution:\nSequence of cities. Real world is absurdly complex. State space must be abstracted \nfor problem solving. Tree Search: Generalized algorithm to solve search problems\nEnumerate in some order all possible paths from the initial state. States do not \nhave parents, children, depth or path cost, but nodes representing states do!\nBFS is optimal if cost = 1 per step!!! Use BFS If there are possibly infinite paths \nin your search space. Preferable to use DFS if you are working with restricted memory.\nDijkstra is a uniform-cost search without a goal. Uniform-cost search is optimal.\nNot all moves are equal in path cost. Depth-first search doesn't have much lower \nspace complexity than iterative deepening. Depth-first search is incomplete.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Component of problem** - the state space, the initial state, a set of actions, a transition model, a set of goal states, and an action cost function\n* **Abstraction** - the process of removing detail from a representation\n* **Problem environment representation** - a state space graph\n* **Solution** - a sequence of actions from the initial state to a goal state\n* **Optimal solution** - the solution with the lowest path cost among all solutions.\n* **Solution in per** - a path through the state space from the initial state to a goal state\n* **Search algorithm representation** - treating states and actions as atomic and without internal structure\n* **Search algorithm judgement** - basis of completeness, cost optimality, time complexity, and space complexity\n* **Uninformed search methods** - has access only to the problem definition\n* **Best-first search** - selects nodes for expansion using an evaluation function\n* **Breadth-first search** - expands the shallowest nodes first, complete, optimal if unit cost, but exponential SC\n* **Uniform-cost search** - expands the node with lowest path cost g(n), optimal for general action costs\n* **Depth-first search** - expands the deepest unexpanded node first, incomplete, suboptimal, linear SC\n* **Depth-limited search** - adds a depth bound to dfs\n* **Iterative deepening search** - calls dfs with increasing depth limits until goal is reached. complete acyclic, optimal unit action costs.\n* **Bidirectional search** - expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet, optimal\n* **The search problem** - the process of looking for a sequence of actions that reaches the goal\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A heuristic function h(n) is the estimated cost of the cheapest\npath from the state at node n to a goal state. 1) Greedy best-first search is a \nform of best-first search that expands first the node with the lowest value, so\nthe evaluation function f(n) = h(n). Greedy best-first graph search is complete \nin finite state spaces, but not in infinite ones. The worst-case time and space \ncomplexity is O(abs(V)). With a good heuristic function, however, the complexity \ncan be reduced substantially, on certain problems reaching O(b*m). 2) A heuristic \nis consistent if, for every node and every successor of \ngenerated by an action h(n) leq c(n, a, n')+h(n'). Consistency is stronger than\nadmissibility, so every consistent heuristic is admissible. 3) Draw contours in\nthe state space. A* expands all nodes that can be reached from the initial state \non a path where every node on the path has, so surely expanded nodes.\nA* with a consistent heuristic is optimally efficient in the sense that any algorithm \nthat extends search paths from the initial state, and uses the same heuristic \ninformation, must expand all nodes that are surely expanded by A*. A* is efficient \nbecause it prunes away search tree nodes that are not necessary for finding an optimal \nsolution. 4) Satisficing solutions are suboptimal but good enough. Weighted A* search\nuses f(n) = g(n) + W * h(n) with W > 1. Find solution between C* and W*C*, usually\nclose to C*. A* is g+h, uniform is g, gbf is h. In bounded-cost search, we look \nfor a solution whose cost is less than some constant And in unbounded-cost search, \nwe accept a solution of any cost, as long as we can find it quickly. Speedy search, \nwhich is a version of greedy best-first search that uses as a heuristic the estimated \nnumber of actions required to reach a goal, regardless of the cost of those actions.\n5) memory is frontier and reached. 1> keep a state in only one of the two places.\n2> remove states from reached when we can prove that they are no longer needed. \nBeam search limits the size of the frontier. The easiest approach is to keep only \nthe nodes with the best f-scores, discarding any other expanded nodes. Incomplete \nand suboptimal, but good memory and the fast execution. Iterative-deepening A* \nsearch (IDA*) is to A* what iterative-deepening search is to depth-first: IDA* \ngives us the benefits of A* without the requirement to keep all reached states \nin memory, at a cost of visiting some states multiple times. Recursive best-first \nsearch attempts to mimic the operation of standard best-first search, but using \nonly linear space. RBFS is somewhat more efficient than IDA*. SMA* proceeds just \nlike A*, expanding the best leaf until memory is full. At this point, it cannot \nadd a new node to the search tree without dropping an old one. SMA* always drops \nthe worst leaf node—the one with the highest -value.5) bidirectional \nA* doesn't produce optimal\n\n## AIMA Chapter 3.6 Heuristic Functions\n 1) effective branching factor b* . N+1=1+b* +(b* )^2..+(b* )^d.\nWell designed heuristic should have b* close to 1. Effective depth is the actual depth\na search performs, which is less than d. When one heuristic dominates another, meaning\nh2(n)>h1(n), h2 is always better than h1 and expands less nodes. 2) relaxed graph\ncreates a supergraph of the origianl set space because it adds in more edges. So\nalways admissible.Just pick the maximum admissible function out of all the choices.\n3) Admissible heuristics can be derived from a subproblem. Pattern databases store\nthe exact solution costs for every possible subproblem. Disjoint pattern databases\ndivide the problems up such that each move affects only one subproblem. 4) Precompute\nof some optimal path costs. Choose a few landmark points. min abs(C* (n, L)+C* (goal, L))\nAdd shortcuts the artificial, edges in the graph that define an optimal multi-action path. \nDifferential heuristic = max abs(C* (n, L)-C* (goal, L)) for landmark L beyond the goal.\nEach state in a metalevel state space captures the internal (computational) state \nof a program that is searching in an ordinary state space such as the map of Romania.\n(To keep the two concepts separate, we call the map of Romania an object-level state space.) \na metalevel learning algorithm can learn from these experiences to avoid \nexploring unpromising subtrees. The goal of learning is to minimize the total cost\n of problem solving, trading off computational expense and path cost. 6) Another way\n is to learn from experience. “Experience” here means solving lots of 8-puzzles, \n for instance. Each optimal solution to an 8-puzzle problem provides an example \n (goal, path) pair. From these examples, a learning algorithm can be used to \n construct a function that can (with luck) approximate the true path cost for \n other states that arise during search. Most of these approaches learn an imperfect \n approximation to the heuristic function, and thus risk inadmissibility. This leads \n to an inevitable tradeoff between learning time, search run time, and solution cost. \n \n\n## Module 4 Lecture Notes\n 1> A search method is uninformed if it only has access \nto the problem definition. 2> Max can't simply search for a single sequence of events \nfrom an initial state to a winning terminal state before the game begins because\nthe best possible move made by MAX at any point in time will depend on the previous \nmove made by MIN. 3> A search method is informed if it has access to the problem \ndefinition and a heuristic function, h(n). 4> The heuristic function h(n) estimates\nthe cost of a solution from a node n. 5> Greedy best-first search expands nodes \nwith minimal h(n). 6> The biggest problem with A* is the space complexity。\n7> A* is complete and optimal. 8> An admissible heuristic is one that never overestimates \nthe cost to reach a goal. 9> IDA* is iterative deepening A* search. 10> RBFS is\nrecursive best-first search. 11> IDA*, SMA*, and RBFS are optimal search algorithms \nwhich are more space efficient than A*. 12> Beam search limits the size of the frontier,\nso suboptimal and incomplete but runs faster than complete search. 13> Weighted A*\nis not optimal but complete, expands fewer nodes than A*. 13>\n\nA* search expands nodes with minimal f(n) = g(n) + h(n) where g(n) is the path cost from the \ninitial state to node and is the estimated cost of the shortest path from to a \ngoal state. An admissible heuristic is one that never overestimates the cost to \nreach a goal, therefore optimistic. With an admissible heuristic, A* is \ncost-optimal. \n\n## Module 4 Definitions\n* **Informed search methods** - has access to a heuristic function that estimates the cost of a solution from current node\n* **Greedy best-first search** - expands nodes with minimal h(n), not optimal but often efficient\n* **A* search** - expands nodes with minimal f(n), complete and optimal when h(n) is admissible\n* **Bidirectional a* search** - sometimes more efficient than A* search\n* **Iterative deepening a* search** - iterative deepening version of A* that addresses SC issue\n* **Recursive best-first search and simpliffied memory-bound a*** - robust, optimal search algorithms that use limited amounts of memory\n* **Beam search** -  puts a limit on the size of the frontier, incomplete and suboptimal but faster\n* **Weighted a*** - search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Competitive environments, in which two or more agents have conflicting \ngoals, giving rise to adversarial search problems. stance 1: the aggregate as \nan economy, allowing us to do things like predict that increasing demand will cause \nprices to rise, without having to predict the action of any individual agent. \nstance 2: adversarial agents as just a part of the environment—a part that makes \nthe environment nondeterministic. stance 3: explicitly model the adversarial agents \nwith the techniques of adversarial game-tree search. We do stance 3. Define the state \nspace graph—a graph where the vertices are states, the edges are moves and a state \nmight be reached by multiple paths. Define the complete game tree as a search tree \nthat follows every sequence of moves all the way to a terminal state.  \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n 0) The minimax value is the utility at a terminal state, the \nmaximum for max and minimum for min. The minimax value assumes that both players \nplay optimally. 1) Minimax search is a recursive algorithm that proceeds all the \nway down to the leaves of the tree and then backs up the minimax values through \nthe tree as the recursion unwinds. The minimax algorithm performs a complete \ndepth-first exploration of the game tree. 2) Multi-agent: each player chooses their\nmax value. 3) Pruning eliminates the examination of some states. alpha is the value\nof the best choice we have found so far at any choice point along the path for MAX.\nbeta the value of the best choice we have found so far at any choice point along \nthe path for MIN. 4) depends on order, so try to first examine the successors that \nare likely to be best. perfect: O(b^(m/2)) instead of O(b^m) for minimax. Iterative \ndeepening record the ranking of moves then try killer moves (best moves). In game \ntree search, repeated states can occur because of transpositions—different permutations \nof the move sequence that end up in the same position, and the problem can be \naddressed with a transposition table that caches the heuristic value of states.\nStrategies when there are too m any states: Type A strategy considers all possible \nmoves to a certain depth in the search tree, and then uses a heuristic evaluation \nfunction to estimate the utility of states at that depth. It explores a wide but \nshallow portion of the tree. A Type B strategy ignores moves that look bad, and \nfollows promising lines “as far as possible.” It explores a deep but narrow portion \nof the tree.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n 1) Heuristic alpha-beta tree search estimates a nonterminal state's\nutility and replace the terminal test by a cutoff test. The heuristic eval(s, p)\nreturns an estimate of the expected utility of state s to player p at a depth level\nthat is cutoff. For terminal states: eval(s,p) = utility(s,p). For nonterminal:\neval is between loss and win utility. A reasonable evaluation is the expected value.\nMaterial value is defined to have feature values for different objects in game.\nEvaluation would be a linear combination of material values(king is 5, pawn is 1).\n2) The evaluation function should be applied only to positions that are quiescent,\npositions in which there is no pending move (such as a capturing the queen) that \nwould wildly swing the evaluation. The horizon effect is more difficult to eliminate. \nIt arises when the program is facing an opponent’s move that causes serious damage \nand is ultimately unavoidable, but can be temporarily avoided by the use of \ndelaying tactics. One strategy to mitigate the horizon effect is to allow singular \nextensions, moves that are “clearly better” than all other moves in a given position, \neven when the search would normally be cut off at that point. 3) Alpha–beta pruning \nprunes branches of the tree that can have no effect on the final evaluation, but \nforward pruning prunes moves that appear to be poor moves, but might possibly be \ngood ones. Thus, the strategy saves computation time at the risk of making an error.\nIn Shannon’s terms, this is a Type B strategy. Beam search: only n best moves, but\nvery dangerous. The PROBCUT, or probabilistic cut, algorithm is a forward-pruning \nversion of alpha–beta search that uses statistics gained from prior experience to \nlessen the chance that the best move will be pruned. Another technique, late move \nreduction, works under the assumption that move ordering has been done well, and \ntherefore moves that appear later in the list of possible moves are less likely \nto be good moves. But rather than pruning them away completely, we just reduce the \ndepth to which we search these moves, thereby saving time. 4) Near the end of the \ngame there are again fewer possible positions, and thus it is easier to do lookup. \nBut here it is the computer that has the expertise: computer analysis of endgames \ngoes far beyond human abilities. Novice humans can win a king-and-rook-versus-king \n(KRK) endgame by following a few simple rules. Other endings, such as king, bishop, \nand knight versus king (KBNK), are difficult to master and have no succinct strategy \ndescription. A computer, on the other hand, can completely solve the endgame by \nproducing a policy, which is a mapping from every possible state to the best move \nin that state. Then the computer can play perfectly by looking up the right move \nin this table. The table is constructed by retrograde minimax search: start by \nconsidering all ways to place the KBNK pieces on the board. Then do reverse moves. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability \nof real life by including a random element. A game tree in backgammon must include \nchance nodes in addition to MAX and MIN nodes. The branches leading from each chance \nnode denote the possible dice rolls; each branch is labeled with the roll and its \nprobability. We can only calculate the expected value of a position: the average \nover all possible outcomes of the chance nodes. The expectiminimax value for games \nwith chance nodes, a generalization of the minimax value for deterministic games.\n1) Expectiminimax takes O(b^m* n^m) compared to minimax that takes O(b^m) where n\nis the number of possible outcomes. Alpha–beta pruning can be applied to game \ntrees with chance nodes.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n A goal-based agent has a binary distinction between good (goal) \nand bad (non-goal) states, while a decision-theoretic agent assigns a continuous \nrange of values to states, and thus can more easily choose a better state even \nwhen no best state is available. A decision network/influence diagram extends Bayesian \nnetworks by incorporating actions and utilities. An agent here has P(s) to each\npossible current state s. The agent's preferences are captured by a utility function\nU(s), and we can compute the expected utility value of each action. The principle \nof maximum expected utility (MEU) says that a rational agent should choose the \naction that maximizes the agent’s expected utility. Estimating the probability distribution\nrequires perception, learning, knowledge representation, and inference. Computing\nrequires a causal model of the world. Consider the environments that could lead \nto an agent having a given percept history, and consider the different agents that \nwe could design. If an agent acts so as to maximize a utility function that correctly \nreflects the performance measure, then the agent will achieve the highest possible \nperformance score (averaged over all the possible environments). This is the \ncentral justification for the MEU principle itself. While the claim may seem \ntautological, it does in fact embody a very important transition from the external \nperformance measure to an internal utility function. The performance measure gives \na score for a history—a sequence of states. Thus it is applied retrospectively after \nan agent completes a sequence of actions. The utility function applies to the very \nnext state, so it can be used to guide actions step by step. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n A lottery L = [P1, S1; P2, S2; ... Pn, Sn] where S is an outcome\nand P is a probability. Orderability states that the agent should prefer one lottery\nover another. Transitivity exists in orderability of preference. Continuity: If lottery\nA > B > C, exists P such that the agent is indifferent between B and [p, A; 1-p, C].\nSubstitutability: if the agent is indifferent between A and B, [p, A; 1-p, C] ~ \n[p, B; 1-p, C]. Monotonicity: A>B and p>q, we have [p, A; 1-p, B] > [q, A; 1-q, B].\nDecomposability: Decomposability: [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B;\n(1-p)(1-q), C]. 2) Exist a utility function such that U(A) = U(B) when indifferent,\nU(A) > U(B) when A > B. Utility of a lottery is the linear combination of probability\ntimes the utility of each S. In a deterministic environment an agent needs only \na preference ranking on states—the numbers don’t matter. This is called a value \nfunction or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation, involves presenting choices to the human \nand using the observed preferences to pin down the underlying utility function.\nNormalized utilities use a scale that utility of best is 1 and utility of worst \nis 0. standard lottery is [p, 1; 1-p, 0]. Currently several agencies of the U.S. \ngovernment use the [value of a statistical \nlife] to determine the costs and benefits of regulations and interventions. One \ncommon “currency” used in medical and safety analysis is the micromort, a one in \na million chance of death. Another measure is the quality-adjusted life \nyear. Patients are willing to accept a shorter life expectancy to avoid a disability.\n2) It will usually be the case that an agent prefers more money to less, all other \nthings being equal. We say that the agent exhibits a monotonic preference for more money. \nWhen the expected monetary value of the gamble is more than the original, but that\ndoes not mean accepting the gamble is a better decision. To determine what to do, \nwe need to assign utilities to the outcome states. Utility is not directly proportional \nto monetary value, because the utility for your first million is very high, whereas \nthe utility for an additional million is smaller. In a pioneering study of actual \nutility functions, Grayson found that the utility of money was almost exactly \nproportional to the logarithm of the amount. For U(L) < U(S-EMV(L)), agents with curves of this \nshape are risk-averse: they prefer a sure thing with a payoff that is less than \nthe expected monetary value of a gamble. On the other hand, in the “desperate” \nregion at large negative wealth, the behavior is risk-seeking. The value an agent \nwill accept in lieu of a lottery is called the certainty equivalent of the lottery.\nThe difference between the EMV of a lottery and its certainty equivalent is called \nthe insurance premium. Risk aversion is the basis for the insurance industry, because \nit means that insurance premiums are positive. Notice that for small changes in \nwealth relative to the current wealth, almost any curve will be approximately linear. \nAn agent that has a linear curve is said to be risk-neutral.\n3) bias = E[E[f]-E[f]_true). P(max(X1 < X...Xk < X))=F(x)^k. p(x) is the derivative\nof F(x)^k. This tendency for the estimated expected utility of the best choice to \nbe too high is called the optimizer’s curse. 4) Decision theory is a normative theory: \nit describes how a rational agent should act. A descriptive theory, on the other hand, \ndescribes how actual agents really do act. One explanation for the apparently irrational \npreferences is the certainty effect people are strongly attracted to gains that are certain. \nPeo want ambituity aversion: wants deterministic. The framing effect is 90% survival\nrate over 10% death rate. The anchoring effect is to sell 50box water when there is\nanother 100box water.\n\n\n## Module 5 Lecture Notes\n 1> The minimax algorithm uses a depth-first approach.\n2> The time complexity of the minimax algorithm is O(b^m) where b is the number of\nlegal moves at each node and m is the maximum depth of the tree. 3> Games differ\nfrom search because games have multiple agents. 4> A state where a game ends is called \na terminal state. 5> A utility function U(s) gives the payoff for each player in \nterminal state s. 6> The minimax search algorthim solves perfect information, zero-sum\ngames. 7> Minimax evaluates nodes in the same order as DFS. 8> Minimax evaluates \neach node as the value of the best terminal state reach by both player playing optimally.\nThe current player tries to maximize the score and the other player tries to minimize \nit. 9> Alpha-beta pruning is more efficient that minimax because it eliminates provably \nirrelevant subtrees. 10> The running time of alpha-beta pruning is impacted by the \norder in which we examine nodes. 11> Alpha-beta pruning has optimal time complexity\nO(b^(m/2)) and worst time complexity O(b^m). 12> A Type A Strategy, as proposed by \nClaude Shannon, explores a wide but shallow portion of the tree. 13> A Type B Strategy, \nas proposed by Claude Shannon, explores a deep but narrow portion of the tree.\n14> Type A and Type B are useful because for games with a large search space, it \nis not feasible to search the whole tree. As such, we have to make tradeoffs about \nwhat part of the tree to search. 15> Heuristic alpha-beta search replaces the utility \nfunction with an evaluation function that estimates the value of non-terminal nodes. \n16> In heuristic alpha-beta pruning, the terminal test is replaced with a cutoff\ntest that decides when to cut off the search. 17> The evaluation function should \nbe applied only to positions that are quiescent. 18> A move is quiescent if there \nis no pending move that would wildly swing the valuation. 19> Forward pruning\nprunes moves that appear to be bad moves. Beam search is forward pruning. FP is\ntype B strategy. 20> MCTS works by playing the game to the end while randomly selecting \nmoves. MCTS evaluates an action by repeatedly playing the game from that state and \ntaking the average of the results. 21> Expectiminimax is used to handle games of\nchance. 22> In minimax search, the value of a node is the optimal value of its children.\n23> Set of terminal states, a utility function, the initial state, and the set of \nlegal moves that a player can make are required to define a game. The Waltz/Mackworth \n\n\n## Module 5 Definitions\n* **Perfect information** - a synonym for fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Move** - a synonym for action\n* **Position** - a synonym for state\n* **Horizontal effect** - facing an opponent’s move that causes serious and unavoidable damage that can be temporarily avoided\n* **Game** - initial state, legal actions at each state, result of action, terminal test, and utility function\n* **Initial state** - how the board is set up\n* **Heuristic evaluation function** - estimates the utility of a state\n* **Expectiminimax** - an extension to the minimax algorithm that evaluates a chance node by weighted average\n\n\n## WARNING: Your definition of 'CSP' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP search algorithms take advantage of the structure of states \nand use general rather than domain-specific heuristics to enable the solution of \ncomplex problems. CSPs have the additional advantage that the actions and transition \nmodel can be deduced from the problem description. 0) An assignment of values to\nvariables is {Xi = vi, Xj = vj...} where vi is in domain Di for Xi. 1) Visualize \nCSP as a constraint graph with nodes corresponding to variables of the problem and \nedges cnnecting two variables as constraints. 2) precedence constraints is one has \nto be earlier than other. disjunctive constraint is that two can't overlap. \n3) The simplest kind of CSP involves variables that have discrete, finite domains.\nA discrete domain can be infinite, such as the set of integers or strings. Special \nsolution algorithms exist for linear constraints on integer variables in which each \nvariable appears only in linear form. It can be shown that no algorithm exists for \nsolving general nonlinear constraints on integer variables—the problem is undecidable.\nThe best-known category of continuous-domain CSPs is that of linear programming \nproblems, where constraints must be linear equalities or inequalities. Linear \nprogramming problems can be solved in time polynomial in the number of variables.\nBinary CSP can be represented as a constraint graph. Cryptarithmetic can be represented\nas aconstraint hypergraph consists of ordinary nodes and hypernodes that represent\nn-th order constraints. We could transform any CSP into one with only binary constraints—which \ncertainly makes the life of the algorithm designer simpler. Another way to convert \nan -ary CSP to a binary one is the dual graph transformation: create a new graph \nin which there will be one variable for each constraint in the original graph, and \none binary constraint for each pair of constraints in the original graph that share \nvariables. Many real-world CSPs include preference constraints indicating which \nsolutions are preferred. Preference constraints can often be encoded as costs on \nindividual variable assignments. With this formulation, CSPs with preferences can \nbe solved with optimization search methods, either path-based or local. We call \nsuch a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 0) A CSP algorithm can do a specific type of inference called \nconstraint propagation: using the constraints to reduce the number of legal values \nfor a variable, which in turn can reduce the legal values for another variable, and so on.\nConstraint propagation may be intertwined with search, or it may be done as a preprocessing \nstep, before search starts. The key idea is enforcing local consistency. 1) A single \nvariable (corresponding to a node in the CSP graph) is node-consistent if all the \nvalues in the variable’s domain satisfy the variable’s unary constraints. \n2) A variable in a CSP is arc-consistent1 if every value in its domain satisfies \nthe variable’s binary constraints. A graph is arc-consistent if every variable is\narc-consistent withe very other variable. We have AC3 with total worst-case time of \nO(c*d^3) where d is the maximal domain size and c is the number of binary constraints.\nChecking consistency of 1 arc is O(d^2) time, and it can be deleted d times. \n3) Path consistency tightens the binary constraints by using implicit constraints \nthat are inferred by looking at triples of variables. 4) A CSP is k-consistent if, \nfor any set of variables and for any consistent assignment to those variables, a \nconsistent value can always be assigned to any th variable.A CSP is strongly k-consistent \nif it is (k-1)-consistent and is also (k-2)-consistent, (k-3)-consistent, all the \nway down to 1-consistent. 5) global constraint: \nThis leads to the following simple algorithm: First, remove any variable in the \nconstraint that has a singleton domain, and delete that variable’s value from the \ndomains of the remaining variables. Repeat as long as there are singleton variables. \nIf at any point an empty domain is produced or there are more variables than domain \nvalues left, then an inconsistency has been detected. Resource constraint/atmost \nconstraint in scheduling problems. Resource-limited problems domains are represented \nby upper and lower bounds and are managed by bounds propagation. We say that a CSP \nis bounds-consistent if for every variable , and for both the lower- bound and upper-bound \nvalues of X, there exists some value Y of that satisfies the constraint between X and \nY for every variable Y. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n 0) Sometimes we can finish the constraint propagation process and \nstill have variables with multiple possible values. In that case we have to search \nfor a solution using standard depth-limited search. A problem is commutative if \nthe order of application of any given set of actions does not matter. Leaves reduce\nfrom n!* d^n to d^n. BACKTRACKING-SEARCH keeps only a single representation of a \nstate (assignment) and alters that representation rather than creating new ones.\n1) Backtracking can choose unassigned static ordering and randomly, but neither\nis optimal. The minimum-remaining-values (MRV) heuristic or the “most constrained \nvariable” or “fail-first” heuristic performs better. Pick a variable that is most \nlikely to cause a failure soon, thereby pruning the search tree.Once a variable has been selected, \nthe algorithm must decide on the order in which to examine its values. The \nleast-constraining-value heuristic is effective for this. It prefers the value \nthat rules out the fewest choices for the neighboring variables in the constraint graph.\n2) forward checking establishes arc consistency whenever a variable is assigned.\nThe maintaining arc consistency algorithm detects inconsistencies by starting\nwith all (Y, X) archs. MAC is stricltly more powerful than forward checking.\n3) Chronological backtracking refers to the most recent decision point being revisited.\nThe conflic t set is a set of assignments that are in conflict with some value for some variable.\nThe backjumping method backtracks to the most recent assignment in the conflict set\nand jump over previous assigned value. A backjumping algorithm that uses conflict \nsets defined in this way is called conflict-directed backjumping. Constraint learning \nis the idea of finding a minimum set of variables from the conflict set that causes \nthe problem. This set of variables, along with their corresponding values, is called \na no-good. We then record the no-good, either by adding a new constraint to the CSP \nto forbid this combination of assignments or by keeping a separate cache of no-goods.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms use a complete-state formulation where\neach state assigns a value to each variable, and the search changes the value of \none variable at a time. Select the value that results in the minimum number of \nconflicts with other variables—the min-conflicts heuristic. The runtime of min-conflicts \nis roughly independent of problem size after initial assignment. The landscape of \na CSP under the min- conflicts heuristic usually has a series of plateaus. There \nmay be millions of variable assignments that are only one conflict away from a solution.\nPlateau search—allowing sideways moves to another state with the same score—can help local \nsearch find its way off this plateau. This wandering on the plateau can be directed \nwith a technique called tabu search: keeping a small list of recently visited states \nand forbidding the algorithm to return to those states. Simulated annealing can \nalso be used to escape from plateaus. Another technique called constraint weighting \naims to concentrate the search on the important constraints. Each constraint is \ngiven a numeric weight, initially all 1. At each step of the search, the algorithm \nchooses a variable/value pair to change that will result in the lowest total weight \nof all violated constraints. The weights are then adjusted by incrementing the weight \nof each constraint that is violated by the current assignment. This has two benefits: \nit adds topography to plateaus, making sure that it is possible to improve from \nthe current state, and it also adds learning: over time the difficult constraints \nare assigned higher weights. Another advantage of local search is that it can be \nused in an online setting when the problem changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n 0) Divide the problem into independent subproblems so that combining\nsubsolutions yields a solution. Independence can be ascertained simply by finding \nconnected components of the constraint graph. n variables in total, c variables in\nsubproblems, d size of domain. O(d^n) is reduced to O(d^c* n/c), which is linear\nto n versus exponential to n. A CSP is defined to be directional arc-consistent \nunder an ordering of variables X1 to Xn if and only if every Xi is arc-consistent \nwith each Xj for j > i. To solve a tree-structured CSP, first pick any variable \nto be the root of the tree, and choose an ordering of the variables such that each \nvariable appears after its parent in the tree. Such an ordering is called a topological \nsort. Any tree with nodes has n-1 edges, so we can make this graph directed arc-consistent \nin O(n) steps, each of which must compare up to possible domain values for two \nvariables, for a total time of O(n* d^2). Once we have a directed arc-consistent \ngraph, we can just march down the list of variables and choose any remaining value. \nThat means we won’t have to backtrack; we can move linearly through the variables.\n1) Cutset conditioning involves assigning values to some variables so that the \nremaining variables form a tree. Need to try various assigned values. Cycle cutset S\nis a subset of the CSP's variables that the CG becomes a tree after the removal \nof S. For each valid assignment in S, remove inconsistent values and solve. If the\ncycle cutset has size c, the total runtime is O(d^c* (n-c)* d^2). Efficient when c is small.\n2) Tree decomposition of the constraint graph is a transformation of the original graph \ninto a tree where each node in the tree consists of a set of variables. Every variable in \nthe original problem appears in at least one of the tree nodes. If two variables are connected \nby a constraint in the original problem, they must appear together (along with the \nconstraint) in at least one of the tree nodes. If a variable appears in two nodes \nin the tree, it must appear in every node along the path connecting those nodes.\nOnce a tree-structure graph is obtained, can solve in O(n* d^2) time when n is the\nnumber of tree nodes and d is the size of the largest domain. Efficient when d is\nsmall. The tree width of a tree decomposition of a graph is one less than the size \nof the largest node; the tree width of the graph itself is defined to be the minimum \nwidth among all its tree decompositions. If a graph has tree width then the problem \ncan be solved in O(n* d^(w+1)) time. NP-hard to find smallest cycle cutset and smallest \ntree width. But tree decomposition is faster!!!! Cycle-cutset approach has linear memory \nwhile tree decomposition requires memory exponential in w. Symmetry-breaking constraint\nbreaks value symmetry by assigning an order.\n\n\n## Module 6 Lecture Notes\n 1> 6.3.2 MAC is a way of interleaving search and inference.\nAC-3 is pure inference. MAC runs while assigning variables in backtracking search. \nInstead of queueing all arcs, MAC only queues arcs incident on the assigned variable. \nThen, it runs identically to AC-3. 2> Cutset conditioning is used to reduce a general \nCSP to a tree structured one. 3> Solving a tree-structued CSP takes linear time in\nthe number of variables. 4> In forward checking, whenever a variable X is assigned, \nwe establish arc consistency for X. 5> The key idea behind inference in CSPs is\nenforcing local consistency. 6> Tree decomposition subproblems are efficient if \nthe tree width of the constraint graph is small. 7> MAC stands for maintaining arc\nconsistency. 8> Solving an arbitrary CSP takes exponential time in the number of\nvariables. 9> Tree decomposition is faster than cutset conditioning. Whenever you \nhave a cycle-cutset of size cc, there is also a tree of width w<c+1. 10> AC3 is \nan algorithm for enforcing arch consistency. 11> Cutset conditioning can be executed \nin linear memory, while tree decomposition requries memory exponential in the tree \nwidth w. 12> Node consistency is k-consistency for k = 1. 13> Backtracking search is\na form of depth-first search. 14> MAC recursively propogrates constraints, whereas \nforward checking does not.If we assign X, forward checking makes all the arcs incident \non X consistent. MAC does this, and if the domain of a variable Y changes, does the \nsame for Y. 15> AC3: Place all the arcs in a queue. Pop arcs. For each arc, remove \ninconsistent values. If we change the values of a node, add its arcs to the queue. \nTerminate when the queue is empty. 16> In CSP solvers, inference techniques use\nconstraints to rule out variable assignment. 17> Tree decomposition techniques transform \nthe CSP into a tree of subproblems. 18> CSP differ from search problems: In search \nproblems, states are black boxes with a transition model to move between boxes. \nIn CSPs, the agent can see inside the states and move between states accordingly.\n19> CSPs can rule out variable assignments using search or inference. 20> In CSP \nsolvers, inference techniques use constraints to rule out variable assignment.\n21> A CSP is k-consistent if, for any set of k-1 variables and for any consistent \nassignment to those variables, a consistent value can always be assigned to any \nkth variable. 22> Backtracking occurs when no legal assignment can be found for\na variable. 23> MRV heuristic stands for Minimum Remaining Value and chooses the \nvariable with the fewest 'legal' values. 24> The degree heuristic chooses the variable \nwith the largest number of constraints. 25> The least constraining value heuristic \nchooses the value that rules out the fewest values for neighboring variables.\n26> constraint learning records the conflicts as they are encountered in the search \nin order to avoid the same conflict later. 27> Cutset conditioning is efficient \nif a small cutset can be found. However, in general, it is no more efficient than \nsolving a CSP directly. There is no free-lunch in solving CSPs indirectly.\nConstraint Propagation Algorithm: 1. Assign every node in the constraint graph a \nset of all possible values. 2. Repeat until there is no change in the set of values \nassociated with any node: 3. For each node i: For each neighboring node j in the picture:\nRemove any value from i which is not arc consistent with j.\nAC-3\nfunction AC-3(csp) return the CSP, possibly with reduced domains inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\nlocal variables: queue, a queue of arcs initially the arcs in csp while queue is not empty do\n(Xi, Xj) ¬ queue.pop()\nif REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\nfor each Xk in NEIGHBORS[Xi ] – {Xj} do add (Xk, Xi) to queue\n  function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value removed ¬ false\nfor each x in DOMAIN[Xi] do\nif no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\nthen delete x from DOMAIN[Xi]; removed is true return removed.\nAC-3: Worst Case Complexity Analysis\no All 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(n2)\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(n2d3)\n(For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3))\n\n\n## Module 6 Definitions\n* **Csp_slide** - consists of finite set of variables, nonempty domain of possible values, and finite set of constraints\n* **Relation** - defines value that those variables can take on\n* **Consistent/legal assignment** - an assignement that does not violate any constraints\n* **Complete assignment** - an assignment in which every variable is assigned a value\n* **Partial assignment** - an assignment that leaves some variables unassigned\n* **Partial solution** - a partial assignment that is consistent\n* **Unary constraint** - restricts the value of a single variable\n* **Binary constraint** - relate two variables\n* **Binary csp** - one with only unary and binary constraints\n* **Ternary constraint** - relate three variables\n* **Global constraint** - a constraint involving an arbitrary number of variables\n* **Csp** - represent a state with a set of variable/value pairs and represent the conditions for a solution by a set of constraints on the variables.\n* **Minimum-remaining-values and degree heuristics** - domain-independent methods for deciding which variable to choose next in a backtracking search.\n* **Least- constraining-value heuristic** - helps in deciding which value to try first for a given variable\n* **Backtracking** - occurs when no legal assignment can be found for a variable.\n* **Conflict-directed backjumping** - backtracks directly to the source of the problem\n* **Constraint learning** - records the conflicts as they are encountered during search in order to avoid the same conflict later in the search\n* **Min-conflicts heuristic** - used by local search and applied to constraint satisfaction problems with great success.\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n In AI, knowledge-based agents use a process of reasoning over an \ninternal representation of knowledge to decide what actions to take. The central \ncomponent of a knowledge-based agent is its knowledge base. A knowledge base is \na set of sentences. Each sentence is expressed in a language called a knowledge \nrepresentation language and represents some assertion about the world. When the \nsentence is taken as being given without being derived from other sentences, we \ncall it an axiom. The standard names for these operations are add is TELL and query \nis ASK, respectively. Both operations may involve inference—that is, deriving new \nsentences from old. Inference must obey the requirement that when one ASKs a question \nof the knowledge base, the answer should follow from what has been told (or TELLed) \nto the knowledge base previously. knowledge level is where we need specify only \nwhat the agent knows and what its goals are, in order to determine its behavior.\nThe knowledge level is independent of the implementation level. Starting with an \nempty knowledge base, the agent designer can TELL sentences one by one until the \nagent knows how to operate in its environment. This is called the declarative approach \nto system building. In contrast, the procedural approach encodes desired behaviors \ndirectly as program code.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PERFORMANCE MEASURE: for climbing out of the cave with the gold,\nfor falling into a pit or being eaten by the wumpus, for each action taken, and\nfor using up the arrow. The game ends either when the agent dies or when the agent \nclimbs out of the cave.\nENVIRONMENT: A grid of rooms, with walls surrounding the grid. The agent always \nstarts in the square labeled [1,1], facing to the east. The locations of the gold \nand the wumpus are chosen randomly, with a uniform distribution, from the squares \nother than the start square. In addition, each square other than the start can be \na pit, with probability 0.2.\nACTUATORS: The agent can move Forward, TurnLeft by 90, or TurnRight by 90. The agent \ndies a miserable death if it enters a square containing a pit or a live wumpus. \n(It is safe, albeit smelly, to enter a square with a dead wumpus.) If an agent tries \nto move forward and bumps into a wall, then the agent does not move. The action Grab can be\nused to pick up the gold if it is in the same square as the agent. The action Shoot \ncan be used to fire an arrow in a straight line in the direction the agent is facing. \nThe arrow continues until it either hits (and hence kills) the wumpus or hits a wall. \nThe agent has only one arrow, so only the first Shoot action has any effect. Finally, \nthe action Climb can be used to climb out of the cave, but only from square [1,1].\nSENSORS: The agent has five sensors, each of which gives a single bit of information:\n‐ In the squares directly (not diagonally) adjacent to the wumpus, the agent will perceive\na Stench.\n‐ In the squares directly adjacent to a pit, the agent will perceive a Breeze.\n‐ In the square where the gold is, the agent will perceive a Glitter.\n‐ When an agent walks into a wall, it will perceive a Bump.\n‐ When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.\nThe percepts will be given to the agent program in the form of a list of five symbols; for \nexample, if there is a stench and a breeze, but no glitter, bump, or scream, the agent \nprogram will get [Stench,Breeze,None,None,None]. \n\n## AIMA Chapter 7.3 Logic\n Knowledge bases consist of sentences. These sentences are expressed \naccording to the syntax of the representation language, which specifies all the \nsentences that are well formed. The notion of syntax is clear enough in ordinary arithmetic.\nA logic must also define the semantics, or meaning, of sentences. The semantics \ndefines the truth of each sentence with respect to each possible world. In standard \nlogics, every sentence must be either true or false in each possible world. \nIf a sentence is true in model m, we say that m satisfies a or sometimes m is a model \nof a. We use the notation M(a) to mean the set of all models of a. The relation of \nlogical entailment between sentences is the idea that a sentence follows logically \nfrom another sentence. formal definition of entailment: β⊨α if and only if in every \nmodel in which beta is true, alpha is also true. β⊨α if and only M(beta) is a subset\nof M(alpha). beta is the stronger assertion and can be x = 0. alpha can by xy = 0.\nAn inference algorithm that derives only entailed sentences is called sound or truth-preserving. \nSoundness is a highly desirable property. An unsound inference procedure essentially \nmakes things up as it goes along. The property of completeness is also desirable: \nan inference algorithm is complete if it can derive any sentence that is entailed. \nThe final issue to consider is grounding—the connection between logical reasoning \nprocesses and the real environment in which the agent exists.  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 1) The syntax of propositional logic defines the allowable sentences. \nThe atomic sentences consist of a single proposition symbol. Complex sentences are \nconstructed from simpler sentences, using parentheses and operators called logical \nconnectives. A literal is either an atomic sentence (a positive literal) or a negated \natomic sentence (a negative literal). AND is conjunction with conjuncts as its parts.\nOR is disjunction with disjunts as its parts. Implication sign has premise/antecedent\nand conclusion/consequent. Implications are also known as rules or if–then statements.\nBiconditional is if and only if. 2) A model sets the truth value, true or false, for\nevery propositional symbol. The rules can also be expressed with truth tables that \nspecify the truth value of a complex sentence for each possible assignment of truth \nvalues to its components\n\n## AIMA 7.5 Propositional Theorem Proving\n Theorem proving—applying rules of inference directly to the sentences \nin our knowledge base to construct a proof of the desired sentence without consulting models.\nIf the number of models is large but the length of the proof is short, then theorem \nproving can be more efficient than model checking. 1) inference rule: a -> b and a\ncan get b. elimination rule: a and b can get a. bidirectional is two inference rules.\n2) resolution: given a1 or a2 or a3 or a4, not a2 or not a4, we have a1 or a3.\ngiven a1 or a2, not a1 or not a3, we have a2 or not a3, but reduce only a1 at this time,\ncan't reduce two things at a time. More: given a1 or a2 or a3, not a2 or a5, a6, have\na1 or a3 or a5 or a6. CNF: or in clauses, clauses connected by and, not on literals.\na and not a should be discarded becuase it is an empty clause. Any complementary \nliterals appear in the same cluase should be discarded. Ground resolution theorem:\nIf a set of clauses is unsatisfiable, then the resolution closure of those clauses\ncontains the empty clause. 3) Horn clauses are closed under resolution. Resolve two\nhorn clauses yields a Horn clause. 1> Every definite clause can be written as an implication \nwhose premise is a conjunction of positive literals and whose conclusion is a single \npositive literal. In Horn form, the premise is called the body and the conclusion \nis called the head. Fact is a sentence consisting of a single positive literal.\n2> Inference with Horn clauses can be done through the forward-chaining and \nbackward-chaining algorithms. 3> Deciding entailment with Horn clauses can be done \nin time that is linear in the size of the knowledge base—a pleasant surprise.\nHorn form: definite clause not a or not b or c is implication a and b is c. \n4) The forward-chaining algorithm determines if a single proposition is entailed\nby a knowledge base of definite cluases. Forward chaining is sound and complete.\nForward chaining is an example of the general concept of data-driven reasoning—that \nis, reasoning in which the focus of attention starts with the known data. \nThe backward-chaining algorithm, as its name suggests, works backward from the \nquery. If the query q is known to be true, then no work is needed. Otherwise, the \nalgorithm finds those implications in the knowledge base whose conclusion is q. \nIf all the premises of one of those implications can be proved true (by backward \nchaining), then is true. Backward chaining is a form of goal-directed reasoning. \n\n## Module 7 Lecture Notes\n \nConjunctive Normal Form (CNF)\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n1> Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n2> Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n3> Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4> Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\nThe sentence is now in CNF!\nResolution Algorithm\nInference procedures based on resolution work using the principle of proof by contradiction.\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\nFirst, convert (KB ⋀ ¬𝛂) into CNF\nThen apply the resolution rule to the resulting clauses.\nResolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\nContinue the process until one of two things happens:\nThere are no new clauses that can be added. In this case, the KB does not entail 𝛂 Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\nThe resolution algorithm is complete! This makes is a very important inference method.\nHowever, we don’t always need the full power of resolution. Some KBs are formulated in a more restrictive form which enables them to use more efficient inference algorithms.\nDefinite clause – disjunction of literals where exactly one is positive\nHorn clause – disjunction of literals where at most one is positive\nThis includes definite clauses\nAnd clauses with no positive literals\nHorn clauses are closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\nKBs with only definite clauses\n1> Every definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal.\n¬ L1,1 ⋁ ¬ Breeze ⋁ B1,1 can be written as the implication L1,1 ⋀ Breeze ⟹ B1,1\n2> Inference with Horn clauses can be done through the forward-chaining and\nbackward-chaining algorithms\n3> Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\nForward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\nBackward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\nBackward chaining is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Wumpus world** - a cave consisting of rooms connected by passageways\n* **Syntax_book** - the structure of sentences\n* **Semantics_book2** - the way in which the truth of sentences is determined\n* **Semantics_book1** - meaning of sentences\n* **Model** - mathematical abstraction of possible worlds\n* **Grounding** - the connection between logical reasoning processes and the real environment in which the agent exists\n* **Literal** - either an atomic sentence or a negated atomic sentence\n* **Logical equivalence** - two sentences are equivalent if and only if each of them entails the other\n* **Validity** - A sentence is valid if it si true in all models\n* **Satisfiability** - A sentence is satisfiable if it is true in some model\n* **Definite clause** - a disjunction of literals with exactly one positive\n* **Horn clause** - a disjunction of literals with at most one positive\n* **Goal clause** - a disjunction of literals with at no positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}