{
  "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": "6fb04d41-be5d-4993-9db3-d80e0816b2f1"
      },
      "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": "67307672-b67c-4578-aa29-fcf3aa6224b0"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Some consider intelligence to be a property of internal thought processes and reasoning, \n",
        "while others focus on intelligent behavior, an external characterization.\n",
        "\n",
        "Computer need following capabilities to pass turing tests:\n",
        "1. natural language processing to communicate successfully in a human language;\n",
        "2. knowledge representation to store what it knows or hears;\n",
        "3. knowledge representation to store what it knows or hears;\n",
        "4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n",
        "\n",
        "Turing viewed the physical simulation of a person as unnecessary to demonstrate intelligence.\n",
        "\n",
        "To pass turing test, robot needs computer vision and speech recognition to perceive the world and\n",
        "robotics to manipulate objects and move about.\n",
        "\n",
        "Learn human thoughts in 3 ways:\n",
        "1. introspection—trying to catch our own thoughts as they go by;\n",
        "2. psychological experiments—observing a person in action;\n",
        "3. brain imaging—observing the brain in action.\n",
        "\n",
        "Syllogisms:\n",
        "Provided patterns for argument structures that always yielded correct conclusions \n",
        "when given correct premises. \n",
        "\n",
        "Logic:\n",
        "as conventionally understood requires knowledge of the world that \n",
        "is certain—a condition that, in reality, is seldom achieved. \n",
        "\n",
        "Agent acting:\n",
        "All the skills needed for the Turing test also allow an agent to act rationally. \n",
        "Knowledge representation and reasoning enable agents to reach good decisions.\n",
        "\n",
        "Rational-agent approach advantages:\n",
        "First, it is more general than the “laws of thought” approach because correct inference \n",
        "is just one of several possible mechanisms for achieving rationality. \n",
        "Second, it is more amenable to scientific development.\n",
        "\n",
        "Standard model bad in long run, because it assumes we supply fully specified objective to machine.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \n",
        "Turing’s “argument from informality of behavior” says that human behavior is far too complex \n",
        "to be captured by any formal set of rules—humans must be using some informal guidelines that \n",
        "(the argument claims) could never be captured in a formal set of rules and thus could never be \n",
        "codified in a computer program.\n",
        "\n",
        "Good Old-Fashioned AI (GOFAI):\n",
        "Artificial intelligence pursued within the cult of computationalism stands \n",
        "not even a ghost of a chance of producing durable results.\n",
        "GOFAI corresponds to the simplest logical agent design described in Chapter 7, \n",
        "and we saw there that it is indeed difficult to capture every contingency of appropriate \n",
        "behavior in a set of necessary and sufficient logical rules; \n",
        "we called that the qualification problem. \n",
        "\n",
        "Embodied cognition:\n",
        "it makes no sense to consider the brain separately: \n",
        "cognition takes place within a body, which is embedded in an environment. \n",
        "We need to study the system as a whole; the brain’s functioning exploits \n",
        "regularities in its environment, including the rest of its body. \n",
        "Under the embodied cognition approach, robotics, vision, and other sensors become central, \n",
        "not peripheral.\n",
        "\n",
        "Gödel sentence G(F) with the following properties:\n",
        "G(F) is a sentence of F, but cannot be proved within F.\n",
        "If F is consistent, then G(F) is true.\n",
        "\n",
        "Second, Gödel’s incompleteness theorem and related results apply to mathematics, not to computers. \n",
        "No entity—human or machine—can prove things that are impossible to prove.\n",
        "\n",
        "Third, Gödel’s incompleteness theorem technically applies only to formal systems that are \n",
        "powerful enough to do arithmetic. This includes Turing machines, and Lucas’s claim is in \n",
        "part based on the assertion that computers are equivalent to Turing machines. \n",
        "\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "Biological naturalism\n",
        "mental states are high-level emergent features that are caused by low-level physical processes \n",
        "in the neurons, and it is the (unspecified) properties of the neurons that matter:\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "An agent is anything that can be viewed as perceiving its environment through sensors \n",
        "and acting upon that environment through actuators.\n",
        "\n",
        "In general, an agent’s choice of action at any given instant can depend on its built-in \n",
        "knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n",
        "\n",
        "External/Internal of agents.\n",
        "Agent function table is external characterization of the agent. \n",
        "Internally, the agent function for an artificial agent will be implemented by an agent program.\n",
        "t is important to keep these two ideas distinct. \n",
        "The agent function is an abstract mathematical description; \n",
        "the agent program is a concrete implementation, running within some physical system.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "What is rational at any given time depends on four things:\n",
        "- The performance measure that defines the criterion of success.\n",
        "- The agent’s prior knowledge of the environment.\n",
        "- The actions that the agent can perform.\n",
        "- The agent’s percept sequence to date.\n",
        "\n",
        "omniscient agent：\n",
        "knows the actual outcome of its actions and can act accordingly; \n",
        "but omniscience is impossible in reality.\n",
        "\n",
        "Rationality VS perfection:\n",
        "Rationality is not the same as perfection. Rationality maximizes expected performance, \n",
        "while perfection maximizes actual performance. \n",
        "Our definition of rationality does not require omniscience, \n",
        "then, because the rational choice depends only on the percept sequence to date.\n",
        "\n",
        "Learning:\n",
        "The agent’s initial configuration could reflect some prior knowledge of the environment, \n",
        "but as the agent gains experience this may be modified and augmented. \n",
        "There are extreme cases in which the environment is completely known a priori and \n",
        "completely predictable.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "Task environments：\n",
        "Essentially the “problems” to which rational agents are the “solutions.”\n",
        "\n",
        "Performance, Environment, Actuators, Sensors (PEAS):\n",
        "Performance: Desirable qualities. \n",
        "Evironment: The more restricted the environment, the easier the design problem.\n",
        "Actuators: Taxi driver, party that is controlling. \n",
        "Sensors: Video camers, ultrasound etc. \n",
        "\n",
        "Fully observable environment benefit:\n",
        "Fully observable environments are convenient because the agent need \n",
        "not maintain any internal state to keep track of the world.\n",
        "\n",
        "Partially observable:\n",
        "An environment might be partially observable because of noisy and inaccurate sensors or \n",
        "because parts of the state are simply missing from the sensor data\n",
        "\n",
        "Single VS multi-agent:\n",
        "If competitive or cooperative. \n",
        "\n",
        "Deterministic vs nondeterministic:\n",
        "If the next state of the environment is completely determined by the current state and \n",
        "the action executed by the agent(s), \n",
        "then we say the environment is deterministic; otherwise, it is nondeterministic.\n",
        "In principle, an agent need not worry about uncertainty in a fully observable, \n",
        "deterministic environment. If the environment is partially observable, \n",
        "however, then it could appear to be nondeterministic.\n",
        "\n",
        "Episodic vs sequential:\n",
        "Single action in atomic episdeos, each episode receives a percept and performs a single action.\n",
        "Otherwise, it is sequential, lke chess and taxi driving. Short term actions can have long \n",
        "term consequences. \n",
        "Episodic environments are much simpler than sequential environments \n",
        "because the agent does not need to think ahead.\n",
        "\n",
        "Discrete vs continuous:\n",
        "The discrete/continuous distinction applies to the state of the environment, \n",
        "to the way time is handled, and to the percepts and actions of the agent.\n",
        "Taxi is continuous. Chess is discrete. \n",
        "\n",
        "Hardest environment.\n",
        "The hardest case is partially observable, multiagent, nondeterministic, \n",
        "sequential, dynamic, continuous, and unknown.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "Agent = architecture + program\n",
        "\n",
        "Agent programs:\n",
        "The agent programs that we design in this book all have the same skeleton: \n",
        "they take the current percept as input from the sensors and return an action to the actuators.\n",
        "5 Notice the difference between the agent program, which takes the current percept as input, \n",
        "and the agent function, which may depend on the entire percept history. \n",
        "The agent program has no choice but to take just the current percept as input because \n",
        "nothing more is available from the environment; if the agent’s actions need to \n",
        "depend on the entire percept sequence, \n",
        "the agent will have to remember the percepts.\n",
        "\n",
        "Key challenge for AI:\n",
        "The key challenge for AI is to find out how to write programs that, to the extent possible, \n",
        "produce rational behavior from a smallish program rather than from a vast table.\n",
        "\n",
        "Model-based reflex agents:\n",
        "The most effective way to handle partial observability is for the agent to keep track \n",
        "of the part of the world it can’t see now. \n",
        "That is, the agent should maintain some sort of internal state that depends on the percept history and \n",
        "thereby reflects at least some of the unobserved aspects of the current state.\n",
        "\n",
        "Utility function:\n",
        "An internalization of the performance measure. \n",
        "Provided that the internal utility function and the external performance measure are in agreement, \n",
        "an agent that chooses actions to maximize its utility will be rational according to the external \n",
        "performance measure.\n",
        "A utility-based agent has many advantages in terms of flexibility and learning\n",
        "\n",
        "Learning agents:\n",
        "A learning agent can be divided into four conceptual components.\n",
        "The most important distinction is between the learning element, \n",
        "which is responsible for making improvements, and the performance element, \n",
        "which is responsible for selecting external actions. \n",
        "The performance element is what we have previously considered to be the entire agent: \n",
        "it takes in percepts and decides on actions. The learning element uses feedback from the \n",
        "critic on how the agent is doing and determines how the performance element should be modified \n",
        "to do better in the future.\n",
        "The critic tells the learning element how well the agent is \n",
        "doing with respect to a fixed performance standard.\n",
        "The last component of the learning agent is the problem generator. \n",
        "It is responsible for suggesting actions that will lead to new and informative experiences.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "An agent is specified by an agent function that maps a \n",
        "sequence of percept vectors P to an action a from a setA.\n",
        "\n",
        "The agent program runs on the physical architecture to produce f.\n",
        "\n",
        "For each possible percept sequence P, a rational agent selects an action\n",
        "that masimizes the expected value of its performance measure. \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"Rational agent\" : \"Agent that acts to get best outcome, or when with uncertainty the best expected outcome\",\n",
        "\"Turing test\" : \"Behavior test. Experiment that sidestep the vagueness whether can a machine think.\",\n",
        "\"Pass turing test\" : \"Cannot tell if a response came from human or machine.\",\n",
        "\"Cognitive Science\" : \"Cognitive science is the interdisciplinary, scientific study of the mind and its processes. \",\n",
        "\"General model\" : \"Creation of agents that focus on doing right things with best expected outcome with ML and probability theory.\",\n",
        "\"Limited rationality\" : \"Act appropriately give limited time ans resources, unable to finish all computations\",\n",
        "\"Value alignment proble\" : \"Different between our true aim and objective given to machine.\",\n",
        "\"Weak AI\" : \"Act as if intelligent.\",\n",
        "\"Strong AI\" : \"Actually think by its own, and not doing simulation.\",\n",
        "\"General AI & Human-level AI\" : \"Strong AI\",\n",
        "\"percept\" : \"What agent's sensor are perceiving\",\n",
        "\"percept seqeunce\" : \"everything full compilation of what agent perceived\",\n",
        "\"agent function\" : \"Defines agent's behaviour, map any given percent sequence to agent's action.\",\n",
        "\"Information gathering\" : \"Perform action to influence percepts in future\",\n",
        "\"Priori\" : \"Applied to knowledge considered to be true without being based on previous experience or observation\",\n",
        "\"Autonomy\" : \"Autonomous agent learn by itself and compensate for incorrect prior knowledge.\",\n",
        "\"Fully observable\" : \"Sensor gives full aspect at each point in time, all espects relevant to decision.\",\n",
        "\"Unobservable\" : \"No sensor at all.\",\n",
        "\"stochastic \" : \"Nondeterministic.\",\n",
        "\"Dynamic\" : \"Environment changes during agent action by time.\",\n",
        "\"Semidynamic \" : \"Environment changes due to agent action but not time.\",\n",
        "\"Single reflex agent\" : \"Action based on current percept, ignore percept history.\",\n",
        "\"Transition model \" : \"Know how the world works, implemented in simple boolean circuits like braking to stop.\",\n",
        "\"Sensor model \" : \"Know what the agent's sensor percept is about.\",\n",
        "\"Model-based agent \" : \"Model that uses transition and sensor model.\",\n",
        "\"Atomic representation\" : \"Each state of world is divisble, no internal structure.\",\n",
        "\"Factored representation\" : \"State can be sliced to fixed set of variable or attributes.\",\n",
        "\"Structured representation\" : \"Objects can be described explicitly\",\n",
        "\"Localist representation\" : \"1-1 mapping between concepts and meory locations.\",\n",
        "\"Distributed representation\" : \"1 to many mapping, memory location to multiple different concepts\",\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
        },
        "outputId": "7e9e2cad-9556-4631-daa7-6bd293e3aaf5"
      },
      "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 Some consider intelligence to be a property of internal thought processes and reasoning, \nwhile others focus on intelligent behavior, an external characterization.\n\nComputer need following capabilities to pass turing tests:\n1. natural language processing to communicate successfully in a human language;\n2. knowledge representation to store what it knows or hears;\n3. knowledge representation to store what it knows or hears;\n4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nTuring viewed the physical simulation of a person as unnecessary to demonstrate intelligence.\n\nTo pass turing test, robot needs computer vision and speech recognition to perceive the world and\nrobotics to manipulate objects and move about.\n\nLearn human thoughts in 3 ways:\n1. introspection—trying to catch our own thoughts as they go by;\n2. psychological experiments—observing a person in action;\n3. brain imaging—observing the brain in action.\n\nSyllogisms:\nProvided patterns for argument structures that always yielded correct conclusions \nwhen given correct premises. \n\nLogic:\nas conventionally understood requires knowledge of the world that \nis certain—a condition that, in reality, is seldom achieved. \n\nAgent acting:\nAll the skills needed for the Turing test also allow an agent to act rationally. \nKnowledge representation and reasoning enable agents to reach good decisions.\n\nRational-agent approach advantages:\nFirst, it is more general than the “laws of thought” approach because correct inference \nis just one of several possible mechanisms for achieving rationality. \nSecond, it is more amenable to scientific development.\n\nStandard model bad in long run, because it assumes we supply fully specified objective to machine.\n\n\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n \nTuring’s “argument from informality of behavior” says that human behavior is far too complex \nto be captured by any formal set of rules—humans must be using some informal guidelines that \n(the argument claims) could never be captured in a formal set of rules and thus could never be \ncodified in a computer program.\n\nGood Old-Fashioned AI (GOFAI):\nArtificial intelligence pursued within the cult of computationalism stands \nnot even a ghost of a chance of producing durable results.\nGOFAI corresponds to the simplest logical agent design described in Chapter 7, \nand we saw there that it is indeed difficult to capture every contingency of appropriate \nbehavior in a set of necessary and sufficient logical rules; \nwe called that the qualification problem. \n\nEmbodied cognition:\nit makes no sense to consider the brain separately: \ncognition takes place within a body, which is embedded in an environment. \nWe need to study the system as a whole; the brain’s functioning exploits \nregularities in its environment, including the rest of its body. \nUnder the embodied cognition approach, robotics, vision, and other sensors become central, \nnot peripheral.\n\nGödel sentence G(F) with the following properties:\nG(F) is a sentence of F, but cannot be proved within F.\nIf F is consistent, then G(F) is true.\n\nSecond, Gödel’s incompleteness theorem and related results apply to mathematics, not to computers. \nNo entity—human or machine—can prove things that are impossible to prove.\n\nThird, Gödel’s incompleteness theorem technically applies only to formal systems that are \npowerful enough to do arithmetic. This includes Turing machines, and Lucas’s claim is in \npart based on the assertion that computers are equivalent to Turing machines. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nBiological naturalism\nmental states are high-level emergent features that are caused by low-level physical processes \nin the neurons, and it is the (unspecified) properties of the neurons that matter:\n \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors \nand acting upon that environment through actuators.\n\nIn general, an agent’s choice of action at any given instant can depend on its built-in \nknowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n\nExternal/Internal of agents.\nAgent function table is external characterization of the agent. \nInternally, the agent function for an artificial agent will be implemented by an agent program.\nt is important to keep these two ideas distinct. \nThe agent function is an abstract mathematical description; \nthe agent program is a concrete implementation, running within some physical system.\n\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWhat is rational at any given time depends on four things:\n- The performance measure that defines the criterion of success.\n- The agent’s prior knowledge of the environment.\n- The actions that the agent can perform.\n- The agent’s percept sequence to date.\n\nomniscient agent：\nknows the actual outcome of its actions and can act accordingly; \nbut omniscience is impossible in reality.\n\nRationality VS perfection:\nRationality is not the same as perfection. Rationality maximizes expected performance, \nwhile perfection maximizes actual performance. \nOur definition of rationality does not require omniscience, \nthen, because the rational choice depends only on the percept sequence to date.\n\nLearning:\nThe agent’s initial configuration could reflect some prior knowledge of the environment, \nbut as the agent gains experience this may be modified and augmented. \nThere are extreme cases in which the environment is completely known a priori and \ncompletely predictable.\n\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nTask environments：\nEssentially the “problems” to which rational agents are the “solutions.”\n\nPerformance, Environment, Actuators, Sensors (PEAS):\nPerformance: Desirable qualities. \nEvironment: The more restricted the environment, the easier the design problem.\nActuators: Taxi driver, party that is controlling. \nSensors: Video camers, ultrasound etc. \n\nFully observable environment benefit:\nFully observable environments are convenient because the agent need \nnot maintain any internal state to keep track of the world.\n\nPartially observable:\nAn environment might be partially observable because of noisy and inaccurate sensors or \nbecause parts of the state are simply missing from the sensor data\n\nSingle VS multi-agent:\nIf competitive or cooperative. \n\nDeterministic vs nondeterministic:\nIf the next state of the environment is completely determined by the current state and \nthe action executed by the agent(s), \nthen we say the environment is deterministic; otherwise, it is nondeterministic.\nIn principle, an agent need not worry about uncertainty in a fully observable, \ndeterministic environment. If the environment is partially observable, \nhowever, then it could appear to be nondeterministic.\n\nEpisodic vs sequential:\nSingle action in atomic episdeos, each episode receives a percept and performs a single action.\nOtherwise, it is sequential, lke chess and taxi driving. Short term actions can have long \nterm consequences. \nEpisodic environments are much simpler than sequential environments \nbecause the agent does not need to think ahead.\n\nDiscrete vs continuous:\nThe discrete/continuous distinction applies to the state of the environment, \nto the way time is handled, and to the percepts and actions of the agent.\nTaxi is continuous. Chess is discrete. \n\nHardest environment.\nThe hardest case is partially observable, multiagent, nondeterministic, \nsequential, dynamic, continuous, and unknown.\n\n\n\n## AIMA 2.4 The Structure of Agents\n \nAgent = architecture + program\n\nAgent programs:\nThe agent programs that we design in this book all have the same skeleton: \nthey take the current percept as input from the sensors and return an action to the actuators.\n5 Notice the difference between the agent program, which takes the current percept as input, \nand the agent function, which may depend on the entire percept history. \nThe agent program has no choice but to take just the current percept as input because \nnothing more is available from the environment; if the agent’s actions need to \ndepend on the entire percept sequence, \nthe agent will have to remember the percepts.\n\nKey challenge for AI:\nThe key challenge for AI is to find out how to write programs that, to the extent possible, \nproduce rational behavior from a smallish program rather than from a vast table.\n\nModel-based reflex agents:\nThe most effective way to handle partial observability is for the agent to keep track \nof the part of the world it can’t see now. \nThat is, the agent should maintain some sort of internal state that depends on the percept history and \nthereby reflects at least some of the unobserved aspects of the current state.\n\nUtility function:\nAn internalization of the performance measure. \nProvided that the internal utility function and the external performance measure are in agreement, \nan agent that chooses actions to maximize its utility will be rational according to the external \nperformance measure.\nA utility-based agent has many advantages in terms of flexibility and learning\n\nLearning agents:\nA learning agent can be divided into four conceptual components.\nThe most important distinction is between the learning element, \nwhich is responsible for making improvements, and the performance element, \nwhich is responsible for selecting external actions. \nThe performance element is what we have previously considered to be the entire agent: \nit takes in percepts and decides on actions. The learning element uses feedback from the \ncritic on how the agent is doing and determines how the performance element should be modified \nto do better in the future.\nThe critic tells the learning element how well the agent is \ndoing with respect to a fixed performance standard.\nThe last component of the learning agent is the problem generator. \nIt is responsible for suggesting actions that will lead to new and informative experiences.\n\n\n## Module 1 Lecture Notes\n\nAn agent is specified by an agent function that maps a \nsequence of percept vectors P to an action a from a setA.\n\nThe agent program runs on the physical architecture to produce f.\n\nFor each possible percept sequence P, a rational agent selects an action\nthat masimizes the expected value of its performance measure. \n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - Agent that acts to get best outcome, or when with uncertainty the best expected outcome\n* **Turing test** - Behavior test. Experiment that sidestep the vagueness whether can a machine think.\n* **Pass turing test** - Cannot tell if a response came from human or machine.\n* **Cognitive science** - Cognitive science is the interdisciplinary, scientific study of the mind and its processes. \n* **General model** - Creation of agents that focus on doing right things with best expected outcome with ML and probability theory.\n* **Limited rationality** - Act appropriately give limited time ans resources, unable to finish all computations\n* **Value alignment proble** - Different between our true aim and objective given to machine.\n* **Weak ai** - Act as if intelligent.\n* **Strong ai** - Actually think by its own, and not doing simulation.\n* **General ai & human-level ai** - Strong AI\n* **Percept** - What agent's sensor are perceiving\n* **Percept seqeunce** - everything full compilation of what agent perceived\n* **Agent function** - Defines agent's behaviour, map any given percent sequence to agent's action.\n* **Information gathering** - Perform action to influence percepts in future\n* **Priori** - Applied to knowledge considered to be true without being based on previous experience or observation\n* **Autonomy** - Autonomous agent learn by itself and compensate for incorrect prior knowledge.\n* **Fully observable** - Sensor gives full aspect at each point in time, all espects relevant to decision.\n* **Unobservable** - No sensor at all.\n* **Stochastic ** - Nondeterministic.\n* **Dynamic** - Environment changes during agent action by time.\n* **Semidynamic ** - Environment changes due to agent action but not time.\n* **Single reflex agent** - Action based on current percept, ignore percept history.\n* **Transition model ** - Know how the world works, implemented in simple boolean circuits like braking to stop.\n* **Sensor model ** - Know what the agent's sensor percept is about.\n* **Model-based agent ** - Model that uses transition and sensor model.\n* **Atomic representation** - Each state of world is divisble, no internal structure.\n* **Factored representation** - State can be sliced to fixed set of variable or attributes.\n* **Structured representation** - Objects can be described explicitly\n* **Localist representation** - 1-1 mapping between concepts and meory locations.\n* **Distributed representation** - 1 to many mapping, memory location to multiple different concepts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "String foratting:\n",
        "print(\"%doge \")\n",
        "String is immutable.\n",
        "s=\"doge\"\n",
        "s.upper() gives DOG\n",
        "s.capitalize() gives Dog\n",
        "dog = \"do--ge\"\n",
        "dog = dog.strip('--ge') gives 'do'\n",
        "\n",
        "List:\n",
        "lst.index(\"b\") # index of first occurrence\n",
        "lst.count(\"b\") # count occurrence\n",
        "lst.remove(\"b\")\n",
        "lst.reverse()\n",
        "lst.sort()\n",
        "sorted(lst) #return a copy sorted\n",
        "\n",
        "Dictionary:\n",
        "dict.values() # gives list of values\n",
        "dict.keys() # gives list of keys\n",
        "dict.items() # list item tuples\n",
        "\n",
        "functions:\n",
        "def print_everything(*args) # accept variable number of non-keyword arguments\n",
        "//accepted as tuples. So (1,2,3) [1] is 2. But ([1,2,3]) is one element.\n",
        "def doge(**args); doge(meow = 1, cat = 2, dash =3); gives \n",
        "{'meow': 1, 'cat': 2, 'dash': 3}\n",
        "// ** is for variable number of keyword arguments\n",
        "\n",
        "Class:\n",
        "class Student:\n",
        "  def __init__(self, name, dept):  # constructor\n",
        "class AI_Student(Student): #this is sub class\n",
        "// During multiple inheritance, follow the front one function\n",
        "super().foo() # parent function foo() called\n",
        "\n",
        "Class magic methods:\n",
        "__str__(self) changes how print works\n",
        "len defines how len(obj) works\n",
        "copy defines how to copy a class\n",
        "cmp defines ==\n",
        "add defines +\n",
        "neg defines how unary negation works for class\n",
        "\n",
        "Iterators: (memory efficient because not storing)\n",
        "Iterable objects can be used in a for loop because have __iter__\n",
        "lst.__iter__()\n",
        "Iterators has __next__() method, throws StopIteration when done\n",
        "i = iter(k) \n",
        "lst.next(i) # produce first result\n",
        "lst.next() # will produce result\n",
        "\n",
        "Generators:\n",
        "yield\n",
        "Each time we call __next__, method runs until encounters yield statement\n",
        "Maintains local state automatically\n",
        "Bad if need to inspect individual values\n",
        "\n",
        "lambda:\n",
        "lst = [x for x in range(1, 101)]\n",
        "for n in nums: s.appendx*x same as [x*x for x in nums]\n",
        "[n*3 for (x,n) in lst] gives [3n,3n,3n]\n",
        "[elem*2 for elem in lst if elem > 4]\n",
        "\n",
        "Import:\n",
        "pip install package_name\n",
        "In Colab, run !pip install nltk\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 484
        },
        "outputId": "31f9dba2-3159-4bab-c2d9-85b6a1f6b230"
      },
      "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 \nString foratting:\nprint(\"%doge \")\nString is immutable.\ns=\"doge\"\ns.upper() gives DOG\ns.capitalize() gives Dog\ndog = \"do--ge\"\ndog = dog.strip('--ge') gives 'do'\n\nList:\nlst.index(\"b\") # index of first occurrence\nlst.count(\"b\") # count occurrence\nlst.remove(\"b\")\nlst.reverse()\nlst.sort()\nsorted(lst) #return a copy sorted\n\nDictionary:\ndict.values() # gives list of values\ndict.keys() # gives list of keys\ndict.items() # list item tuples\n\nfunctions:\ndef print_everything(*args) # accept variable number of non-keyword arguments\n//accepted as tuples. So (1,2,3) [1] is 2. But ([1,2,3]) is one element.\ndef doge(**args); doge(meow = 1, cat = 2, dash =3); gives \n{'meow': 1, 'cat': 2, 'dash': 3}\n// ** is for variable number of keyword arguments\n\nClass:\nclass Student:\n  def __init__(self, name, dept):  # constructor\nclass AI_Student(Student): #this is sub class\n// During multiple inheritance, follow the front one function\nsuper().foo() # parent function foo() called\n\nClass magic methods:\n__str__(self) changes how print works\nlen defines how len(obj) works\ncopy defines how to copy a class\ncmp defines ==\nadd defines +\nneg defines how unary negation works for class\n\nIterators: (memory efficient because not storing)\nIterable objects can be used in a for loop because have __iter__\nlst.__iter__()\nIterators has __next__() method, throws StopIteration when done\ni = iter(k) \nlst.next(i) # produce first result\nlst.next() # will produce result\n\nGenerators:\nyield\nEach time we call __next__, method runs until encounters yield statement\nMaintains local state automatically\nBad if need to inspect individual values\n\nlambda:\nlst = [x for x in range(1, 101)]\nfor n in nums: s.appendx*x same as [x*x for x in nums]\n[n*3 for (x,n) in lst] gives [3n,3n,3n]\n[elem*2 for elem in lst if elem > 4]\n\nImport:\npip install package_name\nIn Colab, run !pip install nltk\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "Goal formulation:\n",
        "Goals organize behavior by limiting the objectives and hence the actions to be considered.\n",
        "\n",
        "Problem formulation:\n",
        "The agent devises a description of the states and actions necessary to reach the \n",
        "goal—an abstract model of the relevant part of the world.\n",
        "Consider actions of traveling from one to adjacent city. \n",
        "\n",
        "Search & Solution:\n",
        "Before taking any action in the real world, the agent simulates sequences of actions in its model, \n",
        "searching until it finds a sequence of actions that reaches the goal.\n",
        "This seqeunce is called Solution. May simulate multiple seqeunces. \n",
        "It is an important property that in a fully observable, deterministic, known environment, \n",
        "the solution to any problem is a fixed sequence of actions.\n",
        "If the model is correct, then once the agent has found a solution, \n",
        "it can ignore its percepts while it is executing the actions.\n",
        "\n",
        "In partially observable or nondeterministic environments, \n",
        "a solution would be a branching strategy that recommends different future actions depending \n",
        "on what percepts arrive.\n",
        "\n",
        "Execution:\n",
        "Exxcute action in the solution one at a time. \n",
        "\n",
        "Problem definition:\n",
        "- State space\n",
        "- Initial state : Where agent starts in, like Arad.\n",
        "- Goal states: A set of one or more goal states. \n",
        "- Actions: Actions available to agent.\n",
        "- Transition model: Describes what each action does. Result (s,a) returns state\n",
        "from doing action a in state s.\n",
        "- Action cost function: Denoted by action cost-(s, a s'), gives numeric cost \n",
        "of applyiong action a in state s to reach state s'.\n",
        "\n",
        "Good problem formulation has right level of detail.\n",
        "\n",
        "Path: \n",
        "A sequence of actions forms a path. A solution is a path from initial state \n",
        "to a goal state. \n",
        "We assume that action costs are additive; that is, \n",
        "the total cost of a path is the sum of the individual action costs. \n",
        "\n",
        "Graph:\n",
        "Represent state space. Vertices are states, edges are actions.\n",
        "\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Standarized problem: \n",
        "Intended to illustrate or exercise various problem-solving methods.\n",
        "\n",
        "Real world problem:\n",
        "such as robot navigation, is one whose solutions people actually use, \n",
        "and whose formulation is idiosyncratic, not standardized.\n",
        "For example, each robot has different sensors that produce different data.\n",
        "\n",
        "Grid world problem:\n",
        "Two-dimensional rectangular array of square cells in which agents can move from cell to cell.\n",
        "\n",
        "Vacuum world Example:\n",
        "States: 8 states, each each has 2 cells. Each room has 1 vaccum cleaner, 0-2 dirt.\n",
        "Initial state; Any state above.\n",
        "Actions: We define 3 actions. Suck, move left, move right. When we are in the right side, right is not applicable.\n",
        "Transition model: Suck removes dirt from agent's cell.\n",
        "Goal state: Every cell is clean.\n",
        "Action cost: Each action costs 1.\n",
        "\n",
        "Note that every problem formulation involves abstractions. \n",
        "The 8-puzzle actions are abstracted to their beginning and final states, \n",
        "ignoring the intermediate locations where the tile is sliding. \n",
        "\n",
        "Real world example Travel Planning Website:\n",
        "States: Each state includes location and current time. \n",
        "Initial state: Home airport.\n",
        "Actions: Any flight from current location, any seat class, enough time\n",
        "for travelling or transfer.\n",
        "Transition model: The state resulting from taking a flight will have the flight’s destination \n",
        "as the new location and the flight’s arrival time as the new time.\n",
        "Goal state: Destination city. (Or more complicated, no stops)\n",
        "Action cost: Combining monetary, waiting time, flight time, customs, quality etc.\n",
        "\n",
        "VLSI layout problem:\n",
        "Requires positioning millions of components and connections on a chip to \n",
        "minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. \n",
        "The layout problem comes after the logical design phase and is usually split into two parts: \n",
        "cell layout and channel routing. In cell layout, the primitive components of the circuit are grouped \n",
        "into cells, each of which performs some recognized function. Each cell has a fixed footprint \n",
        "(size and shape) and requires a certain number of connections to each of the other cells. \n",
        "The aim is to place the cells on the chip so that they do not overlap and so that there is room for \n",
        "the connecting wires to be placed between the cells. \n",
        "Channel routing finds a specific route for each wire through the gaps between the cells. \n",
        "These search problems are extremely complex, but definitely worth solving.\n",
        "\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "\n",
        "In this chapter we consider algorithms that superimpose a search tree over the state-space graph, \n",
        "forming various paths from the initial state, trying to find a path that reaches a goal state. \n",
        "Each node in the search tree corresponds to a state in the state space and \n",
        "the edges in the search tree correspond to actions. \n",
        "The root of the tree corresponds to the initial state of the problem.\n",
        "\n",
        "State space VS search tree:\n",
        "The state space describes the (possibly infinite) set of states in the world,\n",
        "and the actions that allow transitions from one state to another. \n",
        "The search tree describes paths between these states, reaching towards the goal. \n",
        "The search tree may have multiple paths to (and thus multiple nodes for) any given state, \n",
        "but each node in the tree has a unique path back to the root (as in all trees).\n",
        "\n",
        "Best-fit search:\n",
        "- chose a node n, with minimum value of evaluation function f(n).\n",
        "- On each ieration, we choose a node on frontier with minimum f(n), return if the state is goal.\n",
        "- Otherwise expand to generate child nodes, and add to frontier if child nodes are never reached\n",
        "or it is re-added if it is ow being reached with a loer path cost than revious path.\n",
        "Code:\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, with node as element\n",
        "  reached = lookup table, initial and value node.\n",
        "  while not frontier.isEmpty:\n",
        "    node = frontier.pop()\n",
        "    if problem.is_goal(node.State) 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:\n",
        "        reached[s] = child\n",
        "        add child to frontier\n",
        "  return failure\n",
        "\n",
        "function expand(problem, node) yields node:\n",
        "  s = node.State\n",
        "  for each action in problem.ACTIONS(S) do:\n",
        "    s' = problem.RESULTS(s, action)\n",
        "    cost = node.PATH-COST + problem.ACTION-COST(s, Action, s')\n",
        "    yield node(State = s', Parent=node, action=action, path-cost=cost)\n",
        "\n",
        "Data structure choices:\n",
        "- FIFO, LIFO queue.\n",
        "- Add(node, frontier)\n",
        "- Top(frontier) returns top node but not remove\n",
        "\n",
        "To be complete:\n",
        "To be complete, a search algorithm must be systematic in the way it explores an infinite state space, \n",
        "making sure it can eventually reach any state that is connected to the initial state. \n",
        "\n",
        "Implicit state time complexity:\n",
        "- Measured by depth or number of actions in optimal solution.\n",
        "- m, the maximum number of actions in any path.\n",
        "- b, branching factor or number of successors of a node that need to be considered. \n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "\n",
        "BFS:\n",
        "FIFO queue bfaster than priority queue. Will give correct ordero f nodes.\n",
        "def BFS returns solution node or failure:\n",
        "  node = node(problem.initial\n",
        "  if problem.is_goal(node.state)) return node\n",
        "  frontier = Fifo queue\n",
        "  reached add node\n",
        "  while not frontier.isempty():\n",
        "    node = frontier.pop()\n",
        "    for each child in expand(proble, node):\n",
        "      s = child.state\n",
        "      if problem.is_goal return child\n",
        "      if s is not in reached:\n",
        "        reached add s\n",
        "        frontier.add(child)\n",
        "  return failure\n",
        "\n",
        "BFS space & time complexity  = O(b^d). d is depth. b is branching factor.\n",
        "\n",
        "Dijkstra’s algorithm:\n",
        "Called as uniform cost search by AI community.\n",
        "Choose next lowest cost. \n",
        "\n",
        "DFS:\n",
        "Depth-first search always expands the deepest node in the frontier first. \n",
        "It could be implemented as a call to Best-First-Search where the evaluation function f \n",
        "is the negative of the depth. \n",
        "Usually for tree-like search, not keep a table of reached states. \n",
        "Not cost optimal. Returns first found solution even if it is not cheapest.\n",
        "Can cause infinite loop in cyclic state space.\n",
        "So implementation checks new node for cycles.  In infinite state spaces, DFS not systematic. \n",
        "It can go down a infinite path, so incomplete. \n",
        "Memory efficient, O(bm), b is branching factor, m is maximum depth.\n",
        "\n",
        "Backtracking search:\n",
        "Another form of DFS, use less memory. Just O(m).\n",
        "Check for O(1). Use in large state description problems, like robotic assembly.\n",
        "\n",
        "Depth-limited and iterative deepening search (IDS):\n",
        "DFS with limited depth l. Time O(b^l). Memory O(bl).\n",
        "Poor decision for l will cause incomplete.\n",
        "IDS solves picking a good value l. Memory O(bd) when there is solution, or O(bm) on finite\n",
        "spaces with no solution.\n",
        "IDS optimal for problems where all actions have the same cost, \n",
        "and is complete on finite acyclic state spaces, or on any finite state space when we \n",
        "check nodes for cycles all the way up the path.\n",
        "\n",
        "Bidirectional search(BS):\n",
        "Start from initial state and backwards from goal state. Hoping two will meet.\n",
        "For this to work, we need to keep track of two frontiers and two tables of reached states, \n",
        "and we need to be able to reason backwards. If state s1 is successor of s in forward,\n",
        "then we need to know that s is a successor of s1 in backward. Found solution if collides.\n",
        "Although there are two separate frontiers, the node to be expanded next is always one with \n",
        "a minimum value of the evaluation function, across either frontier. \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "\"Open loop\" : \"Ignore the percepts that break the searchig loop between agent and environment.\",  \n",
        "\"Closed loop\" : \"Use if model may be incorrect, it monitors the percepts.\",  \n",
        "\"state space\" : \"Set of possible states that the environment can be in.\",  \n",
        "\"Optimal solution\" : \"Path or solution with lowest cost.\",  \n",
        "\"Model\" : \"Formuating the problem with the problem definition steps. \",  \n",
        "\"Abstraction\" : \"Process of removing unnecessary detail, like weather, from a representation.\",  \n",
        "\"Abstraction is valid\" : \"Elaborate any abstract solution into a solution in more detailed environment.\",   \n",
        "\"Abstraction is useful\" : \"Executing each action in solutions is easier than original problem.\",  \n",
        "\"Egocentric actions\" : \"Actions given in viewpoint of the agent.\",  \n",
        "\"Robot navigation\" : \"Route-finding problem in general.\",  \n",
        "\"Automatic assembly sequencing\" : \"Algo find feasible assembly sequence and optimize the process.\",  \n",
        "\"Touring problems\" : \"Visit the must-visit locations rather tha single goal. Like Tranveling salesperson problem.\",  \n",
        "\"Search algorithm\" : \"Input search problem and returns a solution, or indicate failure.\",  \n",
        "\"Frontier\" : \"Set of unexpanded nodes/choices. Separates interior and exterior regions.\",  \n",
        "\"Reached\" : \"Any state that had a node generated for it, regardless if this node got expanded.\",  \n",
        "\"Cycle\" : \"Loopy path. Special case of redundant state.\",  \n",
        "\"Graph search\" : \"If checks for redundant paths. Remove all references to become tree-like search.\",  \n",
        "\"Tree-like search\" : \"if it does not check for redundant paths, uses less memory.\",  \n",
        "\"Completeness\" : \"Guaranteed to find solution if there is one, and correctly report failure.\",  \n",
        "\"Cost optimality\" : \"Find a solution with lowest path cost of all solutions\",  \n",
        "\"Admissibility\" : \"Same as cost optimality.\",  \n",
        "\"Time complexity\" : \"Time took to find a solution.\",  \n",
        "\"Space complexity\" : \"Memory needed to perform the search.\",  \n",
        "\"Branching factor\" : \"Number of children at each node.\",  \n",
        "\"Diameter of state-space graph\" : \"Find centre for better depth limited search.\",  \n",
        "\"pr\" : \"an\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5e18162c-6196-4790-d953-0aa3be11c627"
      },
      "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 \nGoal formulation:\nGoals organize behavior by limiting the objectives and hence the actions to be considered.\n\nProblem formulation:\nThe agent devises a description of the states and actions necessary to reach the \ngoal—an abstract model of the relevant part of the world.\nConsider actions of traveling from one to adjacent city. \n\nSearch & Solution:\nBefore taking any action in the real world, the agent simulates sequences of actions in its model, \nsearching until it finds a sequence of actions that reaches the goal.\nThis seqeunce is called Solution. May simulate multiple seqeunces. \nIt is an important property that in a fully observable, deterministic, known environment, \nthe solution to any problem is a fixed sequence of actions.\nIf the model is correct, then once the agent has found a solution, \nit can ignore its percepts while it is executing the actions.\n\nIn partially observable or nondeterministic environments, \na solution would be a branching strategy that recommends different future actions depending \non what percepts arrive.\n\nExecution:\nExxcute action in the solution one at a time. \n\nProblem definition:\n- State space\n- Initial state : Where agent starts in, like Arad.\n- Goal states: A set of one or more goal states. \n- Actions: Actions available to agent.\n- Transition model: Describes what each action does. Result (s,a) returns state\nfrom doing action a in state s.\n- Action cost function: Denoted by action cost-(s, a s'), gives numeric cost \nof applyiong action a in state s to reach state s'.\n\nGood problem formulation has right level of detail.\n\nPath: \nA sequence of actions forms a path. A solution is a path from initial state \nto a goal state. \nWe assume that action costs are additive; that is, \nthe total cost of a path is the sum of the individual action costs. \n\nGraph:\nRepresent state space. Vertices are states, edges are actions.\n\n \n\n## AIMA Chapter 3.2 Example Problems\n\nStandarized problem: \nIntended to illustrate or exercise various problem-solving methods.\n\nReal world problem:\nsuch as robot navigation, is one whose solutions people actually use, \nand whose formulation is idiosyncratic, not standardized.\nFor example, each robot has different sensors that produce different data.\n\nGrid world problem:\nTwo-dimensional rectangular array of square cells in which agents can move from cell to cell.\n\nVacuum world Example:\nStates: 8 states, each each has 2 cells. Each room has 1 vaccum cleaner, 0-2 dirt.\nInitial state; Any state above.\nActions: We define 3 actions. Suck, move left, move right. When we are in the right side, right is not applicable.\nTransition model: Suck removes dirt from agent's cell.\nGoal state: Every cell is clean.\nAction cost: Each action costs 1.\n\nNote that every problem formulation involves abstractions. \nThe 8-puzzle actions are abstracted to their beginning and final states, \nignoring the intermediate locations where the tile is sliding. \n\nReal world example Travel Planning Website:\nStates: Each state includes location and current time. \nInitial state: Home airport.\nActions: Any flight from current location, any seat class, enough time\nfor travelling or transfer.\nTransition model: The state resulting from taking a flight will have the flight’s destination \nas the new location and the flight’s arrival time as the new time.\nGoal state: Destination city. (Or more complicated, no stops)\nAction cost: Combining monetary, waiting time, flight time, customs, quality etc.\n\nVLSI layout problem:\nRequires positioning millions of components and connections on a chip to \nminimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. \nThe layout problem comes after the logical design phase and is usually split into two parts: \ncell layout and channel routing. In cell layout, the primitive components of the circuit are grouped \ninto cells, each of which performs some recognized function. Each cell has a fixed footprint \n(size and shape) and requires a certain number of connections to each of the other cells. \nThe aim is to place the cells on the chip so that they do not overlap and so that there is room for \nthe connecting wires to be placed between the cells. \nChannel routing finds a specific route for each wire through the gaps between the cells. \nThese search problems are extremely complex, but definitely worth solving.\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \n\nIn this chapter we consider algorithms that superimpose a search tree over the state-space graph, \nforming various paths from the initial state, trying to find a path that reaches a goal state. \nEach node in the search tree corresponds to a state in the state space and \nthe edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem.\n\nState space VS search tree:\nThe state space describes the (possibly infinite) set of states in the world,\nand the actions that allow transitions from one state to another. \nThe search tree describes paths between these states, reaching towards the goal. \nThe search tree may have multiple paths to (and thus multiple nodes for) any given state, \nbut each node in the tree has a unique path back to the root (as in all trees).\n\nBest-fit search:\n- chose a node n, with minimum value of evaluation function f(n).\n- On each ieration, we choose a node on frontier with minimum f(n), return if the state is goal.\n- Otherwise expand to generate child nodes, and add to frontier if child nodes are never reached\nor it is re-added if it is ow being reached with a loer path cost than revious path.\nCode:\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, with node as element\n  reached = lookup table, initial and value node.\n  while not frontier.isEmpty:\n    node = frontier.pop()\n    if problem.is_goal(node.State) 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:\n        reached[s] = child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields node:\n  s = node.State\n  for each action in problem.ACTIONS(S) do:\n    s' = problem.RESULTS(s, action)\n    cost = node.PATH-COST + problem.ACTION-COST(s, Action, s')\n    yield node(State = s', Parent=node, action=action, path-cost=cost)\n\nData structure choices:\n- FIFO, LIFO queue.\n- Add(node, frontier)\n- Top(frontier) returns top node but not remove\n\nTo be complete:\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space, \nmaking sure it can eventually reach any state that is connected to the initial state. \n\nImplicit state time complexity:\n- Measured by depth or number of actions in optimal solution.\n- m, the maximum number of actions in any path.\n- b, branching factor or number of successors of a node that need to be considered. \n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\nBFS:\nFIFO queue bfaster than priority queue. Will give correct ordero f nodes.\ndef BFS returns solution node or failure:\n  node = node(problem.initial\n  if problem.is_goal(node.state)) return node\n  frontier = Fifo queue\n  reached add node\n  while not frontier.isempty():\n    node = frontier.pop()\n    for each child in expand(proble, node):\n      s = child.state\n      if problem.is_goal return child\n      if s is not in reached:\n        reached add s\n        frontier.add(child)\n  return failure\n\nBFS space & time complexity  = O(b^d). d is depth. b is branching factor.\n\nDijkstra’s algorithm:\nCalled as uniform cost search by AI community.\nChoose next lowest cost. \n\nDFS:\nDepth-first search always expands the deepest node in the frontier first. \nIt could be implemented as a call to Best-First-Search where the evaluation function f \nis the negative of the depth. \nUsually for tree-like search, not keep a table of reached states. \nNot cost optimal. Returns first found solution even if it is not cheapest.\nCan cause infinite loop in cyclic state space.\nSo implementation checks new node for cycles.  In infinite state spaces, DFS not systematic. \nIt can go down a infinite path, so incomplete. \nMemory efficient, O(bm), b is branching factor, m is maximum depth.\n\nBacktracking search:\nAnother form of DFS, use less memory. Just O(m).\nCheck for O(1). Use in large state description problems, like robotic assembly.\n\nDepth-limited and iterative deepening search (IDS):\nDFS with limited depth l. Time O(b^l). Memory O(bl).\nPoor decision for l will cause incomplete.\nIDS solves picking a good value l. Memory O(bd) when there is solution, or O(bm) on finite\nspaces with no solution.\nIDS optimal for problems where all actions have the same cost, \nand is complete on finite acyclic state spaces, or on any finite state space when we \ncheck nodes for cycles all the way up the path.\n\nBidirectional search(BS):\nStart from initial state and backwards from goal state. Hoping two will meet.\nFor this to work, we need to keep track of two frontiers and two tables of reached states, \nand we need to be able to reason backwards. If state s1 is successor of s in forward,\nthen we need to know that s is a successor of s1 in backward. Found solution if collides.\nAlthough there are two separate frontiers, the node to be expanded next is always one with \na minimum value of the evaluation function, across either frontier. \n \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - Ignore the percepts that break the searchig loop between agent and environment.\n* **Closed loop** - Use if model may be incorrect, it monitors the percepts.\n* **State space** - Set of possible states that the environment can be in.\n* **Optimal solution** - Path or solution with lowest cost.\n* **Model** - Formuating the problem with the problem definition steps. \n* **Abstraction** - Process of removing unnecessary detail, like weather, from a representation.\n* **Abstraction is valid** - Elaborate any abstract solution into a solution in more detailed environment.\n* **Abstraction is useful** - Executing each action in solutions is easier than original problem.\n* **Egocentric actions** - Actions given in viewpoint of the agent.\n* **Robot navigation** - Route-finding problem in general.\n* **Automatic assembly sequencing** - Algo find feasible assembly sequence and optimize the process.\n* **Touring problems** - Visit the must-visit locations rather tha single goal. Like Tranveling salesperson problem.\n* **Search algorithm** - Input search problem and returns a solution, or indicate failure.\n* **Frontier** - Set of unexpanded nodes/choices. Separates interior and exterior regions.\n* **Reached** - Any state that had a node generated for it, regardless if this node got expanded.\n* **Cycle** - Loopy path. Special case of redundant state.\n* **Graph search** - If checks for redundant paths. Remove all references to become tree-like search.\n* **Tree-like search** - if it does not check for redundant paths, uses less memory.\n* **Completeness** - Guaranteed to find solution if there is one, and correctly report failure.\n* **Cost optimality** - Find a solution with lowest path cost of all solutions\n* **Admissibility** - Same as cost optimality.\n* **Time complexity** - Time took to find a solution.\n* **Space complexity** - Memory needed to perform the search.\n* **Branching factor** - Number of children at each node.\n* **Diameter of state-space graph** - Find centre for better depth limited search.\n* **Pr** - an\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "#### informed search:\n",
        "Uses domain-specific hints about location of goals, find solutions more efficiently than uninformed strategy.\n",
        "\n",
        "#### Heuristic function:\n",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n",
        "\n",
        "#### Greedy best first search:\n",
        "a form of best-first search that expands first the node with the lowest h(n) value,\n",
        "which is the node that appears to be closest to goal.\n",
        "Evaluation fucntion f(n) = h(n).\n",
        "Complete in finite state spaces, but not infinite ones.\n",
        "Time&space complexity O(|V|). Can be reduced to O(bm) with good h(n).\n",
        "\n",
        "#### A* search\n",
        "Best-first search uses evaluation function f(n) = g(n) + h(n)\n",
        "g(n) is path cost from initial state to node n.\n",
        "h(n) is estimated cost of shortest path from n to a goal state.\n",
        "So, f(n) = estimated cost of best path that continues from n to a goal.\n",
        "\n",
        "Whether A* is cost-optimal depends on certain properties of the heuristic. \n",
        "A key property is admissibility: an admissible heuristic is one that never overestimates \n",
        "the cost to reach a goal. \n",
        "(An admissible heuristic is therefore optimistic.) \n",
        "Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n",
        "With inconsistent heuristics, we may end up with multiple paths reaching the same state, \n",
        "and if each new path has a lower path cost than the previous one, then we will end up with \n",
        "multiple nodes for that state in the frontier, costing us both time and space.\n",
        "With an inadmissible heuristic, A* may or may not be cost-optimal. \n",
        "\n",
        "#### Surely expanded nodes:\n",
        "A* expands all nodes that can be reached from the initial state on a path \n",
        "where every node on the path has f(n) < C*.\n",
        "\n",
        "#### Optimally efficient:\n",
        "We say that A* with a consistent heuristic is optimally efficient in the sense that any algorithm \n",
        "that extends search paths from the initial state, and uses the same heuristic information, \n",
        "must expand all nodes that are surely expanded by A*.\n",
        "\n",
        "#### Search contours\n",
        "Monotonic holds onl ywhen heuristic is consistent. \n",
        "\n",
        "#### A* problems\n",
        "It is complete, cost-optimal, and optimally efficient among all such algorithms.\n",
        "But for many problems, the number of nodes expanded can be exponential in the length of the solution.\n",
        "\n",
        "#### Satisficing search:\n",
        "Accept good enough sub-optimal solutions.\n",
        "Use inadmissible heuristic, we risk missing optimal solution, but heuristic can be more accurate,\n",
        "expand to less nodes. \n",
        "\n",
        "#### Weighted A* search\n",
        "weight the heuristic value more heavily, giving us the evaluation function.\n",
        "Using idea of detour index.\n",
        "f(n) = g(n) + W*h(n), for some W >1.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "\n",
        "#### Misplaced tiles(h1)\n",
        "- h1 s an admissible heuristic because any tile that is out of place will require at least one move to get it to the right place.\n",
        "\n",
        "#### Manhattan distance(h2):\n",
        "- Sum of distances of the tiles from their goal positions. The distance is the sum of the horizontal and vertical distances.\n",
        "- Also admissible because all any move can do is move one tile one step closer to the goal.\n",
        "- Always better than h1. A* using h2 ever expands more nodes than h1. Dominates. \n",
        "- Because h2 is at least as big as h1 for all nodes, every node is surely expanded by A* with h2.\n",
        "h1 might cause other nodes to be expanded as well.\n",
        "- So use heuristic function with higher values provided it is consistent and that the computation time for the heuristic is not too long.\n",
        "- Best of all worlds by h(n) = max{h1, h2, ... , hk}\n",
        "\n",
        "#### The effect of heuristic accuracy on performance\n",
        "- Quality of heuristic can be measured by effective branching factor b*.\n",
        "- b* is the branching factor that a uniform tree of depth d would have to have in order to contain n+1 nodes.\n",
        "Where N is number of nodes generated by A*, d is solution depth. \n",
        "- So N+1 = 1 + b* + (b*)^2 + ... + (b*)^d\n",
        "- a better way to characterize the effect of A* pruning with a given heuristic is that it reduces the effective depth by a constant\n",
        "kh compared to true depth. So total search cost is O(b^{d-kh}) and not O(b^d) for an uninformed search.\n",
        "\n",
        "#### Relaxed problem cost\n",
        "- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "- Because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "#### Memory-bounded search\n",
        "Methods to reduce memory usage.\n",
        "- Memory is split between the frontier and the reached states. In our implementation of best-first search, \n",
        "a state that is on the frontier is stored in two places: as a node in the frontier \n",
        "and as an entry in the table of reached states.\n",
        "- Another possibility is to remove states from reached when we can prove that they are no longer needed.\n",
        "- For other problems, we can keep reference counts of the number of times a state has been reached, \n",
        "and remove it from the reached table when there are no more ways to reach the state. \n",
        "- Beam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes.\n",
        "Or keep every node whose f-score is within standard deviation of best f-score.\n",
        "-  Iterative-deepening A* search (IDA*). The cutoff is f-cost(g+h) instead of depth.\n",
        "- Recursive best-first search (RBFS): Attempts to mimic the operation of standard best-first search, but using only linear space.\n",
        "It uses f_limit variable to keep track of the f-value of best alternative path avaialble from any ancestor of the current node.\n",
        "If the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the \n",
        "f-value of each node along the path with a backed-up value. Optimal if h(n) is admissible. Space complexity is linear in depth of deepest optimal solution.\n",
        "Time complexity depends on accuracy of h(n) and how often the best path changes as nodes are expanded.\n",
        "- RBFS more efficient than IDA*, but suffer from excessive node regeneration. Both suffer from using too little memory.\n",
        " \n",
        " #### Determine how much memory:\n",
        " - MA* (memory-bounded A*) and SMA(simplified MA*)\n",
        " - SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one.\n",
        " Always drop worst leaf node, the one with highest f-value.\n",
        " \n",
        " #### Bidirectional heuristic search\n",
        "- Pair of nodes that can be surely expanded, not individual. \n",
        "So any proof of efficiency will have to consider pairs of nodes.\n",
        "- have f(n) = g(n) + h(n) for both forward and backward direction. \n",
        "- Middle ground to expand fewer nodes that is preferred. \n",
        "- In the worst case of a poor heuristic, the search is no longer focused on the goal, \n",
        "and bidirectional search has the same asymptotic complexity as A*. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Admissible heuristic\" : \"Never overestimates the cost to reach a goal.\",    \n",
        "\"Consistency\" : \"See image.\",  \n",
        "\"Monotonic\" : \"Cost always increase along path, because costs are positive and cumulative.\",  \n",
        "\"Detour index\" : \"Multiplier to straight-line distnce to account for true distance that is not straight.\",  \n",
        "\"Bounded suboptimal search\" : \"Look for solution within a constant factor W of the optimal cost.\",  \n",
        "\"Bounded cost search\" : \"Solution cost is less than a constant C.\",  \n",
        "\"Unbounded cost search\" : \"Accept any solution, aim to find it quickly\", \n",
        "\"Speedy search\" : \"h(n) is estimated number of actions required to reach a goal, a form of greedy best first search.\", \n",
        "\"Backed-up value\" : \"Best f-value of its children node\", \n",
        "\"Relaxed problem\" : \"Problem with less restrictions on actions.\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6c45c537-2239-4d3a-ffb2-241262ab8bc0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n#### informed search:\nUses domain-specific hints about location of goals, find solutions more efficiently than uninformed strategy.\n\n#### Heuristic function:\nh(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n\n#### Greedy best first search:\na form of best-first search that expands first the node with the lowest h(n) value,\nwhich is the node that appears to be closest to goal.\nEvaluation fucntion f(n) = h(n).\nComplete in finite state spaces, but not infinite ones.\nTime&space complexity O(|V|). Can be reduced to O(bm) with good h(n).\n\n#### A* search\nBest-first search uses evaluation function f(n) = g(n) + h(n)\ng(n) is path cost from initial state to node n.\nh(n) is estimated cost of shortest path from n to a goal state.\nSo, f(n) = estimated cost of best path that continues from n to a goal.\n\nWhether A* is cost-optimal depends on certain properties of the heuristic. \nA key property is admissibility: an admissible heuristic is one that never overestimates \nthe cost to reach a goal. \n(An admissible heuristic is therefore optimistic.) \nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\nWith inconsistent heuristics, we may end up with multiple paths reaching the same state, \nand if each new path has a lower path cost than the previous one, then we will end up with \nmultiple nodes for that state in the frontier, costing us both time and space.\nWith an inadmissible heuristic, A* may or may not be cost-optimal. \n\n#### Surely expanded nodes:\nA* expands all nodes that can be reached from the initial state on a path \nwhere every node on the path has f(n) < C*.\n\n#### Optimally efficient:\nWe say that A* with a consistent heuristic is optimally efficient in the sense that any algorithm \nthat extends search paths from the initial state, and uses the same heuristic information, \nmust expand all nodes that are surely expanded by A*.\n\n#### Search contours\nMonotonic holds onl ywhen heuristic is consistent. \n\n#### A* problems\nIt is complete, cost-optimal, and optimally efficient among all such algorithms.\nBut for many problems, the number of nodes expanded can be exponential in the length of the solution.\n\n#### Satisficing search:\nAccept good enough sub-optimal solutions.\nUse inadmissible heuristic, we risk missing optimal solution, but heuristic can be more accurate,\nexpand to less nodes. \n\n#### Weighted A* search\nweight the heuristic value more heavily, giving us the evaluation function.\nUsing idea of detour index.\nf(n) = g(n) + W*h(n), for some W >1.\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n\n#### Misplaced tiles(h1)\n- h1 s an admissible heuristic because any tile that is out of place will require at least one move to get it to the right place.\n\n#### Manhattan distance(h2):\n- Sum of distances of the tiles from their goal positions. The distance is the sum of the horizontal and vertical distances.\n- Also admissible because all any move can do is move one tile one step closer to the goal.\n- Always better than h1. A* using h2 ever expands more nodes than h1. Dominates. \n- Because h2 is at least as big as h1 for all nodes, every node is surely expanded by A* with h2.\nh1 might cause other nodes to be expanded as well.\n- So use heuristic function with higher values provided it is consistent and that the computation time for the heuristic is not too long.\n- Best of all worlds by h(n) = max{h1, h2, ... , hk}\n\n#### The effect of heuristic accuracy on performance\n- Quality of heuristic can be measured by effective branching factor b*.\n- b* is the branching factor that a uniform tree of depth d would have to have in order to contain n+1 nodes.\nWhere N is number of nodes generated by A*, d is solution depth. \n- So N+1 = 1 + b* + (b*)^2 + ... + (b*)^d\n- a better way to characterize the effect of A* pruning with a given heuristic is that it reduces the effective depth by a constant\nkh compared to true depth. So total search cost is O(b^{d-kh}) and not O(b^d) for an uninformed search.\n\n#### Relaxed problem cost\n- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n- Because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n\n\n\n \n\n## Module 4 Lecture Notes\n \n#### Memory-bounded search\nMethods to reduce memory usage.\n- Memory is split between the frontier and the reached states. In our implementation of best-first search, \na state that is on the frontier is stored in two places: as a node in the frontier \nand as an entry in the table of reached states.\n- Another possibility is to remove states from reached when we can prove that they are no longer needed.\n- For other problems, we can keep reference counts of the number of times a state has been reached, \nand remove it from the reached table when there are no more ways to reach the state. \n- Beam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes.\nOr keep every node whose f-score is within standard deviation of best f-score.\n-  Iterative-deepening A* search (IDA*). The cutoff is f-cost(g+h) instead of depth.\n- Recursive best-first search (RBFS): Attempts to mimic the operation of standard best-first search, but using only linear space.\nIt uses f_limit variable to keep track of the f-value of best alternative path avaialble from any ancestor of the current node.\nIf the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the \nf-value of each node along the path with a backed-up value. Optimal if h(n) is admissible. Space complexity is linear in depth of deepest optimal solution.\nTime complexity depends on accuracy of h(n) and how often the best path changes as nodes are expanded.\n- RBFS more efficient than IDA*, but suffer from excessive node regeneration. Both suffer from using too little memory.\n \n #### Determine how much memory:\n - MA* (memory-bounded A*) and SMA(simplified MA*)\n - SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one.\n Always drop worst leaf node, the one with highest f-value.\n \n #### Bidirectional heuristic search\n- Pair of nodes that can be surely expanded, not individual. \nSo any proof of efficiency will have to consider pairs of nodes.\n- have f(n) = g(n) + h(n) for both forward and backward direction. \n- Middle ground to expand fewer nodes that is preferred. \n- In the worst case of a poor heuristic, the search is no longer focused on the goal, \nand bidirectional search has the same asymptotic complexity as A*. \n\n\n \n\n## Module 4 Definitions\n* **Admissible heuristic** - Never overestimates the cost to reach a goal.\n* **Consistency** - See image.\n* **Monotonic** - Cost always increase along path, because costs are positive and cumulative.\n* **Detour index** - Multiplier to straight-line distnce to account for true distance that is not straight.\n* **Bounded suboptimal search** - Look for solution within a constant factor W of the optimal cost.\n* **Bounded cost search** - Solution cost is less than a constant C.\n* **Unbounded cost search** - Accept any solution, aim to find it quickly\n* **Speedy search** - h(n) is estimated number of actions required to reach a goal, a form of greedy best first search.\n* **Backed-up value** - Best f-value of its children node\n* **Relaxed problem** - Problem with less restrictions on actions.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "#### Game theory\n",
        "- 3 Stances to take towards multi-agent environments.\n",
        "- The first stance, appropriate when there are a very large number of agents, is to consider them in the aggregate as an economy.\n",
        "- Second, we could consider adversarial agents as just a part of the environment—a part that makes the environment nondeterministic.\n",
        "- The third stance is to explicitly model the adversarial agents with the techniques of adversarial game-tree search.\n",
        "\n",
        "#### heuristic evaluation function\n",
        "- Estimate who is winning based on features of the state.\n",
        "- We can average the outcomes of many fast simulations of the game from that state all the way to the end.\n",
        "\n",
        "#### Game\n",
        "- Max moves first.\n",
        "- S0 is initial state.\n",
        "- To-move(s): The player whose turn it is to move in state s.\n",
        "- Action(s): The set of legal moves in state s.\n",
        "- Result(s,a): The transition model, which defines the state resulting from taking action a in state s.\n",
        "- Is-Terminal(s): A terminal test, which is true when the game is over and false otherwise.\n",
        "- Utility(s,p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when game ended in terminal state.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "\n",
        "#### Max's strategy:\n",
        "- A conditional plan. A contingent strategy specifying a response to each of min’s possible moves.\n",
        "\n",
        "#### Minimax\n",
        "The minimax value is the utility (for max) of being in that state, assuming that both players play optimally from there to the end of the game. \n",
        "The minimax value of a terminal state is just its utility. \n",
        "In a non-terminal state, 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 maximum value for Min).\n",
        "\n",
        "#### Minimax search algorithm\n",
        "- The minimax algorithm performs a complete depth-first exploration of the game tree.\n",
        "- Time O(b^m), space O(bm). b legal moves at each point, m is max depth of tree. \n",
        "- Depth first.\n",
        "- Alpha: (At least) the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for max. \n",
        "- Beta: (At most) the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. \n",
        "\n",
        "#### When to prune:\n",
        "- The value of the root and hence the minimax decision are independent of the values of the leaves  \n",
        "and , and therefore they can be pruned.\n",
        "- General principle is if a player has a choice to move to n, and \n",
        "if a plyaer has a better choice either at same level or any points\n",
        "higher up in the tree, then player will never move on to n. \n",
        "\n",
        "#### Move ordering:\n",
        "- It might be worthwhile to try to first examine the successors that are likely to be best.\n",
        "- If this could be done perfectly, alpha–beta would need to examine only O(b^{m/2}), instead of O(b^m)\n",
        "\n",
        "#### Type A strategy:\n",
        "- Considers all possible moves to a certain depth in search tree, \n",
        "and then uses a heuristic evaluation function to estimate the utility of states at that depth.\n",
        "- It explores a wide but shallow portion of the tree.\n",
        "\n",
        "#### Type B strategy:\n",
        "- Ignores moves that look bad, and follows promising lines “as far as possible.” \n",
        "- It explores a deep but narrow portion of the tree.\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "\n",
        "#### Heuristic evaluation function:\n",
        "- To states, effectively treating nonterminal nodes as if they were terminal. \n",
        "- Do to make use of our limited computation time, cut off the search early.\n",
        "- Replace Utility function with Eval, which estimates the state's utility.\n",
        "- We also replace the terminal test by a cutoff test, which must return true for terminal states, \n",
        "but is otherwise free to decide when to cut off the search, \n",
        "based on the search depth and any property of the state that it chooses to consider.\n",
        "- Gives H-Minimax(s,d) for heuristic minimax value of state s at search depth d.\n",
        "\n",
        "#### Evaluation functions:\n",
        "- For terminal state, Eval(s,p) = Utility (s,p)\n",
        "- Otherwise, Utility (loss,p) <= Eval(s,p) <= Utility (win,p)\n",
        "- Good evaluation function has not long computation. Strongly correlated with actual chance of winning.\n",
        "- Need not be linearly correlated. \n",
        "- Only applied to positions that are quiescent.\n",
        "\n",
        "#### Cutting off search\n",
        "- Replace is-terminal with \n",
        "- if game.Is-Cutoff(state, depth) then return game.Eval(state, player), null\n",
        "- Increment depth on each recursive call.\n",
        "- The depth d is chosen so that a move is selected within the allocated time. \n",
        "- When time runs out, the program returns the move selected by the deepest completed search.\n",
        "- A more robust approach is to apply iterative deepening.\n",
        "\n",
        "#### Forward pruning\n",
        "- Prunes moves that appear to be poor moves, but might possibly be good ones. \n",
        "- Saves computation time at the risk of making an error.\n",
        "- Type B strategy.\n",
        "- ProbCut, probability cutting: Forward pruning of alpha-beta search\n",
        "that uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n",
        "- Late move reduction: Works under the assumption that move ordering has been done well, \n",
        "and therefore moves that appear later in the list of possible moves are less likely to be good moves.\n",
        "Just reduce depth to which we search these moves, thereby saving time. If reduced search comes back\n",
        "with value above current alpha, we rerun the search with full depth. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "#### Stochastic games\n",
        "- Chance node shows each possible outcome\n",
        "- No defiite minimax values\n",
        "- Calculate expected value of a position (average over all possible outcomes of chance nodes)\n",
        "- Leads to expectiminimax value, a generalization of the minimax value for deterministic games.\n",
        "- The evaluation function must return values that are a positive linear transformation of the probability of winning.\n",
        "- If the program knew in advance all the dice rolls that would occur for the rest of the game, \n",
        "solving a game with dice would be just like solving a game without dice, which minimax does in O(b^m),\n",
        "where b is branching factor and m is maximum depth of game tree.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "\n",
        "#### Simple decisions\n",
        "- Assign probability P(s) to each possible current state s.\n",
        "- There may also be uncertainty about the action outcomes. Transition model given by P(s'|s,a),\n",
        "the probability that action a in state s reaches state s'.\n",
        "- P(Result(a)=s') probability of reaching s' by doing a in the current state. It is summation s of\n",
        "P(s)P(s'|s,a). \n",
        "- The agent’s preferences are captured by a utility function U(s), which assigns a single number to express the desirability of a state.\n",
        "\n",
        "#### Principle of maximum expected utility (MEU)\n",
        "- A rational agent should choose the action that maximizes the agent’s expected utility.\n",
        "- \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "\n",
        "#### Constraints on rational preferences (For utility theory)\n",
        "1. ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n",
        "2. TRANSITIVITY: Given any three lotteries, if an agent prefers A to B, and B to C, then must prefer A to C.\n",
        "3. CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent\n",
        "will be indifferent between getting B for sure and the ottery that yields A with probability p and C with probability 1 - p.\n",
        "4. SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then also indifferent when substituting something with A and B.\n",
        "5. MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A, then the agent must prefer the lottery that has a higher probability for A.\n",
        "6. DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n",
        "\n",
        "#### EXISTENCE OF UTILITY FUNCTION\n",
        "- If an agent’s preferences obey the axioms of utility, then there exists a function.\n",
        "\n",
        "#### EXPECTED UTILITY OF A LOTTERY\n",
        "- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "\n",
        "#### Utility assessment and utility scales\n",
        "- No absolute scale for utilities, but it is helpful, nonetheless, to establish some scale on which utilities can be recorded and compared for any particular problem.\n",
        "- Risk averse: Wants guaranteed payoff that is lower than expected outcome.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "\n",
        "#### Expectimax search\n",
        "- Value should now reflec average case outcomes.\n",
        "- Computer average score under optimal play.\n",
        "- Calculate expected utilities (Chance nodes give uncertain outcome)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Pruning\" : \"Ignore useless portions of search tree to make process more efficient.\", \n",
        "\"Perfect information\" : \"Fully observable.\",  \n",
        "\"Zero-sum\" : \"What is good for one, is bad for another.\",  \n",
        "\"Move\" : \"Action\",  \n",
        "\"Position\" : \"State\",  \n",
        "\"Terminal state\" : \"States when game ended.\",  \n",
        "\"State Space Graph\" : \"Graph where states are vertices, and movs are edges.\",  \n",
        "\"Game tree\" : \"Search tree that follows every sequence of moves to reach terminal state.\",  \n",
        "\"Killer moves\" : \"Best moves.\",  \n",
        "\"Killer move heuristic\" : \"Trying killer moves first.\",  \n",
        "\"Transpositions\" : \"Different permutations of move sequence that will end up in the same position. Cause repated states.\",     \n",
        "\"Weighted linear function\" : \"With material value, assign normalized weight to function.\",   \n",
        "\"Quiescent\" : \"Positions when there is no pending move that will wildly affect evaluation\",   \n",
        "\"Nonquiescent position\" : \"Is-cuttoff returns false\",   \n",
        "\"Horizon effect\" : \"When facing detrimental and unavoidable moves from opponent, only can temporarily delay.\", \n",
        "\"Singular extensions\" : \"Mitigate horizon effect, a clearly better move.\", \n",
        "\"Policy\" : \"Mapping from every possible state to best move in that state.\", \n",
        "\"Decision theory\" : \"Choose among actions based on desirability of immediate outcome.\", \n",
        "\"Expected utility\" : \"Average utility value of outcomes, weighted by chance of outcome occurring.\", \n",
        "\"Value function\" : \"Another name for ordinal utility function.\", \n",
        "\"Ordinal utility function\" : \"An agent needs only a preference ranking on states, numbers dont matter.\", \n",
        "\"Preference elicitation\" : \"Find utility function by presenting choices to humans and observe their preferences.\", \n",
        "\"Optimizer’s curse\" : \"Tendency for the estimated expected utility of the best choice to be too high.\", \n",
        "\"concept\" : \"definition\", \n",
        "\"concept\" : \"definition\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e70dcaf2-f627-4c28-d36e-b7f33c2ec827"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n#### Game theory\n- 3 Stances to take towards multi-agent environments.\n- The first stance, appropriate when there are a very large number of agents, is to consider them in the aggregate as an economy.\n- Second, we could consider adversarial agents as just a part of the environment—a part that makes the environment nondeterministic.\n- The third stance is to explicitly model the adversarial agents with the techniques of adversarial game-tree search.\n\n#### heuristic evaluation function\n- Estimate who is winning based on features of the state.\n- We can average the outcomes of many fast simulations of the game from that state all the way to the end.\n\n#### Game\n- Max moves first.\n- S0 is initial state.\n- To-move(s): The player whose turn it is to move in state s.\n- Action(s): The set of legal moves in state s.\n- Result(s,a): The transition model, which defines the state resulting from taking action a in state s.\n- Is-Terminal(s): A terminal test, which is true when the game is over and false otherwise.\n- Utility(s,p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when game ended in terminal state.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n#### Max's strategy:\n- A conditional plan. A contingent strategy specifying a response to each of min’s possible moves.\n\n#### Minimax\nThe minimax value is the utility (for max) of being in that state, assuming that both players play optimally from there to the end of the game. \nThe minimax value of a terminal state is just its utility. \nIn a non-terminal state, Max prefers to move to a state of maximum value when it is Max’s turn to move, \nand Min prefers a state of minimum value (that is, minimum value for Max and thus maximum value for Min).\n\n#### Minimax search algorithm\n- The minimax algorithm performs a complete depth-first exploration of the game tree.\n- Time O(b^m), space O(bm). b legal moves at each point, m is max depth of tree. \n- Depth first.\n- Alpha: (At least) the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for max. \n- Beta: (At most) the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. \n\n#### When to prune:\n- The value of the root and hence the minimax decision are independent of the values of the leaves  \nand , and therefore they can be pruned.\n- General principle is if a player has a choice to move to n, and \nif a plyaer has a better choice either at same level or any points\nhigher up in the tree, then player will never move on to n. \n\n#### Move ordering:\n- It might be worthwhile to try to first examine the successors that are likely to be best.\n- If this could be done perfectly, alpha–beta would need to examine only O(b^{m/2}), instead of O(b^m)\n\n#### Type A strategy:\n- Considers all possible moves to a certain depth in search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth.\n- It explores a wide but shallow portion of the tree.\n\n#### Type B strategy:\n- Ignores moves that look bad, and follows promising lines “as far as possible.” \n- It explores a deep but narrow portion of the tree.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n\n#### Heuristic evaluation function:\n- To states, effectively treating nonterminal nodes as if they were terminal. \n- Do to make use of our limited computation time, cut off the search early.\n- Replace Utility function with Eval, which estimates the state's utility.\n- We also replace the terminal test by a cutoff test, which must return true for terminal states, \nbut is otherwise free to decide when to cut off the search, \nbased on the search depth and any property of the state that it chooses to consider.\n- Gives H-Minimax(s,d) for heuristic minimax value of state s at search depth d.\n\n#### Evaluation functions:\n- For terminal state, Eval(s,p) = Utility (s,p)\n- Otherwise, Utility (loss,p) <= Eval(s,p) <= Utility (win,p)\n- Good evaluation function has not long computation. Strongly correlated with actual chance of winning.\n- Need not be linearly correlated. \n- Only applied to positions that are quiescent.\n\n#### Cutting off search\n- Replace is-terminal with \n- if game.Is-Cutoff(state, depth) then return game.Eval(state, player), null\n- Increment depth on each recursive call.\n- The depth d is chosen so that a move is selected within the allocated time. \n- When time runs out, the program returns the move selected by the deepest completed search.\n- A more robust approach is to apply iterative deepening.\n\n#### Forward pruning\n- Prunes moves that appear to be poor moves, but might possibly be good ones. \n- Saves computation time at the risk of making an error.\n- Type B strategy.\n- ProbCut, probability cutting: Forward pruning of alpha-beta search\nthat uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n- Late move reduction: Works under the assumption that move ordering has been done well, \nand therefore moves that appear later in the list of possible moves are less likely to be good moves.\nJust reduce depth to which we search these moves, thereby saving time. If reduced search comes back\nwith value above current alpha, we rerun the search with full depth. \n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \n#### Stochastic games\n- Chance node shows each possible outcome\n- No defiite minimax values\n- Calculate expected value of a position (average over all possible outcomes of chance nodes)\n- Leads to expectiminimax value, a generalization of the minimax value for deterministic games.\n- The evaluation function must return values that are a positive linear transformation of the probability of winning.\n- If the program knew in advance all the dice rolls that would occur for the rest of the game, \nsolving a game with dice would be just like solving a game without dice, which minimax does in O(b^m),\nwhere b is branching factor and m is maximum depth of game tree.\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n\n#### Simple decisions\n- Assign probability P(s) to each possible current state s.\n- There may also be uncertainty about the action outcomes. Transition model given by P(s'|s,a),\nthe probability that action a in state s reaches state s'.\n- P(Result(a)=s') probability of reaching s' by doing a in the current state. It is summation s of\nP(s)P(s'|s,a). \n- The agent’s preferences are captured by a utility function U(s), which assigns a single number to express the desirability of a state.\n\n#### Principle of maximum expected utility (MEU)\n- A rational agent should choose the action that maximizes the agent’s expected utility.\n- \n\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n\n#### Constraints on rational preferences (For utility theory)\n1. ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n2. TRANSITIVITY: Given any three lotteries, if an agent prefers A to B, and B to C, then must prefer A to C.\n3. CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent\nwill be indifferent between getting B for sure and the ottery that yields A with probability p and C with probability 1 - p.\n4. SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then also indifferent when substituting something with A and B.\n5. MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A, then the agent must prefer the lottery that has a higher probability for A.\n6. DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n\n#### EXISTENCE OF UTILITY FUNCTION\n- If an agent’s preferences obey the axioms of utility, then there exists a function.\n\n#### EXPECTED UTILITY OF A LOTTERY\n- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n\n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n\n#### Utility assessment and utility scales\n- No absolute scale for utilities, but it is helpful, nonetheless, to establish some scale on which utilities can be recorded and compared for any particular problem.\n- Risk averse: Wants guaranteed payoff that is lower than expected outcome.\n\n\n \n\n## Module 5 Lecture Notes\n\n\n#### Expectimax search\n- Value should now reflec average case outcomes.\n- Computer average score under optimal play.\n- Calculate expected utilities (Chance nodes give uncertain outcome)\n\n\n\n## Module 5 Definitions\n* **Pruning** - Ignore useless portions of search tree to make process more efficient.\n* **Perfect information** - Fully observable.\n* **Zero-sum** - What is good for one, is bad for another.\n* **Move** - Action\n* **Position** - State\n* **Terminal state** - States when game ended.\n* **State space graph** - Graph where states are vertices, and movs are edges.\n* **Game tree** - Search tree that follows every sequence of moves to reach terminal state.\n* **Killer moves** - Best moves.\n* **Killer move heuristic** - Trying killer moves first.\n* **Transpositions** - Different permutations of move sequence that will end up in the same position. Cause repated states.\n* **Weighted linear function** - With material value, assign normalized weight to function.\n* **Quiescent** - Positions when there is no pending move that will wildly affect evaluation\n* **Nonquiescent position** - Is-cuttoff returns false\n* **Horizon effect** - When facing detrimental and unavoidable moves from opponent, only can temporarily delay.\n* **Singular extensions** - Mitigate horizon effect, a clearly better move.\n* **Policy** - Mapping from every possible state to best move in that state.\n* **Decision theory** - Choose among actions based on desirability of immediate outcome.\n* **Expected utility** - Average utility value of outcomes, weighted by chance of outcome occurring.\n* **Value function** - Another name for ordinal utility function.\n* **Ordinal utility function** - An agent needs only a preference ranking on states, numbers dont matter.\n* **Preference elicitation** - Find utility function by presenting choices to humans and observe their preferences.\n* **Optimizer’s curse** - Tendency for the estimated expected utility of the best choice to be too high.\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "\n",
        "#### Constraint satisfaction problem (CSP)\n",
        "- Use a factored representation for each state, which is a set of variables, each of which has a value.\n",
        "- Problem solved when each variable has a value that satisfies all constraints on the variable. \n",
        "- Use general rather than domain-specific heuristics to enable the solution of complex problems.\n",
        "- Actions and transition model can be deduced from the problem description.\n",
        "- Solution to CSP is complete, consistent assignment. \n",
        "- Solving CSP is generally NP-complete. \n",
        "\n",
        "#### CSP components\n",
        "1. X: A set of variables. Like countries in coloring.\n",
        "2. D: A set of domains, one for each variable. Contains allowable values for X. Like colors for countries (RGB).\n",
        "3. C: A set of constraints that specify allowable combination of values. Each constraint consists of \n",
        "a pair <Scope, rel>, scope is a tuple of variables that participate in constraint, and rel is a \n",
        "relation that defines values that those variables can take on. Like <(SA,WA), SA != WA>\n",
        "\n",
        "#### WHY CSP\n",
        "- CSPs yield a natural representation for a wide variety of problems; it is often easy to formulate a problem as a CSP.\n",
        "- Now solves problem efficient and fast.\n",
        "\n",
        "#### Domains\n",
        "- A discrete domain can be infinite, such as the set of integers or strings.\n",
        "- With finite domains, we must use implicit constraints like T1 + d1 <= T2.\n",
        "\n",
        "#### Constraint hypergraph\n",
        "- Consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), \n",
        "which represent n-ary constraints—constraints involving n variables.\n",
        "\n",
        "#### Global contraint better than set of binary constraints\n",
        "- First, it is easier and less error-prone to write the problem description.\n",
        "- Second, it is possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints.\n",
        "\n",
        "#### Constrained optimization problem (COP)\n",
        "- Preference constraints can often be encoded as costs on individual variable assignments—for example, \n",
        "assigning an afternoon slot for Prof. R costs 2 points against the overall objective function, \n",
        "whereas a morning slot costs 1. With this formulation, \n",
        "CSPs with preferences can be solved with optimization search methods, either path-based or local.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "\n",
        "#### Constraint propagation:\n",
        "- Using the constraints to reduce the number of legal values for a variable, \n",
        "which in turn can reduce the legal values for another variable, and so on.\n",
        "- Leave fewer choices to consider when making next choice of a variable assignment. \n",
        "- The key idea is local consistency. Variable as node, binary constraint as edge. \n",
        "Then the process of enforcing local consistency in each part of the graph causes inconsistent \n",
        "values to be eliminated throughout the graph.\n",
        "\n",
        "#### AC-3\n",
        "- Enforce arc consistency. \n",
        "- O(cd^3), d is domain size, c is binary constraints (arcs)\n",
        "\n",
        "#### Path consistency\n",
        "- A two-variable set {A,B} is path-consistent with respect to a third variable C if for every assignment \n",
        "for A and B, there is an assignemnt to C that satisfies {A, C} and {A, B}\n",
        "\n",
        "#### K-consistent\n",
        "- A CSP is k-consistent if, for any set of  k - 1 variables \n",
        "and for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.\n",
        "- 1-consistency ays that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency.\n",
        "- 2-consistency is the same as arc consistency.\n",
        "-  For binary constraint graphs, 3-consistency is the same as path consistency.\n",
        "\n",
        "#### Strongly k-consistent\n",
        "- If CSP is k-consistent, and also (k-1) consistent, (k-2) consistent, until 1-consistent.\n",
        "- Total run time is O(n^2 d), n is k, number of nodes. d is domain size.\n",
        "- NP-complete in general. \n",
        "- Exponential requirement space in n.\n",
        "\n",
        "#### Global constraints\n",
        "- Handled by special-purpose algorithms that are more efficient than the general-purpose methods\n",
        "- To detect inconsistency: First, remove any variable in the constraint that has a singleton domain, and delete that variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected.\n",
        "\n",
        "#### Resource constraint / Bounds-consistent\n",
        "- Also called Atmost constraint.\n",
        "- Given limited resources, find inconsistency by sum of minimum values of current domains.\n",
        "- For bound propagation domains, [0,165] and [0,385] reduced to [35,165] and [255,385] if F1+F2=420.\n",
        "- Bounds consistent if for every variable X and for both the lower-bound and upper-bound values of X,\n",
        "there exists some value of Y that satisfies contraints between X and Y for every variable Y.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "\n",
        "#### Backtracking search for CSPs\n",
        "- Search tree where all the complete assignments (and thus all the solutions) are leaf nodes at depth n.\n",
        "- Branching factor is nd, because any d values can be assigned to any of n variables. Next level is (n-1)d.\n",
        "- So tree has n!*d^n leaves, but only d&n possible complete assignments. \n",
        "- Only a single representation of a state (assignment) and alters that representation rather than creating new ones.\n",
        "- Can be improved using domain-independent heuristics that take advantage of the factored representation of CSPs.\n",
        "- Degree heuristic as tie breaker.\n",
        "- Once a variable has been selected, the algorithm must decide on the order in which to examine its values. The least-constraining-value heuristic is effective for this. \n",
        "It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n",
        "\n",
        "#### Forward checking\n",
        "- Whenever a variable  is assigned, the forward-checking process establishes arc consistency for it.\n",
        "Each Y connects to X by a constant.\n",
        "Delete from Y's domain any value that is inconsistent with the value chosen for X.\n",
        "\n",
        "#### Maintaining Arc Consistency (MAC)\n",
        "- Use when forward checking is not forward enough. \n",
        "- Recursively propagate constraints when changes are made to the domains of variables.\n",
        "\n",
        "#### Backjumping\n",
        "- Backjumping notices failure when a variable’s domain becomes empty, \n",
        "but in many cases a branch is doomed long before this occurs.\n",
        "\n",
        "#### Constraint learning\n",
        "- Avoid running into same problem again after backjumping.\n",
        "- Idea of finding a minimum set of variables from the conflict set that causes the problem. \n",
        "- This set of variables, along with their corresponding values, is called a no-good.\n",
        "- We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.\n",
        "- Not useful if forward checking can tell it is no good.\n",
        "- Useful to know if a state is no good, we will run into same problem again for each possible set of assignments.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "\n",
        "#### Min-conflict\n",
        "- Runtime is roughly  independent of problem size if do not count the initial placement of Queens.\n",
        "\n",
        "####  Tabu search\n",
        "- Keeping a small list of recently visited states and forbidding the algorithm to return to those states. \n",
        "Simulated annealing can also be used to escape from plateaus.\n",
        "\n",
        "#### Constraint weighting\n",
        "- Aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n",
        "- Making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "\n",
        "#### Independent subproblems\n",
        "- Any solution for the mainland combined with any solution for Tasmania yields a solution for the whole map.\n",
        "- Independence can be ascertained simply by finding connected components of the constraint graph.\n",
        "\n",
        "#### Directional arc consistency (DAC)\n",
        "- A CSP is defined to be directional arc-consistent uner an ordering of variables X1, X2,...,Xn if and only if every\n",
        "Xi is arc-consistent with each Xj for j > i.\n",
        "\n",
        "#### Solve tree-structured CSP\n",
        "- Use topological sort.\n",
        "- O(n), time O(nd^2).\n",
        "\n",
        "#### Cutset conditioning\n",
        "- The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\n",
        "- Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n",
        "- For each possible assignment to the variable S that satisfies all constraints on S. Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S. \n",
        "And if the remaining CSP has a solution, return it together with the assignment for S.\n",
        "- Run time is O (d^c * (n-c)d^2)\n",
        "- Need to try each d^c combinations of values for the variables in S, and for each combination we must solve a tree problem of size n - c.\n",
        "- FInding smallest cycle cutset is NP-hard. \n",
        "\n",
        "#### Tree decomposition\n",
        "-  To reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph.\n",
        "- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
        "- Three requirements:\n",
        "1. Every variable in the original problem appears in at least one of the tree nodes.\n",
        "2. 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",
        "3. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n",
        "- O(nd^2) time. n is number of tree nodes, d is size of the largest domain.\n",
        "- A domain is a set of tuples of values, not individul values.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Consistent assignment\" : \"Does not violate constraints.\",    \n",
        "\"Complete assignment\" : \"Every variable is assigned a vlue.\",   \n",
        "\"Partial assignment\" : \"Some values are not assigned.\",   \n",
        "\"Partial solution\" : \"Partial consistnt assignment.\",   \n",
        "\"Linear programming problems\" : \"Constraints are linear equalities or inequalities/ Continuous domain CSP.\",    \n",
        "\"Unary constraint\" : \"Value of a single variable being restricted. Like SouthAus wont tolerate green.\",   \n",
        "\"Binary constraint\" : \"Relates two variables, like SA!=NSW.\",   \n",
        "\"Binary CSP\" : \"Only with unary and binary constraints.\",   \n",
        "\"Global constraint\" : \"Constraint involving an arbitrary number of variables. (need not all) Like Sudoku.\",    \n",
        "\"Preference constraints\" : \"Indicating the preferred solutions. \",   \n",
        "\"Node consistent\" : \"A variable if all values in that variable's domain satify its unary constraints.\",   \n",
        "\"Graph is node-consistent\" : \"Every variable in the graph is node-consistent.\",   \n",
        "\"Arc consistent\" : \"Every value in its domain satisfies the variable’s binary constraints.\",    \n",
        "\"Path consistency\" : \"Tightens binary constraints with implicit constraints inferred by looking at triples of variables\",   \n",
        "\"Bounds propagation\" : \"Manage lower and upper bounds of domains. [0,165] plane capacity.\",   \n",
        "\"Commutative\" : \"A problem is commutative if order of applicatiosn of any give set of actions does not matter\",   \n",
        "\"Minimum-remaining-values (MRV) heuristic\" : \"Choose variable with least legal values.\",    \n",
        "\"Degree heuristic\" : \"Give degree based on largest number of constraints on other unassigned variables. \",   \n",
        "\"Chronological backtracking\" : \"Revisit most recent decision point.\",   \n",
        "\"Backjumping\" : \"Backtracks to most recent assignment in conflict set.\",   \n",
        "\"Conflict-directed backjumping\" : \"A backjumping algorithm that uses conflict sets.\", \n",
        "\"Min-conflicts heuristic\" : \"Select the value that results in the minimum number of conflicts with other variables.\", \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c53b127b-7613-435d-838f-5b3b9e79e8a1"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n\n#### Constraint satisfaction problem (CSP)\n- Use a factored representation for each state, which is a set of variables, each of which has a value.\n- Problem solved when each variable has a value that satisfies all constraints on the variable. \n- Use general rather than domain-specific heuristics to enable the solution of complex problems.\n- Actions and transition model can be deduced from the problem description.\n- Solution to CSP is complete, consistent assignment. \n- Solving CSP is generally NP-complete. \n\n#### CSP components\n1. X: A set of variables. Like countries in coloring.\n2. D: A set of domains, one for each variable. Contains allowable values for X. Like colors for countries (RGB).\n3. C: A set of constraints that specify allowable combination of values. Each constraint consists of \na pair <Scope, rel>, scope is a tuple of variables that participate in constraint, and rel is a \nrelation that defines values that those variables can take on. Like <(SA,WA), SA != WA>\n\n#### WHY CSP\n- CSPs yield a natural representation for a wide variety of problems; it is often easy to formulate a problem as a CSP.\n- Now solves problem efficient and fast.\n\n#### Domains\n- A discrete domain can be infinite, such as the set of integers or strings.\n- With finite domains, we must use implicit constraints like T1 + d1 <= T2.\n\n#### Constraint hypergraph\n- Consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), \nwhich represent n-ary constraints—constraints involving n variables.\n\n#### Global contraint better than set of binary constraints\n- First, it is easier and less error-prone to write the problem description.\n- Second, it is possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints.\n\n#### Constrained optimization problem (COP)\n- Preference constraints can often be encoded as costs on individual variable assignments—for example, \nassigning an afternoon slot for Prof. R costs 2 points against the overall objective function, \nwhereas a morning slot costs 1. With this formulation, \nCSPs with preferences can be solved with optimization search methods, either path-based or local.\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n#### Constraint propagation:\n- Using the constraints to reduce the number of legal values for a variable, \nwhich in turn can reduce the legal values for another variable, and so on.\n- Leave fewer choices to consider when making next choice of a variable assignment. \n- The key idea is local consistency. Variable as node, binary constraint as edge. \nThen the process of enforcing local consistency in each part of the graph causes inconsistent \nvalues to be eliminated throughout the graph.\n\n#### AC-3\n- Enforce arc consistency. \n- O(cd^3), d is domain size, c is binary constraints (arcs)\n\n#### Path consistency\n- A two-variable set {A,B} is path-consistent with respect to a third variable C if for every assignment \nfor A and B, there is an assignemnt to C that satisfies {A, C} and {A, B}\n\n#### K-consistent\n- A CSP is k-consistent if, for any set of  k - 1 variables \nand for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.\n- 1-consistency ays that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency.\n- 2-consistency is the same as arc consistency.\n-  For binary constraint graphs, 3-consistency is the same as path consistency.\n\n#### Strongly k-consistent\n- If CSP is k-consistent, and also (k-1) consistent, (k-2) consistent, until 1-consistent.\n- Total run time is O(n^2 d), n is k, number of nodes. d is domain size.\n- NP-complete in general. \n- Exponential requirement space in n.\n\n#### Global constraints\n- Handled by special-purpose algorithms that are more efficient than the general-purpose methods\n- To detect inconsistency: First, remove any variable in the constraint that has a singleton domain, and delete that variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected.\n\n#### Resource constraint / Bounds-consistent\n- Also called Atmost constraint.\n- Given limited resources, find inconsistency by sum of minimum values of current domains.\n- For bound propagation domains, [0,165] and [0,385] reduced to [35,165] and [255,385] if F1+F2=420.\n- Bounds consistent if for every variable X and for both the lower-bound and upper-bound values of X,\nthere exists some value of Y that satisfies contraints between X and Y for every variable Y.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n\n#### Backtracking search for CSPs\n- Search tree where all the complete assignments (and thus all the solutions) are leaf nodes at depth n.\n- Branching factor is nd, because any d values can be assigned to any of n variables. Next level is (n-1)d.\n- So tree has n!*d^n leaves, but only d&n possible complete assignments. \n- Only a single representation of a state (assignment) and alters that representation rather than creating new ones.\n- Can be improved using domain-independent heuristics that take advantage of the factored representation of CSPs.\n- Degree heuristic as tie breaker.\n- Once a variable has been selected, the algorithm must decide on the order in which to examine its values. The least-constraining-value heuristic is effective for this. \nIt prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n\n#### Forward checking\n- Whenever a variable  is assigned, the forward-checking process establishes arc consistency for it.\nEach Y connects to X by a constant.\nDelete from Y's domain any value that is inconsistent with the value chosen for X.\n\n#### Maintaining Arc Consistency (MAC)\n- Use when forward checking is not forward enough. \n- Recursively propagate constraints when changes are made to the domains of variables.\n\n#### Backjumping\n- Backjumping notices failure when a variable’s domain becomes empty, \nbut in many cases a branch is doomed long before this occurs.\n\n#### Constraint learning\n- Avoid running into same problem again after backjumping.\n- Idea of finding a minimum set of variables from the conflict set that causes the problem. \n- This set of variables, along with their corresponding values, is called a no-good.\n- We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.\n- Not useful if forward checking can tell it is no good.\n- Useful to know if a state is no good, we will run into same problem again for each possible set of assignments.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n\n#### Min-conflict\n- Runtime is roughly  independent of problem size if do not count the initial placement of Queens.\n\n####  Tabu search\n- Keeping a small list of recently visited states and forbidding the algorithm to return to those states. \nSimulated annealing can also be used to escape from plateaus.\n\n#### Constraint weighting\n- Aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n- Making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \n\n#### Independent subproblems\n- Any solution for the mainland combined with any solution for Tasmania yields a solution for the whole map.\n- Independence can be ascertained simply by finding connected components of the constraint graph.\n\n#### Directional arc consistency (DAC)\n- A CSP is defined to be directional arc-consistent uner an ordering of variables X1, X2,...,Xn if and only if every\nXi is arc-consistent with each Xj for j > i.\n\n#### Solve tree-structured CSP\n- Use topological sort.\n- O(n), time O(nd^2).\n\n#### Cutset conditioning\n- The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\n- Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n- For each possible assignment to the variable S that satisfies all constraints on S. Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S. \nAnd if the remaining CSP has a solution, return it together with the assignment for S.\n- Run time is O (d^c * (n-c)d^2)\n- Need to try each d^c combinations of values for the variables in S, and for each combination we must solve a tree problem of size n - c.\n- FInding smallest cycle cutset is NP-hard. \n\n#### Tree decomposition\n-  To reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph.\n- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n- Three requirements:\n1. Every variable in the original problem appears in at least one of the tree nodes.\n2. 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.\n3. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n- O(nd^2) time. n is number of tree nodes, d is size of the largest domain.\n- A domain is a set of tuples of values, not individul values.\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Consistent assignment** - Does not violate constraints.\n* **Complete assignment** - Every variable is assigned a vlue.\n* **Partial assignment** - Some values are not assigned.\n* **Partial solution** - Partial consistnt assignment.\n* **Linear programming problems** - Constraints are linear equalities or inequalities/ Continuous domain CSP.\n* **Unary constraint** - Value of a single variable being restricted. Like SouthAus wont tolerate green.\n* **Binary constraint** - Relates two variables, like SA!=NSW.\n* **Binary csp** - Only with unary and binary constraints.\n* **Global constraint** - Constraint involving an arbitrary number of variables. (need not all) Like Sudoku.\n* **Preference constraints** - Indicating the preferred solutions. \n* **Node consistent** - A variable if all values in that variable's domain satify its unary constraints.\n* **Graph is node-consistent** - Every variable in the graph is node-consistent.\n* **Arc consistent** - Every value in its domain satisfies the variable’s binary constraints.\n* **Path consistency** - Tightens binary constraints with implicit constraints inferred by looking at triples of variables\n* **Bounds propagation** - Manage lower and upper bounds of domains. [0,165] plane capacity.\n* **Commutative** - A problem is commutative if order of applicatiosn of any give set of actions does not matter\n* **Minimum-remaining-values (mrv) heuristic** - Choose variable with least legal values.\n* **Degree heuristic** - Give degree based on largest number of constraints on other unassigned variables. \n* **Chronological backtracking** - Revisit most recent decision point.\n* **Backjumping** - Backtracks to most recent assignment in conflict set.\n* **Conflict-directed backjumping** - A backjumping algorithm that uses conflict sets.\n* **Min-conflicts heuristic** - Select the value that results in the minimum number of conflicts with other variables.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "\n",
        "#### Knowledge base\n",
        "- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world.\n",
        "- KB agent takes a percept as input and returns an action. \n",
        "\n",
        "#### KB Agent program\n",
        "- Do 3 things each time called:\n",
        "1. Tells the knowledge base what it perceives.\n",
        "2. Asks the knowledge base what action it should perform.\n",
        "3. Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n",
        "- Make-Percept-Sentence: 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 action should be done at the current time.\n",
        "- Can be built simply by Telling it what it needs to know. \n",
        "1. Declarative approach: Tell sentences on by one until agent knows how to oeprate in its environment.\n",
        "2. Procedural approach: Encodes desired behaviors directly as program code.\n",
        "\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "\n",
        "#### Wumpus world Sample\n",
        "1. Performance measure: + 1000 for climbing, -1000 for falling, - 1for each action taken.\n",
        "2. Enviornment: 4x4 grid, always start labeled [1,1]\n",
        "3. Actuators: Agent can move forward, turn left by 90, turn right by 90.\n",
        "4. Sensors: 5 Sensors, sense for stench, breeze, glitter, bump, scream. As percepts.\n",
        "- It is deterministic, discrete, static, and single-agent.\n",
        "- Sequential, rewards come after actions are taken. \n",
        "- Partially observable, because some aspects of the state are not directly perceivable.\n",
        "- Transition model itself is unknown, because agent doesnt know which action is fatal. \n",
        "\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "\n",
        "### Logic\n",
        "\n",
        "#### Syntax\n",
        "- Sentences in KB follows syntax of representation language, hich specifies all the sentences that are well formed. \n",
        "\n",
        "#### Models\n",
        "- The possible models are just all possible assignments of nonnegative integers to the variables.\n",
        "- If sentence a is true in model m, m satisfis a or m is a model of a. M(a) mean set of all models of a.\n",
        "\n",
        "#### Entailment\n",
        "- If a entails b, a is a stronger assertion than b, it rules out more possible worlds. \n",
        "\n",
        "#### Sound / truth preserving\n",
        "- An inference algorithm that derives only entailed sentences.\n",
        "- Soundness is highly desirable. \n",
        "- Unsound inference procedure announces nonexistent needles.\n",
        "- If KB is true in real world, then any sentence a derived from KB y a sound inference\n",
        "procedure is also true in real world. \n",
        "\n",
        "#### Check if space of models is finite\n",
        "- Wumpus is fixed size.\n",
        "- Arithmetic space of model is infinite.\n",
        "\n",
        "#### Consider grounding issue\n",
        "- The connection between logical reasoning processes and the real environment in which the agent exists.\n",
        "- Agent's sensors create the connection. \n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "\n",
        "#### Propositional logic\n",
        "- Describe syntax and semantics (the way in which the truth is determined)\n",
        "\n",
        "#### Complex sentences, five connectives in common use\n",
        "- Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n",
        "- not operator has highest precedence, means not A and B, not binds tightest, so it is (not A) and B.\n",
        "\n",
        "#### Semantics\n",
        "- Defines the rules for determining the truth of a sentence with respect to a particular model.\n",
        "- Recursively, the semantics for propositional logic must specify how to compute the truth value of any sentence, given a model.\n",
        "- For complex sentences there are 5 rules: (Check pictures)\n",
        "\n",
        "#### Simple knowledge base\n",
        "- Focus first on immutable aspects.\n",
        "\n",
        "#### Simple inference procedure\n",
        "- Goal is to decide whether KB entails a for some sentence a. Like if not pit 2,1 entailed by KB.\n",
        "- Enumerate models, check if a is true in every model in which KB is true.\n",
        "- Models are assignments of true or false to every proposition symbol.\n",
        "- Models are TF tables, if all possible model rows have same result for certain sentence, then those must be true. Like no pit in 1,2.\n",
        "- Time O(2^n), space O(n).\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "\n",
        "#### Theorem proving\n",
        "- Applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n",
        "\n",
        "#### Validity\n",
        "- A sentence is valid if it is true in all models.\n",
        "- Such as P V not P\n",
        "- Valid sentences are also known as tautologies—they are necessarily true.\n",
        "- Because the sentence True is true in all models, every valid sentence is logically equivalent to True.\n",
        "\n",
        "#### Deduction theorm\n",
        "- Check picture\n",
        "- a entails b by checking that a implies b in every model.\n",
        "\n",
        "#### Satisfiability\n",
        "- A sentence is satisfiable if it is true in, or satisfied by, some model. \n",
        "- Satisfiability can be checked by enumerating the possible models until one is found that satisfies the sentence.\n",
        "- The problem of determining the satisfiability of sentences in propositional logic—the SAT problem—was the first problem proved to be NP-complete.\n",
        "- Connected to validity. a is valid iff not a is unsatisfiable. \n",
        "\n",
        "#### Inference rules\n",
        "- See picture\n",
        "- Any logical equivalences can be used as inference rules. \n",
        "\n",
        "\n",
        "#### Define a proof problem\n",
        "- INITIAL STATE: the initial knowledge base.\n",
        "- ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n",
        "- RESULT: the result of an action is to add the sentence in the bottom half of the inference rule.\n",
        "- GOAL: the goal is a state that contains the sentence we are trying to prove.\n",
        "\n",
        "#### Searching for proof\n",
        "- Searching for proofs is an alternative to enumerating models.\n",
        "- Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are.\n",
        "\n",
        "#### Final property of logical system: Monotonicity\n",
        "- The set of entailed sentences can only increase as information is added to the knowledge base.\n",
        "- Conclusion of the rule must follow regardless of what else is in the knowledge base\n",
        "\n",
        "#### Resolution\n",
        "- Gives resolvent\n",
        "- Negate complementary literals with unit resolution, which means one is the negation of another. \n",
        "- Pit must be in ABC, but not in B and C, so must be in A. This is unit resolution inference rule. \n",
        "- Factoring: Remove multiple copies of literals. (AVB)&(AVnotB) = (AVA) = A\n",
        "\n",
        "#### Conjunctive normal form\n",
        "- Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n",
        "- A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "#### Resolution algorithm\n",
        "- To show KB entails a, we show that KB and not a is not satisfiable. \n",
        "- Inference procedures base don resolution work using the principle of proof by contradiction.\n",
        "- First KB and not a is converted into CNF.\n",
        "- Then, the resolution rule is applied to the resulting clauses.\n",
        "- 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.\n",
        "- The process continues until one of two things happens:\n",
        "1. there are no new clauses that can be added, in which case KB does not entail a; or,\n",
        "2. two clauses resolve to yield the empty clause, in which case KB entails a.\n",
        "- Complete\n",
        "- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n",
        "\n",
        "#### Horn clauses and definite clauses\n",
        "- Definite clauses: a disjunction of literals of which exactly one is positive. \n",
        "- Horn clauses: a disjunction of literals of which at most one is positive.\n",
        "- So all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n",
        "- Horn clauses are closed under resolution: if you resolve two Horn clauses, you get back a Horn clause. One more class is the k-CNF sentence, which is a CNF sentence where each clause has at most k literals.\n",
        "\n",
        "#### Forward and backward chaining\n",
        "- Forward chaining algo determines if a single proposition symbol q, the query, is entailed by a KB of definite clauses.\n",
        "- Meaning L1,1 and Breeze are known, so implies B1,1 and add to KB.\n",
        "- Continue until no further inferences can be made. \n",
        "- General concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n",
        "- Backward chaining is a form of goal-directed reasoning.\n",
        "- If the query  is known to be true, then no work is needed. Otherwise, the algorithm finds those implications in the knowledge base whose conclusion is query. If all the premises of \n",
        "one of those implications can be proved true, then query is true.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge base\" : \"A set of sentences.\",    \n",
        "\"Axiom\" : \"Sentence taken as being given without being derived from other sentences.\", \n",
        "\"Tell and Ask\" : \"Add new sentences to KB and query what is known.\", \n",
        "\"Inference\" : \"Deriving new sentences from old.\", \n",
        "\"Semantics\" : \"Meaning, of sentences. Defines truth of each sentence to each possible world.\", \n",
        "\"Model\" : \"Use model in place of possible world when need to be precise. \", \n",
        "\"Logical entailment\" : \"The idea that a sentence follows logically from another sentence\",    \n",
        "\"Model checking\" : \"Enumerates all possible models to check a is true in all models where KB is true. M(KB)subset of M(a)\", \n",
        "\"Completeness\" : \"If cnan derive any sentence that is entailed. \", \n",
        "\"Syntax\" : \"Defines allowable sentences. \", \n",
        "\"Atomic sentences\" : \"Consist a single proposition symbol\", \n",
        "\"Proposition symbol\" : \"Shows if proposition is true or false.\", \n",
        "\"Logical equivalence\" : \"Two sentences are logical equivalent if they are true in the same set of models.\",    \n",
        "\"Resolution\" : \"Single inference rule, yield complete inference algo with any complete search algo.\", \n",
        "\"Complementary literals\" : \"One is negation of another\", \n",
        "\"Resolution closure\" : \"Computes as the final value of the variable clauses.\", \n",
        "\"Ground resolution theorem\" : \"The completeness theorem for resolution in propositional logic.\", \n",
        "\"Body\" : \"Horn clause premise\", \n",
        "\"Head\" : \"Horn clause head\",    \n",
        "\"Fact\" : \"Sentence with a single positive literal\", \n",
        "\"concept\" : \"definition\", \n",
        "\"concept\" : \"definition\", \n",
        "\"concept\" : \"definition\", \n",
        "\"concept\" : \"definition\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "27532ccd-1e38-43ad-c67f-3fffd8f1d5dc"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n\n#### Knowledge base\n- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world.\n- KB agent takes a percept as input and returns an action. \n\n#### KB Agent program\n- Do 3 things each time called:\n1. Tells the knowledge base what it perceives.\n2. Asks the knowledge base what action it should perform.\n3. Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n- Make-Percept-Sentence: 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 action should be done at the current time.\n- Can be built simply by Telling it what it needs to know. \n1. Declarative approach: Tell sentences on by one until agent knows how to oeprate in its environment.\n2. Procedural approach: Encodes desired behaviors directly as program code.\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n#### Wumpus world Sample\n1. Performance measure: + 1000 for climbing, -1000 for falling, - 1for each action taken.\n2. Enviornment: 4x4 grid, always start labeled [1,1]\n3. Actuators: Agent can move forward, turn left by 90, turn right by 90.\n4. Sensors: 5 Sensors, sense for stench, breeze, glitter, bump, scream. As percepts.\n- It is deterministic, discrete, static, and single-agent.\n- Sequential, rewards come after actions are taken. \n- Partially observable, because some aspects of the state are not directly perceivable.\n- Transition model itself is unknown, because agent doesnt know which action is fatal. \n\n \n\n## AIMA Chapter 7.3 Logic\n \n\n### Logic\n\n#### Syntax\n- Sentences in KB follows syntax of representation language, hich specifies all the sentences that are well formed. \n\n#### Models\n- The possible models are just all possible assignments of nonnegative integers to the variables.\n- If sentence a is true in model m, m satisfis a or m is a model of a. M(a) mean set of all models of a.\n\n#### Entailment\n- If a entails b, a is a stronger assertion than b, it rules out more possible worlds. \n\n#### Sound / truth preserving\n- An inference algorithm that derives only entailed sentences.\n- Soundness is highly desirable. \n- Unsound inference procedure announces nonexistent needles.\n- If KB is true in real world, then any sentence a derived from KB y a sound inference\nprocedure is also true in real world. \n\n#### Check if space of models is finite\n- Wumpus is fixed size.\n- Arithmetic space of model is infinite.\n\n#### Consider grounding issue\n- The connection between logical reasoning processes and the real environment in which the agent exists.\n- Agent's sensors create the connection. \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n\n#### Propositional logic\n- Describe syntax and semantics (the way in which the truth is determined)\n\n#### Complex sentences, five connectives in common use\n- Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n- not operator has highest precedence, means not A and B, not binds tightest, so it is (not A) and B.\n\n#### Semantics\n- Defines the rules for determining the truth of a sentence with respect to a particular model.\n- Recursively, the semantics for propositional logic must specify how to compute the truth value of any sentence, given a model.\n- For complex sentences there are 5 rules: (Check pictures)\n\n#### Simple knowledge base\n- Focus first on immutable aspects.\n\n#### Simple inference procedure\n- Goal is to decide whether KB entails a for some sentence a. Like if not pit 2,1 entailed by KB.\n- Enumerate models, check if a is true in every model in which KB is true.\n- Models are assignments of true or false to every proposition symbol.\n- Models are TF tables, if all possible model rows have same result for certain sentence, then those must be true. Like no pit in 1,2.\n- Time O(2^n), space O(n).\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n#### Theorem proving\n- Applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n\n#### Validity\n- A sentence is valid if it is true in all models.\n- Such as P V not P\n- Valid sentences are also known as tautologies—they are necessarily true.\n- Because the sentence True is true in all models, every valid sentence is logically equivalent to True.\n\n#### Deduction theorm\n- Check picture\n- a entails b by checking that a implies b in every model.\n\n#### Satisfiability\n- A sentence is satisfiable if it is true in, or satisfied by, some model. \n- Satisfiability can be checked by enumerating the possible models until one is found that satisfies the sentence.\n- The problem of determining the satisfiability of sentences in propositional logic—the SAT problem—was the first problem proved to be NP-complete.\n- Connected to validity. a is valid iff not a is unsatisfiable. \n\n#### Inference rules\n- See picture\n- Any logical equivalences can be used as inference rules. \n\n\n#### Define a proof problem\n- INITIAL STATE: the initial knowledge base.\n- ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n- RESULT: the result of an action is to add the sentence in the bottom half of the inference rule.\n- GOAL: the goal is a state that contains the sentence we are trying to prove.\n\n#### Searching for proof\n- Searching for proofs is an alternative to enumerating models.\n- Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are.\n\n#### Final property of logical system: Monotonicity\n- The set of entailed sentences can only increase as information is added to the knowledge base.\n- Conclusion of the rule must follow regardless of what else is in the knowledge base\n\n#### Resolution\n- Gives resolvent\n- Negate complementary literals with unit resolution, which means one is the negation of another. \n- Pit must be in ABC, but not in B and C, so must be in A. This is unit resolution inference rule. \n- Factoring: Remove multiple copies of literals. (AVB)&(AVnotB) = (AVA) = A\n\n#### Conjunctive normal form\n- Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n- A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n\n \n\n## Module 7 Lecture Notes\n \n\n#### Resolution algorithm\n- To show KB entails a, we show that KB and not a is not satisfiable. \n- Inference procedures base don resolution work using the principle of proof by contradiction.\n- First KB and not a is converted into CNF.\n- Then, the resolution rule is applied to the resulting clauses.\n- 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.\n- The process continues until one of two things happens:\n1. there are no new clauses that can be added, in which case KB does not entail a; or,\n2. two clauses resolve to yield the empty clause, in which case KB entails a.\n- Complete\n- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n#### Horn clauses and definite clauses\n- Definite clauses: a disjunction of literals of which exactly one is positive. \n- Horn clauses: a disjunction of literals of which at most one is positive.\n- So all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n- Horn clauses are closed under resolution: if you resolve two Horn clauses, you get back a Horn clause. One more class is the k-CNF sentence, which is a CNF sentence where each clause has at most k literals.\n\n#### Forward and backward chaining\n- Forward chaining algo determines if a single proposition symbol q, the query, is entailed by a KB of definite clauses.\n- Meaning L1,1 and Breeze are known, so implies B1,1 and add to KB.\n- Continue until no further inferences can be made. \n- General concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n- Backward chaining is a form of goal-directed reasoning.\n- If the query  is known to be true, then no work is needed. Otherwise, the algorithm finds those implications in the knowledge base whose conclusion is query. If all the premises of \none of those implications can be proved true, then query is true.\n \n\n## Module 7 Definitions\n* **Knowledge base** - A set of sentences.\n* **Axiom** - Sentence taken as being given without being derived from other sentences.\n* **Tell and ask** - Add new sentences to KB and query what is known.\n* **Inference** - Deriving new sentences from old.\n* **Semantics** - Meaning, of sentences. Defines truth of each sentence to each possible world.\n* **Model** - Use model in place of possible world when need to be precise. \n* **Logical entailment** - The idea that a sentence follows logically from another sentence\n* **Model checking** - Enumerates all possible models to check a is true in all models where KB is true. M(KB)subset of M(a)\n* **Completeness** - If cnan derive any sentence that is entailed. \n* **Syntax** - Defines allowable sentences. \n* **Atomic sentences** - Consist a single proposition symbol\n* **Proposition symbol** - Shows if proposition is true or false.\n* **Logical equivalence** - Two sentences are logical equivalent if they are true in the same set of models.\n* **Resolution** - Single inference rule, yield complete inference algo with any complete search algo.\n* **Complementary literals** - One is negation of another\n* **Resolution closure** - Computes as the final value of the variable clauses.\n* **Ground resolution theorem** - The completeness theorem for resolution in propositional logic.\n* **Body** - Horn clause premise\n* **Head** - Horn clause head\n* **Fact** - Sentence with a single positive literal\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "4432a076-1b21-4eee-d5fa-a06ce4f197c7"
      },
      "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 Some consider intelligence to be a property of internal thought processes and reasoning, \nwhile others focus on intelligent behavior, an external characterization.\n\nComputer need following capabilities to pass turing tests:\n1. natural language processing to communicate successfully in a human language;\n2. knowledge representation to store what it knows or hears;\n3. knowledge representation to store what it knows or hears;\n4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nTuring viewed the physical simulation of a person as unnecessary to demonstrate intelligence.\n\nTo pass turing test, robot needs computer vision and speech recognition to perceive the world and\nrobotics to manipulate objects and move about.\n\nLearn human thoughts in 3 ways:\n1. introspection—trying to catch our own thoughts as they go by;\n2. psychological experiments—observing a person in action;\n3. brain imaging—observing the brain in action.\n\nSyllogisms:\nProvided patterns for argument structures that always yielded correct conclusions \nwhen given correct premises. \n\nLogic:\nas conventionally understood requires knowledge of the world that \nis certain—a condition that, in reality, is seldom achieved. \n\nAgent acting:\nAll the skills needed for the Turing test also allow an agent to act rationally. \nKnowledge representation and reasoning enable agents to reach good decisions.\n\nRational-agent approach advantages:\nFirst, it is more general than the “laws of thought” approach because correct inference \nis just one of several possible mechanisms for achieving rationality. \nSecond, it is more amenable to scientific development.\n\nStandard model bad in long run, because it assumes we supply fully specified objective to machine.\n\n\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n \nTuring’s “argument from informality of behavior” says that human behavior is far too complex \nto be captured by any formal set of rules—humans must be using some informal guidelines that \n(the argument claims) could never be captured in a formal set of rules and thus could never be \ncodified in a computer program.\n\nGood Old-Fashioned AI (GOFAI):\nArtificial intelligence pursued within the cult of computationalism stands \nnot even a ghost of a chance of producing durable results.\nGOFAI corresponds to the simplest logical agent design described in Chapter 7, \nand we saw there that it is indeed difficult to capture every contingency of appropriate \nbehavior in a set of necessary and sufficient logical rules; \nwe called that the qualification problem. \n\nEmbodied cognition:\nit makes no sense to consider the brain separately: \ncognition takes place within a body, which is embedded in an environment. \nWe need to study the system as a whole; the brain’s functioning exploits \nregularities in its environment, including the rest of its body. \nUnder the embodied cognition approach, robotics, vision, and other sensors become central, \nnot peripheral.\n\nGödel sentence G(F) with the following properties:\nG(F) is a sentence of F, but cannot be proved within F.\nIf F is consistent, then G(F) is true.\n\nSecond, Gödel’s incompleteness theorem and related results apply to mathematics, not to computers. \nNo entity—human or machine—can prove things that are impossible to prove.\n\nThird, Gödel’s incompleteness theorem technically applies only to formal systems that are \npowerful enough to do arithmetic. This includes Turing machines, and Lucas’s claim is in \npart based on the assertion that computers are equivalent to Turing machines. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nBiological naturalism\nmental states are high-level emergent features that are caused by low-level physical processes \nin the neurons, and it is the (unspecified) properties of the neurons that matter:\n \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors \nand acting upon that environment through actuators.\n\nIn general, an agent’s choice of action at any given instant can depend on its built-in \nknowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n\nExternal/Internal of agents.\nAgent function table is external characterization of the agent. \nInternally, the agent function for an artificial agent will be implemented by an agent program.\nt is important to keep these two ideas distinct. \nThe agent function is an abstract mathematical description; \nthe agent program is a concrete implementation, running within some physical system.\n\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWhat is rational at any given time depends on four things:\n- The performance measure that defines the criterion of success.\n- The agent’s prior knowledge of the environment.\n- The actions that the agent can perform.\n- The agent’s percept sequence to date.\n\nomniscient agent：\nknows the actual outcome of its actions and can act accordingly; \nbut omniscience is impossible in reality.\n\nRationality VS perfection:\nRationality is not the same as perfection. Rationality maximizes expected performance, \nwhile perfection maximizes actual performance. \nOur definition of rationality does not require omniscience, \nthen, because the rational choice depends only on the percept sequence to date.\n\nLearning:\nThe agent’s initial configuration could reflect some prior knowledge of the environment, \nbut as the agent gains experience this may be modified and augmented. \nThere are extreme cases in which the environment is completely known a priori and \ncompletely predictable.\n\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nTask environments：\nEssentially the “problems” to which rational agents are the “solutions.”\n\nPerformance, Environment, Actuators, Sensors (PEAS):\nPerformance: Desirable qualities. \nEvironment: The more restricted the environment, the easier the design problem.\nActuators: Taxi driver, party that is controlling. \nSensors: Video camers, ultrasound etc. \n\nFully observable environment benefit:\nFully observable environments are convenient because the agent need \nnot maintain any internal state to keep track of the world.\n\nPartially observable:\nAn environment might be partially observable because of noisy and inaccurate sensors or \nbecause parts of the state are simply missing from the sensor data\n\nSingle VS multi-agent:\nIf competitive or cooperative. \n\nDeterministic vs nondeterministic:\nIf the next state of the environment is completely determined by the current state and \nthe action executed by the agent(s), \nthen we say the environment is deterministic; otherwise, it is nondeterministic.\nIn principle, an agent need not worry about uncertainty in a fully observable, \ndeterministic environment. If the environment is partially observable, \nhowever, then it could appear to be nondeterministic.\n\nEpisodic vs sequential:\nSingle action in atomic episdeos, each episode receives a percept and performs a single action.\nOtherwise, it is sequential, lke chess and taxi driving. Short term actions can have long \nterm consequences. \nEpisodic environments are much simpler than sequential environments \nbecause the agent does not need to think ahead.\n\nDiscrete vs continuous:\nThe discrete/continuous distinction applies to the state of the environment, \nto the way time is handled, and to the percepts and actions of the agent.\nTaxi is continuous. Chess is discrete. \n\nHardest environment.\nThe hardest case is partially observable, multiagent, nondeterministic, \nsequential, dynamic, continuous, and unknown.\n\n\n\n## AIMA 2.4 The Structure of Agents\n \nAgent = architecture + program\n\nAgent programs:\nThe agent programs that we design in this book all have the same skeleton: \nthey take the current percept as input from the sensors and return an action to the actuators.\n5 Notice the difference between the agent program, which takes the current percept as input, \nand the agent function, which may depend on the entire percept history. \nThe agent program has no choice but to take just the current percept as input because \nnothing more is available from the environment; if the agent’s actions need to \ndepend on the entire percept sequence, \nthe agent will have to remember the percepts.\n\nKey challenge for AI:\nThe key challenge for AI is to find out how to write programs that, to the extent possible, \nproduce rational behavior from a smallish program rather than from a vast table.\n\nModel-based reflex agents:\nThe most effective way to handle partial observability is for the agent to keep track \nof the part of the world it can’t see now. \nThat is, the agent should maintain some sort of internal state that depends on the percept history and \nthereby reflects at least some of the unobserved aspects of the current state.\n\nUtility function:\nAn internalization of the performance measure. \nProvided that the internal utility function and the external performance measure are in agreement, \nan agent that chooses actions to maximize its utility will be rational according to the external \nperformance measure.\nA utility-based agent has many advantages in terms of flexibility and learning\n\nLearning agents:\nA learning agent can be divided into four conceptual components.\nThe most important distinction is between the learning element, \nwhich is responsible for making improvements, and the performance element, \nwhich is responsible for selecting external actions. \nThe performance element is what we have previously considered to be the entire agent: \nit takes in percepts and decides on actions. The learning element uses feedback from the \ncritic on how the agent is doing and determines how the performance element should be modified \nto do better in the future.\nThe critic tells the learning element how well the agent is \ndoing with respect to a fixed performance standard.\nThe last component of the learning agent is the problem generator. \nIt is responsible for suggesting actions that will lead to new and informative experiences.\n\n\n## Module 1 Lecture Notes\n\nAn agent is specified by an agent function that maps a \nsequence of percept vectors P to an action a from a setA.\n\nThe agent program runs on the physical architecture to produce f.\n\nFor each possible percept sequence P, a rational agent selects an action\nthat masimizes the expected value of its performance measure. \n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - Agent that acts to get best outcome, or when with uncertainty the best expected outcome\n* **Turing test** - Behavior test. Experiment that sidestep the vagueness whether can a machine think.\n* **Pass turing test** - Cannot tell if a response came from human or machine.\n* **Cognitive science** - Cognitive science is the interdisciplinary, scientific study of the mind and its processes. \n* **General model** - Creation of agents that focus on doing right things with best expected outcome with ML and probability theory.\n* **Limited rationality** - Act appropriately give limited time ans resources, unable to finish all computations\n* **Value alignment proble** - Different between our true aim and objective given to machine.\n* **Weak ai** - Act as if intelligent.\n* **Strong ai** - Actually think by its own, and not doing simulation.\n* **General ai & human-level ai** - Strong AI\n* **Percept** - What agent's sensor are perceiving\n* **Percept seqeunce** - everything full compilation of what agent perceived\n* **Agent function** - Defines agent's behaviour, map any given percent sequence to agent's action.\n* **Information gathering** - Perform action to influence percepts in future\n* **Priori** - Applied to knowledge considered to be true without being based on previous experience or observation\n* **Autonomy** - Autonomous agent learn by itself and compensate for incorrect prior knowledge.\n* **Fully observable** - Sensor gives full aspect at each point in time, all espects relevant to decision.\n* **Unobservable** - No sensor at all.\n* **Stochastic ** - Nondeterministic.\n* **Dynamic** - Environment changes during agent action by time.\n* **Semidynamic ** - Environment changes due to agent action but not time.\n* **Single reflex agent** - Action based on current percept, ignore percept history.\n* **Transition model ** - Know how the world works, implemented in simple boolean circuits like braking to stop.\n* **Sensor model ** - Know what the agent's sensor percept is about.\n* **Model-based agent ** - Model that uses transition and sensor model.\n* **Atomic representation** - Each state of world is divisble, no internal structure.\n* **Factored representation** - State can be sliced to fixed set of variable or attributes.\n* **Structured representation** - Objects can be described explicitly\n* **Localist representation** - 1-1 mapping between concepts and meory locations.\n* **Distributed representation** - 1 to many mapping, memory location to multiple different concepts\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nString foratting:\nprint(\"%doge \")\nString is immutable.\ns=\"doge\"\ns.upper() gives DOG\ns.capitalize() gives Dog\ndog = \"do--ge\"\ndog = dog.strip('--ge') gives 'do'\n\nList:\nlst.index(\"b\") # index of first occurrence\nlst.count(\"b\") # count occurrence\nlst.remove(\"b\")\nlst.reverse()\nlst.sort()\nsorted(lst) #return a copy sorted\n\nDictionary:\ndict.values() # gives list of values\ndict.keys() # gives list of keys\ndict.items() # list item tuples\n\nfunctions:\ndef print_everything(*args) # accept variable number of non-keyword arguments\n//accepted as tuples. So (1,2,3) [1] is 2. But ([1,2,3]) is one element.\ndef doge(**args); doge(meow = 1, cat = 2, dash =3); gives \n{'meow': 1, 'cat': 2, 'dash': 3}\n// ** is for variable number of keyword arguments\n\nClass:\nclass Student:\n  def __init__(self, name, dept):  # constructor\nclass AI_Student(Student): #this is sub class\n// During multiple inheritance, follow the front one function\nsuper().foo() # parent function foo() called\n\nClass magic methods:\n__str__(self) changes how print works\nlen defines how len(obj) works\ncopy defines how to copy a class\ncmp defines ==\nadd defines +\nneg defines how unary negation works for class\n\nIterators: (memory efficient because not storing)\nIterable objects can be used in a for loop because have __iter__\nlst.__iter__()\nIterators has __next__() method, throws StopIteration when done\ni = iter(k) \nlst.next(i) # produce first result\nlst.next() # will produce result\n\nGenerators:\nyield\nEach time we call __next__, method runs until encounters yield statement\nMaintains local state automatically\nBad if need to inspect individual values\n\nlambda:\nlst = [x for x in range(1, 101)]\nfor n in nums: s.appendx*x same as [x*x for x in nums]\n[n*3 for (x,n) in lst] gives [3n,3n,3n]\n[elem*2 for elem in lst if elem > 4]\n\nImport:\npip install package_name\nIn Colab, run !pip install nltk\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nGoal formulation:\nGoals organize behavior by limiting the objectives and hence the actions to be considered.\n\nProblem formulation:\nThe agent devises a description of the states and actions necessary to reach the \ngoal—an abstract model of the relevant part of the world.\nConsider actions of traveling from one to adjacent city. \n\nSearch & Solution:\nBefore taking any action in the real world, the agent simulates sequences of actions in its model, \nsearching until it finds a sequence of actions that reaches the goal.\nThis seqeunce is called Solution. May simulate multiple seqeunces. \nIt is an important property that in a fully observable, deterministic, known environment, \nthe solution to any problem is a fixed sequence of actions.\nIf the model is correct, then once the agent has found a solution, \nit can ignore its percepts while it is executing the actions.\n\nIn partially observable or nondeterministic environments, \na solution would be a branching strategy that recommends different future actions depending \non what percepts arrive.\n\nExecution:\nExxcute action in the solution one at a time. \n\nProblem definition:\n- State space\n- Initial state : Where agent starts in, like Arad.\n- Goal states: A set of one or more goal states. \n- Actions: Actions available to agent.\n- Transition model: Describes what each action does. Result (s,a) returns state\nfrom doing action a in state s.\n- Action cost function: Denoted by action cost-(s, a s'), gives numeric cost \nof applyiong action a in state s to reach state s'.\n\nGood problem formulation has right level of detail.\n\nPath: \nA sequence of actions forms a path. A solution is a path from initial state \nto a goal state. \nWe assume that action costs are additive; that is, \nthe total cost of a path is the sum of the individual action costs. \n\nGraph:\nRepresent state space. Vertices are states, edges are actions.\n\n \n\n## AIMA Chapter 3.2 Example Problems\n\nStandarized problem: \nIntended to illustrate or exercise various problem-solving methods.\n\nReal world problem:\nsuch as robot navigation, is one whose solutions people actually use, \nand whose formulation is idiosyncratic, not standardized.\nFor example, each robot has different sensors that produce different data.\n\nGrid world problem:\nTwo-dimensional rectangular array of square cells in which agents can move from cell to cell.\n\nVacuum world Example:\nStates: 8 states, each each has 2 cells. Each room has 1 vaccum cleaner, 0-2 dirt.\nInitial state; Any state above.\nActions: We define 3 actions. Suck, move left, move right. When we are in the right side, right is not applicable.\nTransition model: Suck removes dirt from agent's cell.\nGoal state: Every cell is clean.\nAction cost: Each action costs 1.\n\nNote that every problem formulation involves abstractions. \nThe 8-puzzle actions are abstracted to their beginning and final states, \nignoring the intermediate locations where the tile is sliding. \n\nReal world example Travel Planning Website:\nStates: Each state includes location and current time. \nInitial state: Home airport.\nActions: Any flight from current location, any seat class, enough time\nfor travelling or transfer.\nTransition model: The state resulting from taking a flight will have the flight’s destination \nas the new location and the flight’s arrival time as the new time.\nGoal state: Destination city. (Or more complicated, no stops)\nAction cost: Combining monetary, waiting time, flight time, customs, quality etc.\n\nVLSI layout problem:\nRequires positioning millions of components and connections on a chip to \nminimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. \nThe layout problem comes after the logical design phase and is usually split into two parts: \ncell layout and channel routing. In cell layout, the primitive components of the circuit are grouped \ninto cells, each of which performs some recognized function. Each cell has a fixed footprint \n(size and shape) and requires a certain number of connections to each of the other cells. \nThe aim is to place the cells on the chip so that they do not overlap and so that there is room for \nthe connecting wires to be placed between the cells. \nChannel routing finds a specific route for each wire through the gaps between the cells. \nThese search problems are extremely complex, but definitely worth solving.\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \n\nIn this chapter we consider algorithms that superimpose a search tree over the state-space graph, \nforming various paths from the initial state, trying to find a path that reaches a goal state. \nEach node in the search tree corresponds to a state in the state space and \nthe edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem.\n\nState space VS search tree:\nThe state space describes the (possibly infinite) set of states in the world,\nand the actions that allow transitions from one state to another. \nThe search tree describes paths between these states, reaching towards the goal. \nThe search tree may have multiple paths to (and thus multiple nodes for) any given state, \nbut each node in the tree has a unique path back to the root (as in all trees).\n\nBest-fit search:\n- chose a node n, with minimum value of evaluation function f(n).\n- On each ieration, we choose a node on frontier with minimum f(n), return if the state is goal.\n- Otherwise expand to generate child nodes, and add to frontier if child nodes are never reached\nor it is re-added if it is ow being reached with a loer path cost than revious path.\nCode:\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, with node as element\n  reached = lookup table, initial and value node.\n  while not frontier.isEmpty:\n    node = frontier.pop()\n    if problem.is_goal(node.State) 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:\n        reached[s] = child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields node:\n  s = node.State\n  for each action in problem.ACTIONS(S) do:\n    s' = problem.RESULTS(s, action)\n    cost = node.PATH-COST + problem.ACTION-COST(s, Action, s')\n    yield node(State = s', Parent=node, action=action, path-cost=cost)\n\nData structure choices:\n- FIFO, LIFO queue.\n- Add(node, frontier)\n- Top(frontier) returns top node but not remove\n\nTo be complete:\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space, \nmaking sure it can eventually reach any state that is connected to the initial state. \n\nImplicit state time complexity:\n- Measured by depth or number of actions in optimal solution.\n- m, the maximum number of actions in any path.\n- b, branching factor or number of successors of a node that need to be considered. \n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\nBFS:\nFIFO queue bfaster than priority queue. Will give correct ordero f nodes.\ndef BFS returns solution node or failure:\n  node = node(problem.initial\n  if problem.is_goal(node.state)) return node\n  frontier = Fifo queue\n  reached add node\n  while not frontier.isempty():\n    node = frontier.pop()\n    for each child in expand(proble, node):\n      s = child.state\n      if problem.is_goal return child\n      if s is not in reached:\n        reached add s\n        frontier.add(child)\n  return failure\n\nBFS space & time complexity  = O(b^d). d is depth. b is branching factor.\n\nDijkstra’s algorithm:\nCalled as uniform cost search by AI community.\nChoose next lowest cost. \n\nDFS:\nDepth-first search always expands the deepest node in the frontier first. \nIt could be implemented as a call to Best-First-Search where the evaluation function f \nis the negative of the depth. \nUsually for tree-like search, not keep a table of reached states. \nNot cost optimal. Returns first found solution even if it is not cheapest.\nCan cause infinite loop in cyclic state space.\nSo implementation checks new node for cycles.  In infinite state spaces, DFS not systematic. \nIt can go down a infinite path, so incomplete. \nMemory efficient, O(bm), b is branching factor, m is maximum depth.\n\nBacktracking search:\nAnother form of DFS, use less memory. Just O(m).\nCheck for O(1). Use in large state description problems, like robotic assembly.\n\nDepth-limited and iterative deepening search (IDS):\nDFS with limited depth l. Time O(b^l). Memory O(bl).\nPoor decision for l will cause incomplete.\nIDS solves picking a good value l. Memory O(bd) when there is solution, or O(bm) on finite\nspaces with no solution.\nIDS optimal for problems where all actions have the same cost, \nand is complete on finite acyclic state spaces, or on any finite state space when we \ncheck nodes for cycles all the way up the path.\n\nBidirectional search(BS):\nStart from initial state and backwards from goal state. Hoping two will meet.\nFor this to work, we need to keep track of two frontiers and two tables of reached states, \nand we need to be able to reason backwards. If state s1 is successor of s in forward,\nthen we need to know that s is a successor of s1 in backward. Found solution if collides.\nAlthough there are two separate frontiers, the node to be expanded next is always one with \na minimum value of the evaluation function, across either frontier. \n \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - Ignore the percepts that break the searchig loop between agent and environment.\n* **Closed loop** - Use if model may be incorrect, it monitors the percepts.\n* **State space** - Set of possible states that the environment can be in.\n* **Optimal solution** - Path or solution with lowest cost.\n* **Model** - Formuating the problem with the problem definition steps. \n* **Abstraction** - Process of removing unnecessary detail, like weather, from a representation.\n* **Abstraction is valid** - Elaborate any abstract solution into a solution in more detailed environment.\n* **Abstraction is useful** - Executing each action in solutions is easier than original problem.\n* **Egocentric actions** - Actions given in viewpoint of the agent.\n* **Robot navigation** - Route-finding problem in general.\n* **Automatic assembly sequencing** - Algo find feasible assembly sequence and optimize the process.\n* **Touring problems** - Visit the must-visit locations rather tha single goal. Like Tranveling salesperson problem.\n* **Search algorithm** - Input search problem and returns a solution, or indicate failure.\n* **Frontier** - Set of unexpanded nodes/choices. Separates interior and exterior regions.\n* **Reached** - Any state that had a node generated for it, regardless if this node got expanded.\n* **Cycle** - Loopy path. Special case of redundant state.\n* **Graph search** - If checks for redundant paths. Remove all references to become tree-like search.\n* **Tree-like search** - if it does not check for redundant paths, uses less memory.\n* **Completeness** - Guaranteed to find solution if there is one, and correctly report failure.\n* **Cost optimality** - Find a solution with lowest path cost of all solutions\n* **Admissibility** - Same as cost optimality.\n* **Time complexity** - Time took to find a solution.\n* **Space complexity** - Memory needed to perform the search.\n* **Branching factor** - Number of children at each node.\n* **Diameter of state-space graph** - Find centre for better depth limited search.\n* **Pr** - an\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n#### informed search:\nUses domain-specific hints about location of goals, find solutions more efficiently than uninformed strategy.\n\n#### Heuristic function:\nh(n) = estimated cost of the cheapest path from the state at node n to a goal state.\n\n#### Greedy best first search:\na form of best-first search that expands first the node with the lowest h(n) value,\nwhich is the node that appears to be closest to goal.\nEvaluation fucntion f(n) = h(n).\nComplete in finite state spaces, but not infinite ones.\nTime&space complexity O(|V|). Can be reduced to O(bm) with good h(n).\n\n#### A* search\nBest-first search uses evaluation function f(n) = g(n) + h(n)\ng(n) is path cost from initial state to node n.\nh(n) is estimated cost of shortest path from n to a goal state.\nSo, f(n) = estimated cost of best path that continues from n to a goal.\n\nWhether A* is cost-optimal depends on certain properties of the heuristic. \nA key property is admissibility: an admissible heuristic is one that never overestimates \nthe cost to reach a goal. \n(An admissible heuristic is therefore optimistic.) \nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\nWith inconsistent heuristics, we may end up with multiple paths reaching the same state, \nand if each new path has a lower path cost than the previous one, then we will end up with \nmultiple nodes for that state in the frontier, costing us both time and space.\nWith an inadmissible heuristic, A* may or may not be cost-optimal. \n\n#### Surely expanded nodes:\nA* expands all nodes that can be reached from the initial state on a path \nwhere every node on the path has f(n) < C*.\n\n#### Optimally efficient:\nWe say that A* with a consistent heuristic is optimally efficient in the sense that any algorithm \nthat extends search paths from the initial state, and uses the same heuristic information, \nmust expand all nodes that are surely expanded by A*.\n\n#### Search contours\nMonotonic holds onl ywhen heuristic is consistent. \n\n#### A* problems\nIt is complete, cost-optimal, and optimally efficient among all such algorithms.\nBut for many problems, the number of nodes expanded can be exponential in the length of the solution.\n\n#### Satisficing search:\nAccept good enough sub-optimal solutions.\nUse inadmissible heuristic, we risk missing optimal solution, but heuristic can be more accurate,\nexpand to less nodes. \n\n#### Weighted A* search\nweight the heuristic value more heavily, giving us the evaluation function.\nUsing idea of detour index.\nf(n) = g(n) + W*h(n), for some W >1.\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n\n#### Misplaced tiles(h1)\n- h1 s an admissible heuristic because any tile that is out of place will require at least one move to get it to the right place.\n\n#### Manhattan distance(h2):\n- Sum of distances of the tiles from their goal positions. The distance is the sum of the horizontal and vertical distances.\n- Also admissible because all any move can do is move one tile one step closer to the goal.\n- Always better than h1. A* using h2 ever expands more nodes than h1. Dominates. \n- Because h2 is at least as big as h1 for all nodes, every node is surely expanded by A* with h2.\nh1 might cause other nodes to be expanded as well.\n- So use heuristic function with higher values provided it is consistent and that the computation time for the heuristic is not too long.\n- Best of all worlds by h(n) = max{h1, h2, ... , hk}\n\n#### The effect of heuristic accuracy on performance\n- Quality of heuristic can be measured by effective branching factor b*.\n- b* is the branching factor that a uniform tree of depth d would have to have in order to contain n+1 nodes.\nWhere N is number of nodes generated by A*, d is solution depth. \n- So N+1 = 1 + b* + (b*)^2 + ... + (b*)^d\n- a better way to characterize the effect of A* pruning with a given heuristic is that it reduces the effective depth by a constant\nkh compared to true depth. So total search cost is O(b^{d-kh}) and not O(b^d) for an uninformed search.\n\n#### Relaxed problem cost\n- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n- Because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent\n\n\n\n \n\n## Module 4 Lecture Notes\n \n#### Memory-bounded search\nMethods to reduce memory usage.\n- Memory is split between the frontier and the reached states. In our implementation of best-first search, \na state that is on the frontier is stored in two places: as a node in the frontier \nand as an entry in the table of reached states.\n- Another possibility is to remove states from reached when we can prove that they are no longer needed.\n- For other problems, we can keep reference counts of the number of times a state has been reached, \nand remove it from the reached table when there are no more ways to reach the state. \n- Beam search limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes.\nOr keep every node whose f-score is within standard deviation of best f-score.\n-  Iterative-deepening A* search (IDA*). The cutoff is f-cost(g+h) instead of depth.\n- Recursive best-first search (RBFS): Attempts to mimic the operation of standard best-first search, but using only linear space.\nIt uses f_limit variable to keep track of the f-value of best alternative path avaialble from any ancestor of the current node.\nIf the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the \nf-value of each node along the path with a backed-up value. Optimal if h(n) is admissible. Space complexity is linear in depth of deepest optimal solution.\nTime complexity depends on accuracy of h(n) and how often the best path changes as nodes are expanded.\n- RBFS more efficient than IDA*, but suffer from excessive node regeneration. Both suffer from using too little memory.\n \n #### Determine how much memory:\n - MA* (memory-bounded A*) and SMA(simplified MA*)\n - SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one.\n Always drop worst leaf node, the one with highest f-value.\n \n #### Bidirectional heuristic search\n- Pair of nodes that can be surely expanded, not individual. \nSo any proof of efficiency will have to consider pairs of nodes.\n- have f(n) = g(n) + h(n) for both forward and backward direction. \n- Middle ground to expand fewer nodes that is preferred. \n- In the worst case of a poor heuristic, the search is no longer focused on the goal, \nand bidirectional search has the same asymptotic complexity as A*. \n\n\n \n\n## Module 4 Definitions\n* **Admissible heuristic** - Never overestimates the cost to reach a goal.\n* **Consistency** - See image.\n* **Monotonic** - Cost always increase along path, because costs are positive and cumulative.\n* **Detour index** - Multiplier to straight-line distnce to account for true distance that is not straight.\n* **Bounded suboptimal search** - Look for solution within a constant factor W of the optimal cost.\n* **Bounded cost search** - Solution cost is less than a constant C.\n* **Unbounded cost search** - Accept any solution, aim to find it quickly\n* **Speedy search** - h(n) is estimated number of actions required to reach a goal, a form of greedy best first search.\n* **Backed-up value** - Best f-value of its children node\n* **Relaxed problem** - Problem with less restrictions on actions.\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n#### Game theory\n- 3 Stances to take towards multi-agent environments.\n- The first stance, appropriate when there are a very large number of agents, is to consider them in the aggregate as an economy.\n- Second, we could consider adversarial agents as just a part of the environment—a part that makes the environment nondeterministic.\n- The third stance is to explicitly model the adversarial agents with the techniques of adversarial game-tree search.\n\n#### heuristic evaluation function\n- Estimate who is winning based on features of the state.\n- We can average the outcomes of many fast simulations of the game from that state all the way to the end.\n\n#### Game\n- Max moves first.\n- S0 is initial state.\n- To-move(s): The player whose turn it is to move in state s.\n- Action(s): The set of legal moves in state s.\n- Result(s,a): The transition model, which defines the state resulting from taking action a in state s.\n- Is-Terminal(s): A terminal test, which is true when the game is over and false otherwise.\n- Utility(s,p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when game ended in terminal state.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n#### Max's strategy:\n- A conditional plan. A contingent strategy specifying a response to each of min’s possible moves.\n\n#### Minimax\nThe minimax value is the utility (for max) of being in that state, assuming that both players play optimally from there to the end of the game. \nThe minimax value of a terminal state is just its utility. \nIn a non-terminal state, Max prefers to move to a state of maximum value when it is Max’s turn to move, \nand Min prefers a state of minimum value (that is, minimum value for Max and thus maximum value for Min).\n\n#### Minimax search algorithm\n- The minimax algorithm performs a complete depth-first exploration of the game tree.\n- Time O(b^m), space O(bm). b legal moves at each point, m is max depth of tree. \n- Depth first.\n- Alpha: (At least) the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for max. \n- Beta: (At most) the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. \n\n#### When to prune:\n- The value of the root and hence the minimax decision are independent of the values of the leaves  \nand , and therefore they can be pruned.\n- General principle is if a player has a choice to move to n, and \nif a plyaer has a better choice either at same level or any points\nhigher up in the tree, then player will never move on to n. \n\n#### Move ordering:\n- It might be worthwhile to try to first examine the successors that are likely to be best.\n- If this could be done perfectly, alpha–beta would need to examine only O(b^{m/2}), instead of O(b^m)\n\n#### Type A strategy:\n- Considers all possible moves to a certain depth in search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth.\n- It explores a wide but shallow portion of the tree.\n\n#### Type B strategy:\n- Ignores moves that look bad, and follows promising lines “as far as possible.” \n- It explores a deep but narrow portion of the tree.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n\n#### Heuristic evaluation function:\n- To states, effectively treating nonterminal nodes as if they were terminal. \n- Do to make use of our limited computation time, cut off the search early.\n- Replace Utility function with Eval, which estimates the state's utility.\n- We also replace the terminal test by a cutoff test, which must return true for terminal states, \nbut is otherwise free to decide when to cut off the search, \nbased on the search depth and any property of the state that it chooses to consider.\n- Gives H-Minimax(s,d) for heuristic minimax value of state s at search depth d.\n\n#### Evaluation functions:\n- For terminal state, Eval(s,p) = Utility (s,p)\n- Otherwise, Utility (loss,p) <= Eval(s,p) <= Utility (win,p)\n- Good evaluation function has not long computation. Strongly correlated with actual chance of winning.\n- Need not be linearly correlated. \n- Only applied to positions that are quiescent.\n\n#### Cutting off search\n- Replace is-terminal with \n- if game.Is-Cutoff(state, depth) then return game.Eval(state, player), null\n- Increment depth on each recursive call.\n- The depth d is chosen so that a move is selected within the allocated time. \n- When time runs out, the program returns the move selected by the deepest completed search.\n- A more robust approach is to apply iterative deepening.\n\n#### Forward pruning\n- Prunes moves that appear to be poor moves, but might possibly be good ones. \n- Saves computation time at the risk of making an error.\n- Type B strategy.\n- ProbCut, probability cutting: Forward pruning of alpha-beta search\nthat uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n- Late move reduction: Works under the assumption that move ordering has been done well, \nand therefore moves that appear later in the list of possible moves are less likely to be good moves.\nJust reduce depth to which we search these moves, thereby saving time. If reduced search comes back\nwith value above current alpha, we rerun the search with full depth. \n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \n#### Stochastic games\n- Chance node shows each possible outcome\n- No defiite minimax values\n- Calculate expected value of a position (average over all possible outcomes of chance nodes)\n- Leads to expectiminimax value, a generalization of the minimax value for deterministic games.\n- The evaluation function must return values that are a positive linear transformation of the probability of winning.\n- If the program knew in advance all the dice rolls that would occur for the rest of the game, \nsolving a game with dice would be just like solving a game without dice, which minimax does in O(b^m),\nwhere b is branching factor and m is maximum depth of game tree.\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n\n#### Simple decisions\n- Assign probability P(s) to each possible current state s.\n- There may also be uncertainty about the action outcomes. Transition model given by P(s'|s,a),\nthe probability that action a in state s reaches state s'.\n- P(Result(a)=s') probability of reaching s' by doing a in the current state. It is summation s of\nP(s)P(s'|s,a). \n- The agent’s preferences are captured by a utility function U(s), which assigns a single number to express the desirability of a state.\n\n#### Principle of maximum expected utility (MEU)\n- A rational agent should choose the action that maximizes the agent’s expected utility.\n- \n\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n\n#### Constraints on rational preferences (For utility theory)\n1. ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n2. TRANSITIVITY: Given any three lotteries, if an agent prefers A to B, and B to C, then must prefer A to C.\n3. CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent\nwill be indifferent between getting B for sure and the ottery that yields A with probability p and C with probability 1 - p.\n4. SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then also indifferent when substituting something with A and B.\n5. MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A, then the agent must prefer the lottery that has a higher probability for A.\n6. DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n\n#### EXISTENCE OF UTILITY FUNCTION\n- If an agent’s preferences obey the axioms of utility, then there exists a function.\n\n#### EXPECTED UTILITY OF A LOTTERY\n- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n\n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n\n#### Utility assessment and utility scales\n- No absolute scale for utilities, but it is helpful, nonetheless, to establish some scale on which utilities can be recorded and compared for any particular problem.\n- Risk averse: Wants guaranteed payoff that is lower than expected outcome.\n\n\n \n\n## Module 5 Lecture Notes\n\n\n#### Expectimax search\n- Value should now reflec average case outcomes.\n- Computer average score under optimal play.\n- Calculate expected utilities (Chance nodes give uncertain outcome)\n\n\n\n## Module 5 Definitions\n* **Pruning** - Ignore useless portions of search tree to make process more efficient.\n* **Perfect information** - Fully observable.\n* **Zero-sum** - What is good for one, is bad for another.\n* **Move** - Action\n* **Position** - State\n* **Terminal state** - States when game ended.\n* **State space graph** - Graph where states are vertices, and movs are edges.\n* **Game tree** - Search tree that follows every sequence of moves to reach terminal state.\n* **Killer moves** - Best moves.\n* **Killer move heuristic** - Trying killer moves first.\n* **Transpositions** - Different permutations of move sequence that will end up in the same position. Cause repated states.\n* **Weighted linear function** - With material value, assign normalized weight to function.\n* **Quiescent** - Positions when there is no pending move that will wildly affect evaluation\n* **Nonquiescent position** - Is-cuttoff returns false\n* **Horizon effect** - When facing detrimental and unavoidable moves from opponent, only can temporarily delay.\n* **Singular extensions** - Mitigate horizon effect, a clearly better move.\n* **Policy** - Mapping from every possible state to best move in that state.\n* **Decision theory** - Choose among actions based on desirability of immediate outcome.\n* **Expected utility** - Average utility value of outcomes, weighted by chance of outcome occurring.\n* **Value function** - Another name for ordinal utility function.\n* **Ordinal utility function** - An agent needs only a preference ranking on states, numbers dont matter.\n* **Preference elicitation** - Find utility function by presenting choices to humans and observe their preferences.\n* **Optimizer’s curse** - Tendency for the estimated expected utility of the best choice to be too high.\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n\n#### Constraint satisfaction problem (CSP)\n- Use a factored representation for each state, which is a set of variables, each of which has a value.\n- Problem solved when each variable has a value that satisfies all constraints on the variable. \n- Use general rather than domain-specific heuristics to enable the solution of complex problems.\n- Actions and transition model can be deduced from the problem description.\n- Solution to CSP is complete, consistent assignment. \n- Solving CSP is generally NP-complete. \n\n#### CSP components\n1. X: A set of variables. Like countries in coloring.\n2. D: A set of domains, one for each variable. Contains allowable values for X. Like colors for countries (RGB).\n3. C: A set of constraints that specify allowable combination of values. Each constraint consists of \na pair <Scope, rel>, scope is a tuple of variables that participate in constraint, and rel is a \nrelation that defines values that those variables can take on. Like <(SA,WA), SA != WA>\n\n#### WHY CSP\n- CSPs yield a natural representation for a wide variety of problems; it is often easy to formulate a problem as a CSP.\n- Now solves problem efficient and fast.\n\n#### Domains\n- A discrete domain can be infinite, such as the set of integers or strings.\n- With finite domains, we must use implicit constraints like T1 + d1 <= T2.\n\n#### Constraint hypergraph\n- Consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), \nwhich represent n-ary constraints—constraints involving n variables.\n\n#### Global contraint better than set of binary constraints\n- First, it is easier and less error-prone to write the problem description.\n- Second, it is possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints.\n\n#### Constrained optimization problem (COP)\n- Preference constraints can often be encoded as costs on individual variable assignments—for example, \nassigning an afternoon slot for Prof. R costs 2 points against the overall objective function, \nwhereas a morning slot costs 1. With this formulation, \nCSPs with preferences can be solved with optimization search methods, either path-based or local.\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n#### Constraint propagation:\n- Using the constraints to reduce the number of legal values for a variable, \nwhich in turn can reduce the legal values for another variable, and so on.\n- Leave fewer choices to consider when making next choice of a variable assignment. \n- The key idea is local consistency. Variable as node, binary constraint as edge. \nThen the process of enforcing local consistency in each part of the graph causes inconsistent \nvalues to be eliminated throughout the graph.\n\n#### AC-3\n- Enforce arc consistency. \n- O(cd^3), d is domain size, c is binary constraints (arcs)\n\n#### Path consistency\n- A two-variable set {A,B} is path-consistent with respect to a third variable C if for every assignment \nfor A and B, there is an assignemnt to C that satisfies {A, C} and {A, B}\n\n#### K-consistent\n- A CSP is k-consistent if, for any set of  k - 1 variables \nand for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.\n- 1-consistency ays that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency.\n- 2-consistency is the same as arc consistency.\n-  For binary constraint graphs, 3-consistency is the same as path consistency.\n\n#### Strongly k-consistent\n- If CSP is k-consistent, and also (k-1) consistent, (k-2) consistent, until 1-consistent.\n- Total run time is O(n^2 d), n is k, number of nodes. d is domain size.\n- NP-complete in general. \n- Exponential requirement space in n.\n\n#### Global constraints\n- Handled by special-purpose algorithms that are more efficient than the general-purpose methods\n- To detect inconsistency: First, remove any variable in the constraint that has a singleton domain, and delete that variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected.\n\n#### Resource constraint / Bounds-consistent\n- Also called Atmost constraint.\n- Given limited resources, find inconsistency by sum of minimum values of current domains.\n- For bound propagation domains, [0,165] and [0,385] reduced to [35,165] and [255,385] if F1+F2=420.\n- Bounds consistent if for every variable X and for both the lower-bound and upper-bound values of X,\nthere exists some value of Y that satisfies contraints between X and Y for every variable Y.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n\n#### Backtracking search for CSPs\n- Search tree where all the complete assignments (and thus all the solutions) are leaf nodes at depth n.\n- Branching factor is nd, because any d values can be assigned to any of n variables. Next level is (n-1)d.\n- So tree has n!*d^n leaves, but only d&n possible complete assignments. \n- Only a single representation of a state (assignment) and alters that representation rather than creating new ones.\n- Can be improved using domain-independent heuristics that take advantage of the factored representation of CSPs.\n- Degree heuristic as tie breaker.\n- Once a variable has been selected, the algorithm must decide on the order in which to examine its values. The least-constraining-value heuristic is effective for this. \nIt prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. \n\n#### Forward checking\n- Whenever a variable  is assigned, the forward-checking process establishes arc consistency for it.\nEach Y connects to X by a constant.\nDelete from Y's domain any value that is inconsistent with the value chosen for X.\n\n#### Maintaining Arc Consistency (MAC)\n- Use when forward checking is not forward enough. \n- Recursively propagate constraints when changes are made to the domains of variables.\n\n#### Backjumping\n- Backjumping notices failure when a variable’s domain becomes empty, \nbut in many cases a branch is doomed long before this occurs.\n\n#### Constraint learning\n- Avoid running into same problem again after backjumping.\n- Idea of finding a minimum set of variables from the conflict set that causes the problem. \n- This set of variables, along with their corresponding values, is called a no-good.\n- We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.\n- Not useful if forward checking can tell it is no good.\n- Useful to know if a state is no good, we will run into same problem again for each possible set of assignments.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n\n#### Min-conflict\n- Runtime is roughly  independent of problem size if do not count the initial placement of Queens.\n\n####  Tabu search\n- Keeping a small list of recently visited states and forbidding the algorithm to return to those states. \nSimulated annealing can also be used to escape from plateaus.\n\n#### Constraint weighting\n- Aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n- Making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \n\n#### Independent subproblems\n- Any solution for the mainland combined with any solution for Tasmania yields a solution for the whole map.\n- Independence can be ascertained simply by finding connected components of the constraint graph.\n\n#### Directional arc consistency (DAC)\n- A CSP is defined to be directional arc-consistent uner an ordering of variables X1, X2,...,Xn if and only if every\nXi is arc-consistent with each Xj for j > i.\n\n#### Solve tree-structured CSP\n- Use topological sort.\n- O(n), time O(nd^2).\n\n#### Cutset conditioning\n- The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\n- Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n- For each possible assignment to the variable S that satisfies all constraints on S. Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S. \nAnd if the remaining CSP has a solution, return it together with the assignment for S.\n- Run time is O (d^c * (n-c)d^2)\n- Need to try each d^c combinations of values for the variables in S, and for each combination we must solve a tree problem of size n - c.\n- FInding smallest cycle cutset is NP-hard. \n\n#### Tree decomposition\n-  To reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph.\n- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n- Three requirements:\n1. Every variable in the original problem appears in at least one of the tree nodes.\n2. 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.\n3. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n- O(nd^2) time. n is number of tree nodes, d is size of the largest domain.\n- A domain is a set of tuples of values, not individul values.\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Consistent assignment** - Does not violate constraints.\n* **Complete assignment** - Every variable is assigned a vlue.\n* **Partial assignment** - Some values are not assigned.\n* **Partial solution** - Partial consistnt assignment.\n* **Linear programming problems** - Constraints are linear equalities or inequalities/ Continuous domain CSP.\n* **Unary constraint** - Value of a single variable being restricted. Like SouthAus wont tolerate green.\n* **Binary constraint** - Relates two variables, like SA!=NSW.\n* **Binary csp** - Only with unary and binary constraints.\n* **Global constraint** - Constraint involving an arbitrary number of variables. (need not all) Like Sudoku.\n* **Preference constraints** - Indicating the preferred solutions. \n* **Node consistent** - A variable if all values in that variable's domain satify its unary constraints.\n* **Graph is node-consistent** - Every variable in the graph is node-consistent.\n* **Arc consistent** - Every value in its domain satisfies the variable’s binary constraints.\n* **Path consistency** - Tightens binary constraints with implicit constraints inferred by looking at triples of variables\n* **Bounds propagation** - Manage lower and upper bounds of domains. [0,165] plane capacity.\n* **Commutative** - A problem is commutative if order of applicatiosn of any give set of actions does not matter\n* **Minimum-remaining-values (mrv) heuristic** - Choose variable with least legal values.\n* **Degree heuristic** - Give degree based on largest number of constraints on other unassigned variables. \n* **Chronological backtracking** - Revisit most recent decision point.\n* **Backjumping** - Backtracks to most recent assignment in conflict set.\n* **Conflict-directed backjumping** - A backjumping algorithm that uses conflict sets.\n* **Min-conflicts heuristic** - Select the value that results in the minimum number of conflicts with other variables.\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n\n#### Knowledge base\n- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world.\n- KB agent takes a percept as input and returns an action. \n\n#### KB Agent program\n- Do 3 things each time called:\n1. Tells the knowledge base what it perceives.\n2. Asks the knowledge base what action it should perform.\n3. Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n- Make-Percept-Sentence: 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 action should be done at the current time.\n- Can be built simply by Telling it what it needs to know. \n1. Declarative approach: Tell sentences on by one until agent knows how to oeprate in its environment.\n2. Procedural approach: Encodes desired behaviors directly as program code.\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n#### Wumpus world Sample\n1. Performance measure: + 1000 for climbing, -1000 for falling, - 1for each action taken.\n2. Enviornment: 4x4 grid, always start labeled [1,1]\n3. Actuators: Agent can move forward, turn left by 90, turn right by 90.\n4. Sensors: 5 Sensors, sense for stench, breeze, glitter, bump, scream. As percepts.\n- It is deterministic, discrete, static, and single-agent.\n- Sequential, rewards come after actions are taken. \n- Partially observable, because some aspects of the state are not directly perceivable.\n- Transition model itself is unknown, because agent doesnt know which action is fatal. \n\n \n\n## AIMA Chapter 7.3 Logic\n \n\n### Logic\n\n#### Syntax\n- Sentences in KB follows syntax of representation language, hich specifies all the sentences that are well formed. \n\n#### Models\n- The possible models are just all possible assignments of nonnegative integers to the variables.\n- If sentence a is true in model m, m satisfis a or m is a model of a. M(a) mean set of all models of a.\n\n#### Entailment\n- If a entails b, a is a stronger assertion than b, it rules out more possible worlds. \n\n#### Sound / truth preserving\n- An inference algorithm that derives only entailed sentences.\n- Soundness is highly desirable. \n- Unsound inference procedure announces nonexistent needles.\n- If KB is true in real world, then any sentence a derived from KB y a sound inference\nprocedure is also true in real world. \n\n#### Check if space of models is finite\n- Wumpus is fixed size.\n- Arithmetic space of model is infinite.\n\n#### Consider grounding issue\n- The connection between logical reasoning processes and the real environment in which the agent exists.\n- Agent's sensors create the connection. \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n\n#### Propositional logic\n- Describe syntax and semantics (the way in which the truth is determined)\n\n#### Complex sentences, five connectives in common use\n- Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n- not operator has highest precedence, means not A and B, not binds tightest, so it is (not A) and B.\n\n#### Semantics\n- Defines the rules for determining the truth of a sentence with respect to a particular model.\n- Recursively, the semantics for propositional logic must specify how to compute the truth value of any sentence, given a model.\n- For complex sentences there are 5 rules: (Check pictures)\n\n#### Simple knowledge base\n- Focus first on immutable aspects.\n\n#### Simple inference procedure\n- Goal is to decide whether KB entails a for some sentence a. Like if not pit 2,1 entailed by KB.\n- Enumerate models, check if a is true in every model in which KB is true.\n- Models are assignments of true or false to every proposition symbol.\n- Models are TF tables, if all possible model rows have same result for certain sentence, then those must be true. Like no pit in 1,2.\n- Time O(2^n), space O(n).\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n#### Theorem proving\n- Applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models.\n\n#### Validity\n- A sentence is valid if it is true in all models.\n- Such as P V not P\n- Valid sentences are also known as tautologies—they are necessarily true.\n- Because the sentence True is true in all models, every valid sentence is logically equivalent to True.\n\n#### Deduction theorm\n- Check picture\n- a entails b by checking that a implies b in every model.\n\n#### Satisfiability\n- A sentence is satisfiable if it is true in, or satisfied by, some model. \n- Satisfiability can be checked by enumerating the possible models until one is found that satisfies the sentence.\n- The problem of determining the satisfiability of sentences in propositional logic—the SAT problem—was the first problem proved to be NP-complete.\n- Connected to validity. a is valid iff not a is unsatisfiable. \n\n#### Inference rules\n- See picture\n- Any logical equivalences can be used as inference rules. \n\n\n#### Define a proof problem\n- INITIAL STATE: the initial knowledge base.\n- ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n- RESULT: the result of an action is to add the sentence in the bottom half of the inference rule.\n- GOAL: the goal is a state that contains the sentence we are trying to prove.\n\n#### Searching for proof\n- Searching for proofs is an alternative to enumerating models.\n- Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many of them there are.\n\n#### Final property of logical system: Monotonicity\n- The set of entailed sentences can only increase as information is added to the knowledge base.\n- Conclusion of the rule must follow regardless of what else is in the knowledge base\n\n#### Resolution\n- Gives resolvent\n- Negate complementary literals with unit resolution, which means one is the negation of another. \n- Pit must be in ABC, but not in B and C, so must be in A. This is unit resolution inference rule. \n- Factoring: Remove multiple copies of literals. (AVB)&(AVnotB) = (AVA) = A\n\n#### Conjunctive normal form\n- Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n- A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n\n \n\n## Module 7 Lecture Notes\n \n\n#### Resolution algorithm\n- To show KB entails a, we show that KB and not a is not satisfiable. \n- Inference procedures base don resolution work using the principle of proof by contradiction.\n- First KB and not a is converted into CNF.\n- Then, the resolution rule is applied to the resulting clauses.\n- 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.\n- The process continues until one of two things happens:\n1. there are no new clauses that can be added, in which case KB does not entail a; or,\n2. two clauses resolve to yield the empty clause, in which case KB entails a.\n- Complete\n- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n#### Horn clauses and definite clauses\n- Definite clauses: a disjunction of literals of which exactly one is positive. \n- Horn clauses: a disjunction of literals of which at most one is positive.\n- So all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses.\n- Horn clauses are closed under resolution: if you resolve two Horn clauses, you get back a Horn clause. One more class is the k-CNF sentence, which is a CNF sentence where each clause has at most k literals.\n\n#### Forward and backward chaining\n- Forward chaining algo determines if a single proposition symbol q, the query, is entailed by a KB of definite clauses.\n- Meaning L1,1 and Breeze are known, so implies B1,1 and add to KB.\n- Continue until no further inferences can be made. \n- General concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data.\n- Backward chaining is a form of goal-directed reasoning.\n- If the query  is known to be true, then no work is needed. Otherwise, the algorithm finds those implications in the knowledge base whose conclusion is query. If all the premises of \none of those implications can be proved true, then query is true.\n \n\n## Module 7 Definitions\n* **Knowledge base** - A set of sentences.\n* **Axiom** - Sentence taken as being given without being derived from other sentences.\n* **Tell and ask** - Add new sentences to KB and query what is known.\n* **Inference** - Deriving new sentences from old.\n* **Semantics** - Meaning, of sentences. Defines truth of each sentence to each possible world.\n* **Model** - Use model in place of possible world when need to be precise. \n* **Logical entailment** - The idea that a sentence follows logically from another sentence\n* **Model checking** - Enumerates all possible models to check a is true in all models where KB is true. M(KB)subset of M(a)\n* **Completeness** - If cnan derive any sentence that is entailed. \n* **Syntax** - Defines allowable sentences. \n* **Atomic sentences** - Consist a single proposition symbol\n* **Proposition symbol** - Shows if proposition is true or false.\n* **Logical equivalence** - Two sentences are logical equivalent if they are true in the same set of models.\n* **Resolution** - Single inference rule, yield complete inference algo with any complete search algo.\n* **Complementary literals** - One is negation of another\n* **Resolution closure** - Computes as the final value of the variable clauses.\n* **Ground resolution theorem** - The completeness theorem for resolution in propositional logic.\n* **Body** - Horn clause premise\n* **Head** - Horn clause head\n* **Fact** - Sentence with a single positive literal\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}