{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "09677f1f-fff0-49d4-b65b-43590c840bdb"
      },
      "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": "a7d0030e-026b-4812-9356-0183e5fc57db"
      },
      "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-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" The Turing test says that in order for a machine to be able to think it \n",
        "needs: natural language processing, knowledge prepresetntaion to store what it knows \n",
        "or hears, automated reasoning, and machine learning. The total turing test also requires\n",
        "interaction with objects and people in the world: computer vision and speech recognition, \n",
        "or robotics to manipulate onjects. We learn about human thoughts in 3 ways: introspection, \n",
        "psychological experiments, and brain imaging. Aristotle's syllogisms provided patterens\n",
        "for argument structures. The rational-agent approach has two advantages: it is more\n",
        "general than the \"laws of thought\" because a correct inference is only one of the mechanisms\n",
        "for achieving rationality, and it is more amenable to scientific development. \n",
        "perfect rationality—always taking the exactly optimal action—is not feasible in complex environments\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" The Argument from informality of behavior says human behavior is \n",
        "far too complex to be captured by a formal set of rules. Some could never be \n",
        "codified into a computer program. An agent whose understanding of “dog” comes\n",
        "only from a limited set of logical sentences such as “ Dog(x)⇒Mammal(x)” is at \n",
        "a disadvantage compared to an agent that has watched dogs run, has played fetch\n",
        "with them, and has been licked by one. We need to study the system as a whole; \n",
        "the brain’s functioning exploits regularities in its environment, including the\n",
        "rest of its body. Under the embodied cognition approach, uses robotics, vision, and other sensors become central.\n",
        "The argument from disability makes the claim that “a machine can never do X.” As examples of X\n",
        "Machines are mentally inferior to humansan agent should not be ashamed that it cannot\n",
        "establish the truth of some sentence while other agents can.No entity—human or \n",
        "machine—can prove things that are impossible to prove.\n",
        "Alan Turing, in his famous paper “Computing Machinery and Intelligence” (1950),\n",
        "suggested that instead of asking whether machines can think, we should ask whether \n",
        "machines can pass a behavioral test, which has come to be called the Turing test.\n",
        "The point is to improve basic science and technology and to provide useful tools, not to fool judges.\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Some philosophers claim that a machine that acts intelligently would\n",
        "not be actually thinking but would only be a simulation of thinking. Many AI researches \n",
        "are not concerned with the distinction.\n",
        "Turing said we never have any direct evidence about the internal mental states of other humans\n",
        "The problem of consciousness is ill defined\n",
        "We do agree that behaving intelligently will require some degree of awareness, \n",
        "which will differ from task to task, and that tasks involving interaction with \n",
        "humans will require a model of human subjective experience\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" an agent’s choice of action at any given instant can depend on its \n",
        "built-in knowledge and on the entire percept sequence observed to date, but not on \n",
        "anything it hasn’t perceived. We can imagine tabulating the agent function that \n",
        "describes any given agent; this would be a very large table (infinite). \n",
        "Given an agent we can construct this table by trying out all possible percept sequences\n",
        "and recording which actions the agent does in response. The table is an external \n",
        "characterization of the agent. Internally, the agent function for an artificial\n",
        "agent will be implemented by an agent program.\"\"\"\n",
        "chapter2_2 = \"\"\" In AI the notion of what is the \"right thing\" is called consequenitalism.\n",
        "As a general rule, it is better to design performance measures according to what one \n",
        "actually wants to be achieved in the environment, rather than according to how one\n",
        "thinks the agent should behave. What is rational depends on: \n",
        "1. the performance measure that defines success \n",
        "2. the agent's prior knowledge of the environment \n",
        "3. the actions that the agent can \n",
        "perform \n",
        "4.the agents percept sequence to date. Rationality maximizes expected performance, \n",
        "while perfection maximizes actual performance. If an agent relies on prior knowledge\n",
        "and not its own percepts and learning processes, we say it lacks autonomy. the \n",
        "incorporation of learning allows one to design a single rational agent that will \n",
        "succeed in a vast variety of environments.\"\"\"\n",
        "chapter2_3 = \"\"\" task environment: PEAS (Performance, Environment, Actuators, Sensors). \n",
        "When designing an agent the first step must always be to specify the task environment \n",
        "as fully as possible. virtual task environments can be just as complex as the “real” world:\n",
        "a software agent (or software robot or softbot) is just as valid. An environment might be \n",
        "partially observable because of noisy and inaccurate sensors or because parts of the\n",
        "state are simply missing from the sensor data. The distinction between known and unknown\n",
        "environments is not the same as the one between fully and partially observable environments. \n",
        "It is possible for a known environment to be partially observableve/an unknown \n",
        "environment can be fully observable. The performance measure could even be unknown.\n",
        "The hardest case is partially observable, multiagent, nondeterministic, sequential, \n",
        "dynamic, continuous, and unknown. \"\"\"\n",
        "chapter2_4 = r\"\"\" agent program, agent function\n",
        "``` \n",
        "function table_driven_agent(percept) returns an_action\n",
        "  persistent: percepts, a sequence, initially empty\n",
        "              table, a table of actions, indexed by percept sequences, initailly fully specified\n",
        "  append percept to the end of percepts\n",
        "  action <- look_up(percepts, table)\n",
        "  return action\n",
        "```\n",
        "This is doomed to failure, if P is percepts adn T is lifetime, the lookup will contain \n",
        "$$\\sum_{t=1}^{\\tau}\\|\\P|^{t}$$ no physical agent in the univers would have the space to store this\n",
        "\n",
        "Key challenge for AI is to write programs that produce rational behavior from a smallish program \n",
        "rather than from a vast table. The simplest agent: simple reflex agent. These implement \n",
        "the condition-action rule (if-then rules). These only work in fully observable environments. \n",
        "\n",
        "The most effective way to handle partial observability is for the agent to keep track of the part of the world \n",
        "it can’t see now(maintain some sort of internal state.) \n",
        "\n",
        "To update the internal state we need: a transition model, and a sensor model. Allows the agent to track of the state.\n",
        "``` \n",
        "function model-based-reflex-agent(percept) retuns an action\n",
        "  persistent: state\n",
        "              transition_model\n",
        "              sensor_model\n",
        "                    reflected in the agent's percepts\n",
        "              rules\n",
        "              action, the most recent action, initially none\n",
        "  state <- update_state(state, action, percept, transition_model, sensor_model)\n",
        "  rule <- rule_match(state, rules)\n",
        "  action <- rule, action\n",
        "  return action\n",
        "``` \n",
        "Search and planning find action sequences that achieve the agents goals. While goal-based agent \n",
        "appear less efficient, they are more flexible because the knowledge that supports decisions is \n",
        "represented explicitly and can be modified. In many environments goals are not enough to \n",
        "generate good behavior. A more general performance measure allows a comparison of different \n",
        "world states according to their expected utility. This works insituations where other agents would fail, \n",
        "ie: there are conflicting goals (some can be achieved)-> utility function specifies the \n",
        "appropriate tradeoff or when there are several goals that the agent can aim for \n",
        "(none of which are certain), weighs the likelihood of success the importance of the goals.\n",
        "This allows the agent to operate in initially unknown environments and to be more \n",
        "competent than its initial knowledge alone might allow.\n",
        "\n",
        "Learning in intelligent agents: a process of modification of each component of the agent \n",
        "to bring the components into closer agreement with the available feedback information, \n",
        "improving the overall performance of the agent.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"Decartes: priciple of dualism - the mind or thinking self\n",
        "is essentiall incorporeal or spiritual - the mind exists separate from the body. Find a test only \n",
        "a human could pass. Alan Turing: Can machines think? John Searle: the chinese room.\n",
        "Turing test is bad because the appearance of being a good conversational participant is achievable through\n",
        "simple symbol manipulation. Dennett: If a brain in a cat is procssing symbols what makes\n",
        "this different from a computer processing symbols. There are four views of artificial intelligence:\n",
        "thinking humanly, thinking rationally, acting humanly, acting rationally. An agent \n",
        "is specified by an agent function f:P⇒A that maps a sequence of percept vectors P to an action\n",
        "a from a set A. The agent program runs on the physical architecture to produce f. \n",
        "We define a performance measure: An objective criterion for success of an \n",
        "agent's behavior, given the evidence provided by the percept sequence. It is better to design performance measures according to what you want to be\n",
        "achieved in the environment, rather than how you think the agent should behave.\n",
        "computational limitations make complete rationality unachievable. To design a rational agent we need\n",
        "to specify a taks environment: PEAS (performance measure, environment, actuators, sensors).\n",
        "With a given task environment: 1. construct an agent function f that maximizes the expected \n",
        "value of the performance measure 2. design an agent program that impelments f on a particular architecture.\"\"\"\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 (though sensors) and act in an environment (through actuators)\",\n",
        "\"percept\" : \"what the agent's sensor percieve\",\n",
        "\"percept sequence\" : \"what the agent's sensor percieve\",\n",
        "\"artificial intelligence\" : \"the study of understanding and building intelligent entities\",\n",
        "\"rationality\": \"doing the right thing\",\n",
        "\"turring test\": \" thought experiment that bypasses the vagueness of 'can a machine think?'\",\n",
        "\"natural language processing\": \"communicate effectively in human language\",\n",
        "\"knowledge represetnation\": \"storing what a computer knows or hears\",\n",
        "\"automated reasoning\": \"answering questions and drawing new conclusions\",\n",
        "\"machine learning\": \"adapting to new circumstances and detecting/extrapolating patterns\",\n",
        "\"introspection\": \"trying to catch ones thoughts as they go by\",\n",
        "\"psychological experiments\": \"obsercing a person while in action\",\n",
        "\"brain imaginging\": \"observing the brain while in action\",\n",
        "\"cognitive science\": \"testable theories of the human mind that come from AI and experimental psychology\",\n",
        "\"syllogisms\": \"patterns for the structures of arguments that give correct conclusions with correct premices\",\n",
        "\"logicist\": \"the theory that knowledge of the world that is certain, ie right or wrong\",\n",
        "\"probability\": \"allows for reasoning without perfect information, lets a model think rationally\",\n",
        "\"rational agent\": \"an agent that should select an action that will maximize its performace measure given its percept sequence\",\n",
        "\"standard model\": \"study and construction of agents that do the right thing as defined by the objective provided to the agent\",\n",
        "\"limited rationality\": \"acting correctly when there is not enoug time to do all computations\",\n",
        "\"value alignment problem\": \"values put into the machine must be those of a human\",\n",
        "\"provably beneficial\": \"if the complete objective is not known, machine has an incentive to act with caution, ask permission\",\n",
        "\"weak AI\": \"machines could act as if htey were intelligent\",\n",
        "\"strong AI\": \"machines are actually consciously thinking\",\n",
        "\"good old-fashioned AI (GOFAI)\": \"the simplest logical agent\",\n",
        "\"qualification problem\": \"it is difficult to capture every contingency of appropriate behavior in a set of rules\",\n",
        "\"embodied cognition\": \"cognition takes place withing a body which is embedded in an environment\",\n",
        "\"chinese room\": \" rule book/stacks of paper, don't understand Chinese. So there is no understanding of Chinese.\",\n",
        "\"biological naturalism\": \"neurons have “it” and transistors do not\",\n",
        "\"consciousness\": \"awareness of the outside wrold\",\n",
        "\"qualia\": \"intrinsic nature of experiences\",\n",
        "\"consequentialism\": \"an evaluation of an agents behaviour based on its consequences\",\n",
        "\"performance measure\": \"evaluates a sequenc of performance states\",\n",
        "\"omniscience\": \"omnicient agent knows the outcome of its actions and acts accordingly, not possible in real world\",\n",
        "\"information gathering\": \"doing actions in order to modify future percepts\",\n",
        "\"exploration\": \"surveying an initially unknown environment\",\n",
        "\"autonomy\": \"\",\n",
        "\"task environment\": \"the problems to which rational agents are the solutions\",\n",
        "\"performance measure\": \"desirable qualities or goals for the task environment\",\n",
        "\"environment\": \"what will the agent face\",\n",
        "\"actuators\": \"what the agent can move or manipulate\",\n",
        "\"sensors\": \"what does the agent have to observe its environment\",\n",
        "\"competitive\": \"when agent B is trying to maximize its performance measure while minimizing agent A's\",\n",
        "\"cooperative\": \"when doing something maximizes the performance for each of the agents\",\n",
        "\"intelligent\": \"\",\n",
        "\"fully observable\": \"if the agent's sensors give it access to teh complete state of the enviornment at every point in time\",\n",
        "\"unobservable\": \"if the agent has no sesors at all\",\n",
        "\"partially observable\": \"\",\n",
        "\"deterministic\": \"if the next state is completely determined by the current state and action\",\n",
        "\"nondeterministic\": \"if the next state is NOT completely determined by the current state and action\",\n",
        "\"stochastic\": \"a nondeterministic environment that directly relates to probabilities\",\n",
        "\"episodic\": \"\",\n",
        "\"sequential\": \"\",\n",
        "\"static\": \"the environment cannot change while the agent is deliberating\",\n",
        "\"dynamic\": \"if the environment can change while the agent is deciding\",\n",
        "\"semidynamic\": \"if the environment does not change but the agent's performace does\",\n",
        "\"discrete\": \"if the agent has a finite number of discrete states for the percepts and actions\",\n",
        "\"continuous\": \"continuous-state, continuouts-time problems\",\n",
        "\"known\": \"the agent knows all outcomes for all actions that are given\",\n",
        "\"unknown\": \"the agent will have to learn how the environment works in order to make good decisions\",\n",
        "\"agent program\": \"implements the agent function (current percept (input from the sensors), return (action to the actuators)\",\n",
        "\"agent function\": \"maps a sequence of percept vectors P to an action\",\n",
        "\"agent architecture\": \"where an agetn program runs (some computing device with physical sensors and actuators\",\n",
        "\"simple reflex agent\": \"selects actions based on the current percept, ignoring the rest of the percept history\",\n",
        "\"internal state\": \"depends on percept history and reflects some of the unobserved aspects of the current state\",\n",
        "\"transition model\" : \"info about how the world changes over time (the effects of the agent's actions and how the world evolves)\",\n",
        "\"sensor model\": \"info about how the stare of the world is reflected in teh agent's percepts\",\n",
        "\"model based reflex agent\": \"an agent that uses transition models and sensor models to keep track of the state of the world\",\n",
        "\"goal based agent\": \"same as model based agent but with a goal\",\n",
        "\"utility\": \"the quality of being useful\",\n",
        "\"utility function\": \"internalization of the perforamce measure\",\n",
        "\"expected utility\": \"the utility the agent expects to derrive\",\n",
        "\"model free agent\": \"can learn what action is best in a sityation without learning how the action changes the environment\",\n",
        "\"learning agent\": \"makes improvemnts\",\n",
        "\"performance element\": \"selects external actions\",\n",
        "\"critic\": \"gives feedback on how the agent is doing and determines how the performance element should be modified\",\n",
        "\"problem generator\": \"suggests actions that will lead to new and informative experiences\",\n",
        "\"reward (or penalty)\": \"provides direct feedback on the quality of the agent's behavior\",\n",
        "\"atomic representation\": \"each state is indivisible, no internal structure\",\n",
        "\"factored representation\": \"splits each state into a fixed set of variables or attributes, each of which has a value\",\n",
        "\"structured representation\": \"when objects can be described explicitly\",\n",
        "\"utility based agent\": \"\",\n",
        "\"single agent\": \"\",\n",
        "\"multi agent\": \"\",\n",
        "\"reflex agent\": \"\",\n",
        "\"problem solving agent\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4d77dcfe-ba7b-4e85-d440-e4326777b376"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n The Turing test says that in order for a machine to be able to think it \nneeds: natural language processing, knowledge prepresetntaion to store what it knows \nor hears, automated reasoning, and machine learning. The total turing test also requires\ninteraction with objects and people in the world: computer vision and speech recognition, \nor robotics to manipulate onjects. We learn about human thoughts in 3 ways: introspection, \npsychological experiments, and brain imaging. Aristotle's syllogisms provided patterens\nfor argument structures. The rational-agent approach has two advantages: it is more\ngeneral than the \"laws of thought\" because a correct inference is only one of the mechanisms\nfor achieving rationality, and it is more amenable to scientific development. \nperfect rationality—always taking the exactly optimal action—is not feasible in complex environments\n\n## AIMA Chapter 27.1 The Limits of AI\n The Argument from informality of behavior says human behavior is \nfar too complex to be captured by a formal set of rules. Some could never be \ncodified into a computer program. An agent whose understanding of “dog” comes\nonly from a limited set of logical sentences such as “ Dog(x)⇒Mammal(x)” is at \na disadvantage compared to an agent that has watched dogs run, has played fetch\nwith them, and has been licked by one. We need to study the system as a whole; \nthe brain’s functioning exploits regularities in its environment, including the\nrest of its body. Under the embodied cognition approach, uses robotics, vision, and other sensors become central.\nThe argument from disability makes the claim that “a machine can never do X.” As examples of X\nMachines are mentally inferior to humansan agent should not be ashamed that it cannot\nestablish the truth of some sentence while other agents can.No entity—human or \nmachine—can prove things that are impossible to prove.\nAlan Turing, in his famous paper “Computing Machinery and Intelligence” (1950),\nsuggested that instead of asking whether machines can think, we should ask whether \nmachines can pass a behavioral test, which has come to be called the Turing test.\nThe point is to improve basic science and technology and to provide useful tools, not to fool judges.\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Some philosophers claim that a machine that acts intelligently would\nnot be actually thinking but would only be a simulation of thinking. Many AI researches \nare not concerned with the distinction.\nTuring said we never have any direct evidence about the internal mental states of other humans\nThe problem of consciousness is ill defined\nWe do agree that behaving intelligently will require some degree of awareness, \nwhich will differ from task to task, and that tasks involving interaction with \nhumans will require a model of human subjective experience\n \n\n## AIMA 2.1 Agents and Environments\n an agent’s choice of action at any given instant can depend on its \nbuilt-in knowledge and on the entire percept sequence observed to date, but not on \nanything it hasn’t perceived. We can imagine tabulating the agent function that \ndescribes any given agent; this would be a very large table (infinite). \nGiven an agent we can construct this table by trying out all possible percept sequences\nand recording which actions the agent does in response. The table is an external \ncharacterization of the agent. Internally, the agent function for an artificial\nagent will be implemented by an agent program.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n In AI the notion of what is the \"right thing\" is called consequenitalism.\nAs a general rule, it is better to design performance measures according to what one \nactually wants to be achieved in the environment, rather than according to how one\nthinks the agent should behave. What is rational depends on: \n1. the performance measure that defines success \n2. the agent's prior knowledge of the environment \n3. the actions that the agent can \nperform \n4.the agents percept sequence to date. Rationality maximizes expected performance, \nwhile perfection maximizes actual performance. If an agent relies on prior knowledge\nand not its own percepts and learning processes, we say it lacks autonomy. the \nincorporation of learning allows one to design a single rational agent that will \nsucceed in a vast variety of environments.\n\n## AIMA 2.3 The Nature of Environments\n task environment: PEAS (Performance, Environment, Actuators, Sensors). \nWhen designing an agent the first step must always be to specify the task environment \nas fully as possible. virtual task environments can be just as complex as the “real” world:\na software agent (or software robot or softbot) is just as valid. An environment might be \npartially observable because of noisy and inaccurate sensors or because parts of the\nstate are simply missing from the sensor data. The distinction between known and unknown\nenvironments is not the same as the one between fully and partially observable environments. \nIt is possible for a known environment to be partially observableve/an unknown \nenvironment can be fully observable. The performance measure could even be unknown.\nThe hardest case is partially observable, multiagent, nondeterministic, sequential, \ndynamic, continuous, and unknown. \n\n## AIMA 2.4 The Structure of Agents\n agent program, agent function\n``` \nfunction table_driven_agent(percept) returns an_action\n  persistent: percepts, a sequence, initially empty\n              table, a table of actions, indexed by percept sequences, initailly fully specified\n  append percept to the end of percepts\n  action <- look_up(percepts, table)\n  return action\n```\nThis is doomed to failure, if P is percepts adn T is lifetime, the lookup will contain \n$$\\sum_{t=1}^{\\tau}\\|\\P|^{t}$$ no physical agent in the univers would have the space to store this\n\nKey challenge for AI is to write programs that produce rational behavior from a smallish program \nrather than from a vast table. The simplest agent: simple reflex agent. These implement \nthe condition-action rule (if-then rules). These only work in fully observable environments. \n\nThe most effective way to handle partial observability is for the agent to keep track of the part of the world \nit can’t see now(maintain some sort of internal state.) \n\nTo update the internal state we need: a transition model, and a sensor model. Allows the agent to track of the state.\n``` \nfunction model-based-reflex-agent(percept) retuns an action\n  persistent: state\n              transition_model\n              sensor_model\n                    reflected in the agent's percepts\n              rules\n              action, the most recent action, initially none\n  state <- update_state(state, action, percept, transition_model, sensor_model)\n  rule <- rule_match(state, rules)\n  action <- rule, action\n  return action\n``` \nSearch and planning find action sequences that achieve the agents goals. While goal-based agent \nappear less efficient, they are more flexible because the knowledge that supports decisions is \nrepresented explicitly and can be modified. In many environments goals are not enough to \ngenerate good behavior. A more general performance measure allows a comparison of different \nworld states according to their expected utility. This works insituations where other agents would fail, \nie: there are conflicting goals (some can be achieved)-> utility function specifies the \nappropriate tradeoff or when there are several goals that the agent can aim for \n(none of which are certain), weighs the likelihood of success the importance of the goals.\nThis allows the agent to operate in initially unknown environments and to be more \ncompetent than its initial knowledge alone might allow.\n\nLearning in intelligent agents: a process of modification of each component of the agent \nto bring the components into closer agreement with the available feedback information, \nimproving the overall performance of the agent.\n\n## Module 1 Lecture Notes\nDecartes: priciple of dualism - the mind or thinking self\nis essentiall incorporeal or spiritual - the mind exists separate from the body. Find a test only \na human could pass. Alan Turing: Can machines think? John Searle: the chinese room.\nTuring test is bad because the appearance of being a good conversational participant is achievable through\nsimple symbol manipulation. Dennett: If a brain in a cat is procssing symbols what makes\nthis different from a computer processing symbols. There are four views of artificial intelligence:\nthinking humanly, thinking rationally, acting humanly, acting rationally. An agent \nis specified by an agent function f:P⇒A that maps a sequence of percept vectors P to an action\na from a set A. The agent program runs on the physical architecture to produce f. \nWe define a performance measure: An objective criterion for success of an \nagent's behavior, given the evidence provided by the percept sequence. It is better to design performance measures according to what you want to be\nachieved in the environment, rather than how you think the agent should behave.\ncomputational limitations make complete rationality unachievable. To design a rational agent we need\nto specify a taks environment: PEAS (performance measure, environment, actuators, sensors).\nWith a given task environment: 1. construct an agent function f that maximizes the expected \nvalue of the performance measure 2. design an agent program that impelments f on a particular architecture.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (though sensors) and act in an environment (through actuators)\n* **Percept** - what the agent's sensor percieve\n* **Percept sequence** - what the agent's sensor percieve\n* **Artificial intelligence** - the study of understanding and building intelligent entities\n* **Rationality** - doing the right thing\n* **Turring test** -  thought experiment that bypasses the vagueness of 'can a machine think?'\n* **Natural language processing** - communicate effectively in human language\n* **Knowledge represetnation** - storing what a computer knows or hears\n* **Automated reasoning** - answering questions and drawing new conclusions\n* **Machine learning** - adapting to new circumstances and detecting/extrapolating patterns\n* **Introspection** - trying to catch ones thoughts as they go by\n* **Psychological experiments** - obsercing a person while in action\n* **Brain imaginging** - observing the brain while in action\n* **Cognitive science** - testable theories of the human mind that come from AI and experimental psychology\n* **Syllogisms** - patterns for the structures of arguments that give correct conclusions with correct premices\n* **Logicist** - the theory that knowledge of the world that is certain, ie right or wrong\n* **Probability** - allows for reasoning without perfect information, lets a model think rationally\n* **Rational agent** - an agent that should select an action that will maximize its performace measure given its percept sequence\n* **Standard model** - study and construction of agents that do the right thing as defined by the objective provided to the agent\n* **Limited rationality** - acting correctly when there is not enoug time to do all computations\n* **Value alignment problem** - values put into the machine must be those of a human\n* **Provably beneficial** - if the complete objective is not known, machine has an incentive to act with caution, ask permission\n* **Weak ai** - machines could act as if htey were intelligent\n* **Strong ai** - machines are actually consciously thinking\n* **Good old-fashioned ai (gofai)** - the simplest logical agent\n* **Qualification problem** - it is difficult to capture every contingency of appropriate behavior in a set of rules\n* **Embodied cognition** - cognition takes place withing a body which is embedded in an environment\n* **Chinese room** -  rule book/stacks of paper, don't understand Chinese. So there is no understanding of Chinese.\n* **Biological naturalism** - neurons have “it” and transistors do not\n* **Consciousness** - awareness of the outside wrold\n* **Qualia** - intrinsic nature of experiences\n* **Consequentialism** - an evaluation of an agents behaviour based on its consequences\n* **Performance measure** - desirable qualities or goals for the task environment\n* **Omniscience** - omnicient agent knows the outcome of its actions and acts accordingly, not possible in real world\n* **Information gathering** - doing actions in order to modify future percepts\n* **Exploration** - surveying an initially unknown environment\n* **Autonomy** - \n* **Task environment** - the problems to which rational agents are the solutions\n* **Environment** - what will the agent face\n* **Actuators** - what the agent can move or manipulate\n* **Sensors** - what does the agent have to observe its environment\n* **Competitive** - when agent B is trying to maximize its performance measure while minimizing agent A's\n* **Cooperative** - when doing something maximizes the performance for each of the agents\n* **Intelligent** - \n* **Fully observable** - if the agent's sensors give it access to teh complete state of the enviornment at every point in time\n* **Unobservable** - if the agent has no sesors at all\n* **Partially observable** - \n* **Deterministic** - if the next state is completely determined by the current state and action\n* **Nondeterministic** - if the next state is NOT completely determined by the current state and action\n* **Stochastic** - a nondeterministic environment that directly relates to probabilities\n* **Episodic** - \n* **Sequential** - \n* **Static** - the environment cannot change while the agent is deliberating\n* **Dynamic** - if the environment can change while the agent is deciding\n* **Semidynamic** - if the environment does not change but the agent's performace does\n* **Discrete** - if the agent has a finite number of discrete states for the percepts and actions\n* **Continuous** - continuous-state, continuouts-time problems\n* **Known** - the agent knows all outcomes for all actions that are given\n* **Unknown** - the agent will have to learn how the environment works in order to make good decisions\n* **Agent program** - implements the agent function (current percept (input from the sensors), return (action to the actuators)\n* **Agent function** - maps a sequence of percept vectors P to an action\n* **Agent architecture** - where an agetn program runs (some computing device with physical sensors and actuators\n* **Simple reflex agent** - selects actions based on the current percept, ignoring the rest of the percept history\n* **Internal state** - depends on percept history and reflects some of the unobserved aspects of the current state\n* **Transition model** - info about how the world changes over time (the effects of the agent's actions and how the world evolves)\n* **Sensor model** - info about how the stare of the world is reflected in teh agent's percepts\n* **Model based reflex agent** - an agent that uses transition models and sensor models to keep track of the state of the world\n* **Goal based agent** - same as model based agent but with a goal\n* **Utility** - the quality of being useful\n* **Utility function** - internalization of the perforamce measure\n* **Expected utility** - the utility the agent expects to derrive\n* **Model free agent** - can learn what action is best in a sityation without learning how the action changes the environment\n* **Learning agent** - makes improvemnts\n* **Performance element** - selects external actions\n* **Critic** - gives feedback on how the agent is doing and determines how the performance element should be modified\n* **Problem generator** - suggests actions that will lead to new and informative experiences\n* **Reward (or penalty)** - provides direct feedback on the quality of the agent's behavior\n* **Atomic representation** - each state is indivisible, no internal structure\n* **Factored representation** - splits each state into a fixed set of variables or attributes, each of which has a value\n* **Structured representation** - when objects can be described explicitly\n* **Utility based agent** - \n* **Single agent** - \n* **Multi agent** - \n* **Reflex agent** - \n* **Problem solving agent** - \n* **** - \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 = \"\"\" In python all data is treated as objects (an object is deleted \n",
        "once unreachable) \n",
        "Strong typing - every object has a fixed type, doesn't allow things incompatible with that type\n",
        "- example of types: int, float, str, tuple, dict, list, bool, None, generator, function\n",
        "\n",
        "Static vs Dynamic typing - Python is dynamic variables come into existance when first assigned\n",
        "(x = 2 not int x = 2)\n",
        "\n",
        "Strings: single or double quotes, concatenation: separating literals with white space or +,\n",
        "prefixing with r means raw, formatting, immutable\n",
        "\n",
        "Refrences and mutability\n",
        "- strings are immutable\n",
        "  - == checks whether vars point to objects of the same value\n",
        "  - is checks wheather vars point to the same object\n",
        "  - reg strings are Unicode and use 2-byte characters\n",
        "  -  words = s.split(\" \") # splits on space\n",
        "- lists are mutable\n",
        "  - use y=x[:] to get a shallow copy of any sequence\n",
        "  - t[1:-1:2] # selection of every nth item.\n",
        "  - t[:2] # copy from beginning of sequence\n",
        "  - t[2:] # copy to the very end of the sequence\n",
        "  - li.insert(2, 'i') # inserts at index 2\n",
        "  - li.reverse() # reverse the list *in place* (modify)\n",
        "  - li.sort() # sort the list *in place*\n",
        "  - li.sort(some_function) # sort in place using user-defined comparison\n",
        "- tuples are immutable \n",
        "  - items can be of mixed types (inc collection types)\n",
        "- dict\n",
        "  - Dictionaries are unordered & work by hashing, so keys must be immutable\n",
        "  - Constant average time add, lookup, update\n",
        "- functions\n",
        "  - no fuction overloading, a function is specified by its name alone, even if they \n",
        "    have different input arguments\n",
        "  - operator overloading (overloading +, ==, -, etc.) can happen when you implement a class\n",
        "  - they are first class objects and first class citizens\n",
        "- classes\n",
        "  - subclasses: To define a subclass, put the name of the superclass in parentheses after the\n",
        "    subclass’s name on the first line of the definition \n",
        "  - You can implement operator overloading with magic methods\n",
        "    operators trigger a magic method, defined in a class\n",
        "  - We can call the Python function len() on any class that implements ```__len__``` .\n",
        "- list comprehesnion:\n",
        "  - li = [3, 6, 2, 7, 1, 9]\n",
        "  - [elem * 2 for elem in li if elem > 4]\n",
        "  - [12, 14, 18]\n",
        "- dictionary, set comprehension also exists\n",
        "  - d = { k: v for k,v in lst1 }\n",
        "  - s = { x for x in lst2 }\n",
        "- iterators\n",
        "  - have a ``` __next__()```  method\n",
        "    - they don't have a hasnext() method, just catch the StopIteration exception\n",
        "  - use memory efficiently\n",
        "- generators\n",
        "  - iterators\n",
        "  - Creating Generators: yield\n",
        "  - Less code than writing a standard iterator\n",
        "  - Maintains local state automatically\n",
        "  - Values are computed one at a time, as they’re needed\n",
        "  - Avoids storing the entire sequence in memory\n",
        "  - Good for aggregating (summing, counting) items. One pass.\n",
        "  - Crucial for infinite sequences\n",
        "  - Bad if you need to inspect the individual values\n",
        "    \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "\"immutable\": \"cannot be modified once created\",\n",
        "\"tuple\": \"simple immutable ordered sequence of items\",\n",
        "\"list\": \"mutable ordered sequence of mixed types\",\n",
        "\"first class object\": \" entitiy that can be dynamically created, destroyedm passed to a func, returned as a val\",\n",
        "\"first class citizens\": \"pass funcs as args to other funcs, return funcs from other funcs, assign funcs to vars or store\",\n",
        "\"higher order functions\": \"higher order funcs take other funcs as inputs\",\n",
        "\"subclass\": \"a class can extend the def of another class, allows the use of methords or atttributes in the previous class\",\n",
        "\"magic methods\": \"allow user-defined classes to behave like built in types\",\n",
        "\"duck typing\": \"establishes situbility of an object by determining presence of methods\",\n",
        "\"iterator objects\": \"can be used in a for loop bc they have an ``` __iter__```  magic method\",\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b6475358-1985-4a8e-c9c8-ab6961d3de65"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n In python all data is treated as objects (an object is deleted \nonce unreachable) \nStrong typing - every object has a fixed type, doesn't allow things incompatible with that type\n- example of types: int, float, str, tuple, dict, list, bool, None, generator, function\n\nStatic vs Dynamic typing - Python is dynamic variables come into existance when first assigned\n(x = 2 not int x = 2)\n\nStrings: single or double quotes, concatenation: separating literals with white space or +,\nprefixing with r means raw, formatting, immutable\n\nRefrences and mutability\n- strings are immutable\n  - == checks whether vars point to objects of the same value\n  - is checks wheather vars point to the same object\n  - reg strings are Unicode and use 2-byte characters\n  -  words = s.split(\" \") # splits on space\n- lists are mutable\n  - use y=x[:] to get a shallow copy of any sequence\n  - t[1:-1:2] # selection of every nth item.\n  - t[:2] # copy from beginning of sequence\n  - t[2:] # copy to the very end of the sequence\n  - li.insert(2, 'i') # inserts at index 2\n  - li.reverse() # reverse the list *in place* (modify)\n  - li.sort() # sort the list *in place*\n  - li.sort(some_function) # sort in place using user-defined comparison\n- tuples are immutable \n  - items can be of mixed types (inc collection types)\n- dict\n  - Dictionaries are unordered & work by hashing, so keys must be immutable\n  - Constant average time add, lookup, update\n- functions\n  - no fuction overloading, a function is specified by its name alone, even if they \n    have different input arguments\n  - operator overloading (overloading +, ==, -, etc.) can happen when you implement a class\n  - they are first class objects and first class citizens\n- classes\n  - subclasses: To define a subclass, put the name of the superclass in parentheses after the\n    subclass’s name on the first line of the definition \n  - You can implement operator overloading with magic methods\n    operators trigger a magic method, defined in a class\n  - We can call the Python function len() on any class that implements ```__len__``` .\n- list comprehesnion:\n  - li = [3, 6, 2, 7, 1, 9]\n  - [elem * 2 for elem in li if elem > 4]\n  - [12, 14, 18]\n- dictionary, set comprehension also exists\n  - d = { k: v for k,v in lst1 }\n  - s = { x for x in lst2 }\n- iterators\n  - have a ``` __next__()```  method\n    - they don't have a hasnext() method, just catch the StopIteration exception\n  - use memory efficiently\n- generators\n  - iterators\n  - Creating Generators: yield\n  - Less code than writing a standard iterator\n  - Maintains local state automatically\n  - Values are computed one at a time, as they’re needed\n  - Avoids storing the entire sequence in memory\n  - Good for aggregating (summing, counting) items. One pass.\n  - Crucial for infinite sequences\n  - Bad if you need to inspect the individual values\n    \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Immutable** - cannot be modified once created\n* **Tuple** - simple immutable ordered sequence of items\n* **List** - mutable ordered sequence of mixed types\n* **First class object** -  entitiy that can be dynamically created, destroyedm passed to a func, returned as a val\n* **First class citizens** - pass funcs as args to other funcs, return funcs from other funcs, assign funcs to vars or store\n* **Higher order functions** - higher order funcs take other funcs as inputs\n* **Subclass** - a class can extend the def of another class, allows the use of methords or atttributes in the previous class\n* **Magic methods** - allow user-defined classes to behave like built in types\n* **Duck typing** - establishes situbility of an object by determining presence of methods\n* **Iterator objects** - can be used in a for loop bc they have an ``` __iter__```  magic method\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" In this chapter, we consider only the simplest environments: episodic, \n",
        "single agent, fully observable, deterministic, static, Discrete, known. \n",
        "We distinguish between informed algorithms and uninformed algorithms, and Unknown environments.\n",
        "\n",
        "Assuming that agents have access to information about the world the agent can follow this\n",
        "four phase problem solving process: goal formulation, problem formulation, search, and execution.\n",
        "  - in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n",
        "Defining a problem:\n",
        "  - State space\n",
        "  - A set of one or more goal states\n",
        "  - The actions available to the agent\n",
        "  - A transitional model \n",
        "  - Action cost function\n",
        "\n",
        "Abstraction is valid if we can elaborate any abstract solution into a solution in the more \n",
        "detailed world.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Real world vs theoretical examples\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" Search algorithms:\n",
        "  - Search tree over the state space graph\n",
        "  - Each node corresponds to a state\n",
        "  - Expand a node\n",
        "  - Generating a new node (child node/successor node)\n",
        "  - Each node has a parent node (first step)\n",
        "  - Frontier \n",
        "    - frontier separates state-space graph: \n",
        "      - an interior region where every state has been expanded\n",
        "      - exterior region of states that have not yet been reached\n",
        " \n",
        "``` \n",
        "function best-first-search(problem,f) returns a solution node or failure\n",
        "  node <- NODE(STATE=problem.initial)\n",
        "  frontier <- priority queue ordered by f, wiht node as an element\n",
        "  reached <- lookup table, wiht one entry wiht key problem.initial and a value node\n",
        "  while not is-empty(frontier) do\n",
        "    node <- pop(frontier)\n",
        "    if problem.is-goal(node.STATE) then return node\n",
        "    for each child in EXPAND(problem, node) do\n",
        "    s <- child.STATE\n",
        "    if s is not in reached or child.PATH-COST < reached[s].PATH-COST then \n",
        "      reached[s] <- child\n",
        "      add child to frontier\n",
        "  return failure\n",
        "``` \n",
        "node in the tree represented by\n",
        "  - node.state: to which it corresponds\n",
        "  - node.parent: the node that generated it\n",
        "  - node.action: the action that was applied to the parent's state to get it\n",
        "  - node.path-cost: the cost of the path from the inital state to this node\n",
        "frontier: queue of some kinds is appropriate bc the operations on it are:\n",
        "  - is-empty: returns true only if there are no nodes in the frontier\n",
        "  - pop: removes the top node from the frontier and returns it\n",
        "  - top: returns but does not remove the top node of the fronier\n",
        "  - add: inserts node into its proper place in the queue\n",
        "queues:\n",
        "  - priority queue\n",
        "  - fifo queue\n",
        "  - lifo queue (stack)\n",
        "evaluate an algorithms performance:\n",
        "  - completeness\n",
        "  - cost optimality\n",
        "  - time complexity\n",
        "  - space complexity\n",
        "To be complete a search algorithm must be systematic in the way it explores an infinite state\n",
        "State space complexity can be measured in terms of d the depth and m the maximum number\n",
        "of actions in any bath; and b the branching factor\"\"\"\n",
        "chapter3_4 = \"\"\" Breadth-first-search\n",
        "``` \n",
        "function breadth-first-search(problem) returns a solution node or failure\n",
        "  node <- NODE(problem.INITIAL)\n",
        "  if problem.IS-GOAL(node.STATE) then return node\n",
        "  frontier <- a FIFO queue, with node as an element\n",
        "  reached <- {problem.INITIAL}\n",
        "  while not IS_EMPTY(frontier) do \n",
        "    node <- POP(frontier)\n",
        "    for each child in EXPAND(problem, node) do\n",
        "    s <- child.STATE\n",
        "    if problem.IS-GOAL(s) then return child\n",
        "    if s is not in reached then \n",
        "      add s to reached\n",
        "      add child to frontier\n",
        "    return failure\n",
        "    \n",
        "``` \n",
        "\\n\n",
        "``` \n",
        "function uniform-cost-search(problem) returns a solution node, or failure\n",
        "  return best-first-search(problem, path-cost)\n",
        "\n",
        "``` \n",
        "\\n\n",
        "``` \n",
        "function iterativ-deepening-search(problem) returns a solution node or failure\n",
        "  for depth = 0 to inf fo\n",
        "  result <- depth-limited-search(problem, depth)\n",
        "  if result != cutoof then return result\n",
        "\n",
        "``` \n",
        "\\n\n",
        "``` \n",
        "function depth-limited-search(problem, l) returns a node or failure or cutoff\n",
        "  froniter <- a LIFO queue (stack) with Node(problem.INITIAL) as an element\n",
        "  result <- failure\n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node <- POP(frontier)\n",
        "    if problem.IS-GOAL(node.STATE) then return node\n",
        "    if DEPTH(node) > l then \n",
        "      result <- cutoff\n",
        "    else if not IS-CYCLE(node) do\n",
        "      for each child in EXPAND(problem, node) do\n",
        "        add child to frontier\n",
        "  return result\n",
        "\n",
        "``` \n",
        "\n",
        "\\n\n",
        "``` \n",
        "function BIBF-Search(problemF,fF, problemB, fB) returns a solution node or failure\n",
        "  nodeF <-(problemF>initial)\n",
        "  nodeB <-(problemB>initial)\n",
        "  frontierF <- priority queue ordered by fF, with nodeF as an element\n",
        "  frontierB <- priority queue ordered by fB, with nodeB as an element\n",
        "  reachedF <- lookup table, with one key nodeF.STATE and value nodeF\n",
        "  reachedB <- lookup table, with one key nodeB.STATE and value nodeB\n",
        "  solution <- Failure\n",
        "  while not TERMINATED(solution, frontierF, frontierB) do\n",
        "    if fF(TOP(frontierF))<fB(TOP(frontierB)) then\n",
        "      solution <- PROCEED(F, problemF, frontierF, reachedF, reached B, solution)\n",
        "    else solution <- PROCEED(B, problemB, frontierB, reachedB, reached F, solution)\n",
        "  return solution\n",
        "\n",
        "```\n",
        "\\n\n",
        "``` \n",
        "function PROCEED(dir, problem, frontier, reached, reached2, solution) returns a solution\n",
        "  node <- POP(frontier)\n",
        "  for each child in EXPAND(problem,node) do \n",
        "  s <- child.STATE\n",
        "  if s not in reached or PATH-COST(child)<PATH-COST(reached[s]) then\n",
        "    reached[s]<-child\n",
        "    add child to frontier\n",
        "    if s in reached2 then \n",
        "      solution2 <- JOIN-NODES(dir, child, reached2[s])\n",
        "      if PATH-COST(solution2) < PATH-COST(solution) then\n",
        "        solution <- solution2\n",
        "  return solution\n",
        "\n",
        "  ``` \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" A problem-solving agent must planahead.\n",
        "The computational process that it undertakes is called search.\n",
        "It will consider a sequence of actions that form a path to a goal state.\n",
        "Such a sequence is called a solution\n",
        "\n",
        "Defining a search problem:\n",
        "  - states: a set S\n",
        "  - Initial state\n",
        "  - Actions a set A\n",
        "    - the set of actions that can be executed in s, that are applicable in s\n",
        "  - Transition Model\n",
        "  - path cost - must be additive\n",
        "  - goal test\n",
        "    - s is a goal state if Goal(s) is true\n",
        "Decide:\n",
        "  - Which properties matter & how to represent\n",
        "    - Initial State, Goal State, Possible Intermediate States\n",
        "  - Which actions are possible & how to represent\n",
        "    - Operator Set: Actions and Transition Model\n",
        "  - Which action is next\n",
        "    - Path Cost Function\n",
        "State space must be abstracted for problem solving - easier than the real problem\n",
        "\n",
        "Breadth-first-search\n",
        "  - cost optimal for probs where all actions have the same cost\n",
        "  - complete - yes\n",
        "  - optimal - yes\n",
        "  - time O(b^d)\n",
        "  - memory O(b^d)\n",
        "  \n",
        "Unifrom cost search (Dijkstra's algorithm)\n",
        "  - complete - Yes\n",
        "  - cost optimal - Yes\n",
        "  - time O(b^(1 + [c*/e]))\n",
        "  - memory O(b^(1 + [c*/e]))\n",
        "  - uniform-cost search spreads out in waves of uniform path-cost\n",
        "  - when all costs are equal its similar ot breadth first search\n",
        "Depth first search\n",
        "  - complete - No\n",
        "  - optimal - No\n",
        "  - time O(b^m)\n",
        "  - memory O(bm)\n",
        "  - expands the deepest node in the frontier first\n",
        "  - finite spaces\n",
        "    - efficient and complete\n",
        "  - for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory\n",
        "  - backtracking search - depth firstbut they only generate one successor at a time\n",
        "    - memory O(m)\n",
        "Depth limited search\n",
        "  - complete - No\n",
        "  - optimal - No\n",
        "  - time complexity O(b^l)\n",
        "  - space complexity O(bl)\n",
        "  - To keep depth-first search from wandering down an infinite path\n",
        "  - supply a depth limit l\n",
        "  - and treat all nodes at depth l as if they had no successors \n",
        "Iterative deepening search\n",
        "  - complete - yes\n",
        "  - optimal - yes\n",
        "  - time O(b^d) if there is a solution otherwise O(b^m)\n",
        "  - space O(bd) if there is a solution otherwise O(bm)\n",
        "\n",
        "In general, iterative deepening is the preferred uninformed search method when the \n",
        "search state space is larger than can fit in memory and the depth of the solution \n",
        "is not known.\n",
        "\n",
        "Bidirectional search\n",
        "  - complete - yes\n",
        "  - optimal cost - yes\n",
        "  - time O(b^d/2)\n",
        "  - space O(b^d/2)\"\"\"\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",
        " \"unknown environment\": \"the agent can do no better than excecute an action at random\",\n",
        " \"goal formulation\": \"what the agent wants the outcome to be, winning/bucharest/some end state\",\n",
        " \"problem formulation\": \"a description of the states and actions necessary to reach a goal\",\n",
        " \"search\": \"agent simulating sequences of actions until one reaches the goal\",\n",
        " \"solution\": \"sequence of actions that reaches the goal, path to goal\",\n",
        " \"exectution\": \"the agent can now execute the actions in the solution\",\n",
        " \"open loop\": \"once the agent finds a soluton it ignores the percept and executes\",\n",
        " \"closed loop\": \"if the agent needs feedback while executing to gaurantee it reaches the solution\",\n",
        " \"state space\": \"a set of all possible states the problem can be in\",\n",
        " \"transistion model\": \"returns the state that results from doing action a in state s\",\n",
        " \"action cost function\": \"numeric cost of applying action a in state s to reach state s'\",\n",
        " \"path\": \"sequence of actions\",\n",
        " \"optimal solution\": \"solution with the lowest path cost among all solutions\",\n",
        " \"graph\": \"veticies are states and directed edges between them are actions\",\n",
        " \"model\": \"abstract mathematical description\",\n",
        " \"abstraction\": \"removing detail from a representation\",\n",
        " \"level of abstraction\": \"how much detail is needed for a clear problem statements\",\n",
        " \"standardizend problem\": \"illustrates or exercises various problem-solving methods, good benchmark for reshearches to compare\",\n",
        " \"real world problem\": \"solutions are actually useful, formulation is idiosyncratic\",\n",
        " \"grid world\": \"problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell\",\n",
        " \"search algorithm\": \"takes a search problem as an input and returns a solution or failure\",\n",
        " \"frontier\": \"a set of unexpanded nodes\",\n",
        " \"reached\": \"if a node has been expanded\",\n",
        " \"best first search\": \"choose a node n with min val of some evaluation function f(n)\",\n",
        " \"expand a node\": \"by considering the available actions for that state, using transition model\",\n",
        " \"priority queue\": \"pops the node wihtthe minimum cost according to some ecaluation function f\",\n",
        " \"FIFO queue\": \"pops the node that was added to the queue first\",\n",
        " \"LIFO queue\": \"pops the first most recently added node\",\n",
        " \"repeated state\": \"if a node has been visited more than once\",\n",
        " \"redundant path\": \"worse way to get to the same state\",\n",
        " \"graph search\": \"checks for redundant paths\",\n",
        " \"tree-like search\": \"does not check for redundant paths (less memory)\",\n",
        " \"completeness\": \"is the algorithm guaranteed to find a solution when there is one (or report failure)\",\n",
        " \"cost optimality\": \"does it find a solution wiht the lowest path cost of all solutions\",\n",
        " \"time complexity\": \" how long does it take to find a solution\",\n",
        " \"space complexity\": \"how much memory is needed for the search\",\n",
        " \"depth\": \"number of actions in an optimal solution\",\n",
        " \"branching factor\": \"number of successors of a node that need to be consiered\",\n",
        " \"early goal test\": \"checking if a node is a solution as soon as it is generated\",\n",
        " \"late goal test\": \"waiting until a node is popped off the queue\",\n",
        " \"diameter\": \"of a state space graph, gives a good depth limit\",\n",
        " \"search problem\": \"states, actions, performance measure\",\n",
        " \"state\": \"representation of a physical configuration\",\n",
        " \"node\": \"data structure constituting part of a search tree\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "5b528025-08ad-4eb2-c68b-1978cfef2fda"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In this chapter, we consider only the simplest environments: episodic, \nsingle agent, fully observable, deterministic, static, Discrete, known. \nWe distinguish between informed algorithms and uninformed algorithms, and Unknown environments.\n\nAssuming that agents have access to information about the world the agent can follow this\nfour phase problem solving process: goal formulation, problem formulation, search, and execution.\n  - in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\nDefining a problem:\n  - State space\n  - A set of one or more goal states\n  - The actions available to the agent\n  - A transitional model \n  - Action cost function\n\nAbstraction is valid if we can elaborate any abstract solution into a solution in the more \ndetailed world.\n\n\n## AIMA Chapter 3.2 Example Problems\n Real world vs theoretical examples\n\n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithms:\n  - Search tree over the state space graph\n  - Each node corresponds to a state\n  - Expand a node\n  - Generating a new node (child node/successor node)\n  - Each node has a parent node (first step)\n  - Frontier \n    - frontier separates state-space graph: \n      - an interior region where every state has been expanded\n      - exterior region of states that have not yet been reached\n \n``` \nfunction best-first-search(problem,f) returns a solution node or failure\n  node <- NODE(STATE=problem.initial)\n  frontier <- priority queue ordered by f, wiht node as an element\n  reached <- lookup table, wiht one entry wiht key problem.initial and a value node\n  while not is-empty(frontier) do\n    node <- pop(frontier)\n    if problem.is-goal(node.STATE) then return node\n    for each child in EXPAND(problem, node) do\n    s <- child.STATE\n    if s is not in reached or child.PATH-COST < reached[s].PATH-COST then \n      reached[s] <- child\n      add child to frontier\n  return failure\n``` \nnode in the tree represented by\n  - node.state: to which it corresponds\n  - node.parent: the node that generated it\n  - node.action: the action that was applied to the parent's state to get it\n  - node.path-cost: the cost of the path from the inital state to this node\nfrontier: queue of some kinds is appropriate bc the operations on it are:\n  - is-empty: returns true only if there are no nodes in the frontier\n  - pop: removes the top node from the frontier and returns it\n  - top: returns but does not remove the top node of the fronier\n  - add: inserts node into its proper place in the queue\nqueues:\n  - priority queue\n  - fifo queue\n  - lifo queue (stack)\nevaluate an algorithms performance:\n  - completeness\n  - cost optimality\n  - time complexity\n  - space complexity\nTo be complete a search algorithm must be systematic in the way it explores an infinite state\nState space complexity can be measured in terms of d the depth and m the maximum number\nof actions in any bath; and b the branching factor\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth-first-search\n``` \nfunction breadth-first-search(problem) returns a solution node or failure\n  node <- NODE(problem.INITIAL)\n  if problem.IS-GOAL(node.STATE) then return node\n  frontier <- a FIFO queue, with node as an element\n  reached <- {problem.INITIAL}\n  while not IS_EMPTY(frontier) do \n    node <- POP(frontier)\n    for each child in EXPAND(problem, node) do\n    s <- child.STATE\n    if problem.IS-GOAL(s) then return child\n    if s is not in reached then \n      add s to reached\n      add child to frontier\n    return failure\n    \n``` \n\n\n``` \nfunction uniform-cost-search(problem) returns a solution node, or failure\n  return best-first-search(problem, path-cost)\n\n``` \n\n\n``` \nfunction iterativ-deepening-search(problem) returns a solution node or failure\n  for depth = 0 to inf fo\n  result <- depth-limited-search(problem, depth)\n  if result != cutoof then return result\n\n``` \n\n\n``` \nfunction depth-limited-search(problem, l) returns a node or failure or cutoff\n  froniter <- a LIFO queue (stack) with Node(problem.INITIAL) as an element\n  result <- failure\n  while not IS-EMPTY(frontier) do\n    node <- POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    if DEPTH(node) > l then \n      result <- cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do\n        add child to frontier\n  return result\n\n``` \n\n\n\n``` \nfunction BIBF-Search(problemF,fF, problemB, fB) returns a solution node or failure\n  nodeF <-(problemF>initial)\n  nodeB <-(problemB>initial)\n  frontierF <- priority queue ordered by fF, with nodeF as an element\n  frontierB <- priority queue ordered by fB, with nodeB as an element\n  reachedF <- lookup table, with one key nodeF.STATE and value nodeF\n  reachedB <- lookup table, with one key nodeB.STATE and value nodeB\n  solution <- Failure\n  while not TERMINATED(solution, frontierF, frontierB) do\n    if fF(TOP(frontierF))<fB(TOP(frontierB)) then\n      solution <- PROCEED(F, problemF, frontierF, reachedF, reached B, solution)\n    else solution <- PROCEED(B, problemB, frontierB, reachedB, reached F, solution)\n  return solution\n\n```\n\n\n``` \nfunction PROCEED(dir, problem, frontier, reached, reached2, solution) returns a solution\n  node <- POP(frontier)\n  for each child in EXPAND(problem,node) do \n  s <- child.STATE\n  if s not in reached or PATH-COST(child)<PATH-COST(reached[s]) then\n    reached[s]<-child\n    add child to frontier\n    if s in reached2 then \n      solution2 <- JOIN-NODES(dir, child, reached2[s])\n      if PATH-COST(solution2) < PATH-COST(solution) then\n        solution <- solution2\n  return solution\n\n  ``` \n\n\n## Module 3 Lecture Notes\n A problem-solving agent must planahead.\nThe computational process that it undertakes is called search.\nIt will consider a sequence of actions that form a path to a goal state.\nSuch a sequence is called a solution\n\nDefining a search problem:\n  - states: a set S\n  - Initial state\n  - Actions a set A\n    - the set of actions that can be executed in s, that are applicable in s\n  - Transition Model\n  - path cost - must be additive\n  - goal test\n    - s is a goal state if Goal(s) is true\nDecide:\n  - Which properties matter & how to represent\n    - Initial State, Goal State, Possible Intermediate States\n  - Which actions are possible & how to represent\n    - Operator Set: Actions and Transition Model\n  - Which action is next\n    - Path Cost Function\nState space must be abstracted for problem solving - easier than the real problem\n\nBreadth-first-search\n  - cost optimal for probs where all actions have the same cost\n  - complete - yes\n  - optimal - yes\n  - time O(b^d)\n  - memory O(b^d)\n  \nUnifrom cost search (Dijkstra's algorithm)\n  - complete - Yes\n  - cost optimal - Yes\n  - time O(b^(1 + [c*/e]))\n  - memory O(b^(1 + [c*/e]))\n  - uniform-cost search spreads out in waves of uniform path-cost\n  - when all costs are equal its similar ot breadth first search\nDepth first search\n  - complete - No\n  - optimal - No\n  - time O(b^m)\n  - memory O(bm)\n  - expands the deepest node in the frontier first\n  - finite spaces\n    - efficient and complete\n  - for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory\n  - backtracking search - depth firstbut they only generate one successor at a time\n    - memory O(m)\nDepth limited search\n  - complete - No\n  - optimal - No\n  - time complexity O(b^l)\n  - space complexity O(bl)\n  - To keep depth-first search from wandering down an infinite path\n  - supply a depth limit l\n  - and treat all nodes at depth l as if they had no successors \nIterative deepening search\n  - complete - yes\n  - optimal - yes\n  - time O(b^d) if there is a solution otherwise O(b^m)\n  - space O(bd) if there is a solution otherwise O(bm)\n\nIn general, iterative deepening is the preferred uninformed search method when the \nsearch state space is larger than can fit in memory and the depth of the solution \nis not known.\n\nBidirectional search\n  - complete - yes\n  - optimal cost - yes\n  - time O(b^d/2)\n  - space O(b^d/2)\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Unknown environment** - the agent can do no better than excecute an action at random\n* **Goal formulation** - what the agent wants the outcome to be, winning/bucharest/some end state\n* **Problem formulation** - a description of the states and actions necessary to reach a goal\n* **Search** - agent simulating sequences of actions until one reaches the goal\n* **Solution** - sequence of actions that reaches the goal, path to goal\n* **Exectution** - the agent can now execute the actions in the solution\n* **Open loop** - once the agent finds a soluton it ignores the percept and executes\n* **Closed loop** - if the agent needs feedback while executing to gaurantee it reaches the solution\n* **State space** - a set of all possible states the problem can be in\n* **Transistion model** - returns the state that results from doing action a in state s\n* **Action cost function** - numeric cost of applying action a in state s to reach state s'\n* **Path** - sequence of actions\n* **Optimal solution** - solution with the lowest path cost among all solutions\n* **Graph** - veticies are states and directed edges between them are actions\n* **Model** - abstract mathematical description\n* **Abstraction** - removing detail from a representation\n* **Level of abstraction** - how much detail is needed for a clear problem statements\n* **Standardizend problem** - illustrates or exercises various problem-solving methods, good benchmark for reshearches to compare\n* **Real world problem** - solutions are actually useful, formulation is idiosyncratic\n* **Grid world** - problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell\n* **Search algorithm** - takes a search problem as an input and returns a solution or failure\n* **Frontier** - a set of unexpanded nodes\n* **Reached** - if a node has been expanded\n* **Best first search** - choose a node n with min val of some evaluation function f(n)\n* **Expand a node** - by considering the available actions for that state, using transition model\n* **Priority queue** - pops the node wihtthe minimum cost according to some ecaluation function f\n* **Fifo queue** - pops the node that was added to the queue first\n* **Lifo queue** - pops the first most recently added node\n* **Repeated state** - if a node has been visited more than once\n* **Redundant path** - worse way to get to the same state\n* **Graph search** - checks for redundant paths\n* **Tree-like search** - does not check for redundant paths (less memory)\n* **Completeness** - is the algorithm guaranteed to find a solution when there is one (or report failure)\n* **Cost optimality** - does it find a solution wiht the lowest path cost of all solutions\n* **Time complexity** -  how long does it take to find a solution\n* **Space complexity** - how much memory is needed for the search\n* **Depth** - number of actions in an optimal solution\n* **Branching factor** - number of successors of a node that need to be consiered\n* **Early goal test** - checking if a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue\n* **Diameter** - of a state space graph, gives a good depth limit\n* **Search problem** - states, actions, performance measure\n* **State** - representation of a physical configuration\n* **Node** - data structure constituting part of a search tree\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed (Heuristic) search strategies - use domain specific hits about the location of goals.\n",
        "h(n) = cheapest path\n",
        "Greedy best first search\n",
        "  - Expands first the node with the lowest h(n) value \n",
        "  - Appears to be closest to the goal\n",
        "  - Complete in finite state spaces but not in infinite ones\n",
        "A* search \n",
        "  - f(n) = g(n) + h(n)\n",
        "    - g(n) path cost from the initial state to node \n",
        "    - h(n) estimated cost of the shortest path from curr to a goal state\n",
        "  - complete\n",
        "  - if cost-optimal depends on certain properties of the heuristic. \n",
        "    - admissibility\n",
        "    - A slightly stronger property is called consistency\n",
        "  - A* with a consistent heuristic is optimally efficient\n",
        "  - A* is efficient because it prunes\n",
        "  - if inadmissible heuristic (may overestimate) then we risk missing the optimal solution\n",
        "    - the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded\n",
        "bounded suboptimal search - solution that is guaranteed to be within a constant factor of the optimal cost. \n",
        "  - Weighted A* provides this guarantee\n",
        "unbounded-cost search - as long as we can find it quickly.\n",
        "speedy search, which is a version of greedy best-first search that uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions. \n",
        "Memory bounded search\n",
        "  - Memory is split between the frontier and the reached states\n",
        "  - Some only keep one of the two places\n",
        "  - Or remove from reached when we can prove that they are no longer needed\n",
        "iterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: \n",
        "  - IDA* 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. \n",
        "Recursive best-first search\n",
        "  - Standard best first search but using only linear space\n",
        "    - Recursive depth-first search with a f_limit\n",
        "MA* (memory-bounded A*) and SMA* (simplified MA*). \n",
        "  - SMA* proceeds just like A*, expanding the best leaf until memory is full. At \n",
        "  this point, it cannot add a new node to the search tree without dropping an old one.\n",
        "  always drops the worst leaf node—the one with the highest -value.\n",
        "  Like RBFS, SMA* then backs up the value of the forgotten node to its parent.\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" Tile puzzle\n",
        "  - H1 = the number of misplaced tiles (not including blank)\n",
        "  - H2 = the sum of the distance of the tiles from their goal positions\n",
        "Effective branching factor b*\n",
        "  - N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\n",
        "better way to characterize the effect of A* pruning with a given heuristic  is that it reduces the effective depth by a constant compared to the true depth\n",
        "A problem with fewer restrictions on the actions is called a relaxed problem.\n",
        "Composite heuristic picks which func is most accurate on the node in question\n",
        "Subproblems \n",
        "  - Pattern databases store the solution cost for each possible sub problem\n",
        "  - with each additional database there are diminishing returns and increased memory \n",
        "  and computation costs.\n",
        "  - the sum of the two costs is still a lower bound on the cost of solving the entire problem\n",
        "could generate a perfect heuristic by precomputing and storing the cost of the optimal \n",
        "path between every pair of vertices\n",
        "  - O(|V|^2) and O(|E|^3)\n",
        " better approach is to choose a few (perhaps 10 or 20) landmark points16 from the vertices. Then for each landmark  and for each other vertex  in the graph, we compute and store C*(v,L)\n",
        "shortcuts—artificial edges in the graph that define an optimal multi-action path.\n",
        "\n",
        "Each state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\n",
        "each state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\n",
        "For harder problems, there will be many such missteps, and a metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtrees.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" uniform cost search\n",
        "  - expand node wiht lowest path cost\n",
        "  - forntier = priority queue orderded by g(n) \n",
        "``` \n",
        "function greedy best-first search\n",
        "  frontier = PriotityQueue()\n",
        "  frontier.put(state, 0)\n",
        "  came_from = {}\n",
        "  came_from[start] = NONE\n",
        "\n",
        "  while not frontier.empty\n",
        "    current = frontier.get()\n",
        "    if current == goal \n",
        "      break\n",
        "    for next in graph.neighbors(current):\n",
        "      if next not in came_from:\n",
        "        priority = heuristic(goal, next)\n",
        "        frontier.put(next, priority)\n",
        "        came_from[next] = current\n",
        "```\n",
        "```\n",
        "function A*\n",
        "  frontier = Queue()\n",
        "  frontier.put(start )\n",
        "  reached = set()\n",
        "  reached.add(start)\n",
        "\n",
        "  while not frontier.empty():\n",
        "    current = frontier.get()\n",
        "    for next in graph.neighbors(current):\n",
        "        if next not in reached:\n",
        "          frontier.put(next)\n",
        "          reached.add(next) \n",
        "```\n",
        "``` \n",
        "function recursive-best-first-search(problem) returns a solution or faukure\n",
        "  solution, fvalue <- RBFS(problem, NODE(problem.INITIAL), infinity)\n",
        "return solution\n",
        "``` \n",
        "``` \n",
        "function RBFS(problem, node, f_limit) returns a solution or faulure and a new f-cost limit\n",
        "  if problem.IS-GOal(node.STATE) then return node\n",
        "  successors <- list(EXPAND(node))\n",
        "  if successors is empty then return failure, infinity\n",
        "  for each s in successors do\n",
        "    s,f <- max(s.PATH-COST + h(s), node.f)\n",
        "  while true do\n",
        "    best <- the node in successors with lowest f-value\n",
        "    if best.f > f_limit then return failure, best.f\n",
        "    alternative <- the second lowest f-value among successors\n",
        "    result, best.f <- RBFS(problem, best, min(f_limit, alternative))\n",
        "    if result != failure then return result, best.f\n",
        "``` \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed (heuristic) search strategies\": \"uses domain- specific hints about the loc of goals\",\n",
        "\"heuristic\": \"cost of the cheapest path from the state at node n to a goal\",\n",
        "\"straight line distance heuristic\": \"correlated with actual road distances\",\n",
        "\"admissible heruistic\": \"one that never overestimates the cost to reach a goal, optimistic!\",\n",
        "\"consistency\": \"h(n) is consistent if for every node n and successor n' we have h(n) <= c(n, a, n') + h(n')\",\n",
        "\"triangle inewuality\": \"sides of a triangle cant be longer than the sum of the other 2 sides\",\n",
        "\"contours\": \"ranges where the maps all have the same f(n), order to be expanded\",\n",
        "\"monotonic\": \"the path cost always increases as you go along a path, because action costs are always positive\",\n",
        "\"surely expanded nodes\": \"all nodes that can be reached from the inital state where f(n) < C*\",\n",
        "\"optimally efficient\": \"algorithms that extends search paths from the initial state, with h(n), expands all nodes that are surely expanded by A*\",\n",
        "\"prunes\": \"eliminates possibilites from consideration without having to examine them\",\n",
        "\"satisficing\": \"solutions that are suboptimal but good enough\",\n",
        "\"detour index\": \"multiplier applied to the straight line distance to account for curving roads\",\n",
        "\"weighted A* search\": \"weight the heuristic value mroe heavilyf(n) + W x h(n)\",\n",
        "\"bounded suboptimal search\": \"find a solution that is guaranteed to be within a constant factor  of the optimal cost (Weighted A*)\",\n",
        "\"bounded cost search\": \"solution whose cost is less than some constant \",\n",
        "\"unbounded-cost search\": \"accept a solution of any cost\",\n",
        "\"speedy search\": \"heuristic is the num actions required to reach a goal regardless of theri cost\",\n",
        "\"refrence counts\": \"track the num times a state has been reached -> remove it when out of ways to reach it\",\n",
        "\"beam search\": \"limits the size of the frontier, keep only the k nodes with teh best f-scores\",\n",
        "\"Iterative - deepening A* search\": \"all the benefits of A* without the requirement to keep all reached states in memory\",\n",
        "\"recursive best-first search\": \"mimic the operation of standard bes-first search but using linear space\",\n",
        "\"backed up value\": \"best value of its children\",\n",
        "\"front-to-end search\": \"hF estimates the distance to the goal and hB estimates distance to start\",\n",
        "\"front-to-front\": \"estimates the distance to the other fronier\",\n",
        "\"manhattan distance\": \"city block distance, sum of horizontal and vertical distances\",\n",
        "\"effective branching factor b*\": \"nodes N,depth is d then b* is the branching factor to have N + 1 nodes\",\n",
        "\"effective depth\": \"reduce the search cost\",\n",
        "\"dominates\": \"if one heruistic expands more valid nodes than another\",\n",
        "\"relaxed problem\": \"fewer restrictions of the actions\",\n",
        "\"pattern databases\": \"store solutions for possible subproblems \",\n",
        "\"disjoint pattern databases\": \"dont record the total cost but the number of moves\",\n",
        "\"precomputation\": \"generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices\",\n",
        "\"shortcuts\": \"artificial edges in teh fraph that define and optimal multi-action path\",\n",
        "\"differential heuristic\": \"hDH(n) = max |C*(n,L)-C*(goal,L)|\",\n",
        "\"metalevel state space\": \"captures the internal (computational) state of a program that is searching\",\n",
        "\"object level state space\": \"state of a program\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4ee40c10-d721-4855-e91d-86825e16521c"
      },
      "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\", module3_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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) search strategies - use domain specific hits about the location of goals.\nh(n) = cheapest path\nGreedy best first search\n  - Expands first the node with the lowest h(n) value \n  - Appears to be closest to the goal\n  - Complete in finite state spaces but not in infinite ones\nA* search \n  - f(n) = g(n) + h(n)\n    - g(n) path cost from the initial state to node \n    - h(n) estimated cost of the shortest path from curr to a goal state\n  - complete\n  - if cost-optimal depends on certain properties of the heuristic. \n    - admissibility\n    - A slightly stronger property is called consistency\n  - A* with a consistent heuristic is optimally efficient\n  - A* is efficient because it prunes\n  - if inadmissible heuristic (may overestimate) then we risk missing the optimal solution\n    - the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded\nbounded suboptimal search - solution that is guaranteed to be within a constant factor of the optimal cost. \n  - Weighted A* provides this guarantee\nunbounded-cost search - as long as we can find it quickly.\nspeedy search, which is a version of greedy best-first search that uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions. \nMemory bounded search\n  - Memory is split between the frontier and the reached states\n  - Some only keep one of the two places\n  - Or remove from reached when we can prove that they are no longer needed\niterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: \n  - IDA* 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. \nRecursive best-first search\n  - Standard best first search but using only linear space\n    - Recursive depth-first search with a f_limit\nMA* (memory-bounded A*) and SMA* (simplified MA*). \n  - SMA* proceeds just like A*, expanding the best leaf until memory is full. At \n  this point, it cannot add a new node to the search tree without dropping an old one.\n  always drops the worst leaf node—the one with the highest -value.\n  Like RBFS, SMA* then backs up the value of the forgotten node to its parent.\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Tile puzzle\n  - H1 = the number of misplaced tiles (not including blank)\n  - H2 = the sum of the distance of the tiles from their goal positions\nEffective branching factor b*\n  - N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\nbetter way to characterize the effect of A* pruning with a given heuristic  is that it reduces the effective depth by a constant compared to the true depth\nA problem with fewer restrictions on the actions is called a relaxed problem.\nComposite heuristic picks which func is most accurate on the node in question\nSubproblems \n  - Pattern databases store the solution cost for each possible sub problem\n  - with each additional database there are diminishing returns and increased memory \n  and computation costs.\n  - the sum of the two costs is still a lower bound on the cost of solving the entire problem\ncould generate a perfect heuristic by precomputing and storing the cost of the optimal \npath between every pair of vertices\n  - O(|V|^2) and O(|E|^3)\n better approach is to choose a few (perhaps 10 or 20) landmark points16 from the vertices. Then for each landmark  and for each other vertex  in the graph, we compute and store C*(v,L)\nshortcuts—artificial edges in the graph that define an optimal multi-action path.\n\nEach state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\neach state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\nFor harder problems, there will be many such missteps, and a metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtrees.\n\n \n\n## Module 4 Lecture Notes\n A problem-solving agent must planahead.\nThe computational process that it undertakes is called search.\nIt will consider a sequence of actions that form a path to a goal state.\nSuch a sequence is called a solution\n\nDefining a search problem:\n  - states: a set S\n  - Initial state\n  - Actions a set A\n    - the set of actions that can be executed in s, that are applicable in s\n  - Transition Model\n  - path cost - must be additive\n  - goal test\n    - s is a goal state if Goal(s) is true\nDecide:\n  - Which properties matter & how to represent\n    - Initial State, Goal State, Possible Intermediate States\n  - Which actions are possible & how to represent\n    - Operator Set: Actions and Transition Model\n  - Which action is next\n    - Path Cost Function\nState space must be abstracted for problem solving - easier than the real problem\n\nBreadth-first-search\n  - cost optimal for probs where all actions have the same cost\n  - complete - yes\n  - optimal - yes\n  - time O(b^d)\n  - memory O(b^d)\n  \nUnifrom cost search (Dijkstra's algorithm)\n  - complete - Yes\n  - cost optimal - Yes\n  - time O(b^(1 + [c*/e]))\n  - memory O(b^(1 + [c*/e]))\n  - uniform-cost search spreads out in waves of uniform path-cost\n  - when all costs are equal its similar ot breadth first search\nDepth first search\n  - complete - No\n  - optimal - No\n  - time O(b^m)\n  - memory O(bm)\n  - expands the deepest node in the frontier first\n  - finite spaces\n    - efficient and complete\n  - for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory\n  - backtracking search - depth firstbut they only generate one successor at a time\n    - memory O(m)\nDepth limited search\n  - complete - No\n  - optimal - No\n  - time complexity O(b^l)\n  - space complexity O(bl)\n  - To keep depth-first search from wandering down an infinite path\n  - supply a depth limit l\n  - and treat all nodes at depth l as if they had no successors \nIterative deepening search\n  - complete - yes\n  - optimal - yes\n  - time O(b^d) if there is a solution otherwise O(b^m)\n  - space O(bd) if there is a solution otherwise O(bm)\n\nIn general, iterative deepening is the preferred uninformed search method when the \nsearch state space is larger than can fit in memory and the depth of the solution \nis not known.\n\nBidirectional search\n  - complete - yes\n  - optimal cost - yes\n  - time O(b^d/2)\n  - space O(b^d/2)\n\n## Module 4 Definitions\n* **Informed (heuristic) search strategies** - uses domain- specific hints about the loc of goals\n* **Heuristic** - cost of the cheapest path from the state at node n to a goal\n* **Straight line distance heuristic** - correlated with actual road distances\n* **Admissible heruistic** - one that never overestimates the cost to reach a goal, optimistic!\n* **Consistency** - h(n) is consistent if for every node n and successor n' we have h(n) <= c(n, a, n') + h(n')\n* **Triangle inewuality** - sides of a triangle cant be longer than the sum of the other 2 sides\n* **Contours** - ranges where the maps all have the same f(n), order to be expanded\n* **Monotonic** - the path cost always increases as you go along a path, because action costs are always positive\n* **Surely expanded nodes** - all nodes that can be reached from the inital state where f(n) < C*\n* **Optimally efficient** - algorithms that extends search paths from the initial state, with h(n), expands all nodes that are surely expanded by A*\n* **Prunes** - eliminates possibilites from consideration without having to examine them\n* **Satisficing** - solutions that are suboptimal but good enough\n* **Detour index** - multiplier applied to the straight line distance to account for curving roads\n* **Weighted a* search** - weight the heuristic value mroe heavilyf(n) + W x h(n)\n* **Bounded suboptimal search** - find a solution that is guaranteed to be within a constant factor  of the optimal cost (Weighted A*)\n* **Bounded cost search** - solution whose cost is less than some constant \n* **Unbounded-cost search** - accept a solution of any cost\n* **Speedy search** - heuristic is the num actions required to reach a goal regardless of theri cost\n* **Refrence counts** - track the num times a state has been reached -> remove it when out of ways to reach it\n* **Beam search** - limits the size of the frontier, keep only the k nodes with teh best f-scores\n* **Iterative - deepening a* search** - all the benefits of A* without the requirement to keep all reached states in memory\n* **Recursive best-first search** - mimic the operation of standard bes-first search but using linear space\n* **Backed up value** - best value of its children\n* **Front-to-end search** - hF estimates the distance to the goal and hB estimates distance to start\n* **Front-to-front** - estimates the distance to the other fronier\n* **Manhattan distance** - city block distance, sum of horizontal and vertical distances\n* **Effective branching factor b*** - nodes N,depth is d then b* is the branching factor to have N + 1 nodes\n* **Effective depth** - reduce the search cost\n* **Dominates** - if one heruistic expands more valid nodes than another\n* **Relaxed problem** - fewer restrictions of the actions\n* **Pattern databases** - store solutions for possible subproblems \n* **Disjoint pattern databases** - dont record the total cost but the number of moves\n* **Precomputation** - generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices\n* **Shortcuts** - artificial edges in teh fraph that define and optimal multi-action path\n* **Differential heuristic** - hDH(n) = max |C*(n,L)-C*(goal,L)|\n* **Metalevel state space** - captures the internal (computational) state of a program that is searching\n* **Object level state space** - state of a program\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Three stances to take towards multi-agetn environments:\n",
        "  - consider them like in the aggregate as an economy \n",
        "  - consider them as just a part of the environment- part that makes it nondeterministic\n",
        "  - explicitly model the adversarial agetns with techniques of adversarial game-tree search\n",
        "every time we stop searching we ask who is winning\n",
        "  - evaluation function\n",
        "  - average the outcomes of many fast simulations of the game to the end\n",
        "Game can be formally defined with:\n",
        "  - S0 - the initial state\n",
        "  - TO-MOVE(s) - the player who's turn it is to move in the state s\n",
        "  - ACTIONS(s) the set of legal moves in s\n",
        "  - RESULT(s,a) the transistion model\n",
        "  - IS-TERMINAL(s) - terminal test\n",
        "  - UTILITY(s,p) - utility function\n",
        "State space graph is defined by:\n",
        "  - initial state\n",
        "  - actions function\n",
        "  - result function  \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" minimax search\n",
        "  - for games with multiple outcome scores - more general algorithm \n",
        "  - Max prefers to move to a state of maximum value when it is Max’s turn to move, \n",
        "  and Min prefers a state of minimum value (that is, minimum value for Max and thus \n",
        "  maximum value for Min)\n",
        "  - time complexity is O(b^m)\n",
        "  - space complexity\n",
        "    - all actions at once O(bm)\n",
        "    - one action at a time O(m)\n",
        "Humans make alliances in Games\n",
        "  - how can a computer mimic this? \n",
        "\n",
        "minimax: \n",
        "```\n",
        "function minimax-search(game,state) returns an action\n",
        "  player <- game.TO-MOVE(state)\n",
        "  value, move <-MAX-VALUE(game,state)\n",
        "  return move\n",
        "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        " if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v <- -infinity\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 > v then\n",
        "      v, move <- v2, a\n",
        "  return v, move\n",
        "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        " if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v <- +infinity\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 < v then\n",
        "      v, move <- v2, a\n",
        "  return v, move\n",
        "```\n",
        "Alpha Beta Pruning\n",
        "  - Num game states is exponential in the depth of the tree\n",
        "  - Can immediately prune large states of the tree\n",
        "  - the value of the root/the minimax decision are independent of the values of the leaves  and , therefore they can be pruned.\n",
        "\n",
        "\n",
        "```\n",
        "function alpha-beta-search(game,state, alpha, beta) returns an action\n",
        "  player <- game.TO-MOVE(state)\n",
        "  value, move <- MAX-VALUE(game,state, -inf, +inf)\n",
        "  return move\n",
        "function MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
        " if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v <- -infinity\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n",
        "    if v2 > v then\n",
        "      v, move <- v2, a\n",
        "      alpha <- MAX(alpha, v)\n",
        "    if v >= betha then return v, move\n",
        "  return v, move\n",
        "function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
        " if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v <- +infinity\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a), alpha, beta)\n",
        "    if v2 < v then\n",
        "      v, move <- v2, a\n",
        "      beta <- MIN(beta, v)\n",
        "    if v <= alpha then return v,move\n",
        "  return v, move\n",
        "```\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "Apply a heuristic evaluation funcion states  \n",
        "  - effectively treating them as if they were terminal \n",
        "Replace the terminal test by a cutoff test\n",
        "Heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p \n",
        "The evaluation function does not know which states are which, but it can return a single value that estimates the proportion of states with each outcome. \n",
        "Material value for each piece (ie chess) \n",
        "Weighted linear function  \n",
        "Current depth must be increment in each recursive call \n",
        "  - The most straightforward approach to controlling the amount of search is to set a fixed depth limit so that Is-Cutoff(state, depth) returns true for all depth greater than some fixed depth d \n",
        "The evaluation function should be applied only to positions that are quiescent \n",
        "  - For nonquiescent positions the Is-Cutoff returns false, and the search continues until quiescent positions are reached.  \n",
        "  - This extra quiescence search is sometimes restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position. \n",
        "The horizon effect is more difficult to eliminate. and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics. \n",
        "  - To mitigate the horizon effect, allow singular extensions moves that are “clearly better” than all other moves, even when the search would normally be cut off at that point \n",
        "Forward pruning- prunes moves that appear to be poor moves \n",
        "Beam search - on each ply consider only a beam of the best n moves \n",
        "Probcut algorithm is a froward pruning version that uses statistics gained from prior experience \n",
        "Late move reduction \n",
        "  - assumes move ordering has been done and therefore moves appear later in the list of possible moves \n",
        "Table lookup is usually faster than searching from the start \n",
        "A computer can completely solve the endgame by producing a policy \n",
        "Then the computer can play perfectly by looking up the right move in this table. The table is constructed by retrograde minimax search: \n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Stochastic Games \n",
        "  - incorporate random elements (such as rolling dice) \n",
        "  - Add a chance node in addition to max and min \n",
        "  - Positions no longer have a definite minimax value \n",
        "    - we can only calculate the expected value of the position \n",
        "  - expectiminimax value for games with chance nodes \n",
        "    - a generalization of the minimax value for deterministic games. \n",
        "    - Terminal nodes and max and min nodes work exactly the same way as before\n",
        "    (with the caveat that the legal moves for max and min will depend on the outcome\n",
        "    of the dice roll in the previous chance node).\n",
        "  - Evaluation functions have to be much more careful about which moves to choose \n",
        "    - They must be positive linear transformation of the probability of winning \n",
        "    - Takes (O(b^m*n^m) where n is the number of distinct rolls \n",
        "    - In games where the branching factor for chance nodes is high—consider a game like Yahtzee where you roll 5 dice on every turn—you may want to consider forward pruning that samples a smaller number of the possible chance branches. Or you may want to avoid using an evaluation function altogether, and opt for Monte Carlo tree search instead, where each playout includes random dice rolls. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "- Agent has to make a decision, it has actions a. If there are uncertainties about the current state we will assume probability P(s) is applied to each state s. Transition model P(s’|s,a). \n",
        "  - The probability that action a in state s reaches state s’ \n",
        "- Decision theory deals with choosing actions base on the desirability of their immediate outcomes \n",
        "  - The agents preferences are captured by a utility function which assigns a single number to express the desirability of a state. \n",
        "  - Expected utility is the average utility value of the outcomes weighted by the probability that they occur \n",
        "  - The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" Any reasonable preference must obey \n",
        "  - ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding. \n",
        "  - TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C \n",
        "  - CONTINUITY: if some lotteryB is between A and C in preference then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 - p \n",
        "  - SUBSTITUTABILITY: If an agent is indifferent between two lotteries  A and B, then the agent is indifferent between two more complex lotteries that are the same except that  B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries. \n",
        "  - ONOTONICITY: Suppose two lotteries have the same two possible outcomes, A  and B. If an agent prefers A to B,  then the agent must prefer the lottery that has a higher probability for  A and vice versa). \n",
        "  - DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule:  \n",
        "IF THE AGENTS PREFERENCES THE AXIOMS OF UTILITY THERE IS A FUNCTION:\n",
        "  - U(A)>U(B) adn U(A)+U(B) \n",
        "  - As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "- preference elicitation, involves presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n",
        "- Normalized utilities use a scale with u T perp (best option) = 1 and u other perp = 0 worst option \n",
        "​​  - we can assess the utility of any particular prize  by asking the agent to choose between  and a standard lottery \n",
        "- Although nobody feels comfortable with putting a value on human life, it is a fact that tradeoffs on matters of life and death are made all the time. \n",
        "  - Paradoxically, a refusal to put a monetary value on life can mean that life is undervalued \n",
        "- humans prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.  \n",
        "  - in the “desperate” region at large negative wealth the behavior is risk-seeking.  \n",
        "- The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. \n",
        "- This calculation is a special case of computing an order statistic, the distribution of any particular ranked element of a sample \n",
        "- optimizer’s curse (Smith and Winkler, 2006). It afflicts even the most seasoned decision analysts and statisticians. Serious manifestations include believing that an exciting new drug that has cured 80% of patients in a trial will cure 80% of patients (it’s been chosen from  thousands of candidate drugs) \n",
        "- Decision theory is a normative theory: it describes how a rational agent should act. \n",
        "- A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act.  \n",
        "- Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect. Experiments show that people like a medical procedure that is described as having a “90% survival rate” about twice as much as one described as having a “10% death rate,” \n",
        "- Anchoring effect - People feel more comfortable making relative utility judgments rather than absolute ones. \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Games \n",
        "  - simplest game environment - multiagent, static, discrete, fullyy observable, strategic \n",
        "  - general scheme  \n",
        "    1. Consider all legal successors to the current state (‘board position’) \n",
        "    2. Evaluate each successor board position \n",
        "    3. Pick the move which leads to the best board position. \n",
        "    4. After your opponent moves, repeat. \n",
        "  - design issues \n",
        "    - representing board \n",
        "    - representing legal next moves \n",
        "    - evaluating positions \n",
        "    - looking ahead \n",
        "  - evaluation function f(n) \n",
        "    - Evaluates how good a ‘board position’ is \n",
        "    -Based on static features of that board alone \n",
        "    - Zero-sum assumption lets us use one function to describe goodness for both players. \n",
        "      - f(n)>0 if MAX is winning in position n \n",
        "      - f(n)=0 if position n is tied \n",
        "      - f(n)<0 if MIN is winning in position n \n",
        "    - Build using expert knowledge  \n",
        "  - Definition of optimal play for MAX assumes MIN plays optimally: \n",
        "    - if MIN does not play optimally MAX will do even better \n",
        "  - alpha beta pruning \n",
        "    - alpha:  MAX’s current lower bound on MAX’s outcome  \n",
        "      - MAX will never allow a move that could lead to a worse score (for MAX) than α  \n",
        "    - beta:  MIN’s current upper bound on MIN’s outcome  \n",
        "      - MIN will never allow a move that could lead to a better score (for MAX) than β \n",
        "Expectimax and Utilities \n",
        "  - Expectimax search: compute the average score under optimal \n",
        "    - playMax nodes as in minimax search \n",
        "    - Chance nodes are like min nodes but the outcome is uncertain  \n",
        "    - Calculate their expected utilities \n",
        "      - I.e. take weighted average (expectation) of children  \n",
        "\n",
        "```\n",
        "def exp-value(state):\n",
        "  initialize v = 0\n",
        "  for each successor of state:\n",
        "    p = probability(successor)\n",
        "    v += p * value(successor)\n",
        "  return v\n",
        "```\n",
        "\n",
        "Probabilities \n",
        "  - A random variable represents an event whose outcome is unknown \n",
        "  - A probability distribution is an assignment of weights to outcomes \n",
        "  - For now, assume each chance node magically comes along with probabilities that\n",
        "   specify the distribution over its outcomes  \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"economy\": \"predict that increasing demand will raise prices, without predicting agent actions\",\n",
        "\"evaluation function\": \"asks who is willing based on features of the state\",\n",
        "\"imperfect information\": \"games with an element of chance\",\n",
        "\"perfect information\": \"fully observable\",\n",
        "\"zero-sum games\": \"what is good for one player is just as bad for the other\",\n",
        "\"move\": \"action\",\n",
        "\"position\": \"state\",\n",
        "\"terminal test\": \"true when the game is voer\",\n",
        "\"terminal states\": \"states where the game has ended\",\n",
        "\"transition model\": \"defines the state resulting from taking action a in state s\",\n",
        "\"utility function\": \"defines teh numeric valute ot player p when the game ends in terminal state s\",\n",
        "\"state space graph\": \"verticies are states, edges are moves, state might be reached by multiple paths\",\n",
        "\"game tree\": \"search tree that follows every sequence of moves to the termial state\",\n",
        "\"ply\": \"one move by one player\",\n",
        "\"minimax value\": \"utility (for MAX) being in that state, assuming both players play optimally\",\n",
        "\"minimax decisison\": \"the action a that is the optimal choice for MAX because it leads to the highest minimax value\",\n",
        "\"backs up\": \"goes all the way down the leaves of the tree then goes up as recursion unwinds\",\n",
        "\"alliance\": \"made and broke as the game goes along\",\n",
        "\"alpha-beta pruning\": \"prunes subtrees\",\n",
        "\"iterative deepening\": \"search one ply at a time\",\n",
        "\"killer moves\": \"best moves\",\n",
        "\"transpositions\": \"diff permutations of the move sequence that end up in the same position\",\n",
        "\"transposition table\": \"catches the heuristic value of states\",\n",
        "\"type A strategy\": \"all possible moves to a depth and uses h(n) to estimate expected utility\",\n",
        "\"type B strategy\": \"ignores moves that look bad, follows promising lines as far as possible\",\n",
        "\"evaluation function\": \"treating nonterminal nodes as if they were terminal\",\n",
        "\"cutoff test\": \"returns true for terminal states\",\n",
        "\"features\": \"define categories or equivalence classes of states\",\n",
        "\"expected value\": \"determined fro each catefory of states resulting in an eval func that works for any state\",\n",
        "\"material value\": \"val for a piece (ie king is 10 etc\",\n",
        "\"weighted linear function\": \"evlauation function using the material values of pieces\",\n",
        "\"quiescent\": \"a postion where no possible move would swing the game\",\n",
        "\"quiescence search\": \"restricted to consider the moves that will resolve unsertanties in teh position\",\n",
        "\"horizon effect\": \"when the program faces an opponents move that causes serious damage unavoidable, only delayed\",\n",
        "\"singular extension\": \"allow moves that are clearly better than all other moves, even when the search would be cut off\",\n",
        "\"forward pruning\": \"prunes moves that appear to be poor moves, but could be good\",\n",
        "\"beam search\": \"consider a beam of the n best moves, rather than all\",\n",
        "\"late move reduction\": \"assumes move ordering is good, and less likely that a good move is late in the list\",\n",
        "\"policy\": \"mapping from every possible state to the best move in that state\",\n",
        "\"retrograde\": \"table that shows all winning states and the moves that lead up to them\",\n",
        "\"stochastic games\": \"include a random element (like dice)\",\n",
        "\"chance nodes\": \"involve the chance (ie 1-6 for a dice roll)\",\n",
        "\"expected value\": \"average over all possible outcomes of the chance nodes\",\n",
        "\"expectiminimax value\": \"a generalization of the minimax value for deterministic games\",\n",
        "\"utility function\": \"assigns a number to the desirability of a state\",\n",
        "\"expected utility\": \"average utility value of teh outcomes weighted by the probability that it occurs\",\n",
        "\"maximum expected utility\": \"rational agent should choose the action that maximizes the agents EU\",\n",
        "\"lottery\": \"set of outcomes for each action\",\n",
        "\"value function\": \"an agent only needs a prefrence ranking of states - numbers dont matter\",\n",
        "\"ordinal utility function\": \"value function\",\n",
        "\"preference elicitation\": \"presenting choices to the human and using the observed preferences to get utility func\",\n",
        "\"normalized utilities\": \"scale of 0 to 1\",\n",
        "\"standard lottery\": \"[p, uT; (i-p), u _|_\",\n",
        "\"value of a statistical life\": \"determine costs and benefits of regs and interventions ~ 10 mil\",\n",
        "\"micromort\": \"1 in a million chance of death\",\n",
        "\"QALY (quality adjusted life year)\": \"patients are willing to accept a shorter life to avoid disability\",\n",
        "\"monotonic prefrence\": \"agent prefers more money to less\",\n",
        "\"EMV (expected monetary value)\": \"average of possible outcomes\",\n",
        "\"risk - averse\": \"prefer a sure thing with a payoff less than the EMV of a gamble\",\n",
        "\"risk - seeking\": \"in the “desperate” region at large negative wealth\",\n",
        "\"certainty equivalent\": \"value an agent will accept in liew of a lottery\",\n",
        "\"insurance premium\": \"difference between the EMV of a lottery and its certainty equivalent\",\n",
        "\"risk neutral\": \"agent with a linear curve\",\n",
        "\"unbiased\": \"expected value of the error is zero\",\n",
        "\"order statistic\": \"distrobution of any ranked element of a sample\",\n",
        "\"optimizers curse\": \"estimated expected utility of the best choice being too high \",\n",
        "\"normative theory\": \"how rational agents should act\",\n",
        "\"descriptive theory\": \"how actual agents (humans) act\",\n",
        "\"certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"ambiguity aversion\": \"elect the known probability rather than the unknown unknowns\",\n",
        "\"framing effect\": \"90% survival rate is better than 10% death rate even tho they are the same\",\n",
        "\"anchoring effect\": \"feel more comfortable making relative utility judgments rather than absolute ones\",\n",
        "\"evolutionary psychology\": \"brain’s decision-making mechanisms did not evolve to solve word problems with probabilities\",\n",
        "\"static\": \"no changes while an agent deliberates\",\n",
        "\"discrete\": \"finite set of percepts and actions\",\n",
        "\"strategic\": \"next state determined by curr state and action\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f11da400-94e8-4b49-9d3e-5180d7396908"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Three stances to take towards multi-agetn environments:\n  - consider them like in the aggregate as an economy \n  - consider them as just a part of the environment- part that makes it nondeterministic\n  - explicitly model the adversarial agetns with techniques of adversarial game-tree search\nevery time we stop searching we ask who is winning\n  - evaluation function\n  - average the outcomes of many fast simulations of the game to the end\nGame can be formally defined with:\n  - S0 - the initial state\n  - TO-MOVE(s) - the player who's turn it is to move in the state s\n  - ACTIONS(s) the set of legal moves in s\n  - RESULT(s,a) the transistion model\n  - IS-TERMINAL(s) - terminal test\n  - UTILITY(s,p) - utility function\nState space graph is defined by:\n  - initial state\n  - actions function\n  - result function  \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n minimax search\n  - for games with multiple outcome scores - more general algorithm \n  - Max prefers to move to a state of maximum value when it is Max’s turn to move, \n  and Min prefers a state of minimum value (that is, minimum value for Max and thus \n  maximum value for Min)\n  - time complexity is O(b^m)\n  - space complexity\n    - all actions at once O(bm)\n    - one action at a time O(m)\nHumans make alliances in Games\n  - how can a computer mimic this? \n\nminimax: \n```\nfunction minimax-search(game,state) returns an action\n  player <- game.TO-MOVE(state)\n  value, move <-MAX-VALUE(game,state)\n  return move\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- -infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n      v, move <- v2, a\n  return v, move\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- +infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move <- v2, a\n  return v, move\n```\nAlpha Beta Pruning\n  - Num game states is exponential in the depth of the tree\n  - Can immediately prune large states of the tree\n  - the value of the root/the minimax decision are independent of the values of the leaves  and , therefore they can be pruned.\n\n\n```\nfunction alpha-beta-search(game,state, alpha, beta) returns an action\n  player <- game.TO-MOVE(state)\n  value, move <- MAX-VALUE(game,state, -inf, +inf)\n  return move\nfunction MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- -infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n    if v2 > v then\n      v, move <- v2, a\n      alpha <- MAX(alpha, v)\n    if v >= betha then return v, move\n  return v, move\nfunction MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- +infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a), alpha, beta)\n    if v2 < v then\n      v, move <- v2, a\n      beta <- MIN(beta, v)\n    if v <= alpha then return v,move\n  return v, move\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nApply a heuristic evaluation funcion states  \n  - effectively treating them as if they were terminal \nReplace the terminal test by a cutoff test\nHeuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p \nThe evaluation function does not know which states are which, but it can return a single value that estimates the proportion of states with each outcome. \nMaterial value for each piece (ie chess) \nWeighted linear function  \nCurrent depth must be increment in each recursive call \n  - The most straightforward approach to controlling the amount of search is to set a fixed depth limit so that Is-Cutoff(state, depth) returns true for all depth greater than some fixed depth d \nThe evaluation function should be applied only to positions that are quiescent \n  - For nonquiescent positions the Is-Cutoff returns false, and the search continues until quiescent positions are reached.  \n  - This extra quiescence search is sometimes restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position. \nThe horizon effect is more difficult to eliminate. and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics. \n  - To mitigate the horizon effect, allow singular extensions moves that are “clearly better” than all other moves, even when the search would normally be cut off at that point \nForward pruning- prunes moves that appear to be poor moves \nBeam search - on each ply consider only a beam of the best n moves \nProbcut algorithm is a froward pruning version that uses statistics gained from prior experience \nLate move reduction \n  - assumes move ordering has been done and therefore moves appear later in the list of possible moves \nTable lookup is usually faster than searching from the start \nA computer can completely solve the endgame by producing a policy \nThen the computer can play perfectly by looking up the right move in this table. The table is constructed by retrograde minimax search: \n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic Games \n  - incorporate random elements (such as rolling dice) \n  - Add a chance node in addition to max and min \n  - Positions no longer have a definite minimax value \n    - we can only calculate the expected value of the position \n  - expectiminimax value for games with chance nodes \n    - a generalization of the minimax value for deterministic games. \n    - Terminal nodes and max and min nodes work exactly the same way as before\n    (with the caveat that the legal moves for max and min will depend on the outcome\n    of the dice roll in the previous chance node).\n  - Evaluation functions have to be much more careful about which moves to choose \n    - They must be positive linear transformation of the probability of winning \n    - Takes (O(b^m*n^m) where n is the number of distinct rolls \n    - In games where the branching factor for chance nodes is high—consider a game like Yahtzee where you roll 5 dice on every turn—you may want to consider forward pruning that samples a smaller number of the possible chance branches. Or you may want to avoid using an evaluation function altogether, and opt for Monte Carlo tree search instead, where each playout includes random dice rolls. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Agent has to make a decision, it has actions a. If there are uncertainties about the current state we will assume probability P(s) is applied to each state s. Transition model P(s’|s,a). \n  - The probability that action a in state s reaches state s’ \n- Decision theory deals with choosing actions base on the desirability of their immediate outcomes \n  - The agents preferences are captured by a utility function which assigns a single number to express the desirability of a state. \n  - Expected utility is the average utility value of the outcomes weighted by the probability that they occur \n  - The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Any reasonable preference must obey \n  - ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding. \n  - TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C \n  - CONTINUITY: if some lotteryB is between A and C in preference then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 - p \n  - SUBSTITUTABILITY: If an agent is indifferent between two lotteries  A and B, then the agent is indifferent between two more complex lotteries that are the same except that  B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries. \n  - ONOTONICITY: Suppose two lotteries have the same two possible outcomes, A  and B. If an agent prefers A to B,  then the agent must prefer the lottery that has a higher probability for  A and vice versa). \n  - DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule:  \nIF THE AGENTS PREFERENCES THE AXIOMS OF UTILITY THERE IS A FUNCTION:\n  - U(A)>U(B) adn U(A)+U(B) \n  - As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n \n\n## AIMA Chapter 16.3 Utility Functions\n \n- preference elicitation, involves presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n- Normalized utilities use a scale with u T perp (best option) = 1 and u other perp = 0 worst option \n​​  - we can assess the utility of any particular prize  by asking the agent to choose between  and a standard lottery \n- Although nobody feels comfortable with putting a value on human life, it is a fact that tradeoffs on matters of life and death are made all the time. \n  - Paradoxically, a refusal to put a monetary value on life can mean that life is undervalued \n- humans prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.  \n  - in the “desperate” region at large negative wealth the behavior is risk-seeking.  \n- The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. \n- This calculation is a special case of computing an order statistic, the distribution of any particular ranked element of a sample \n- optimizer’s curse (Smith and Winkler, 2006). It afflicts even the most seasoned decision analysts and statisticians. Serious manifestations include believing that an exciting new drug that has cured 80% of patients in a trial will cure 80% of patients (it’s been chosen from  thousands of candidate drugs) \n- Decision theory is a normative theory: it describes how a rational agent should act. \n- A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act.  \n- Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect. Experiments show that people like a medical procedure that is described as having a “90% survival rate” about twice as much as one described as having a “10% death rate,” \n- Anchoring effect - People feel more comfortable making relative utility judgments rather than absolute ones. \n \n\n## Module 5 Lecture Notes\n\nGames \n  - simplest game environment - multiagent, static, discrete, fullyy observable, strategic \n  - general scheme  \n    1. Consider all legal successors to the current state (‘board position’) \n    2. Evaluate each successor board position \n    3. Pick the move which leads to the best board position. \n    4. After your opponent moves, repeat. \n  - design issues \n    - representing board \n    - representing legal next moves \n    - evaluating positions \n    - looking ahead \n  - evaluation function f(n) \n    - Evaluates how good a ‘board position’ is \n    -Based on static features of that board alone \n    - Zero-sum assumption lets us use one function to describe goodness for both players. \n      - f(n)>0 if MAX is winning in position n \n      - f(n)=0 if position n is tied \n      - f(n)<0 if MIN is winning in position n \n    - Build using expert knowledge  \n  - Definition of optimal play for MAX assumes MIN plays optimally: \n    - if MIN does not play optimally MAX will do even better \n  - alpha beta pruning \n    - alpha:  MAX’s current lower bound on MAX’s outcome  \n      - MAX will never allow a move that could lead to a worse score (for MAX) than α  \n    - beta:  MIN’s current upper bound on MIN’s outcome  \n      - MIN will never allow a move that could lead to a better score (for MAX) than β \nExpectimax and Utilities \n  - Expectimax search: compute the average score under optimal \n    - playMax nodes as in minimax search \n    - Chance nodes are like min nodes but the outcome is uncertain  \n    - Calculate their expected utilities \n      - I.e. take weighted average (expectation) of children \n```\ndef exp-value(state):\n  initialize v = 0\n  for each successor of state:\n    p = probability(successor)\n    v += p * value(successor)\n  return v\n```\nProbabilities \n  - A random variable represents an event whose outcome is unknown \n  - A probability distribution is an assignment of weights to outcomes \n  - For now, assume each chance node magically comes along with probabilities that\n   specify the distribution over its outcomes  \n\n\n\n## Module 5 Definitions\n* **Economy** - predict that increasing demand will raise prices, without predicting agent actions\n* **Evaluation function** - treating nonterminal nodes as if they were terminal\n* **Imperfect information** - games with an element of chance\n* **Perfect information** - fully observable\n* **Zero-sum games** - what is good for one player is just as bad for the other\n* **Move** - action\n* **Position** - state\n* **Terminal test** - true when the game is voer\n* **Terminal states** - states where the game has ended\n* **Transition model** - defines the state resulting from taking action a in state s\n* **Utility function** - assigns a number to the desirability of a state\n* **State space graph** - verticies are states, edges are moves, state might be reached by multiple paths\n* **Game tree** - search tree that follows every sequence of moves to the termial state\n* **Ply** - one move by one player\n* **Minimax value** - utility (for MAX) being in that state, assuming both players play optimally\n* **Minimax decisison** - the action a that is the optimal choice for MAX because it leads to the highest minimax value\n* **Backs up** - goes all the way down the leaves of the tree then goes up as recursion unwinds\n* **Alliance** - made and broke as the game goes along\n* **Alpha-beta pruning** - prunes subtrees\n* **Iterative deepening** - search one ply at a time\n* **Killer moves** - best moves\n* **Transpositions** - diff permutations of the move sequence that end up in the same position\n* **Transposition table** - catches the heuristic value of states\n* **Type a strategy** - all possible moves to a depth and uses h(n) to estimate expected utility\n* **Type b strategy** - ignores moves that look bad, follows promising lines as far as possible\n* **Cutoff test** - returns true for terminal states\n* **Features** - define categories or equivalence classes of states\n* **Expected value** - average over all possible outcomes of the chance nodes\n* **Material value** - val for a piece (ie king is 10 etc\n* **Weighted linear function** - evlauation function using the material values of pieces\n* **Quiescent** - a postion where no possible move would swing the game\n* **Quiescence search** - restricted to consider the moves that will resolve unsertanties in teh position\n* **Horizon effect** - when the program faces an opponents move that causes serious damage unavoidable, only delayed\n* **Singular extension** - allow moves that are clearly better than all other moves, even when the search would be cut off\n* **Forward pruning** - prunes moves that appear to be poor moves, but could be good\n* **Beam search** - consider a beam of the n best moves, rather than all\n* **Late move reduction** - assumes move ordering is good, and less likely that a good move is late in the list\n* **Policy** - mapping from every possible state to the best move in that state\n* **Retrograde** - table that shows all winning states and the moves that lead up to them\n* **Stochastic games** - include a random element (like dice)\n* **Chance nodes** - involve the chance (ie 1-6 for a dice roll)\n* **Expectiminimax value** - a generalization of the minimax value for deterministic games\n* **Expected utility** - average utility value of teh outcomes weighted by the probability that it occurs\n* **Maximum expected utility** - rational agent should choose the action that maximizes the agents EU\n* **Lottery** - set of outcomes for each action\n* **Value function** - an agent only needs a prefrence ranking of states - numbers dont matter\n* **Ordinal utility function** - value function\n* **Preference elicitation** - presenting choices to the human and using the observed preferences to get utility func\n* **Normalized utilities** - scale of 0 to 1\n* **Standard lottery** - [p, uT; (i-p), u _|_\n* **Value of a statistical life** - determine costs and benefits of regs and interventions ~ 10 mil\n* **Micromort** - 1 in a million chance of death\n* **Qaly (quality adjusted life year)** - patients are willing to accept a shorter life to avoid disability\n* **Monotonic prefrence** - agent prefers more money to less\n* **Emv (expected monetary value)** - average of possible outcomes\n* **Risk - averse** - prefer a sure thing with a payoff less than the EMV of a gamble\n* **Risk - seeking** - in the “desperate” region at large negative wealth\n* **Certainty equivalent** - value an agent will accept in liew of a lottery\n* **Insurance premium** - difference between the EMV of a lottery and its certainty equivalent\n* **Risk neutral** - agent with a linear curve\n* **Unbiased** - expected value of the error is zero\n* **Order statistic** - distrobution of any ranked element of a sample\n* **Optimizers curse** - estimated expected utility of the best choice being too high \n* **Normative theory** - how rational agents should act\n* **Descriptive theory** - how actual agents (humans) act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - elect the known probability rather than the unknown unknowns\n* **Framing effect** - 90% survival rate is better than 10% death rate even tho they are the same\n* **Anchoring effect** - feel more comfortable making relative utility judgments rather than absolute ones\n* **Evolutionary psychology** - brain’s decision-making mechanisms did not evolve to solve word problems with probabilities\n* **Static** - no changes while an agent deliberates\n* **Discrete** - finite set of percepts and actions\n* **Strategic** - next state determined by curr state and action\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Constraint satisfaction problems: \n",
        "  - consists of three components X, D, and C \n",
        "    - each constraint Cj consists of a pair <scope, rel> \n",
        "  - CSPs deal with assignments of values to variables \n",
        "    - a solution to a CSP is a consistent, complete assignment\n",
        "    - partial assignment is one that leaves some variables unassigned\n",
        "    - partial solution is a partial assignment that is consistent\n",
        "    - it can be helpful to visualize a CSP as a constraint graph\n",
        "      - nodes are variables \n",
        "      - edges connect 2 variables\n",
        "  - why use a CSP?\n",
        "    - yield a natural representation for a wide variety of problems; \n",
        "      - it is often easy to formulate a problem as a CSP. \n",
        "    - years of development work have gone into making CSP solvers fast and efficient. \n",
        "    - a CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot.\n",
        "  - precedence constraint - one must be before the other\n",
        "    - T1 + d1 <= T2\n",
        "  - disjunctive constraint - cannot overlap in time\n",
        "    - ie. axleF + 10 <= axleB or axleB + 10 <= axleF \n",
        "  - simplest CSPs have discrete finite domains\n",
        "    - a discrete domain can be infinite\n",
        "    - no algorithm exists for solving general nonlinear constraints on integer variables—the problem is undecidable \n",
        "  - types of constraints\n",
        "     - unary\n",
        "     - binary CSP - only unary and binary constraints\n",
        "     - global\n",
        "     - prefrence (in many real world CSPs)\n",
        "  \"\"\"\n",
        "chapter6_2 = \"\"\" constraint propogation: \n",
        "  - leaves fewer choices to consider when we make the next choice \n",
        "  - key idea is local consistency: treat each variable as a node in a graph and each\n",
        "  binary constraint as an edge, then the process of enforcing local consistency in each\n",
        "  part of the graph causes inconsistent values to be eliminated throughout the graph. \n",
        "    - node consistency k = 1 \n",
        "    - arc consistency k = 2\n",
        "      - AC-3 : enforces arc consistency\n",
        "        - time O(cd^3)\n",
        "    - path consistency\n",
        "\n",
        "```\n",
        "function AC-3(csp) returns false if an inconsistency is found and true otherwise\n",
        "  queue <- a queue of arcs, initially all the arcs in csp\n",
        "  while queue is not empty do\n",
        "  (Ci, Xj) <- POP(queue)\n",
        "  if REVISE(csp, Xi, Xj) then \n",
        "    if size of Di = 0 then return false\n",
        "    for each Xk in xi.NEIGHBORS - {Xj} fo \n",
        "      add (Xk, Xi) to queue\n",
        "  return true\n",
        "function REVISE(csp, Xi, Xj)returns true iff we revise teh domain of Xi\n",
        "  revised <- false\n",
        "  for each x in Di do\n",
        "    if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then\n",
        "      delete x from Di\n",
        "      revised <- true\n",
        "  return revised\n",
        "```\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" backtracking search for csps \n",
        "   - finish constraint propagation and still have vars with possible values then we search for a solution\n",
        "   - communutativity \n",
        "\n",
        "```\n",
        "function BACKTRACKING-SEARCH(csp) returns a solution or failure\n",
        "  return BACKTRACK(csp, {})\n",
        "function BACKTRACK(csp, assignment) retruns a solution or failure\n",
        "  if assignment is complete then return assignment\n",
        "  var <- SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n",
        "  for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do \n",
        "    if value is consistent wiht assignment then\n",
        "      add {var = value} to assignment\n",
        "      inferences <- INFERENCE(csp, var, assignment)\n",
        "      if inferences != failure then\n",
        "        add inferences to csp\n",
        "        result <- BACKTRACK(csp, assignment)\n",
        "        if result != failure then return result\n",
        "        remove inferences from csp\n",
        "      remove {var = value} from assignment\n",
        "  return failure\n",
        "```\n",
        "\n",
        "domain-independent heuristics that take advantage of the factored representation of CSPs\n",
        "  - Which variable should be assigned next (Select-Unassigned-Variable), and in what order should its values be tried (Order-Domain-Values)?\n",
        "    - minimum remaining values\n",
        "    - degree heuristic\n",
        "    - least constraining calue\n",
        "  - What inferences should be performed at each step in the search (Inference)?\n",
        "    - forward checking\n",
        "    - MAC\n",
        "  - Can we Backtrack more than one step when appropriate?\n",
        "    - chronological backtracking\n",
        "    - conflict set\n",
        "    - backjumping\n",
        "    - conflict directed backjumping\n",
        "  - Can we save and reuse partial results from the search?\n",
        "    - constraint learning\n",
        "    - no-good\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" local search for CSPs \n",
        "  - complete state formulation: each state assigns a val to each variable and the search changes one at at time\n",
        "    - min-conflicts heuristic\n",
        "    - constraint weighting\n",
        "      - the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. \n",
        "      - the weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n",
        "      - This has two benefits: \n",
        "        - it adds topography to plateaus, making sure that it is possible to improve from the current state \n",
        "        - adds learning: over time the difficult constraints are assigned higher weights.\n",
        "\n",
        "```\n",
        "function MIN-CONFLICT(csp, max_steps) returns a solution or failure\n",
        "  current <- an initial complete assignment for csp\n",
        "  for i = 1 to max_steps do\n",
        "    if current is a solution for csp then return current\n",
        "    var <- randomly chosen conflicted variable from csp.VARIABLES\n",
        "    value <- the value v for car that minimixes CONFLICTS(csp, var, v, current)\n",
        "    set var = value in current\n",
        "  return failure\n",
        "```\n",
        "\n",
        "   \"\"\"\n",
        "chapter6_5 = \"\"\" the structure of problems - represented by the constraint graph\n",
        "  - independent sub problems \n",
        "  - connected compopnents \n",
        "    - subproblem CSPi if assignment Si is a solutions of CSPi' then UiSi is a solution\n",
        "    of UiCSPi\n",
        "  - a constraint graph is a tree when any two variables are connected by only one path\n",
        "    - any tree-structured CSP can be solved in time linear in the number of variable \n",
        "    - topological sort\n",
        "    \n",
        "\n",
        "```\n",
        "function TREE-CSP-SOLVER(csp (X, D, C)) returns a solution or failure\n",
        "  n <- number of variables in X\n",
        "  assignment <- an empty assignment\n",
        "  root <- any variable in X\n",
        "  X <- TOPOLOGICALSORT(X, root)\n",
        "  for j = n down to 2 do\n",
        "    MAKE-ARC-CONSISTENT(PARENT(Xj), Xj)\n",
        "    if it cannot be made consistent then return failure\n",
        "  for i = 1 to n do \n",
        "    assignment[Xi] <- any consistent value from Di\n",
        "    if there is no consistent value then return failure\n",
        "  return assignment\n",
        "\n",
        "```\n",
        "Two ways to reduce a CSP: \n",
        "  - Cutset condidtioning\n",
        "    - cycle cutset with size c\n",
        "    - For each possible assignment to the variables in S that satisfies all constraints on S,\n",
        "      - remove from the domains of the remaining variables any values that are inconsistent with the assignment for S\n",
        "      - if the remaining CSP has a solution, return it together with the assignment for S.\n",
        "    - runtime is O(d^c *(n-c)d^2)\n",
        "\n",
        "  - Tree decomosition\n",
        "    - must satisfy:\n",
        "      - every variable in the original problem appears in at least one of the tree nodes. \n",
        "      - if two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n",
        "      - if a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n",
        "      - tree width\n",
        "      - CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSPs\n",
        "  - A CSP consists of:\n",
        "    - Finite set of variables X1, X2, …, Xn\n",
        "    - Nonempty domain of possible values for each variable D1, D2, … Dn where Di = {v1, …, vk}\n",
        "    - Finite set of constraints C1, C2, …, Cm\n",
        "      - Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2 A state is defined as an assignment of values to some or all variables.\n",
        "  - A consistent assignment does not violate the constraints. \n",
        "  - An assignment is complete when every variable is assigned a value.\n",
        "  - A solution to a CSP is a complete, consistent assignment.\n",
        "  - Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.\n",
        "  - Beyond our scope: CSPs that require a solution that maximizes an objective function.\n",
        "  - benefits:\n",
        "    - Clean specification of many problems, generic goal, successor function & heuristics\n",
        "      - Just represent problem as a CSP & solve with general package\n",
        "    - CSP “knows” which variables violate a constraint \n",
        "      - And hence where to focus the search\n",
        "    - CSPs: Automatically prune off all branches that violate constraints\n",
        "      - (State space search could do this only by hand-building constraints into the successor function)\n",
        "  - A CSP can easily be expressed as a search problem\n",
        "    - Initial State: the empty assignment {}.\n",
        "    - Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n",
        "    - Goal test: the current assignment is complete.\n",
        "    - Path cost: a constant cost for every step.\n",
        "    - *Solution is always found at depth n, for n variables\n",
        "      - Hence Depth First Search can be used\n",
        "  - improving backtracking\n",
        "    - General-purpose methods & general-purpose heuristics can give huge gains in speed, on average\n",
        "    - Heuristics: Q: Which variable should be assigned next?\n",
        "      1. Most constrained variable\n",
        "      2. (if ties:) Most constraining variable\n",
        "      Q: In what order should that variable’s values be tried?\n",
        "      3. Least constraining value\n",
        "      Q: Can we detect inevitable failure early?\n",
        "      4. Forward checking\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"X\": \" a set of variables {X1,...,Xn}\",\n",
        "\"D\": \"a set of domains for each variable {D1, ..., Dn}\",\n",
        "\"C\": \"a set of constraints that specify allowable combinations o fvalues\",\n",
        "\"relation\": \"defines the values that variables take on\",\n",
        "\"scope\": \"tuple of variables that participate in teh constraint\",\n",
        "\"consistent assignmnet\": \"does not violate any constraints\",\n",
        "\"complete assignment\": \"every variable is assigned a value\",\n",
        "\"precedence constraint\": \"whenever a task 1 must occur between task 2 and the durration\",\n",
        "\"disjunctive constraint\": \"whenever tasks cannot overlap in time\",\n",
        "\"linear programming problems\": \"constraints must be linear equalities or inqualities\",\n",
        "\"unary constraint\": \"restricts the val of a single varible\",\n",
        "\"binary constraint\": \"relates 2 variable\",\n",
        "\"global constraint\": \"involves an arbitrary number of variables\",\n",
        "\"constraint hypergraph\": \"ordinary nodes and hyper nodes, represent n-array constraints\",\n",
        "\"n-array constraints\": \"constraints with n variables\",\n",
        "\"dual graph\": \"convert n-array CSP to a binary one\",\n",
        "\"prefrence constraints\": \"indicates which solutions are prefered\",\n",
        "\"constrained optimization problem\": \"CSPs with prefrences, solved wiht optimization search methods\",\n",
        "\"constraint propagation\": \"using the constraint to reduce the num legal moves for a var-> then another\",\n",
        "\"local consistency\": \"treat each var as a node, binary constraint as an edge -> eliminate inconsistencies\",\n",
        "\"node consistency\": \"single variable (node), if all vals satisfy its unary constraints\",\n",
        "\"arc consistency\": \"every value in its domain satisfies the variables bunary constraints\",\n",
        "\"path consistency\": \"tightens binary constraints by using inferred implicit constraints on triplets of vars\",\n",
        "\"k - consistency\": \"set of k-1 vars a cal can be assigned to any kth variable\",\n",
        "\"strongly k - consistent\": \"k consistent, and k-1 consistent and k-2 consistent... 1- consistent\",\n",
        "\"resource constraint\": \"ie no more than 10 people doing something\",\n",
        "\"bounds propagation\": \"domains are represented as upper and lower bounds\",\n",
        "\"commutativity\": \"order of application of any given set of actions does not matterd\",\n",
        "\"minimum remaining values\": \"chosing the cariable with teh fewest legal values\",\n",
        "\"degreee heuristic\": \"selecting the variable that is involved in the larges num constraints in unsolved vals\",\n",
        "\"least constraining value heuristic\": \" prefers the value that rules out the fewest choices for the neighboring variables in the graph\",\n",
        "\"forward checking\": \"when X is assigned establish arc consistency for it, delete from Ys domain any val inconsistent with X\",\n",
        "\"MAC (maintaining arc consistency)\": \"deletes inconsistencies within the neighbors\",\n",
        "\"chronological backtracking\": \"when a branch of the search fails back up and try again\",\n",
        "\"conflict set\": \"set of assignment that are in conflict for some value for ___\",\n",
        "\"backjumping\": \"backtracks to the most recent assignment in teh conflict set\",\n",
        "\"conflict directed backjumping\": \"backjumping algorithm that uses conflict sets of subsequent values\",\n",
        "\"constraint learning\": \"finding a min set of variables from teh conflict set that causes the problem\",\n",
        "\"no good\": \"constraint learning and their values\",\n",
        "\"min-conflicts heuristic\": \"select the variable wiht the least conflicts with other variables\",\n",
        "\"independent sup problems\": \"-> the solutions will solve the whole problem when you have both\",\n",
        "\"topological sort\": \"pick a var to be the root and choose an ordering so each appears after its parent\",\n",
        "\"cycle cutset\": \"Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S\",\n",
        "\"tree width\": \"tree decomposition of a graph is one less than the size of the largest node\",\n",
        "}\n"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "606da2dc-909f-4dfd-9dc2-22516c978235"
      },
      "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": 58,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Constraint satisfaction problems: \n  - consists of three components X, D, and C \n    - each constraint Cj consists of a pair <scope, rel> \n  - CSPs deal with assignments of values to variables \n    - a solution to a CSP is a consistent, complete assignment\n    - partial assignment is one that leaves some variables unassigned\n    - partial solution is a partial assignment that is consistent\n    - it can be helpful to visualize a CSP as a constraint graph\n      - nodes are variables \n      - edges connect 2 variables\n  - why use a CSP?\n    - yield a natural representation for a wide variety of problems; \n      - it is often easy to formulate a problem as a CSP. \n    - years of development work have gone into making CSP solvers fast and efficient. \n    - a CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot.\n  - precedence constraint - one must be before the other\n    - T1 + d1 <= T2\n  - disjunctive constraint - cannot overlap in time\n    - ie. axleF + 10 <= axleB or axleB + 10 <= axleF \n  - simplest CSPs have discrete finite domains\n    - a discrete domain can be infinite\n    - no algorithm exists for solving general nonlinear constraints on integer variables—the problem is undecidable \n  - types of constraints\n     - unary\n     - binary CSP - only unary and binary constraints\n     - global\n     - prefrence (in many real world CSPs)\n  \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propogation: \n  - leaves fewer choices to consider when we make the next choice \n  - key idea is local consistency: treat each variable as a node in a graph and each\n  binary constraint as an edge, then the process of enforcing local consistency in each\n  part of the graph causes inconsistent values to be eliminated throughout the graph. \n    - node consistency k = 1 \n    - arc consistency k = 2\n      - AC-3 : enforces arc consistency\n        - time O(cd^3)\n    - path consistency\n\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise\n  queue <- a queue of arcs, initially all the arcs in csp\n  while queue is not empty do\n  (Ci, Xj) <- POP(queue)\n  if REVISE(csp, Xi, Xj) then \n    if size of Di = 0 then return false\n    for each Xk in xi.NEIGHBORS - {Xj} fo \n      add (Xk, Xi) to queue\n  return true\nfunction REVISE(csp, Xi, Xj)returns true iff we revise teh domain of Xi\n  revised <- false\n  for each x in Di do\n    if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then\n      delete x from Di\n      revised <- true\n  return revised\n```\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n backtracking search for csps \n   - finish constraint propagation and still have vars with possible values then we search for a solution\n   - communutativity \n\n```\nfunction BACKTRACKING-SEARCH(csp) returns a solution or failure\n  return BACKTRACK(csp, {})\nfunction BACKTRACK(csp, assignment) retruns a solution or failure\n  if assignment is complete then return assignment\n  var <- SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n  for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do \n    if value is consistent wiht assignment then\n      add {var = value} to assignment\n      inferences <- INFERENCE(csp, var, assignment)\n      if inferences != failure then\n        add inferences to csp\n        result <- BACKTRACK(csp, assignment)\n        if result != failure then return result\n        remove inferences from csp\n      remove {var = value} from assignment\n  return failure\n```\n\ndomain-independent heuristics that take advantage of the factored representation of CSPs\n  - Which variable should be assigned next (Select-Unassigned-Variable), and in what order should its values be tried (Order-Domain-Values)?\n    - minimum remaining values\n    - degree heuristic\n    - least constraining calue\n  - What inferences should be performed at each step in the search (Inference)?\n    - forward checking\n    - MAC\n  - Can we Backtrack more than one step when appropriate?\n    - chronological backtracking\n    - conflict set\n    - backjumping\n    - conflict directed backjumping\n  - Can we save and reuse partial results from the search?\n    - constraint learning\n    - no-good\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n local search for CSPs \n  - complete state formulation: each state assigns a val to each variable and the search changes one at at time\n    - min-conflicts heuristic\n    - constraint weighting\n      - the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. \n      - the weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n      - This has two benefits: \n        - it adds topography to plateaus, making sure that it is possible to improve from the current state \n        - adds learning: over time the difficult constraints are assigned higher weights.\n\n```\nfunction MIN-CONFLICT(csp, max_steps) returns a solution or failure\n  current <- an initial complete assignment for csp\n  for i = 1 to max_steps do\n    if current is a solution for csp then return current\n    var <- randomly chosen conflicted variable from csp.VARIABLES\n    value <- the value v for car that minimixes CONFLICTS(csp, var, v, current)\n    set var = value in current\n  return failure\n```\n\n   \n\n## AIMA Chapter 6.5 The Structure of Problems\n the structure of problems - represented by the constraint graph\n  - independent sub problems \n  - connected compopnents \n    - subproblem CSPi if assignment Si is a solutions of CSPi' then UiSi is a solution\n    of UiCSPi\n  - a constraint graph is a tree when any two variables are connected by only one path\n    - any tree-structured CSP can be solved in time linear in the number of variable \n    - topological sort\n    \n\n```\nfunction TREE-CSP-SOLVER(csp (X, D, C)) returns a solution or failure\n  n <- number of variables in X\n  assignment <- an empty assignment\n  root <- any variable in X\n  X <- TOPOLOGICALSORT(X, root)\n  for j = n down to 2 do\n    MAKE-ARC-CONSISTENT(PARENT(Xj), Xj)\n    if it cannot be made consistent then return failure\n  for i = 1 to n do \n    assignment[Xi] <- any consistent value from Di\n    if there is no consistent value then return failure\n  return assignment\n\n```\nTwo ways to reduce a CSP: \n  - Cutset condidtioning\n    - cycle cutset with size c\n    - For each possible assignment to the variables in S that satisfies all constraints on S,\n      - remove from the domains of the remaining variables any values that are inconsistent with the assignment for S\n      - if the remaining CSP has a solution, return it together with the assignment for S.\n    - runtime is O(d^c *(n-c)d^2)\n\n  - Tree decomosition\n    - must satisfy:\n      - every variable in the original problem appears in at least one of the tree nodes. \n      - if two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n      - if a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n      - tree width\n      - CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n\n\n## Module 6 Lecture Notes\n CSPs\n  - A CSP consists of:\n    - Finite set of variables X1, X2, …, Xn\n    - Nonempty domain of possible values for each variable D1, D2, … Dn where Di = {v1, …, vk}\n    - Finite set of constraints C1, C2, …, Cm\n      - Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2 A state is defined as an assignment of values to some or all variables.\n  - A consistent assignment does not violate the constraints. \n  - An assignment is complete when every variable is assigned a value.\n  - A solution to a CSP is a complete, consistent assignment.\n  - Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.\n  - Beyond our scope: CSPs that require a solution that maximizes an objective function.\n  - benefits:\n    - Clean specification of many problems, generic goal, successor function & heuristics\n      - Just represent problem as a CSP & solve with general package\n    - CSP “knows” which variables violate a constraint \n      - And hence where to focus the search\n    - CSPs: Automatically prune off all branches that violate constraints\n      - (State space search could do this only by hand-building constraints into the successor function)\n  - A CSP can easily be expressed as a search problem\n    - Initial State: the empty assignment {}.\n    - Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n    - Goal test: the current assignment is complete.\n    - Path cost: a constant cost for every step.\n    - *Solution is always found at depth n, for n variables\n      - Hence Depth First Search can be used\n  - improving backtracking\n    - General-purpose methods & general-purpose heuristics can give huge gains in speed, on average\n    - Heuristics: Q: Which variable should be assigned next?\n      1. Most constrained variable\n      2. (if ties:) Most constraining variable\n      Q: In what order should that variable’s values be tried?\n      3. Least constraining value\n      Q: Can we detect inevitable failure early?\n      4. Forward checking\n  \n\n## Module 6 Definitions\n* **X** -  a set of variables {X1,...,Xn}\n* **D** - a set of domains for each variable {D1, ..., Dn}\n* **C** - a set of constraints that specify allowable combinations o fvalues\n* **Relation** - defines the values that variables take on\n* **Scope** - tuple of variables that participate in teh constraint\n* **Consistent assignmnet** - does not violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Precedence constraint** - whenever a task 1 must occur between task 2 and the durration\n* **Disjunctive constraint** - whenever tasks cannot overlap in time\n* **Linear programming problems** - constraints must be linear equalities or inqualities\n* **Unary constraint** - restricts the val of a single varible\n* **Binary constraint** - relates 2 variable\n* **Global constraint** - involves an arbitrary number of variables\n* **Constraint hypergraph** - ordinary nodes and hyper nodes, represent n-array constraints\n* **N-array constraints** - constraints with n variables\n* **Dual graph** - convert n-array CSP to a binary one\n* **Prefrence constraints** - indicates which solutions are prefered\n* **Constrained optimization problem** - CSPs with prefrences, solved wiht optimization search methods\n* **Constraint propagation** - using the constraint to reduce the num legal moves for a var-> then another\n* **Local consistency** - treat each var as a node, binary constraint as an edge -> eliminate inconsistencies\n* **Node consistency** - single variable (node), if all vals satisfy its unary constraints\n* **Arc consistency** - every value in its domain satisfies the variables bunary constraints\n* **Path consistency** - tightens binary constraints by using inferred implicit constraints on triplets of vars\n* **K - consistency** - set of k-1 vars a cal can be assigned to any kth variable\n* **Strongly k - consistent** - k consistent, and k-1 consistent and k-2 consistent... 1- consistent\n* **Resource constraint** - ie no more than 10 people doing something\n* **Bounds propagation** - domains are represented as upper and lower bounds\n* **Commutativity** - order of application of any given set of actions does not matterd\n* **Minimum remaining values** - chosing the cariable with teh fewest legal values\n* **Degreee heuristic** - selecting the variable that is involved in the larges num constraints in unsolved vals\n* **Least constraining value heuristic** -  prefers the value that rules out the fewest choices for the neighboring variables in the graph\n* **Forward checking** - when X is assigned establish arc consistency for it, delete from Ys domain any val inconsistent with X\n* **Mac (maintaining arc consistency)** - deletes inconsistencies within the neighbors\n* **Chronological backtracking** - when a branch of the search fails back up and try again\n* **Conflict set** - set of assignment that are in conflict for some value for ___\n* **Backjumping** - backtracks to the most recent assignment in teh conflict set\n* **Conflict directed backjumping** - backjumping algorithm that uses conflict sets of subsequent values\n* **Constraint learning** - finding a min set of variables from teh conflict set that causes the problem\n* **No good** - constraint learning and their values\n* **Min-conflicts heuristic** - select the variable wiht the least conflicts with other variables\n* **Independent sup problems** - -> the solutions will solve the whole problem when you have both\n* **Topological sort** - pick a var to be the root and choose an ordering so each appears after its parent\n* **Cycle cutset** - Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S\n* **Tree width** - tree decomposition of a graph is one less than the size of the largest node\n* **** - \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 = \"\"\" 7.1 Knowledge-Based Agents\n",
        "  - The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set of sentences.\n",
        "    - Each sentence is expressed in a language called a knowledge representation language \n",
        "    - axiom\n",
        "    - Tell \n",
        "    - Ask \n",
        "    - Inference \n",
        "  - The agent maintains a knowledge base, KB, which may initially contain some background knowledge.\n",
        "\n",
        "```\n",
        "function KB-Agent(percept) returns and action\n",
        "  persistent: KB, a knowledge base\n",
        "    t, a counter, initially 0 indicating time\n",
        "  Tell(KB, Make-Percept_sentence(percept,t))\n",
        "  action<- ask(KB,Make-Action_query(t)\n",
        "  Tell(KB, Make-action-sentence(action,t)\n",
        "  t<t+1\n",
        "  return action\n",
        "```\n",
        "\n",
        "  - Each time the program is called:\n",
        "    - Tells the knowledge base what is perceives\n",
        "    - Asks the knowledge base what action it should perform\n",
        "    - Tells the knowledge base which action was chosen and returns the action so it can be executed\n",
        "  - Details of representation language are hidden inside 3 functions\n",
        "    - Make-percept-sentence\n",
        "    - Make-action-query \n",
        "    - Make-action-sentence \n",
        "  - Knowledge level - where we need to specify only what the agent knows and what its goals are in order to determine its behavior\n",
        "  - Knowledge based agent can be built simply by telling it what it needs to know\n",
        "    - Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment. \n",
        "    - This is called the declarative approach to system building. \n",
        "    - the procedural approach encodes desired behaviors directly as program code.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" he Wumpus World\n",
        "The wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the agent has only one arrow.\n",
        "Bottomless pits\n",
        "PEAS description of the task environment\n",
        "Performance measure\n",
        "Environment\n",
        "Actuators\n",
        "Sensors\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" Knowledge bases consist of sentences. These sentences are expressed according to the syntax of the representation language\n",
        "Must define the semantics or meaning of sentences\n",
        "Define the truth of each sentence with respect to each possible world\n",
        "When we need to be precise we use the term model in place of the “possible world”\n",
        "If a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha\n",
        "Logical reasoning - involves the relation of logical entailment between sentences- the idea that a sentence follows logically from another sentence\n",
        "Alpha is derived from KB by i\n",
        "An inference algorithm that derives only entailed sentences called sound or truth-preserving\n",
        "Soundness is highly desirable\n",
        "Completeness is also desirable - an inference algorithm is complete if it can derive any sentence that is entailed\n",
        "If KB is true in the real world, then any sentence alpha derived from KB by a sound inference procedure is also true in the real world. \n",
        "Grounding - the connection between logical reasoning processes and the real environment in which the agent exists\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" propositional Logic: a very simple logic\n",
        "The syntax of propositional logic defines the allowable sentences\n",
        "Atomic sentences consist of a single proposition signal\n",
        "Complex sentences are constricted from simpler sentences, using parentheses and operators called logical connectives\n",
        "- not, the negation\n",
        "A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n",
        "^ (and) a sentence whose main connective is ^, is called conjunction; its parts are the conjuncts\n",
        "V (down arrow) and a disjunction; its parts are the disjuncts\n",
        " -> (implies) is called an implication (or conditional) its. Implications are also known as rules or if - then statements\n",
        "<-> if and only if, is a biconditional\n",
        "Semantics - defines the rules for determining the truth of a sentence with respect to a particular model\n",
        "Model sets the truth value for every proposition symbol\n",
        "The semantics for propositional logic must specify how to compute the truth value of any sentence, given a model.\n",
        "Recursive\n",
        "The rules can also be expressed with truth tables that specify the truth value of a complex sentence for each possible assignment of truth values to its components.\n",
        "TT-Entails? performs a recursive enumeration of a finite space of assignments to symbols. The algorithm is sound because it implements directly the definition of entailment, and complete because it works for any KB and alpha and always terminates—there are only finitely many models to examine.\n",
        "Function TT-entails(KB, alpha) returns true or false\n",
        "inputs : KB, the knowledge base, a sentence in propositional logic, alpha, the query, a sentence in propositional logic\n",
        "Symbols <- a list of th epropostion symbols in KB and alpha\n",
        "Return TT-check-all(kb, alpha, symbols, {})\n",
        "Function TT-check_all(KB, alpha, symbols, model) returns true or false\n",
        "If empty? (symbols) then\n",
        "If PL-true?(KB, model) then return PL-True?(alpha, model)\n",
        "Else return true\n",
        "Else\n",
        "P<- first(symbols)\n",
        "Rest <- REST(Symbols)\n",
        "Return (TT-Check-All(KB, alpha, rest, model U {P=true} and TT-Check-All(KB, alpha, rest, model U {P=false}\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" Propositional Theorem Proving\n",
        "theorem proving—applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models. \n",
        "Logical equivalence: two sentences a and b are logically equivalent if they are true in the same set of models\n",
        "Validity: a sentence is valid if it is true in all models\n",
        "Valid sentences are known as tautologies - they are necessarily true\n",
        "Deduction theorem: every  valid implication sentence describes a legitimate inference\n",
        "Satisfiability: a sentence is satisfiable if it is true in or satisfied by some model\n",
        "Proving beta from alpha by checking the unsatisfiability of (alpha ^ - Beta) corresponds exactly to the standard mathematical proof technique of reductio ad absurdum (literally, “reduction to an absurd thing”). It is also called proof by refutation or proof by contradiction. \n",
        "Inference and proofs\n",
        "Modus ponens- when any sentence of the form alpha-> beta and alpha are given then beta can be inferred\n",
        " monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n",
        "Proof by resolution\n",
        "resolution, that yields a complete inference algorithm when coupled with any complete search algorithm.\n",
        "unit resolution inference rule\n",
        "where each l is a literal li and m\n",
        " and  are complementary literals (i.e., one is the negation of the other). Thus, the unit resolution rule takes a clause—a disjunction of literals—and a literal and produces a new clause.\n",
        "Unit clause\n",
        "A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF \n",
        "Resolution algorithm\n",
        "is converted into CNF. Then, the resolution rule is applied to the resulting clauses. Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not already present. The process continues \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge representation language\": \"and represents some assertion about the world.\",\n",
        "\"axiom\": \"When the sentence is taken as being given without being derived from other sentences\",\n",
        "\"tell\": \"add new sentences to the knowledge base\",\n",
        "\"ask\": \"query what is known\",\n",
        "\"inference\": \"deriving new sentences from old\",\n",
        "\"make-percept sequence\": \"constructs a sentence asserting that the agent perceived the given percept at the given time\",\n",
        "\"make-action-query\": \"constructs a sentence that asks what should be done at the current time\",\n",
        "\"make-action-sequence\": \"constructs a sentence asserting that the chosen action was executed\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",\n",
        "\"\": \"\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 59,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "75ec6ba4-a8b0-440d-efda-f40233e430b4"
      },
      "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": 60,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n 7.1 Knowledge-Based Agents\n  - The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set of sentences.\n    - Each sentence is expressed in a language called a knowledge representation language \n    - axiom\n    - Tell \n    - Ask \n    - Inference \n  - The agent maintains a knowledge base, KB, which may initially contain some background knowledge.\n\n```\nfunction KB-Agent(percept) returns and action\n  persistent: KB, a knowledge base\n    t, a counter, initially 0 indicating time\n  Tell(KB, Make-Percept_sentence(percept,t))\n  action<- ask(KB,Make-Action_query(t)\n  Tell(KB, Make-action-sentence(action,t)\n  t<t+1\n  return action\n```\n\n  - Each time the program is called:\n    - Tells the knowledge base what is perceives\n    - Asks the knowledge base what action it should perform\n    - Tells the knowledge base which action was chosen and returns the action so it can be executed\n  - Details of representation language are hidden inside 3 functions\n    - Make-percept-sentence\n    - Make-action-query \n    - Make-action-sentence \n  - Knowledge level - where we need to specify only what the agent knows and what its goals are in order to determine its behavior\n  - Knowledge based agent can be built simply by telling it what it needs to know\n    - Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment. \n    - This is called the declarative approach to system building. \n    - the procedural approach encodes desired behaviors directly as program code.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n he Wumpus World\nThe wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the agent has only one arrow.\nBottomless pits\nPEAS description of the task environment\nPerformance measure\nEnvironment\nActuators\nSensors\n \n\n## AIMA Chapter 7.3 Logic\n Knowledge bases consist of sentences. These sentences are expressed according to the syntax of the representation language\nMust define the semantics or meaning of sentences\nDefine the truth of each sentence with respect to each possible world\nWhen we need to be precise we use the term model in place of the “possible world”\nIf a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha\nLogical reasoning - involves the relation of logical entailment between sentences- the idea that a sentence follows logically from another sentence\nAlpha is derived from KB by i\nAn inference algorithm that derives only entailed sentences called sound or truth-preserving\nSoundness is highly desirable\nCompleteness is also desirable - an inference algorithm is complete if it can derive any sentence that is entailed\nIf KB is true in the real world, then any sentence alpha derived from KB by a sound inference procedure is also true in the real world. \nGrounding - the connection between logical reasoning processes and the real environment in which the agent exists\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n propositional Logic: a very simple logic\nThe syntax of propositional logic defines the allowable sentences\nAtomic sentences consist of a single proposition signal\nComplex sentences are constricted from simpler sentences, using parentheses and operators called logical connectives\n- not, the negation\nA literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n^ (and) a sentence whose main connective is ^, is called conjunction; its parts are the conjuncts\nV (down arrow) and a disjunction; its parts are the disjuncts\n -> (implies) is called an implication (or conditional) its. Implications are also known as rules or if - then statements\n<-> if and only if, is a biconditional\nSemantics - defines the rules for determining the truth of a sentence with respect to a particular model\nModel sets the truth value for every proposition symbol\nThe semantics for propositional logic must specify how to compute the truth value of any sentence, given a model.\nRecursive\nThe rules can also be expressed with truth tables that specify the truth value of a complex sentence for each possible assignment of truth values to its components.\nTT-Entails? performs a recursive enumeration of a finite space of assignments to symbols. The algorithm is sound because it implements directly the definition of entailment, and complete because it works for any KB and alpha and always terminates—there are only finitely many models to examine.\nFunction TT-entails(KB, alpha) returns true or false\ninputs : KB, the knowledge base, a sentence in propositional logic, alpha, the query, a sentence in propositional logic\nSymbols <- a list of th epropostion symbols in KB and alpha\nReturn TT-check-all(kb, alpha, symbols, {})\nFunction TT-check_all(KB, alpha, symbols, model) returns true or false\nIf empty? (symbols) then\nIf PL-true?(KB, model) then return PL-True?(alpha, model)\nElse return true\nElse\nP<- first(symbols)\nRest <- REST(Symbols)\nReturn (TT-Check-All(KB, alpha, rest, model U {P=true} and TT-Check-All(KB, alpha, rest, model U {P=false}\n \n\n## AIMA 7.5 Propositional Theorem Proving\n Propositional Theorem Proving\ntheorem proving—applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models. \nLogical equivalence: two sentences a and b are logically equivalent if they are true in the same set of models\nValidity: a sentence is valid if it is true in all models\nValid sentences are known as tautologies - they are necessarily true\nDeduction theorem: every  valid implication sentence describes a legitimate inference\nSatisfiability: a sentence is satisfiable if it is true in or satisfied by some model\nProving beta from alpha by checking the unsatisfiability of (alpha ^ - Beta) corresponds exactly to the standard mathematical proof technique of reductio ad absurdum (literally, “reduction to an absurd thing”). It is also called proof by refutation or proof by contradiction. \nInference and proofs\nModus ponens- when any sentence of the form alpha-> beta and alpha are given then beta can be inferred\n monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base.\nProof by resolution\nresolution, that yields a complete inference algorithm when coupled with any complete search algorithm.\nunit resolution inference rule\nwhere each l is a literal li and m\n and  are complementary literals (i.e., one is the negation of the other). Thus, the unit resolution rule takes a clause—a disjunction of literals—and a literal and produces a new clause.\nUnit clause\nA sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF \nResolution algorithm\nis converted into CNF. Then, the resolution rule is applied to the resulting clauses. Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not already present. The process continues \n \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge representation language** - and represents some assertion about the world.\n* **Axiom** - When the sentence is taken as being given without being derived from other sentences\n* **Tell** - add new sentences to the knowledge base\n* **Ask** - query what is known\n* **Inference** - deriving new sentences from old\n* **Make-percept sequence** - constructs a sentence asserting that the agent perceived the given percept at the given time\n* **Make-action-query** - constructs a sentence that asks what should be done at the current time\n* **Make-action-sequence** - constructs a sentence asserting that the chosen action was executed\n* **** - \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": "03a3e346-8088-44d4-96f2-c257112a528e"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n The Turing test says that in order for a machine to be able to think it \nneeds: natural language processing, knowledge prepresetntaion to store what it knows \nor hears, automated reasoning, and machine learning. The total turing test also requires\ninteraction with objects and people in the world: computer vision and speech recognition, \nor robotics to manipulate onjects. We learn about human thoughts in 3 ways: introspection, \npsychological experiments, and brain imaging. Aristotle's syllogisms provided patterens\nfor argument structures. The rational-agent approach has two advantages: it is more\ngeneral than the \"laws of thought\" because a correct inference is only one of the mechanisms\nfor achieving rationality, and it is more amenable to scientific development. \nperfect rationality—always taking the exactly optimal action—is not feasible in complex environments\n\n## AIMA Chapter 27.1 The Limits of AI\n The Argument from informality of behavior says human behavior is \nfar too complex to be captured by a formal set of rules. Some could never be \ncodified into a computer program. An agent whose understanding of “dog” comes\nonly from a limited set of logical sentences such as “ Dog(x)⇒Mammal(x)” is at \na disadvantage compared to an agent that has watched dogs run, has played fetch\nwith them, and has been licked by one. We need to study the system as a whole; \nthe brain’s functioning exploits regularities in its environment, including the\nrest of its body. Under the embodied cognition approach, uses robotics, vision, and other sensors become central.\nThe argument from disability makes the claim that “a machine can never do X.” As examples of X\nMachines are mentally inferior to humansan agent should not be ashamed that it cannot\nestablish the truth of some sentence while other agents can.No entity—human or \nmachine—can prove things that are impossible to prove.\nAlan Turing, in his famous paper “Computing Machinery and Intelligence” (1950),\nsuggested that instead of asking whether machines can think, we should ask whether \nmachines can pass a behavioral test, which has come to be called the Turing test.\nThe point is to improve basic science and technology and to provide useful tools, not to fool judges.\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Some philosophers claim that a machine that acts intelligently would\nnot be actually thinking but would only be a simulation of thinking. Many AI researches \nare not concerned with the distinction.\nTuring said we never have any direct evidence about the internal mental states of other humans\nThe problem of consciousness is ill defined\nWe do agree that behaving intelligently will require some degree of awareness, \nwhich will differ from task to task, and that tasks involving interaction with \nhumans will require a model of human subjective experience\n \n\n## AIMA 2.1 Agents and Environments\n an agent’s choice of action at any given instant can depend on its \nbuilt-in knowledge and on the entire percept sequence observed to date, but not on \nanything it hasn’t perceived. We can imagine tabulating the agent function that \ndescribes any given agent; this would be a very large table (infinite). \nGiven an agent we can construct this table by trying out all possible percept sequences\nand recording which actions the agent does in response. The table is an external \ncharacterization of the agent. Internally, the agent function for an artificial\nagent will be implemented by an agent program.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n In AI the notion of what is the \"right thing\" is called consequenitalism.\nAs a general rule, it is better to design performance measures according to what one \nactually wants to be achieved in the environment, rather than according to how one\nthinks the agent should behave. What is rational depends on: \n1. the performance measure that defines success \n2. the agent's prior knowledge of the environment \n3. the actions that the agent can \nperform \n4.the agents percept sequence to date. Rationality maximizes expected performance, \nwhile perfection maximizes actual performance. If an agent relies on prior knowledge\nand not its own percepts and learning processes, we say it lacks autonomy. the \nincorporation of learning allows one to design a single rational agent that will \nsucceed in a vast variety of environments.\n\n## AIMA 2.3 The Nature of Environments\n task environment: PEAS (Performance, Environment, Actuators, Sensors). \nWhen designing an agent the first step must always be to specify the task environment \nas fully as possible. virtual task environments can be just as complex as the “real” world:\na software agent (or software robot or softbot) is just as valid. An environment might be \npartially observable because of noisy and inaccurate sensors or because parts of the\nstate are simply missing from the sensor data. The distinction between known and unknown\nenvironments is not the same as the one between fully and partially observable environments. \nIt is possible for a known environment to be partially observableve/an unknown \nenvironment can be fully observable. The performance measure could even be unknown.\nThe hardest case is partially observable, multiagent, nondeterministic, sequential, \ndynamic, continuous, and unknown. \n\n## AIMA 2.4 The Structure of Agents\n agent program, agent function\n``` \nfunction table_driven_agent(percept) returns an_action\n  persistent: percepts, a sequence, initially empty\n              table, a table of actions, indexed by percept sequences, initailly fully specified\n  append percept to the end of percepts\n  action <- look_up(percepts, table)\n  return action\n```\nThis is doomed to failure, if P is percepts adn T is lifetime, the lookup will contain \n$$\\sum_{t=1}^{\\tau}\\|\\P|^{t}$$ no physical agent in the univers would have the space to store this\n\nKey challenge for AI is to write programs that produce rational behavior from a smallish program \nrather than from a vast table. The simplest agent: simple reflex agent. These implement \nthe condition-action rule (if-then rules). These only work in fully observable environments. \n\nThe most effective way to handle partial observability is for the agent to keep track of the part of the world \nit can’t see now(maintain some sort of internal state.) \n\nTo update the internal state we need: a transition model, and a sensor model. Allows the agent to track of the state.\n``` \nfunction model-based-reflex-agent(percept) retuns an action\n  persistent: state\n              transition_model\n              sensor_model\n                    reflected in the agent's percepts\n              rules\n              action, the most recent action, initially none\n  state <- update_state(state, action, percept, transition_model, sensor_model)\n  rule <- rule_match(state, rules)\n  action <- rule, action\n  return action\n``` \nSearch and planning find action sequences that achieve the agents goals. While goal-based agent \nappear less efficient, they are more flexible because the knowledge that supports decisions is \nrepresented explicitly and can be modified. In many environments goals are not enough to \ngenerate good behavior. A more general performance measure allows a comparison of different \nworld states according to their expected utility. This works insituations where other agents would fail, \nie: there are conflicting goals (some can be achieved)-> utility function specifies the \nappropriate tradeoff or when there are several goals that the agent can aim for \n(none of which are certain), weighs the likelihood of success the importance of the goals.\nThis allows the agent to operate in initially unknown environments and to be more \ncompetent than its initial knowledge alone might allow.\n\nLearning in intelligent agents: a process of modification of each component of the agent \nto bring the components into closer agreement with the available feedback information, \nimproving the overall performance of the agent.\n\n## Module 1 Lecture Notes\nDecartes: priciple of dualism - the mind or thinking self\nis essentiall incorporeal or spiritual - the mind exists separate from the body. Find a test only \na human could pass. Alan Turing: Can machines think? John Searle: the chinese room.\nTuring test is bad because the appearance of being a good conversational participant is achievable through\nsimple symbol manipulation. Dennett: If a brain in a cat is procssing symbols what makes\nthis different from a computer processing symbols. There are four views of artificial intelligence:\nthinking humanly, thinking rationally, acting humanly, acting rationally. An agent \nis specified by an agent function f:P⇒A that maps a sequence of percept vectors P to an action\na from a set A. The agent program runs on the physical architecture to produce f. \nWe define a performance measure: An objective criterion for success of an \nagent's behavior, given the evidence provided by the percept sequence. It is better to design performance measures according to what you want to be\nachieved in the environment, rather than how you think the agent should behave.\ncomputational limitations make complete rationality unachievable. To design a rational agent we need\nto specify a taks environment: PEAS (performance measure, environment, actuators, sensors).\nWith a given task environment: 1. construct an agent function f that maximizes the expected \nvalue of the performance measure 2. design an agent program that impelments f on a particular architecture.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (though sensors) and act in an environment (through actuators)\n* **Percept** - what the agent's sensor percieve\n* **Percept sequence** - what the agent's sensor percieve\n* **Artificial intelligence** - the study of understanding and building intelligent entities\n* **Rationality** - doing the right thing\n* **Turring test** -  thought experiment that bypasses the vagueness of 'can a machine think?'\n* **Natural language processing** - communicate effectively in human language\n* **Knowledge represetnation** - storing what a computer knows or hears\n* **Automated reasoning** - answering questions and drawing new conclusions\n* **Machine learning** - adapting to new circumstances and detecting/extrapolating patterns\n* **Introspection** - trying to catch ones thoughts as they go by\n* **Psychological experiments** - obsercing a person while in action\n* **Brain imaginging** - observing the brain while in action\n* **Cognitive science** - testable theories of the human mind that come from AI and experimental psychology\n* **Syllogisms** - patterns for the structures of arguments that give correct conclusions with correct premices\n* **Logicist** - the theory that knowledge of the world that is certain, ie right or wrong\n* **Probability** - allows for reasoning without perfect information, lets a model think rationally\n* **Rational agent** - an agent that should select an action that will maximize its performace measure given its percept sequence\n* **Standard model** - study and construction of agents that do the right thing as defined by the objective provided to the agent\n* **Limited rationality** - acting correctly when there is not enoug time to do all computations\n* **Value alignment problem** - values put into the machine must be those of a human\n* **Provably beneficial** - if the complete objective is not known, machine has an incentive to act with caution, ask permission\n* **Weak ai** - machines could act as if htey were intelligent\n* **Strong ai** - machines are actually consciously thinking\n* **Good old-fashioned ai (gofai)** - the simplest logical agent\n* **Qualification problem** - it is difficult to capture every contingency of appropriate behavior in a set of rules\n* **Embodied cognition** - cognition takes place withing a body which is embedded in an environment\n* **Chinese room** -  rule book/stacks of paper, don't understand Chinese. So there is no understanding of Chinese.\n* **Biological naturalism** - neurons have “it” and transistors do not\n* **Consciousness** - awareness of the outside wrold\n* **Qualia** - intrinsic nature of experiences\n* **Consequentialism** - an evaluation of an agents behaviour based on its consequences\n* **Performance measure** - desirable qualities or goals for the task environment\n* **Omniscience** - omnicient agent knows the outcome of its actions and acts accordingly, not possible in real world\n* **Information gathering** - doing actions in order to modify future percepts\n* **Exploration** - surveying an initially unknown environment\n* **Autonomy** - \n* **Task environment** - the problems to which rational agents are the solutions\n* **Environment** - what will the agent face\n* **Actuators** - what the agent can move or manipulate\n* **Sensors** - what does the agent have to observe its environment\n* **Competitive** - when agent B is trying to maximize its performance measure while minimizing agent A's\n* **Cooperative** - when doing something maximizes the performance for each of the agents\n* **Intelligent** - \n* **Fully observable** - if the agent's sensors give it access to teh complete state of the enviornment at every point in time\n* **Unobservable** - if the agent has no sesors at all\n* **Partially observable** - \n* **Deterministic** - if the next state is completely determined by the current state and action\n* **Nondeterministic** - if the next state is NOT completely determined by the current state and action\n* **Stochastic** - a nondeterministic environment that directly relates to probabilities\n* **Episodic** - \n* **Sequential** - \n* **Static** - the environment cannot change while the agent is deliberating\n* **Dynamic** - if the environment can change while the agent is deciding\n* **Semidynamic** - if the environment does not change but the agent's performace does\n* **Discrete** - if the agent has a finite number of discrete states for the percepts and actions\n* **Continuous** - continuous-state, continuouts-time problems\n* **Known** - the agent knows all outcomes for all actions that are given\n* **Unknown** - the agent will have to learn how the environment works in order to make good decisions\n* **Agent program** - implements the agent function (current percept (input from the sensors), return (action to the actuators)\n* **Agent function** - maps a sequence of percept vectors P to an action\n* **Agent architecture** - where an agetn program runs (some computing device with physical sensors and actuators\n* **Simple reflex agent** - selects actions based on the current percept, ignoring the rest of the percept history\n* **Internal state** - depends on percept history and reflects some of the unobserved aspects of the current state\n* **Transition model** - info about how the world changes over time (the effects of the agent's actions and how the world evolves)\n* **Sensor model** - info about how the stare of the world is reflected in teh agent's percepts\n* **Model based reflex agent** - an agent that uses transition models and sensor models to keep track of the state of the world\n* **Goal based agent** - same as model based agent but with a goal\n* **Utility** - the quality of being useful\n* **Utility function** - internalization of the perforamce measure\n* **Expected utility** - the utility the agent expects to derrive\n* **Model free agent** - can learn what action is best in a sityation without learning how the action changes the environment\n* **Learning agent** - makes improvemnts\n* **Performance element** - selects external actions\n* **Critic** - gives feedback on how the agent is doing and determines how the performance element should be modified\n* **Problem generator** - suggests actions that will lead to new and informative experiences\n* **Reward (or penalty)** - provides direct feedback on the quality of the agent's behavior\n* **Atomic representation** - each state is indivisible, no internal structure\n* **Factored representation** - splits each state into a fixed set of variables or attributes, each of which has a value\n* **Structured representation** - when objects can be described explicitly\n* **Utility based agent** - \n* **Single agent** - \n* **Multi agent** - \n* **Reflex agent** - \n* **Problem solving agent** - \n* **** - \n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n In python all data is treated as objects (an object is deleted \nonce unreachable) \nStrong typing - every object has a fixed type, doesn't allow things incompatible with that type\n- example of types: int, float, str, tuple, dict, list, bool, None, generator, function\n\nStatic vs Dynamic typing - Python is dynamic variables come into existance when first assigned\n(x = 2 not int x = 2)\n\nStrings: single or double quotes, concatenation: separating literals with white space or +,\nprefixing with r means raw, formatting, immutable\n\nRefrences and mutability\n- strings are immutable\n  - == checks whether vars point to objects of the same value\n  - is checks wheather vars point to the same object\n  - reg strings are Unicode and use 2-byte characters\n  -  words = s.split(\" \") # splits on space\n- lists are mutable\n  - use y=x[:] to get a shallow copy of any sequence\n  - t[1:-1:2] # selection of every nth item.\n  - t[:2] # copy from beginning of sequence\n  - t[2:] # copy to the very end of the sequence\n  - li.insert(2, 'i') # inserts at index 2\n  - li.reverse() # reverse the list *in place* (modify)\n  - li.sort() # sort the list *in place*\n  - li.sort(some_function) # sort in place using user-defined comparison\n- tuples are immutable \n  - items can be of mixed types (inc collection types)\n- dict\n  - Dictionaries are unordered & work by hashing, so keys must be immutable\n  - Constant average time add, lookup, update\n- functions\n  - no fuction overloading, a function is specified by its name alone, even if they \n    have different input arguments\n  - operator overloading (overloading +, ==, -, etc.) can happen when you implement a class\n  - they are first class objects and first class citizens\n- classes\n  - subclasses: To define a subclass, put the name of the superclass in parentheses after the\n    subclass’s name on the first line of the definition \n  - You can implement operator overloading with magic methods\n    operators trigger a magic method, defined in a class\n  - We can call the Python function len() on any class that implements ```__len__``` .\n- list comprehesnion:\n  - li = [3, 6, 2, 7, 1, 9]\n  - [elem * 2 for elem in li if elem > 4]\n  - [12, 14, 18]\n- dictionary, set comprehension also exists\n  - d = { k: v for k,v in lst1 }\n  - s = { x for x in lst2 }\n- iterators\n  - have a ``` __next__()```  method\n    - they don't have a hasnext() method, just catch the StopIteration exception\n  - use memory efficiently\n- generators\n  - iterators\n  - Creating Generators: yield\n  - Less code than writing a standard iterator\n  - Maintains local state automatically\n  - Values are computed one at a time, as they’re needed\n  - Avoids storing the entire sequence in memory\n  - Good for aggregating (summing, counting) items. One pass.\n  - Crucial for infinite sequences\n  - Bad if you need to inspect the individual values\n    \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Immutable** - cannot be modified once created\n* **Tuple** - simple immutable ordered sequence of items\n* **List** - mutable ordered sequence of mixed types\n* **First class object** -  entitiy that can be dynamically created, destroyedm passed to a func, returned as a val\n* **First class citizens** - pass funcs as args to other funcs, return funcs from other funcs, assign funcs to vars or store\n* **Higher order functions** - higher order funcs take other funcs as inputs\n* **Subclass** - a class can extend the def of another class, allows the use of methords or atttributes in the previous class\n* **Magic methods** - allow user-defined classes to behave like built in types\n* **Duck typing** - establishes situbility of an object by determining presence of methods\n* **Iterator objects** - can be used in a for loop bc they have an ``` __iter__```  magic method\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In this chapter, we consider only the simplest environments: episodic, \nsingle agent, fully observable, deterministic, static, Discrete, known. \nWe distinguish between informed algorithms and uninformed algorithms, and Unknown environments.\n\nAssuming that agents have access to information about the world the agent can follow this\nfour phase problem solving process: goal formulation, problem formulation, search, and execution.\n  - in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\nDefining a problem:\n  - State space\n  - A set of one or more goal states\n  - The actions available to the agent\n  - A transitional model \n  - Action cost function\n\nAbstraction is valid if we can elaborate any abstract solution into a solution in the more \ndetailed world.\n\n\n## AIMA Chapter 3.2 Example Problems\n Real world vs theoretical examples\n\n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithms:\n  - Search tree over the state space graph\n  - Each node corresponds to a state\n  - Expand a node\n  - Generating a new node (child node/successor node)\n  - Each node has a parent node (first step)\n  - Frontier \n    - frontier separates state-space graph: \n      - an interior region where every state has been expanded\n      - exterior region of states that have not yet been reached\n \n``` \nfunction best-first-search(problem,f) returns a solution node or failure\n  node <- NODE(STATE=problem.initial)\n  frontier <- priority queue ordered by f, wiht node as an element\n  reached <- lookup table, wiht one entry wiht key problem.initial and a value node\n  while not is-empty(frontier) do\n    node <- pop(frontier)\n    if problem.is-goal(node.STATE) then return node\n    for each child in EXPAND(problem, node) do\n    s <- child.STATE\n    if s is not in reached or child.PATH-COST < reached[s].PATH-COST then \n      reached[s] <- child\n      add child to frontier\n  return failure\n``` \nnode in the tree represented by\n  - node.state: to which it corresponds\n  - node.parent: the node that generated it\n  - node.action: the action that was applied to the parent's state to get it\n  - node.path-cost: the cost of the path from the inital state to this node\nfrontier: queue of some kinds is appropriate bc the operations on it are:\n  - is-empty: returns true only if there are no nodes in the frontier\n  - pop: removes the top node from the frontier and returns it\n  - top: returns but does not remove the top node of the fronier\n  - add: inserts node into its proper place in the queue\nqueues:\n  - priority queue\n  - fifo queue\n  - lifo queue (stack)\nevaluate an algorithms performance:\n  - completeness\n  - cost optimality\n  - time complexity\n  - space complexity\nTo be complete a search algorithm must be systematic in the way it explores an infinite state\nState space complexity can be measured in terms of d the depth and m the maximum number\nof actions in any bath; and b the branching factor\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth-first-search\n``` \nfunction breadth-first-search(problem) returns a solution node or failure\n  node <- NODE(problem.INITIAL)\n  if problem.IS-GOAL(node.STATE) then return node\n  frontier <- a FIFO queue, with node as an element\n  reached <- {problem.INITIAL}\n  while not IS_EMPTY(frontier) do \n    node <- POP(frontier)\n    for each child in EXPAND(problem, node) do\n    s <- child.STATE\n    if problem.IS-GOAL(s) then return child\n    if s is not in reached then \n      add s to reached\n      add child to frontier\n    return failure\n    \n``` \n\n\n``` \nfunction uniform-cost-search(problem) returns a solution node, or failure\n  return best-first-search(problem, path-cost)\n\n``` \n\n\n``` \nfunction iterativ-deepening-search(problem) returns a solution node or failure\n  for depth = 0 to inf fo\n  result <- depth-limited-search(problem, depth)\n  if result != cutoof then return result\n\n``` \n\n\n``` \nfunction depth-limited-search(problem, l) returns a node or failure or cutoff\n  froniter <- a LIFO queue (stack) with Node(problem.INITIAL) as an element\n  result <- failure\n  while not IS-EMPTY(frontier) do\n    node <- POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node\n    if DEPTH(node) > l then \n      result <- cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do\n        add child to frontier\n  return result\n\n``` \n\n\n\n``` \nfunction BIBF-Search(problemF,fF, problemB, fB) returns a solution node or failure\n  nodeF <-(problemF>initial)\n  nodeB <-(problemB>initial)\n  frontierF <- priority queue ordered by fF, with nodeF as an element\n  frontierB <- priority queue ordered by fB, with nodeB as an element\n  reachedF <- lookup table, with one key nodeF.STATE and value nodeF\n  reachedB <- lookup table, with one key nodeB.STATE and value nodeB\n  solution <- Failure\n  while not TERMINATED(solution, frontierF, frontierB) do\n    if fF(TOP(frontierF))<fB(TOP(frontierB)) then\n      solution <- PROCEED(F, problemF, frontierF, reachedF, reached B, solution)\n    else solution <- PROCEED(B, problemB, frontierB, reachedB, reached F, solution)\n  return solution\n\n```\n\n\n``` \nfunction PROCEED(dir, problem, frontier, reached, reached2, solution) returns a solution\n  node <- POP(frontier)\n  for each child in EXPAND(problem,node) do \n  s <- child.STATE\n  if s not in reached or PATH-COST(child)<PATH-COST(reached[s]) then\n    reached[s]<-child\n    add child to frontier\n    if s in reached2 then \n      solution2 <- JOIN-NODES(dir, child, reached2[s])\n      if PATH-COST(solution2) < PATH-COST(solution) then\n        solution <- solution2\n  return solution\n\n  ``` \n\n\n## Module 3 Lecture Notes\n A problem-solving agent must planahead.\nThe computational process that it undertakes is called search.\nIt will consider a sequence of actions that form a path to a goal state.\nSuch a sequence is called a solution\n\nDefining a search problem:\n  - states: a set S\n  - Initial state\n  - Actions a set A\n    - the set of actions that can be executed in s, that are applicable in s\n  - Transition Model\n  - path cost - must be additive\n  - goal test\n    - s is a goal state if Goal(s) is true\nDecide:\n  - Which properties matter & how to represent\n    - Initial State, Goal State, Possible Intermediate States\n  - Which actions are possible & how to represent\n    - Operator Set: Actions and Transition Model\n  - Which action is next\n    - Path Cost Function\nState space must be abstracted for problem solving - easier than the real problem\n\nBreadth-first-search\n  - cost optimal for probs where all actions have the same cost\n  - complete - yes\n  - optimal - yes\n  - time O(b^d)\n  - memory O(b^d)\n  \nUnifrom cost search (Dijkstra's algorithm)\n  - complete - Yes\n  - cost optimal - Yes\n  - time O(b^(1 + [c*/e]))\n  - memory O(b^(1 + [c*/e]))\n  - uniform-cost search spreads out in waves of uniform path-cost\n  - when all costs are equal its similar ot breadth first search\nDepth first search\n  - complete - No\n  - optimal - No\n  - time O(b^m)\n  - memory O(bm)\n  - expands the deepest node in the frontier first\n  - finite spaces\n    - efficient and complete\n  - for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory\n  - backtracking search - depth firstbut they only generate one successor at a time\n    - memory O(m)\nDepth limited search\n  - complete - No\n  - optimal - No\n  - time complexity O(b^l)\n  - space complexity O(bl)\n  - To keep depth-first search from wandering down an infinite path\n  - supply a depth limit l\n  - and treat all nodes at depth l as if they had no successors \nIterative deepening search\n  - complete - yes\n  - optimal - yes\n  - time O(b^d) if there is a solution otherwise O(b^m)\n  - space O(bd) if there is a solution otherwise O(bm)\n\nIn general, iterative deepening is the preferred uninformed search method when the \nsearch state space is larger than can fit in memory and the depth of the solution \nis not known.\n\nBidirectional search\n  - complete - yes\n  - optimal cost - yes\n  - time O(b^d/2)\n  - space O(b^d/2)\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Unknown environment** - the agent can do no better than excecute an action at random\n* **Goal formulation** - what the agent wants the outcome to be, winning/bucharest/some end state\n* **Problem formulation** - a description of the states and actions necessary to reach a goal\n* **Search** - agent simulating sequences of actions until one reaches the goal\n* **Solution** - sequence of actions that reaches the goal, path to goal\n* **Exectution** - the agent can now execute the actions in the solution\n* **Open loop** - once the agent finds a soluton it ignores the percept and executes\n* **Closed loop** - if the agent needs feedback while executing to gaurantee it reaches the solution\n* **State space** - a set of all possible states the problem can be in\n* **Transistion model** - returns the state that results from doing action a in state s\n* **Action cost function** - numeric cost of applying action a in state s to reach state s'\n* **Path** - sequence of actions\n* **Optimal solution** - solution with the lowest path cost among all solutions\n* **Graph** - veticies are states and directed edges between them are actions\n* **Model** - abstract mathematical description\n* **Abstraction** - removing detail from a representation\n* **Level of abstraction** - how much detail is needed for a clear problem statements\n* **Standardizend problem** - illustrates or exercises various problem-solving methods, good benchmark for reshearches to compare\n* **Real world problem** - solutions are actually useful, formulation is idiosyncratic\n* **Grid world** - problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell\n* **Search algorithm** - takes a search problem as an input and returns a solution or failure\n* **Frontier** - a set of unexpanded nodes\n* **Reached** - if a node has been expanded\n* **Best first search** - choose a node n with min val of some evaluation function f(n)\n* **Expand a node** - by considering the available actions for that state, using transition model\n* **Priority queue** - pops the node wihtthe minimum cost according to some ecaluation function f\n* **Fifo queue** - pops the node that was added to the queue first\n* **Lifo queue** - pops the first most recently added node\n* **Repeated state** - if a node has been visited more than once\n* **Redundant path** - worse way to get to the same state\n* **Graph search** - checks for redundant paths\n* **Tree-like search** - does not check for redundant paths (less memory)\n* **Completeness** - is the algorithm guaranteed to find a solution when there is one (or report failure)\n* **Cost optimality** - does it find a solution wiht the lowest path cost of all solutions\n* **Time complexity** -  how long does it take to find a solution\n* **Space complexity** - how much memory is needed for the search\n* **Depth** - number of actions in an optimal solution\n* **Branching factor** - number of successors of a node that need to be consiered\n* **Early goal test** - checking if a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue\n* **Diameter** - of a state space graph, gives a good depth limit\n* **Search problem** - states, actions, performance measure\n* **State** - representation of a physical configuration\n* **Node** - data structure constituting part of a search tree\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) search strategies - use domain specific hits about the location of goals.\nh(n) = cheapest path\nGreedy best first search\n  - Expands first the node with the lowest h(n) value \n  - Appears to be closest to the goal\n  - Complete in finite state spaces but not in infinite ones\nA* search \n  - f(n) = g(n) + h(n)\n    - g(n) path cost from the initial state to node \n    - h(n) estimated cost of the shortest path from curr to a goal state\n  - complete\n  - if cost-optimal depends on certain properties of the heuristic. \n    - admissibility\n    - A slightly stronger property is called consistency\n  - A* with a consistent heuristic is optimally efficient\n  - A* is efficient because it prunes\n  - if inadmissible heuristic (may overestimate) then we risk missing the optimal solution\n    - the heuristic can potentially be more accurate, thereby reducing the number of nodes expanded\nbounded suboptimal search - solution that is guaranteed to be within a constant factor of the optimal cost. \n  - Weighted A* provides this guarantee\nunbounded-cost search - as long as we can find it quickly.\nspeedy search, which is a version of greedy best-first search that uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions. \nMemory bounded search\n  - Memory is split between the frontier and the reached states\n  - Some only keep one of the two places\n  - Or remove from reached when we can prove that they are no longer needed\niterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: \n  - IDA* 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. \nRecursive best-first search\n  - Standard best first search but using only linear space\n    - Recursive depth-first search with a f_limit\nMA* (memory-bounded A*) and SMA* (simplified MA*). \n  - SMA* proceeds just like A*, expanding the best leaf until memory is full. At \n  this point, it cannot add a new node to the search tree without dropping an old one.\n  always drops the worst leaf node—the one with the highest -value.\n  Like RBFS, SMA* then backs up the value of the forgotten node to its parent.\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Tile puzzle\n  - H1 = the number of misplaced tiles (not including blank)\n  - H2 = the sum of the distance of the tiles from their goal positions\nEffective branching factor b*\n  - N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\nbetter way to characterize the effect of A* pruning with a given heuristic  is that it reduces the effective depth by a constant compared to the true depth\nA problem with fewer restrictions on the actions is called a relaxed problem.\nComposite heuristic picks which func is most accurate on the node in question\nSubproblems \n  - Pattern databases store the solution cost for each possible sub problem\n  - with each additional database there are diminishing returns and increased memory \n  and computation costs.\n  - the sum of the two costs is still a lower bound on the cost of solving the entire problem\ncould generate a perfect heuristic by precomputing and storing the cost of the optimal \npath between every pair of vertices\n  - O(|V|^2) and O(|E|^3)\n better approach is to choose a few (perhaps 10 or 20) landmark points16 from the vertices. Then for each landmark  and for each other vertex  in the graph, we compute and store C*(v,L)\nshortcuts—artificial edges in the graph that define an optimal multi-action path.\n\nEach state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\neach state in a metalevel state space captures the internal (computational) state of a program that is searching in an ordinary state space such as the map of Romania.\nFor harder problems, there will be many such missteps, and a metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtrees.\n\n \n\n## Module 4 Lecture Notes\n A problem-solving agent must planahead.\nThe computational process that it undertakes is called search.\nIt will consider a sequence of actions that form a path to a goal state.\nSuch a sequence is called a solution\n\nDefining a search problem:\n  - states: a set S\n  - Initial state\n  - Actions a set A\n    - the set of actions that can be executed in s, that are applicable in s\n  - Transition Model\n  - path cost - must be additive\n  - goal test\n    - s is a goal state if Goal(s) is true\nDecide:\n  - Which properties matter & how to represent\n    - Initial State, Goal State, Possible Intermediate States\n  - Which actions are possible & how to represent\n    - Operator Set: Actions and Transition Model\n  - Which action is next\n    - Path Cost Function\nState space must be abstracted for problem solving - easier than the real problem\n\nBreadth-first-search\n  - cost optimal for probs where all actions have the same cost\n  - complete - yes\n  - optimal - yes\n  - time O(b^d)\n  - memory O(b^d)\n  \nUnifrom cost search (Dijkstra's algorithm)\n  - complete - Yes\n  - cost optimal - Yes\n  - time O(b^(1 + [c*/e]))\n  - memory O(b^(1 + [c*/e]))\n  - uniform-cost search spreads out in waves of uniform path-cost\n  - when all costs are equal its similar ot breadth first search\nDepth first search\n  - complete - No\n  - optimal - No\n  - time O(b^m)\n  - memory O(bm)\n  - expands the deepest node in the frontier first\n  - finite spaces\n    - efficient and complete\n  - for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory\n  - backtracking search - depth firstbut they only generate one successor at a time\n    - memory O(m)\nDepth limited search\n  - complete - No\n  - optimal - No\n  - time complexity O(b^l)\n  - space complexity O(bl)\n  - To keep depth-first search from wandering down an infinite path\n  - supply a depth limit l\n  - and treat all nodes at depth l as if they had no successors \nIterative deepening search\n  - complete - yes\n  - optimal - yes\n  - time O(b^d) if there is a solution otherwise O(b^m)\n  - space O(bd) if there is a solution otherwise O(bm)\n\nIn general, iterative deepening is the preferred uninformed search method when the \nsearch state space is larger than can fit in memory and the depth of the solution \nis not known.\n\nBidirectional search\n  - complete - yes\n  - optimal cost - yes\n  - time O(b^d/2)\n  - space O(b^d/2)\n\n## Module 4 Definitions\n* **Informed (heuristic) search strategies** - uses domain- specific hints about the loc of goals\n* **Heuristic** - cost of the cheapest path from the state at node n to a goal\n* **Straight line distance heuristic** - correlated with actual road distances\n* **Admissible heruistic** - one that never overestimates the cost to reach a goal, optimistic!\n* **Consistency** - h(n) is consistent if for every node n and successor n' we have h(n) <= c(n, a, n') + h(n')\n* **Triangle inewuality** - sides of a triangle cant be longer than the sum of the other 2 sides\n* **Contours** - ranges where the maps all have the same f(n), order to be expanded\n* **Monotonic** - the path cost always increases as you go along a path, because action costs are always positive\n* **Surely expanded nodes** - all nodes that can be reached from the inital state where f(n) < C*\n* **Optimally efficient** - algorithms that extends search paths from the initial state, with h(n), expands all nodes that are surely expanded by A*\n* **Prunes** - eliminates possibilites from consideration without having to examine them\n* **Satisficing** - solutions that are suboptimal but good enough\n* **Detour index** - multiplier applied to the straight line distance to account for curving roads\n* **Weighted a* search** - weight the heuristic value mroe heavilyf(n) + W x h(n)\n* **Bounded suboptimal search** - find a solution that is guaranteed to be within a constant factor  of the optimal cost (Weighted A*)\n* **Bounded cost search** - solution whose cost is less than some constant \n* **Unbounded-cost search** - accept a solution of any cost\n* **Speedy search** - heuristic is the num actions required to reach a goal regardless of theri cost\n* **Refrence counts** - track the num times a state has been reached -> remove it when out of ways to reach it\n* **Beam search** - limits the size of the frontier, keep only the k nodes with teh best f-scores\n* **Iterative - deepening a* search** - all the benefits of A* without the requirement to keep all reached states in memory\n* **Recursive best-first search** - mimic the operation of standard bes-first search but using linear space\n* **Backed up value** - best value of its children\n* **Front-to-end search** - hF estimates the distance to the goal and hB estimates distance to start\n* **Front-to-front** - estimates the distance to the other fronier\n* **Manhattan distance** - city block distance, sum of horizontal and vertical distances\n* **Effective branching factor b*** - nodes N,depth is d then b* is the branching factor to have N + 1 nodes\n* **Effective depth** - reduce the search cost\n* **Dominates** - if one heruistic expands more valid nodes than another\n* **Relaxed problem** - fewer restrictions of the actions\n* **Pattern databases** - store solutions for possible subproblems \n* **Disjoint pattern databases** - dont record the total cost but the number of moves\n* **Precomputation** - generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices\n* **Shortcuts** - artificial edges in teh fraph that define and optimal multi-action path\n* **Differential heuristic** - hDH(n) = max |C*(n,L)-C*(goal,L)|\n* **Metalevel state space** - captures the internal (computational) state of a program that is searching\n* **Object level state space** - state of a program\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Three stances to take towards multi-agetn environments:\n  - consider them like in the aggregate as an economy \n  - consider them as just a part of the environment- part that makes it nondeterministic\n  - explicitly model the adversarial agetns with techniques of adversarial game-tree search\nevery time we stop searching we ask who is winning\n  - evaluation function\n  - average the outcomes of many fast simulations of the game to the end\nGame can be formally defined with:\n  - S0 - the initial state\n  - TO-MOVE(s) - the player who's turn it is to move in the state s\n  - ACTIONS(s) the set of legal moves in s\n  - RESULT(s,a) the transistion model\n  - IS-TERMINAL(s) - terminal test\n  - UTILITY(s,p) - utility function\nState space graph is defined by:\n  - initial state\n  - actions function\n  - result function  \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n minimax search\n  - for games with multiple outcome scores - more general algorithm \n  - Max prefers to move to a state of maximum value when it is Max’s turn to move, \n  and Min prefers a state of minimum value (that is, minimum value for Max and thus \n  maximum value for Min)\n  - time complexity is O(b^m)\n  - space complexity\n    - all actions at once O(bm)\n    - one action at a time O(m)\nHumans make alliances in Games\n  - how can a computer mimic this? \n\nminimax: \n```\nfunction minimax-search(game,state) returns an action\n  player <- game.TO-MOVE(state)\n  value, move <-MAX-VALUE(game,state)\n  return move\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- -infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n      v, move <- v2, a\n  return v, move\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- +infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move <- v2, a\n  return v, move\n```\nAlpha Beta Pruning\n  - Num game states is exponential in the depth of the tree\n  - Can immediately prune large states of the tree\n  - the value of the root/the minimax decision are independent of the values of the leaves  and , therefore they can be pruned.\n\n\n```\nfunction alpha-beta-search(game,state, alpha, beta) returns an action\n  player <- game.TO-MOVE(state)\n  value, move <- MAX-VALUE(game,state, -inf, +inf)\n  return move\nfunction MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- -infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n    if v2 > v then\n      v, move <- v2, a\n      alpha <- MAX(alpha, v)\n    if v >= betha then return v, move\n  return v, move\nfunction MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v <- +infinity\n  for each a in game.ACTIONS(state) do\n    v2,a2 <- MAX-VALUE(game, game.RESULT(state, a), alpha, beta)\n    if v2 < v then\n      v, move <- v2, a\n      beta <- MIN(beta, v)\n    if v <= alpha then return v,move\n  return v, move\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Economy** - predict that increasing demand will raise prices, without predicting agent actions\n* **Evaluation function** - treating nonterminal nodes as if they were terminal\n* **Imperfect information** - games with an element of chance\n* **Perfect information** - fully observable\n* **Zero-sum games** - what is good for one player is just as bad for the other\n* **Move** - action\n* **Position** - state\n* **Terminal test** - true when the game is voer\n* **Terminal states** - states where the game has ended\n* **Transition model** - defines the state resulting from taking action a in state s\n* **Utility function** - defines teh numeric valute ot player p when the game ends in terminal state s\n* **State space graph** - verticies are states, edges are moves, state might be reached by multiple paths\n* **Game tree** - search tree that follows every sequence of moves to the termial state\n* **Ply** - one move by one player\n* **Minimax value** - utility (for MAX) being in that state, assuming both players play optimally\n* **Minimax decisison** - the action a that is the optimal choice for MAX because it leads to the highest minimax value\n* **Backs up** - goes all the way down the leaves of the tree then goes up as recursion unwinds\n* **Alliance** - made and broke as the game goes along\n* **Alpha-beta pruning** - prunes subtrees\n* **Iterative deepening** - search one ply at a time\n* **Killer moves** - best moves\n* **Transpositions** - diff permutations of the move sequence that end up in the same position\n* **Transposition table** - catches the heuristic value of states\n* **Type a strategy** - all possible moves to a depth and uses h(n) to estimate expected utility\n* **Type b strategy** - ignores moves that look bad, follows promising lines as far as possible\n* **Cutoff test** - returns true for terminal states\n* **Features** - define categories or equivalence classes of states\n* **Expected value** - determined fro each catefory of states resulting in an eval func that works for any state\n* **Material value** - val for a piece (ie king is 10 etc\n* **** - \n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}