{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "b161a836-c4f0-4833-b311-4bff41e1a8ac"
      },
      "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": 5,
      "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": "1853b288-498f-4a3d-c835-4e0958fd1e20"
      },
      "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": 6,
      "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": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "Artificial intelligence is defined in different ways: **human vs rational** and **thought vs behavior**.\n",
        "\n",
        "On the human side, a machine would need NLP, knowledge representation, automated reasoning (inference), and machine learning to pass the Turing test. \\\n",
        "It would also need computer vision and robotics to pass the total Turing test. We need to know how humans think to imitate them. This requires introspection, \\\n",
        "psychological experiments, and brain imaging. The field of cognitive science brings together computer models and experimental techniques from psychology to \\\n",
        "make theories about the human mind. \n",
        "\n",
        "On the rational side, the theory of logic underpins AI development (logicist tradition), with the theory of probability allowing rigorous reasoning with uncertain information. \\\n",
        "This can lead to a model of rational thought, but not sufficient for rational behavior model.\n",
        "\n",
        "The **rational agent model** is more general than the \"laws of thought\" approach (correct inference is just one of several mechanisms for achieving rationality), \\\n",
        "and the goal is more mathematically well-defined. It involves the study and construction of agents that \"do the right thing\". It is the most popular approach to AI, \\\n",
        "and is sometimes called the **standard model**. \n",
        "\n",
        "It is hard to anticipate the ways a rational agent might go about achieving a given objective, and thus it is difficult to align our true preferences with the objectives \\\n",
        "we give machines (value alignment problem). This is a shortcoming of the standard model; we want machines to act cautiously, ask permission, learn more about \\\n",
        "our preferences, and defer to human control when their given objectives are incomplete or unclear (we want agents that are **provably beneficial** to humans).\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "John Searle made the distinction between strong AI and weak AI (pretending to be intelligent vs actually employing intelligence).\n",
        "\n",
        "Alan Turing's **argument from informality of behavior** says that human behavior is too complex and informal to be guided by a set of formal rules that could be codified into a computer program. \\\n",
        "Similar arguments made by Hubert Dreyfus (computational AI won't be able to succeed). These critiques reflect the **qualification problem**, that it is hard to capture every contingency of appropriate \\\n",
        "behavior in a set of logical rules. These critiques of Good Old-Fashioned AI have been eclipsed by new kinds of AI models, employing probabilistic techniques and deep learning (for example).\n",
        "\n",
        "The **embodied cognition** approach (Hubert Dreyfus) claims that cognition happens within a body, embedded in an environment; the brain exploits regularities in its environment, including the rest of its body. \\\n",
        "Robotics, vision, and other sensors are central to AI under this approach.\n",
        "\n",
        "Turing's **argument from disability** says that some elements of human behavior cannot be replicated by a machine \\\n",
        "(empathy, emotion, novelty/initiative, intuition, imperfection, introspection/self-awareness, etc). \\\n",
        "Some of these behaviors have already been replicated by AI. \\\n",
        "\n",
        "**Godel's incompleteness theorem**: an axiomatic framework cannot simultaneously be recursive (implementable on a computer), powerful enough to do arithmetic, \\\n",
        "complete (can either prove or disprove any X), and consistent (never proves X and not X). This is a false critique of AI since humans have the same issue.\n",
        "\n",
        "Work on passing Turing test isn't super important. More important to improve science/technology and provide useful tools for humans using AI.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Turing points out the solipsism that we don't know if other humans think, but we believe the **polite convention** that everyone thinks. We could extend this convention to machines \\\n",
        "if we had experience with ones that acted intelligently.\n",
        "\n",
        "John Searle's **Chinese room**: English-speaking human inside box reading Chinese messages, applying rules from book to construct answer, and sending response. \\\n",
        "The human or book doesn't realy 'understand' Chinese, and a computer is analogous, so it doesn't generate understanding.\n",
        "\n",
        "John Searle supports **biological naturalism**: high level emergent features of mental states are caused by low-level physical processes in the neurons that can't be automated. \n",
        "\n",
        "Does a machine really feel? Whether machines can have qualia and the precise definition of conciousness are under debate. These questions aren't really practical/important for AI work.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent perceives its environment through **sensors** and acts on its environment through **actuators**. The content of a sensor reading is a **percept**, and the history of \\\n",
        "sensor readings is the **percept sequence**. We characterize an agent by its **agent function**, mapping a given percept sequence to an action. This function could be tabulated \\\n",
        "as an external characterization of the agent's behavior. Internally, the agent's behavior is implemented by an **agent program**.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "A rational agent does the right thing, but what is the right thing? AI usually sticks with **consequentialism**, evaluating an agent based on the consequences of its behavior \\\n",
        "(the sequence of environment states caused by the agent's sequence of actions). A **performance measure** evaluates a given sequence of environment states. The agent may or may not be directly \\\n",
        "aware of its performance measure. It is better to design performance measures based on what you actually want achieved in the environment, rather than how you think the agent should behave. \\\n",
        "May want to build agents that reflect initial uncertainty about the true performance measure and learn more with time.\n",
        "\n",
        "**Rationality** depends on the performance measure, the agent's prior knowledge of the environment, the actions that the agent can perform, and the agent's percept sequence. A **rational agent** \n",
        "selects an action to maximize its performance measure, given its percept sequence and prior knowledge. An **omnicient** agent knows the actual outcome of its actions and can act accordingly \\\n",
        "(impossible in reality). Rationality does not require omnicience. Rational choice depends only on the percept sequence so far and prior knowledge, and maximizes expected performance measure. \n",
        "This includes **exploring** enough to reflect enough relevant information in its percept sequence (blindly taking your best guess action without exploring first is not rational). Doing actions \\\n",
        "in order to modify future percepts is called **information gathering**. A rational agent should also **learn** as much as possible from gathered information and prior knowledge (inference). \\\n",
        "An **autonomous** agent learns what it can to compensate for partial or incorrect prior knowledge. A rational agent should eventually learn enough to become independent of its prior knowledge.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "A **task environment** is (informally) the 'problem' that a rational agent has to solve. It is comprised of **PEAS** (**Performance Measure**, **Environment**, **Actuators**, **Sensors**). \\\n",
        "The environment (E within PEAS) is the set of conditions, constraints, and other agents the agent will interact with. \n",
        "\n",
        "The following are dimensions with which we can characterize task environments.\n",
        "\n",
        "**Fully observable** vs **partially observable**. A task environment is fully observable if the agent's sensors give it access to all aspects of the environment that are relevant to its \\\n",
        "choice of action (relevance depends on the performance measure). A TE could be partially observable because of noisy/inaccurate sensors or because parts of the environment state are missing \\\n",
        "from sensor data. If the agent has no sensors, the environment is **unobservable**.\n",
        "\n",
        "**Single agent** vs **multi agent**. How many agents are interacting in the environment? Another object should be viewed as an agent if its behavior is best described as \\\n",
        "maximizing a performance measure whose value depends on our agent's behavior. In a **competitive** multiagent environment, different agents' performance measures are at odds. \\\n",
        "In a **cooperative** multiagent environment, different agents' performance measures are positively correlated in some ways. \n",
        "\n",
        "**Deterministic vs nondeterministic**. In a deterministic TE, the next state of the environment is completely determined by the current state and the agent's action. \\\n",
        "A partially observable TE could appear to be nondeterministic, or the rules for state change could be so complicated that they are treated as nondeterministic. \\\n",
        "A **stochastic** TE explicitly deals with probabilities (in a non-stochastic nondeterministic TE, the state transition function is uncertain and not probabilistically quantifiable).\n",
        "\n",
        "**Episodic** vs **sequential**. In an episodic TE, the next episode does not depend on the actions taken in previous episodes (an **episode** is a unit of receiving a percept and performing a single action). \\\n",
        "In a sequential TE, the current action could affect future decisions (you have to think ahead to act rationally).\n",
        "\n",
        "**Static** vs **dynamic**. In a dynamic TE, the environment can change while an agent is deliberating. In a static environment, the agent can ignore its environment \\\n",
        "and doesn't need to worry about the passage of time while it is deliberating. In a **semidynamic** environment, the environment does not change while the agent is deliberating, \\\n",
        "but the agent's score does change.\n",
        "\n",
        "**Discrete** vs **continuous**. This dimension characterizes the state of the environment, the way time is handled, and the percepts and actions of the agent.\n",
        "\n",
        "**Known** vs **unknown**. This dimension refers not to the environment itself but to whether the agent knows the laws/rules of the environment. \n",
        "\n",
        "The hardest task environment is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "Agent program should be a compressed characterization of the agent function (i.e. not a whole tabular representation).\n",
        "\n",
        "A **simple reflex agent** selects actions based on the current percept, ignoring the rest of the percept history. A percept condition can directly trigger an action in response \\\n",
        "(a connection called a **condition-action rule**). These agents only work in fully observable environments, and are susceptible to infinite loops (can be mitigated with **randomization**).\n",
        "\n",
        "A **model-based reflex agent** keeps track of what it has seen (i.e. maintains **internal state** based on percept sequence, may be a 'best guess' of relevant information). \\\n",
        "Updating this internal state over time requires information about how the world changes over time (effects of agent's action and how the world evolves independently), \\\n",
        "called a **transition model**. Also need information about how the state of the world is reflected in the agent's percepts: the **sensor model**. \\\n",
        "\n",
        "A **goal-based agent** is a model-based agent that has certain goal states. **Search** and **planning** involve finding action sequences that achieve a goal. \\\n",
        "A goal-based agent has a deeper understanding of why it is taking certain actions, in contrast to reflex agents.\n",
        "\n",
        "A **utility-based agent** aims to maximize a known **utility function** (an internalization of the performance measure). \\\n",
        "A utility-based agent works even when there are conflicting goals, or several possible goals (none of which can be achieved with certainty). A rational utility-based agent takes actions to \\\n",
        "maximize the **expected utility** of the action outcomes.\n",
        "\n",
        "A **model-free** agent can learn what action is best without learning why the action is best.\n",
        "\n",
        "A **learning agent** learns rather than being explicitly programmed, and is self-improving. Can operate in an initially unknown environment and become more competent. Composed of a \\\n",
        "**problem generator** (suggests actions to lead to new and informative experiences, i.e. exploration), **performance element** (selects actions), **critic** (judges results), \\\n",
        "and **learning element** (improves behavior; can change knowledge base, transition model, or sensor model; can generate reward or penalty).\n",
        "\n",
        "Three ways to represent states and transitions. **Atomic representation**: state is a black box with no internal structure (e.g. node). \\\n",
        "**Factored representation**: state is a vector of boolean/real/enum attribute **values** (or **variables**), e.g. vector of telemetry. \\\n",
        "**Structured representation**: a state includes objects with nested attributes and/or relationships to other objects (e.g. graph, ER diagram). \\\n",
        "These representations are increasingly **expressive** (increasing compression of information, increasing difficulty of reasoning and learning).\n",
        "\n",
        "In a **localist representation** there is a direct mapping between concepts and memory locations. In a **distributed representation**, a concept can be \\\n",
        "spread across many memory locations (more robust to noise and information loss).\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "Rene Descartes: principle of **dualism** - the mind or thinking self is incorporeal/spiritual (exists separately from the body). How to know that others aren't automata (*solipsism*)? \\\n",
        "Can an automata simulate a thinking being? Could make a test that only a person could pass.\n",
        "\n",
        "Daniel Dennett: Brain in a Vat. Brain in vat remote controlling body, body is destroyed by radiation, but conciousness continues in vat. \\\n",
        "Scientists construct him in a new body. Then revealed that they constructed a computer duplicate of his brain. How is this different from brain in vat?\n",
        "\n",
        "Strong AI vs weak AI: actually thinking vs simulating thinking. Not super practical distinction.\n",
        "\n",
        "**Machine learning** vs **Artificial General Intelligence**: most modern research focused on optimizing performance on certain tasks, rather than \\\n",
        "pondering whether it is possible to construct systems that are truly intelligent.\n",
        "\n",
        "**The Heilmeier Catechism**: what are you trying to do (no jargon allowed)? How is it done today, and what are the limits of current practice? \\\n",
        "What is new in your approach and why will it be successful? Who cares? If you are successful, what difference will it make?\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",
        "  \"Turing test\" : \"A test for 'true' AI, in which a human tries to distinguish a machine from a human through Q&A.\",\n",
        "  \"total Turing test\": \"Same as the Turing test, except it also requires that the interrogation involves visual acuity and physical interaction.\",\n",
        "  \"syllogisms\": \"A kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions.\",\n",
        "  \"logic\": \"An interdisciplinary field which studies truth and reasoning.\",\n",
        "  \"agent (informal)\": \"Something that acts.\",\n",
        "  \"rational agent (informal)\": \"An agent that acts so as to achieve the best outcome or (under uncertainty) the best expected outcome.\",\n",
        "  \"standard model\": \"The rational agent model (called the standard model due to its popularity in the field of AI).\",\n",
        "  \"limited rationality\": \"Acting appropriately when there is not enough time to do all the computations one might like.\",\n",
        "  \"value alignment problem\": \"The problem of achieving agreement between our true preferences and the objective we give to a machine.\",\n",
        "  \"weak AI\": \"Machines that can act as if they were intelligent, but are really just pretending (John Searle).\",\n",
        "  \"strong AI\": \"Programs that can arbitrary / various tasks, including novel ones, and do so as well as a human.\",\n",
        "  \"Good Old-Fashioned AI (GOFAI)\": \"The simplest kind of logical agent.\",\n",
        "  \"qualification problem\": \"it is hard to capture every contingency of appropriate behavior in a set of logical rules\",\n",
        "  \"conciousness\": \"Awareness of the outside world, and of the self, and the subjective experience of living.\",\n",
        "  \"qualia\": \"The internal and subjective component of sense perceptions, arising from stimulation of the senses by phenomena.\",\n",
        "  \"agent (formal)\": \"Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\",\n",
        "  \"percept\": \"The content an agent’s sensors are perceiving.\",\n",
        "  \"percept sequence\": \"The complete history of everything the agent has ever perceived.\",\n",
        "  \"agent function\": \"Maps a given percept sequence to an action.\",\n",
        "  \"agent program\": \"An agent's internal implementation of its agent function.\",\n",
        "  \"consequentialism\": \"Evaluating an agent based on the consequences of its behavior.\",\n",
        "  \"rational agent (formal)\": \"Chooses an action to maximize expected performance measure based on percept sequence and prior knowledge.\",\n",
        "  \"information gathering\": \"Doing actions in order to modify future percepts.\",\n",
        "  \"autonomous agent\": \"Learns what it can to compensate for partial or incorrect prior knowledge.\",\n",
        "  \"task environment\": \"The 'problem' that a rational agent has to solve (Performance, Environment, Actuators, Sensors).\",\n",
        "  \"fully observable environment\": \"The agent's sensors give it access to all relevant aspects of the environment for its action.\",\n",
        "  \"partially observable environment\": \"Not fully observable.\",\n",
        "  \"deterministic environment\": \"The next state of the environment is completely determined by the current state and the agent's action\",\n",
        "  \"episode\": \"A unit of receiving a percept and performing a single action.\",\n",
        "  \"episodic environment\": \"The next episode does not depend on the actions taken in previous episodes.\",\n",
        "  \"sequential environment\": \"The current action could affect future decisions (you have to think ahead to act rationally)\",\n",
        "  \"dynamic environment\": \"The environment can change while an agent is deliberating.\",\n",
        "  \"static environment\": \"The agent can ignore its environment and doesn't need to worry about the passage of time while it is deliberating.\",\n",
        "  \"semidynamic environment\": \"The environment doesn't change while an agent is deliberating, but the agent's score does.\",\n",
        "  \"environment class\": \"A group of related task environments.\",\n",
        "  \"agent architecture\": \"Feeds percepts to the program, runs the program, and feeds the program’s action choices to the actuators.\",\n",
        "  \"table-driven agent\": \"Just uses tabluar form of its agent function for its agent program (usually impractical).\",\n",
        "  \"simple reflex agent\": \"Selects actions on the basis of just the current percept.\",\n",
        "  \"condition-action rule\": \"A direct connection in the agent program between a condition of the percept and an action.\",\n",
        "  \"model-based reflex agent\": \"Keeps track of the part of the world it has seen before but can't see now.\",\n",
        "  \"transition model\": \"An understanding of how the world changes over time (effects of agent's action and how the world evolves independently).\",\n",
        "  \"sensor model\": \"An understanding of how the state of the world is reflected in the agent's percepts.\",\n",
        "  \"model-based reflex agent\": \"Selects actions using stored internal state, as well as a transition model and a sensor model.\",\n",
        "  \"utility-based agent\": \"Aims to maximize a known utility function.\",\n",
        "  \"utility function\": \"A known internalization of an agent's performance measure.\",\n",
        "  \"model-free agent\": \"Can learn what action is best without ever learning exactly how that action works.\",\n",
        "  \"learning agent\": \"Improve the performance of their components to generate better actions.\",\n",
        "  \"problem generator\": \"Component of a learning agent that suggests actions to lead to new and informative experiences (exploration).\",\n",
        "  \"performance element\": \"Component of a learning agent that selects actions.\",\n",
        "  \"critic\": \"Component of a learning agent that judges results.\",\n",
        "  \"learning element\": \"Component of a learning agent that improves behavior.\",\n",
        "  \"atomic representation\": \"A state is a black box with no internal structure.\",\n",
        "  \"factored representation\": \"A state consists of a vector of attribute values (boolean, real, or enum).\",\n",
        "  \"structured representation\": \"A state includes objects, each of which may have attributes of its own as well as relationships to other objects.\",\n",
        "  \"localist representation\": \"A state representation with a one-to-one mapping between concepts and memory locations.\",\n",
        "  \"distributed representation\": \"A state representation in which a concept can be spread across many memory locations.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "43b45065-9bf0-4ed9-c750-b17b49f62918"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nArtificial intelligence is defined in different ways: **human vs rational** and **thought vs behavior**.\n\nOn the human side, a machine would need NLP, knowledge representation, automated reasoning (inference), and machine learning to pass the Turing test. It would also need computer vision and robotics to pass the total Turing test. We need to know how humans think to imitate them. This requires introspection, psychological experiments, and brain imaging. The field of cognitive science brings together computer models and experimental techniques from psychology to make theories about the human mind. \n\nOn the rational side, the theory of logic underpins AI development (logicist tradition), with the theory of probability allowing rigorous reasoning with uncertain information. This can lead to a model of rational thought, but not sufficient for rational behavior model.\n\nThe **rational agent model** is more general than the \"laws of thought\" approach (correct inference is just one of several mechanisms for achieving rationality), and the goal is more mathematically well-defined. It involves the study and construction of agents that \"do the right thing\". It is the most popular approach to AI, and is sometimes called the **standard model**. \n\nIt is hard to anticipate the ways a rational agent might go about achieving a given objective, and thus it is difficult to align our true preferences with the objectives we give machines (value alignment problem). This is a shortcoming of the standard model; we want machines to act cautiously, ask permission, learn more about our preferences, and defer to human control when their given objectives are incomplete or unclear (we want agents that are **provably beneficial** to humans).\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nJohn Searle made the distinction between strong AI and weak AI (pretending to be intelligent vs actually employing intelligence).\n\nAlan Turing's **argument from informality of behavior** says that human behavior is too complex and informal to be guided by a set of formal rules that could be codified into a computer program. Similar arguments made by Hubert Dreyfus (computational AI won't be able to succeed). These critiques reflect the **qualification problem**, that it is hard to capture every contingency of appropriate behavior in a set of logical rules. These critiques of Good Old-Fashioned AI have been eclipsed by new kinds of AI models, employing probabilistic techniques and deep learning (for example).\n\nThe **embodied cognition** approach (Hubert Dreyfus) claims that cognition happens within a body, embedded in an environment; the brain exploits regularities in its environment, including the rest of its body. Robotics, vision, and other sensors are central to AI under this approach.\n\nTuring's **argument from disability** says that some elements of human behavior cannot be replicated by a machine (empathy, emotion, novelty/initiative, intuition, imperfection, introspection/self-awareness, etc). Some of these behaviors have already been replicated by AI. \n**Godel's incompleteness theorem**: an axiomatic framework cannot simultaneously be recursive (implementable on a computer), powerful enough to do arithmetic, complete (can either prove or disprove any X), and consistent (never proves X and not X). This is a false critique of AI since humans have the same issue.\n\nWork on passing Turing test isn't super important. More important to improve science/technology and provide useful tools for humans using AI.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nTuring points out the solipsism that we don't know if other humans think, but we believe the **polite convention** that everyone thinks. We could extend this convention to machines if we had experience with ones that acted intelligently.\n\nJohn Searle's **Chinese room**: English-speaking human inside box reading Chinese messages, applying rules from book to construct answer, and sending response. The human or book doesn't realy 'understand' Chinese, and a computer is analogous, so it doesn't generate understanding.\n\nJohn Searle supports **biological naturalism**: high level emergent features of mental states are caused by low-level physical processes in the neurons that can't be automated. \n\nDoes a machine really feel? Whether machines can have qualia and the precise definition of conciousness are under debate. These questions aren't really practical/important for AI work.\n\n\n## AIMA 2.1 Agents and Environments\n\nAn agent perceives its environment through **sensors** and acts on its environment through **actuators**. The content of a sensor reading is a **percept**, and the history of sensor readings is the **percept sequence**. We characterize an agent by its **agent function**, mapping a given percept sequence to an action. This function could be tabulated as an external characterization of the agent's behavior. Internally, the agent's behavior is implemented by an **agent program**.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nA rational agent does the right thing, but what is the right thing? AI usually sticks with **consequentialism**, evaluating an agent based on the consequences of its behavior (the sequence of environment states caused by the agent's sequence of actions). A **performance measure** evaluates a given sequence of environment states. The agent may or may not be directly aware of its performance measure. It is better to design performance measures based on what you actually want achieved in the environment, rather than how you think the agent should behave. May want to build agents that reflect initial uncertainty about the true performance measure and learn more with time.\n\n**Rationality** depends on the performance measure, the agent's prior knowledge of the environment, the actions that the agent can perform, and the agent's percept sequence. A **rational agent** \nselects an action to maximize its performance measure, given its percept sequence and prior knowledge. An **omnicient** agent knows the actual outcome of its actions and can act accordingly (impossible in reality). Rationality does not require omnicience. Rational choice depends only on the percept sequence so far and prior knowledge, and maximizes expected performance measure. \nThis includes **exploring** enough to reflect enough relevant information in its percept sequence (blindly taking your best guess action without exploring first is not rational). Doing actions in order to modify future percepts is called **information gathering**. A rational agent should also **learn** as much as possible from gathered information and prior knowledge (inference). An **autonomous** agent learns what it can to compensate for partial or incorrect prior knowledge. A rational agent should eventually learn enough to become independent of its prior knowledge.\n\n\n## AIMA 2.3 The Nature of Environments\n\nA **task environment** is (informally) the 'problem' that a rational agent has to solve. It is comprised of **PEAS** (**Performance Measure**, **Environment**, **Actuators**, **Sensors**). The environment (E within PEAS) is the set of conditions, constraints, and other agents the agent will interact with. \n\nThe following are dimensions with which we can characterize task environments.\n\n**Fully observable** vs **partially observable**. A task environment is fully observable if the agent's sensors give it access to all aspects of the environment that are relevant to its choice of action (relevance depends on the performance measure). A TE could be partially observable because of noisy/inaccurate sensors or because parts of the environment state are missing from sensor data. If the agent has no sensors, the environment is **unobservable**.\n\n**Single agent** vs **multi agent**. How many agents are interacting in the environment? Another object should be viewed as an agent if its behavior is best described as maximizing a performance measure whose value depends on our agent's behavior. In a **competitive** multiagent environment, different agents' performance measures are at odds. In a **cooperative** multiagent environment, different agents' performance measures are positively correlated in some ways. \n\n**Deterministic vs nondeterministic**. In a deterministic TE, the next state of the environment is completely determined by the current state and the agent's action. A partially observable TE could appear to be nondeterministic, or the rules for state change could be so complicated that they are treated as nondeterministic. A **stochastic** TE explicitly deals with probabilities (in a non-stochastic nondeterministic TE, the state transition function is uncertain and not probabilistically quantifiable).\n\n**Episodic** vs **sequential**. In an episodic TE, the next episode does not depend on the actions taken in previous episodes (an **episode** is a unit of receiving a percept and performing a single action). In a sequential TE, the current action could affect future decisions (you have to think ahead to act rationally).\n\n**Static** vs **dynamic**. In a dynamic TE, the environment can change while an agent is deliberating. In a static environment, the agent can ignore its environment and doesn't need to worry about the passage of time while it is deliberating. In a **semidynamic** environment, the environment does not change while the agent is deliberating, but the agent's score does change.\n\n**Discrete** vs **continuous**. This dimension characterizes the state of the environment, the way time is handled, and the percepts and actions of the agent.\n\n**Known** vs **unknown**. This dimension refers not to the environment itself but to whether the agent knows the laws/rules of the environment. \n\nThe hardest task environment is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n\nAgent program should be a compressed characterization of the agent function (i.e. not a whole tabular representation).\n\nA **simple reflex agent** selects actions based on the current percept, ignoring the rest of the percept history. A percept condition can directly trigger an action in response (a connection called a **condition-action rule**). These agents only work in fully observable environments, and are susceptible to infinite loops (can be mitigated with **randomization**).\n\nA **model-based reflex agent** keeps track of what it has seen (i.e. maintains **internal state** based on percept sequence, may be a 'best guess' of relevant information). Updating this internal state over time requires information about how the world changes over time (effects of agent's action and how the world evolves independently), called a **transition model**. Also need information about how the state of the world is reflected in the agent's percepts: the **sensor model**. \nA **goal-based agent** is a model-based agent that has certain goal states. **Search** and **planning** involve finding action sequences that achieve a goal. A goal-based agent has a deeper understanding of why it is taking certain actions, in contrast to reflex agents.\n\nA **utility-based agent** aims to maximize a known **utility function** (an internalization of the performance measure). A utility-based agent works even when there are conflicting goals, or several possible goals (none of which can be achieved with certainty). A rational utility-based agent takes actions to maximize the **expected utility** of the action outcomes.\n\nA **model-free** agent can learn what action is best without learning why the action is best.\n\nA **learning agent** learns rather than being explicitly programmed, and is self-improving. Can operate in an initially unknown environment and become more competent. Composed of a **problem generator** (suggests actions to lead to new and informative experiences, i.e. exploration), **performance element** (selects actions), **critic** (judges results), and **learning element** (improves behavior; can change knowledge base, transition model, or sensor model; can generate reward or penalty).\n\nThree ways to represent states and transitions. **Atomic representation**: state is a black box with no internal structure (e.g. node). **Factored representation**: state is a vector of boolean/real/enum attribute **values** (or **variables**), e.g. vector of telemetry. **Structured representation**: a state includes objects with nested attributes and/or relationships to other objects (e.g. graph, ER diagram). These representations are increasingly **expressive** (increasing compression of information, increasing difficulty of reasoning and learning).\n\nIn a **localist representation** there is a direct mapping between concepts and memory locations. In a **distributed representation**, a concept can be spread across many memory locations (more robust to noise and information loss).\n\n\n## Module 1 Lecture Notes\n\nRene Descartes: principle of **dualism** - the mind or thinking self is incorporeal/spiritual (exists separately from the body). How to know that others aren't automata (*solipsism*)? Can an automata simulate a thinking being? Could make a test that only a person could pass.\n\nDaniel Dennett: Brain in a Vat. Brain in vat remote controlling body, body is destroyed by radiation, but conciousness continues in vat. Scientists construct him in a new body. Then revealed that they constructed a computer duplicate of his brain. How is this different from brain in vat?\n\nStrong AI vs weak AI: actually thinking vs simulating thinking. Not super practical distinction.\n\n**Machine learning** vs **Artificial General Intelligence**: most modern research focused on optimizing performance on certain tasks, rather than pondering whether it is possible to construct systems that are truly intelligent.\n\n**The Heilmeier Catechism**: what are you trying to do (no jargon allowed)? How is it done today, and what are the limits of current practice? What is new in your approach and why will it be successful? Who cares? If you are successful, what difference will it make?\n\n\n## Module 1 Definitions\n* **Turing test** - A test for 'true' AI, in which a human tries to distinguish a machine from a human through Q&A.\n* **Total turing test** - Same as the Turing test, except it also requires that the interrogation involves visual acuity and physical interaction.\n* **Syllogisms** - A kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions.\n* **Logic** - An interdisciplinary field which studies truth and reasoning.\n* **Agent (informal)** - Something that acts.\n* **Rational agent (informal)** - An agent that acts so as to achieve the best outcome or (under uncertainty) the best expected outcome.\n* **Standard model** - The rational agent model (called the standard model due to its popularity in the field of AI).\n* **Limited rationality** - Acting appropriately when there is not enough time to do all the computations one might like.\n* **Value alignment problem** - The problem of achieving agreement between our true preferences and the objective we give to a machine.\n* **Weak ai** - Machines that can act as if they were intelligent, but are really just pretending (John Searle).\n* **Strong ai** - Programs that can arbitrary / various tasks, including novel ones, and do so as well as a human.\n* **Good old-fashioned ai (gofai)** - The simplest kind of logical agent.\n* **Qualification problem** - it is hard to capture every contingency of appropriate behavior in a set of logical rules\n* **Conciousness** - Awareness of the outside world, and of the self, and the subjective experience of living.\n* **Qualia** - The internal and subjective component of sense perceptions, arising from stimulation of the senses by phenomena.\n* **Agent (formal)** - Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n* **Percept** - The content an agent’s sensors are perceiving.\n* **Percept sequence** - The complete history of everything the agent has ever perceived.\n* **Agent function** - Maps a given percept sequence to an action.\n* **Agent program** - An agent's internal implementation of its agent function.\n* **Consequentialism** - Evaluating an agent based on the consequences of its behavior.\n* **Rational agent (formal)** - Chooses an action to maximize expected performance measure based on percept sequence and prior knowledge.\n* **Information gathering** - Doing actions in order to modify future percepts.\n* **Autonomous agent** - Learns what it can to compensate for partial or incorrect prior knowledge.\n* **Task environment** - The 'problem' that a rational agent has to solve (Performance, Environment, Actuators, Sensors).\n* **Fully observable environment** - The agent's sensors give it access to all relevant aspects of the environment for its action.\n* **Partially observable environment** - Not fully observable.\n* **Deterministic environment** - The next state of the environment is completely determined by the current state and the agent's action\n* **Episode** - A unit of receiving a percept and performing a single action.\n* **Episodic environment** - The next episode does not depend on the actions taken in previous episodes.\n* **Sequential environment** - The current action could affect future decisions (you have to think ahead to act rationally)\n* **Dynamic environment** - The environment can change while an agent is deliberating.\n* **Static environment** - The agent can ignore its environment and doesn't need to worry about the passage of time while it is deliberating.\n* **Semidynamic environment** - The environment doesn't change while an agent is deliberating, but the agent's score does.\n* **Environment class** - A group of related task environments.\n* **Agent architecture** - Feeds percepts to the program, runs the program, and feeds the program’s action choices to the actuators.\n* **Table-driven agent** - Just uses tabluar form of its agent function for its agent program (usually impractical).\n* **Simple reflex agent** - Selects actions on the basis of just the current percept.\n* **Condition-action rule** - A direct connection in the agent program between a condition of the percept and an action.\n* **Model-based reflex agent** - Selects actions using stored internal state, as well as a transition model and a sensor model.\n* **Transition model** - An understanding of how the world changes over time (effects of agent's action and how the world evolves independently).\n* **Sensor model** - An understanding of how the state of the world is reflected in the agent's percepts.\n* **Utility-based agent** - Aims to maximize a known utility function.\n* **Utility function** - A known internalization of an agent's performance measure.\n* **Model-free agent** - Can learn what action is best without ever learning exactly how that action works.\n* **Learning agent** - Improve the performance of their components to generate better actions.\n* **Problem generator** - Component of a learning agent that suggests actions to lead to new and informative experiences (exploration).\n* **Performance element** - Component of a learning agent that selects actions.\n* **Critic** - Component of a learning agent that judges results.\n* **Learning element** - Component of a learning agent that improves behavior.\n* **Atomic representation** - A state is a black box with no internal structure.\n* **Factored representation** - A state consists of a vector of attribute values (boolean, real, or enum).\n* **Structured representation** - A state includes objects, each of which may have attributes of its own as well as relationships to other objects.\n* **Localist representation** - A state representation with a one-to-one mapping between concepts and memory locations.\n* **Distributed representation** - A state representation in which a concept can be spread across many memory locations.\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",
        "Python has fast development (concise, intuitive syntax, whitespace delimited), garbage collected, portable, has plenty of built-in types, \\\n",
        "has large collection of support libraries.\n",
        "\n",
        "Strongly typed (there are restrictions on conversions between types), dynamically typed (you can change the type of a variable after declaration/initialization).\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {}"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 225
        },
        "outputId": "00a2ab89-3a85-4791-81e6-052ec179eef1"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython has fast development (concise, intuitive syntax, whitespace delimited), garbage collected, portable, has plenty of built-in types, has large collection of support libraries.\n\nStrongly typed (there are restrictions on conversions between types), dynamically typed (you can change the type of a variable after declaration/initialization).\n\n\n## Module 2 Definitions\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",
        "In fully observable and known environments, agents can follow this 4-step problem solving process: 1. **goal formulation**: recognize goal state (limit objectives and hence actions to be considered). \\\n",
        "2. **problem formulation**: devise a description of states and actions necessary to reach the goal. 3. **search**: before taking any actions in the real world, the agent simulates a sequence of \\\n",
        "actions in its model, searching until it finds a sequence of actions leading to the goal (called a **solution**). 4. **execution**: the agent can now execute the actions in the solution one-at-a-time.\n",
        "\n",
        "In a fully observable, deterministic, single-agent, known environment, the solution to any problem is a fixed sequence of actions. This is an **open-loop** system (ignoring percepts to follow a plan, breaking \\\n",
        "loop between agent and environment). If it's possible the solution is incorrect, or the environment is nondeterministic, multi-agent, or partially observable, then the agent would be safer using \\\n",
        "a **closed-loop** approach that monitors the percepts and applies a branching strategy (recommending different future actions based on what percepts arrive).\n",
        "\n",
        "A **search problem** consists of a set of possible **states** (**state space**), the **initial state**, a set of **goal states**, the **actions** available to the agent at each state, \\\n",
        "a **transition model** describing what each action does at each state, and an **action cost function** that gives the numeric cost (assumed to be positive) of applying action a in \\\n",
        "state s to reach state s' (this should reflect the performance measure). The state space can be represented as a graph[states, actions/transitions]. A search problem is a **model** \\\n",
        "of a real-life problem (removing detail from representation is called **abstraction**; an abstraction is valid if we can turn any abstract solution into a solution in the real world; \\\n",
        "an abstraction is useful if it makes the problem easier; the best abstraction maximizes usefulness while maintaining validity).\n",
        "\n",
        "A sequence of actions forms a **path**, and a **solution** is a path from the initial state to a goal state. We assume action costs are additive (total cost of path is sum of action costs). \\\n",
        "An **optimal solution** has the lowest path cost among all solutions.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "### Standardized problems\n",
        "(intended to illustrate or exercise various problem-solving methods)\n",
        "A **grid-world** problem is a 2D rectangular array of square cells, agents move cell-to-cell (up to all 8 directions), cells can be obstructed or contain objects with arbitrary properties. \\\n",
        "In a **sokoban puzzle**, the agent's goal is to push boxes scattered about the grid to storage locations (n obstacle cells and b boxes, $n\\times n!/(b!(n-b)!)$ states). \\\n",
        "In a **sliding-tile** puzzle, a number of tiles are arranged in a grid with one or more blank spaces that tiles can move into (e.g. rush hour puzzle, **8-puzzle** 3x3 grid, **15-puzzle** 4x4 grid). \\\n",
        "Knuth problem with infinite states: integer states, can apply square root, factorial, and floor operations (conjecture: can reach any positive integer).\n",
        "\n",
        "### Real-world problems\n",
        "(problem with practical real-world applications and details, usually with an idiosyncratic formulation)\n",
        "The **route-finding problem** has various practical applications (e.g. car navigation systems, IP routing, operations planning, airline travel planning). \\\n",
        "A **touring problem** describes a set of locations that must be visited (rather than a single goal from a set of possible goals). \\\n",
        "The **traveling salesperson problem (TSP)** is a touring problem in which every city on a map must be visited (minimizing cost of journey). \\\n",
        "A **VLSI layout** problem requires positioning components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield (usually split into \\\n",
        "**cell layout** and **channel routing**). \\\n",
        "**Robot navigation** is a generalization of the route-finding problem (continuous space, many-dimensional, partially observable, errors in sensor readings and motor controls, multi-agent). \\\n",
        "**Automatic assembly sequencing** of complex objects (like manufacturing). This includes **protein design** / protein folding.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "A **search algorithm** takes a search problem as input and returns a solution, or an indication of failure. We consider algorithms that explore a **search tree** \\\n",
        "over the state-space graph, trying to find a path that reaches a goal node (each node in the search tree corresponds to a state in the state space, edges correspond to actions, \\\n",
        "the root corresponds to the initial state). We **expand** a node in the search tree by **generating** new nodes for each available action applied to the current state. \\\n",
        "We always have a **frontier** of nodes that we haven't yet expanded (separating an interior region of the state-space graph where every state has been expanded, \\\n",
        "and an exterior region of states that have not yet been reached: the **separation property** of graph search). Any state that has a node in the search tree has been **reached**.\n",
        "\n",
        "In **best-first search**, we expand the node $n$ on the frontier with the minimum value of some **evaluation function**, $f(n)$.\n",
        "\n",
        "A **node** in a search tree is comprised of four components: **state** (element of state-space), **parent**: the node in the search tree that \\\n",
        "generated this node, **action**: the action applied to the parent's state to generate this node, and **path cost**: the total cost of the path from the initial state \\\n",
        "to this node ($g(n)$). \n",
        "\n",
        "We should store the nodes on the frontier using a **queue** of some kind (need to check if is empty, pop, peek, add). A **priority queue** \n",
        "pops the node with the minimum cost according to some function. A **FIFO queue** is a traditional queue (BFS). \\\n",
        "A **LIFO queue** is a stack (DFS). The visited states can be stored in a lookup table (e.g. hash set).\n",
        "\n",
        "A **repeated state** in the search tree occurs multiple times on a path (can be caused by a cycle in the state-space graph). A **redundant path** is a less optimal version of some other path. \\\n",
        "Can store visited states and eliminate them, allow them, or check for cycles but not redundant paths in general \\\n",
        "(follow parent pointers for a certain number of steps to see if you've been here before). A search algorithm is called a **graph search** if it checks for redundant paths, and a **tree-like search** if \\\n",
        "it does not check.\n",
        "\n",
        "We can evaluate search algorithms by **completeness** (is the algorithm guaranteed to find a solution when there is one, and correctly report failure when there is not; a complete algorithm must be \\\n",
        "**systematic** in exploring an infinite state space), **cost optimality** (does the algorithm find a solution with the lowest path cost of all solutions), \\\n",
        "**time complexity** (how long does it take to find a solution), and **space complexity** (how much memory is needed to perform the search). Time and space complexity are measured \\\n",
        "relative to $d$ (the **depth** or number of actions in an optimal solution), $m$ (the maximum number of actions in any path), and $b$ (the **branching factor** or number of successors \\\n",
        "of any node that should be considered).\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "An **uninformed search algorithm** is given no clue about how close a state is to the goal(s).\n",
        "\n",
        "When all actions have the same cost, a good strategy is **breadth-first** search; root node expanded first, then level 1 nodes expanded, then level 2 nodes, etc. \\\n",
        "It is systematic and therefore complete. Implemented with a FIFO queue. Does an **early goal test** (checking if a node is solution as soon as it is generated) rather than \\\n",
        "a **late goal test** (waiting until a node is popped off the queue to check if it is a solution). BFS is cost-optimal for problems where all actions have the same cost \\\n",
        "because it explores iteratively by the depth of a node (shortest path to that state). Both time and space complexity are $O(b^d)$.\n",
        "\n",
        "When actions have different costs, Dijkstra's algorithm (**uniform-cost search**) is a good choice. It expands nodes from the frontier with minimum $g(n)$ (cumulative path cost). \\\n",
        "Implemented with a priority queue. Spreads out in waves of roughly uniform path-cost. It is cost-optimal, systematic, and complete. The time and space complexity of uniform-cost search is \\\n",
        "$O(b^{1+floor(C^*/\\epsilon)})$, where $C^*$ is the cost of the optimal solution and $\\epsilon$ is a lower bound on the cost of each action. UCS can explore large trees of actions \\\n",
        "with low costs before exploring paths involving a high-cost and possibly useful action.\n",
        "\n",
        "Depth-first search expands the deepest node in the frontier first. Implemented with a stack. Usually implemented as a tree-like search (doesn't check for redundant paths). \\\n",
        "DFS is not cost-optimal (returns the first solution it finds, even if it isn't the cheapest). Not complete since it can get stuck in an infinite path, or cycles (some implementations \\\n",
        "check for cycles). Highly memory-efficient. Time complexity O(b^m), space complexity $O(bm)$. Variant called **backtracking search** uses $O(m)$ memory \\\n",
        "by generating only one successor at a time by modifying the current state description (and undoing the modification after recursive call).\n",
        "\n",
        "**Depth-limited search** is a variant of depth-first search in which we apply a depth limit $l$ and pretend that nodes at depth $l$ have no successors. Time complexity $O(b^l)$, space complexity $O(bl)$. \\\n",
        "Not complete or optimal unless $l=d$. Can check for cycles by following parent pointers.\n",
        "\n",
        "**Iterative deepening search** does depth-limited search with $l=0,1,2,...$ until it finds a solution. IDS is complete. IDS is optimal if all actions have the same cost. \\\n",
        "IDS takes $O(b^d)$ time and $O(bd)$ space ($\\sum_{l=0}^d O(b^l) = O(b^d)$).\n",
        "\n",
        "Could try BFS until almost all available memory is consumed, then run IDS from all the nodes in the frontier.\n",
        "\n",
        "**Bidirectional search** starts from initial state node and goal node, running search from each (2 frontiers, 2 visited sets), have a solution when the 2 frontiers collide. \\\n",
        "Reduces BFS to $O(b^{(d/2)})$ time/space and uniform-cost search to $O(b^{1+floor(C^*/\\epsilon)/2})$ time/space.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Covered by textbook.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "  \"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "  \"goal formulation\": \"recognize goal state (limit objectives and hence actions to be considered)\",\n",
        "  \"problem formulation\": \"devise a description of states and actions necessary to reach the goal\",\n",
        "  \"search\": \"simulate actions until you find a solution (sequence of actions leading to a goal)\",\n",
        "  \"solution\": \"a sequence of actions leading to a goal state\",\n",
        "  \"execution\": \"execute actions in solution one-by-one\",\n",
        "  \"open-loop system\": \"The agent follows a fixed sequence of actions, ignoring percepts.\",\n",
        "  \"closed-loop system\": \"The agent monitors the percepts and applies a branching strategy based on percepts.\",\n",
        "  \"abstraction\": \"removing detail from representation\",\n",
        "  \"valid abstraction\": \"we can turn any abstract solution into a solution in the real world\",\n",
        "  \"useful abstraction\": \"the abstract problem is easier to solve than the real-world problem\",\n",
        "  \"path\": \"a sequence of actions\",\n",
        "  \"path cost\": \"the sum of the action cost function applied to each action in the sequence\",\n",
        "  \"solution\": \"a path from the initial state to the goal state\",\n",
        "  \"optimal solution\": \"a solution with minimal path cost\",\n",
        "  \"standardized problem\": \"intended to illustrate or exercise various problem-solving methods\",\n",
        "  \"real-world problem\": \"problem with practical real-world applications and details, usually with an idiosyncratic formulation\",\n",
        "  \"egocentric actions\": \"actions with directions defined relative to the agent's perspective\",\n",
        "  \"absolute actions\": \"actions with directions defined by global dimensions\",\n",
        "  \"search algorithm\": \"takes a search problem as input and returns a solution, or an indication of failure\",\n",
        "  \"frontier\": \"the set of nodes in the search tree that haven't yet been expanded\",\n",
        "  \"reached\": \"a state is reached if it has a node in the search tree\",\n",
        "  \"best-first search\": \"we expand the node $n$ on the frontier with the minimum value of some **evaluation function**, $f(n)$\",\n",
        "  \"repeated state\": \"a state that occurs multiple times on a path in the search tree\",\n",
        "  \"redundant path\": \"a less optimal version of some other path\",\n",
        "  \"graph search\": \"checks for redundant paths\",\n",
        "  \"tree search\": \"does not check for redundant paths\",\n",
        "  \"early goal test\": \"checking if a node is solution as soon as it is generated\",\n",
        "  \"late goal test\": \"waiting until a node is popped off the queue to check if it is a solution\",\n",
        "  \"completeness\": \"is the algorithm guaranteed to find a solution when there is one, and correctly report failure when there is not\",\n",
        "  \"cost optimality\": \"does the algorithm find a solution with the lowest path cost of all solutions\",\n",
        "  \"time complexity\": \"how long does it take to find a solution\", \n",
        "  \"space complexity\": \"how much memory is needed to perform the search)\",\n",
        "  \"uninformed search algorithm\": \"is given no clue about how close a state is to the goal(s)\",\n",
        "  \"diameter (of a graph)\": \"the maximum path length\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "68ae26e8-d000-4b12-c2ac-49519770320f"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nIn fully observable and known environments, agents can follow this 4-step problem solving process: 1. **goal formulation**: recognize goal state (limit objectives and hence actions to be considered). 2. **problem formulation**: devise a description of states and actions necessary to reach the goal. 3. **search**: before taking any actions in the real world, the agent simulates a sequence of actions in its model, searching until it finds a sequence of actions leading to the goal (called a **solution**). 4. **execution**: the agent can now execute the actions in the solution one-at-a-time.\n\nIn a fully observable, deterministic, single-agent, known environment, the solution to any problem is a fixed sequence of actions. This is an **open-loop** system (ignoring percepts to follow a plan, breaking loop between agent and environment). If it's possible the solution is incorrect, or the environment is nondeterministic, multi-agent, or partially observable, then the agent would be safer using a **closed-loop** approach that monitors the percepts and applies a branching strategy (recommending different future actions based on what percepts arrive).\n\nA **search problem** consists of a set of possible **states** (**state space**), the **initial state**, a set of **goal states**, the **actions** available to the agent at each state, a **transition model** describing what each action does at each state, and an **action cost function** that gives the numeric cost (assumed to be positive) of applying action a in state s to reach state s' (this should reflect the performance measure). The state space can be represented as a graph[states, actions/transitions]. A search problem is a **model** of a real-life problem (removing detail from representation is called **abstraction**; an abstraction is valid if we can turn any abstract solution into a solution in the real world; an abstraction is useful if it makes the problem easier; the best abstraction maximizes usefulness while maintaining validity).\n\nA sequence of actions forms a **path**, and a **solution** is a path from the initial state to a goal state. We assume action costs are additive (total cost of path is sum of action costs). An **optimal solution** has the lowest path cost among all solutions.\n\n\n## AIMA Chapter 3.2 Example Problems\n\n### Standardized problems\n(intended to illustrate or exercise various problem-solving methods)\nA **grid-world** problem is a 2D rectangular array of square cells, agents move cell-to-cell (up to all 8 directions), cells can be obstructed or contain objects with arbitrary properties. In a **sokoban puzzle**, the agent's goal is to push boxes scattered about the grid to storage locations (n obstacle cells and b boxes, $n\times n!/(b!(n-b)!)$ states). In a **sliding-tile** puzzle, a number of tiles are arranged in a grid with one or more blank spaces that tiles can move into (e.g. rush hour puzzle, **8-puzzle** 3x3 grid, **15-puzzle** 4x4 grid). Knuth problem with infinite states: integer states, can apply square root, factorial, and floor operations (conjecture: can reach any positive integer).\n\n### Real-world problems\n(problem with practical real-world applications and details, usually with an idiosyncratic formulation)\nThe **route-finding problem** has various practical applications (e.g. car navigation systems, IP routing, operations planning, airline travel planning). A **touring problem** describes a set of locations that must be visited (rather than a single goal from a set of possible goals). The **traveling salesperson problem (TSP)** is a touring problem in which every city on a map must be visited (minimizing cost of journey). A **VLSI layout** problem requires positioning components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield (usually split into **cell layout** and **channel routing**). **Robot navigation** is a generalization of the route-finding problem (continuous space, many-dimensional, partially observable, errors in sensor readings and motor controls, multi-agent). **Automatic assembly sequencing** of complex objects (like manufacturing). This includes **protein design** / protein folding.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nA **search algorithm** takes a search problem as input and returns a solution, or an indication of failure. We consider algorithms that explore a **search tree** over the state-space graph, trying to find a path that reaches a goal node (each node in the search tree corresponds to a state in the state space, edges correspond to actions, the root corresponds to the initial state). We **expand** a node in the search tree by **generating** new nodes for each available action applied to the current state. We always have a **frontier** of nodes that we haven't yet expanded (separating an interior region of the state-space graph where every state has been expanded, and an exterior region of states that have not yet been reached: the **separation property** of graph search). Any state that has a node in the search tree has been **reached**.\n\nIn **best-first search**, we expand the node $n$ on the frontier with the minimum value of some **evaluation function**, $f(n)$.\n\nA **node** in a search tree is comprised of four components: **state** (element of state-space), **parent**: the node in the search tree that generated this node, **action**: the action applied to the parent's state to generate this node, and **path cost**: the total cost of the path from the initial state to this node ($g(n)$). \n\nWe should store the nodes on the frontier using a **queue** of some kind (need to check if is empty, pop, peek, add). A **priority queue** \npops the node with the minimum cost according to some function. A **FIFO queue** is a traditional queue (BFS). A **LIFO queue** is a stack (DFS). The visited states can be stored in a lookup table (e.g. hash set).\n\nA **repeated state** in the search tree occurs multiple times on a path (can be caused by a cycle in the state-space graph). A **redundant path** is a less optimal version of some other path. Can store visited states and eliminate them, allow them, or check for cycles but not redundant paths in general (follow parent pointers for a certain number of steps to see if you've been here before). A search algorithm is called a **graph search** if it checks for redundant paths, and a **tree-like search** if it does not check.\n\nWe can evaluate search algorithms by **completeness** (is the algorithm guaranteed to find a solution when there is one, and correctly report failure when there is not; a complete algorithm must be **systematic** in exploring an infinite state space), **cost optimality** (does the algorithm find a solution with the lowest path cost of all solutions), **time complexity** (how long does it take to find a solution), and **space complexity** (how much memory is needed to perform the search). Time and space complexity are measured relative to $d$ (the **depth** or number of actions in an optimal solution), $m$ (the maximum number of actions in any path), and $b$ (the **branching factor** or number of successors of any node that should be considered).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nAn **uninformed search algorithm** is given no clue about how close a state is to the goal(s).\n\nWhen all actions have the same cost, a good strategy is **breadth-first** search; root node expanded first, then level 1 nodes expanded, then level 2 nodes, etc. It is systematic and therefore complete. Implemented with a FIFO queue. Does an **early goal test** (checking if a node is solution as soon as it is generated) rather than a **late goal test** (waiting until a node is popped off the queue to check if it is a solution). BFS is cost-optimal for problems where all actions have the same cost because it explores iteratively by the depth of a node (shortest path to that state). Both time and space complexity are $O(b^d)$.\n\nWhen actions have different costs, Dijkstra's algorithm (**uniform-cost search**) is a good choice. It expands nodes from the frontier with minimum $g(n)$ (cumulative path cost). Implemented with a priority queue. Spreads out in waves of roughly uniform path-cost. It is cost-optimal, systematic, and complete. The time and space complexity of uniform-cost search is $O(b^{1+floor(C^*/\\epsilon)})$, where $C^*$ is the cost of the optimal solution and $\\epsilon$ is a lower bound on the cost of each action. UCS can explore large trees of actions with low costs before exploring paths involving a high-cost and possibly useful action.\n\nDepth-first search expands the deepest node in the frontier first. Implemented with a stack. Usually implemented as a tree-like search (doesn't check for redundant paths). DFS is not cost-optimal (returns the first solution it finds, even if it isn't the cheapest). Not complete since it can get stuck in an infinite path, or cycles (some implementations check for cycles). Highly memory-efficient. Time complexity O(b^m), space complexity $O(bm)$. Variant called **backtracking search** uses $O(m)$ memory by generating only one successor at a time by modifying the current state description (and undoing the modification after recursive call).\n\n**Depth-limited search** is a variant of depth-first search in which we apply a depth limit $l$ and pretend that nodes at depth $l$ have no successors. Time complexity $O(b^l)$, space complexity $O(bl)$. Not complete or optimal unless $l=d$. Can check for cycles by following parent pointers.\n\n**Iterative deepening search** does depth-limited search with $l=0,1,2,...$ until it finds a solution. IDS is complete. IDS is optimal if all actions have the same cost. IDS takes $O(b^d)$ time and $O(bd)$ space ($\\sum_{l=0}^d O(b^l) = O(b^d)$).\n\nCould try BFS until almost all available memory is consumed, then run IDS from all the nodes in the frontier.\n\n**Bidirectional search** starts from initial state node and goal node, running search from each (2 frontiers, 2 visited sets), have a solution when the 2 frontiers collide. Reduces BFS to $O(b^{(d/2)})$ time/space and uniform-cost search to $O(b^{1+floor(C^*/\\epsilon)/2})$ time/space.\n\n\n## Module 3 Lecture Notes\n\nCovered by textbook.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Goal formulation** - recognize goal state (limit objectives and hence actions to be considered)\n* **Problem formulation** - devise a description of states and actions necessary to reach the goal\n* **Search** - simulate actions until you find a solution (sequence of actions leading to a goal)\n* **Solution** - a path from the initial state to the goal state\n* **Execution** - execute actions in solution one-by-one\n* **Open-loop system** - The agent follows a fixed sequence of actions, ignoring percepts.\n* **Closed-loop system** - The agent monitors the percepts and applies a branching strategy based on percepts.\n* **Abstraction** - removing detail from representation\n* **Valid abstraction** - we can turn any abstract solution into a solution in the real world\n* **Useful abstraction** - the abstract problem is easier to solve than the real-world problem\n* **Path** - a sequence of actions\n* **Path cost** - the sum of the action cost function applied to each action in the sequence\n* **Optimal solution** - a solution with minimal path cost\n* **Standardized problem** - intended to illustrate or exercise various problem-solving methods\n* **Real-world problem** - problem with practical real-world applications and details, usually with an idiosyncratic formulation\n* **Egocentric actions** - actions with directions defined relative to the agent's perspective\n* **Absolute actions** - actions with directions defined by global dimensions\n* **Search algorithm** - takes a search problem as input and returns a solution, or an indication of failure\n* **Frontier** - the set of nodes in the search tree that haven't yet been expanded\n* **Reached** - a state is reached if it has a node in the search tree\n* **Best-first search** - we expand the node $n$ on the frontier with the minimum value of some **evaluation function**, $f(n)$\n* **Repeated state** - a state that occurs multiple times on a path in the search tree\n* **Redundant path** - a less optimal version of some other path\n* **Graph search** - checks for redundant paths\n* **Tree search** - does not check for redundant paths\n* **Early goal test** - checking if a node is solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue to check if it is a solution\n* **Completeness** - is the algorithm guaranteed to find a solution when there is one, and correctly report failure when there is not\n* **Cost optimality** - does the algorithm find a solution with the lowest path cost of all solutions\n* **Time complexity** - how long does it take to find a solution\n* **Space complexity** - how much memory is needed to perform the search)\n* **Uninformed search algorithm** - is given no clue about how close a state is to the goal(s)\n* **Diameter (of a graph)** - the maximum path length\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",
        "**Greedy best-first search** expands the node on the frontier with the lowest $h(n)$ value (evaluation function $f(n) = h(n)$). Not optimal because \\\n",
        "it can be misled by heuristic function being too optimistic about certain nodes. Complete in finite state spaces but not in infinite ones. Worst case \\\n",
        "time/space complexity is O(states + actions) but a good heuristic function can attain $O(bm)$ time/space.\n",
        "\n",
        "**A* search** is the most common informed search algorithm. It uses the evaluation function $f(n) = g(n) + h(n)$ (where $g(n)$ is the path cost from \\\n",
        "the initial state to node $n$). Thus $f(n)$ represents the estimated cost of the shortest path from the initial state that continues from $n$ to a goal. \\\n",
        "A* is complete. A* is optimal if the heuristic is **admissible** (never overestimates the cost to reach a goal, i.e. optimistic), or if even one cost-optimal path \\\n",
        "exists on which $h(n)$ is admissible for all nodes $n$ on the path, or if $h(n)$ never overestimates by more than $C_2-C^*$ (where $C_2$ is the second-best cost). \\\n",
        "If the heuristic is **consistent** ($h(n) \\leq c(n, a, n') + h(n')$, where $c(n, a, n')$ is the cost of taking an action from $n$ to $n'$, i.e. triangle inequality), \\\n",
        "the first time we reach a state it will be on an optimal path (never have to re-add a state to the frontier). A* expands in increasing **contours** of $f$-cost. \\\n",
        "As you extend a path, the $g$ costs are monotonically increasing. The $f$ costs are monotonically increasing iff $h$ is consistent. A* expands all **surely expanded nodes** \\\n",
        "(surely reached nodes with $f(n) < C^*$), might expand nodes on the **goal contour** (where $f(n)=C^*$), and expands no nodes \\\n",
        "with $f(n) > C^*$. A* with a consistent heuristic is **optimally efficient**. A* is efficient since it **prunes** away search tree nodes that are not necessary for finding an optimal solution.\n",
        "\n",
        "A* with inadmissible but accurate heuristic suboptimal but faster / less space. In **weighted A* search** we weight $h$ more heavily: $f(n) = g(n) + W\\cdot h(n)$ for some $W>1$ (will find a solution of cost \\\n",
        "between $C^*$ and $W\\cdot C^*$, but usually close to optimal in practice). Example of **bounded suboptimal search** (find a solution within a constant factor $W$ of the original cost).\n",
        "\n",
        "In **bounded-cost search** we look for solution with cost below some constant $C$. In **unbounded-cost search** we accept any solution as long as we can find it quickly \\\n",
        "(e.g. **speedy search**, greedy best-first with heuristic estimating number of actions remaining to goal).\n",
        "\n",
        "Can save memory by removing states from reached when no longer needed (e.g. use separation property along with prohibition of U-turn actions; actions move out from frontier or onto another frontier state). \\\n",
        "Can also keep **reference counts** of number of times visited, and remove when no more ways to visit.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "For 8-puzzle, good admissible heuristic is **Manhattan distance**, or city-block distance. For shortest path, good admissible heuristic is **straight-line distance**.\n",
        "\n",
        "Can use **effective branching factor** $b^*$ to characterize the quality of a heuristic ($N+1=1+b^*+(b^*)^2+...+(b^*)^d$, i.e. $N=x\\cdot((b^*)^d-1)/(b^*-1)$ \\\n",
        "where $N$ is the number of nodes generated by A* and $d$ is the solution depth). Another characterization: the heuristic reduces the **effective depth** by constant $k_h$ compared \\\n",
        "to true depth; total search cost is $O(b^{d-k_h})$ compared to $O(b^d)$ for uninformed search.\n",
        "\n",
        "If we have $h_1(n) \\leq h_2(n)$ for all $n$, we say heuristic $h_2$ **dominates** $h_1$; running A* with $h_2$ will never expand more nodes than $h_1$. \n",
        "\n",
        "A problem with fewer restrictions on the actions is called a **relaxed problem** (simplified version of the problem). The state-space graph of the relaxed problem is a supergraph of the original state space \\\n",
        "(removal of restrictions can only add edges). Any solution to the original problem is a solution to the relaxed problem (but the relaxed solution may have better solutions). \\\n",
        "Thus the cost of an optimal solution to the relaxed problem is an admissible heuristic for the original problem. The heuristic also obeys the triangle inequality so it is consistent.\n",
        "\n",
        "Can combine admissible heuristics into a better admissible heuristic by taking max $h(n) \\max(h_1(n),...,h_k(n))$ (consistent if all $h_i$ are consistent).\n",
        "\n",
        "Can generate admissible heuristic from a **subproblem** (fewer states). Can store subproblem solutions in **pattern database** (generated using DP) and look up subproblem for heuristic. \\\n",
        "Can add together heuristic values from **disjoint pattern database** (solutions to disjoint subproblems) for admissible heuristic. \n",
        "\n",
        "To speed up shortest path queries, can **precompute** optimal path costs between landmark states. Inadmissible (but good) heuristic: \\\n",
        "take min of optimal path cost to landmark and then to goal node for each landmark. Similarly can use admissible/efficient **differential heuristic** $h_{DH} = \\max_{L\\in Landmarks}|C^*(n, L)-C^*(goal, L)|$. Should \\\n",
        "spread landmarks out (greedy pick farthest node from landmark at each step) and coincide with popular states in queries. For DH, good to spread landmarks around perimeter (find the centroid, \\\n",
        "arrange $k$ fans around the centroid, select vertex farthest from center in each).\n",
        "\n",
        "Other optimization: add **shortcut** edges in graph corresponding to an optimal multi-action path between states.\n",
        "\n",
        "Can learn to search better with **metalevel state space** (states capture internal computational state of a searching program) as opposed to **object-level state space** (normal state space). \\\n",
        "Learn what program steps are unpromising, minimize total cost (trade off computational expense and path cost).\n",
        "\n",
        "Can learn a good heuristic from experience (using ML techniques). May work better with **features** of a state, relevant to predicting heuristic value.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "**Heuristic knowledge** is useful, but not necessarily correct. **Heuristic algorithms** use heuristic knowledge to solve a problem. \\\n",
        "A **heuristic function** $h(n)$ estimates distance from $n$ to goal.\n",
        "\n",
        "**Oracle heuristic** $h^*(n)$ is true distance from $n$ to goal (dominates all other admissible heuristics). $h_{teleportation}(n) = 0$ dominated by all heuristics.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "  \"informed search strategy\" : \"uses domain-specific hints about the location of goals to find solutions more efficiently\",\n",
        "  \"heuristic function\" : \"the estimated cost of the cheapest path from the state at node $n$ to a goal state\",\n",
        "  \"admissible heuristic\" : \"a heuristic that never overestimates the cost to reach a goal, i.e. an optimistic heuristic\",\n",
        "  \"consistent heuristic\" : \"$h(n) \\leq c(n, a, n') + h(n')$, i.e. triangle inequality\",\n",
        "  \"A* surely expanded nodes\" : \"surely reached nodes with $f(n) < C^*$\",\n",
        "  \"goal contour\" : \"nodes where $f(n) = C^*$\",\n",
        "  \"optimally efficient\" : \"any search algorithm with same heuristic would have to expand A*'s surely expanded nodes\",\n",
        "  \"satisficing solutions\" : \"not optimal, but 'good enough'\",\n",
        "  \"beam search\" : \"only keep the $k$ nodes with the best $f$-scores, or keep nodes within $\\delta$ of best $f$-score\",\n",
        "  \"iterative deepening A* search\" : \"only keeps nodes with $f$-cost below cutoff (cutoff value is smallest $f$-cost of nodes that exceeded cutoff in previous iteration)\",\n",
        "  \"recursive best-first search\" : \"DFS but stops digging if $f$-value exceeds the $f$-value of the best alternative path available from an ancestor\",\n",
        "  \"backed-up value (RBFS)\" : \"the best $f$-value of a node's children (replaces $f$-value of parent as RBFS unwinds)\",\n",
        "  \"simplified memory-bounded A*\" : \"runs A* until OOM, then backs-up $f$-value of worst leaf to its parent (regenerates only when all other paths worse)\",\n",
        "  \"effective branching factor $b^*$\" : \"$N+1=1+b^*+(b^*)^2+...+(b^*)^d$, i.e. $N=x\\cdot((b^*)^d-1)/(b^*-1)$ where $N$ is number of nodes generated by A* and $d$ is solution depth\",\n",
        "  \"heuristic domination\" : \"if we have $h_1(n) \\leq h_2(n)$ for all $n$, we say heuristic $h_2$ **dominates** $h_1$\",\n",
        "  \"relaxed problem\" : \"problem with fewer restrictions, i.e. more edges in state-space graph\",\n",
        "  \"subproblem\" : \"problem with fewer states\",\n",
        "  \"differential heuristic\" : \"$h_{DH} = \\max_{L\\in Landmarks}|C^*(n, L) - C^*(goal, L)|$\",\n",
        "  \"shortcut edges\" : \"edges in graph corresponding to an optimal multi-action path between states\",\n",
        "  \"metalevel state space\" : \"states capture internal computational state of a searching program\",\n",
        "  \"heuristic\": \"A rule of thumb, simplification, or educated guess that reduces/limits the search for solutions in difficult/poorly understood domains\",\n",
        "  \"Oracle heuristic\": \"$h^*(n)$ is true distance from $n$ to goal\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fd0a8488-26ce-4ca7-bb6f-3ee347c0d881"
      },
      "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": 21,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n**Greedy best-first search** expands the node on the frontier with the lowest $h(n)$ value (evaluation function $f(n) = h(n)$). Not optimal because it can be misled by heuristic function being too optimistic about certain nodes. Complete in finite state spaces but not in infinite ones. Worst case time/space complexity is O(states + actions) but a good heuristic function can attain $O(bm)$ time/space.\n\n**A* search** is the most common informed search algorithm. It uses the evaluation function $f(n) = g(n) + h(n)$ (where $g(n)$ is the path cost from the initial state to node $n$). Thus $f(n)$ represents the estimated cost of the shortest path from the initial state that continues from $n$ to a goal. A* is complete. A* is optimal if the heuristic is **admissible** (never overestimates the cost to reach a goal, i.e. optimistic), or if even one cost-optimal path exists on which $h(n)$ is admissible for all nodes $n$ on the path, or if $h(n)$ never overestimates by more than $C_2-C^*$ (where $C_2$ is the second-best cost). If the heuristic is **consistent** ($h(n) \\leq c(n, a, n') + h(n')$, where $c(n, a, n')$ is the cost of taking an action from $n$ to $n'$, i.e. triangle inequality), the first time we reach a state it will be on an optimal path (never have to re-add a state to the frontier). A* expands in increasing **contours** of $f$-cost. As you extend a path, the $g$ costs are monotonically increasing. The $f$ costs are monotonically increasing iff $h$ is consistent. A* expands all **surely expanded nodes** (surely reached nodes with $f(n) < C^*$), might expand nodes on the **goal contour** (where $f(n)=C^*$), and expands no nodes with $f(n) > C^*$. A* with a consistent heuristic is **optimally efficient**. A* is efficient since it **prunes** away search tree nodes that are not necessary for finding an optimal solution.\n\nA* with inadmissible but accurate heuristic suboptimal but faster / less space. In **weighted A* search** we weight $h$ more heavily: $f(n) = g(n) + W\\cdot h(n)$ for some $W>1$ (will find a solution of cost between $C^*$ and $W\\cdot C^*$, but usually close to optimal in practice). Example of **bounded suboptimal search** (find a solution within a constant factor $W$ of the original cost).\n\nIn **bounded-cost search** we look for solution with cost below some constant $C$. In **unbounded-cost search** we accept any solution as long as we can find it quickly (e.g. **speedy search**, greedy best-first with heuristic estimating number of actions remaining to goal).\n\nCan save memory by removing states from reached when no longer needed (e.g. use separation property along with prohibition of U-turn actions; actions move out from frontier or onto another frontier state). Can also keep **reference counts** of number of times visited, and remove when no more ways to visit.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nFor 8-puzzle, good admissible heuristic is **Manhattan distance**, or city-block distance. For shortest path, good admissible heuristic is **straight-line distance**.\n\nCan use **effective branching factor** $b^*$ to characterize the quality of a heuristic ($N+1=1+b^*+(b^*)^2+...+(b^*)^d$, i.e. $N=x\\cdot((b^*)^d-1)/(b^*-1)$ where $N$ is the number of nodes generated by A* and $d$ is the solution depth). Another characterization: the heuristic reduces the **effective depth** by constant $k_h$ compared to true depth; total search cost is $O(b^{d-k_h})$ compared to $O(b^d)$ for uninformed search.\n\nIf we have $h_1(n) \\leq h_2(n)$ for all $n$, we say heuristic $h_2$ **dominates** $h_1$; running A* with $h_2$ will never expand more nodes than $h_1$. \n\nA problem with fewer restrictions on the actions is called a **relaxed problem** (simplified version of the problem). The state-space graph of the relaxed problem is a supergraph of the original state space (removal of restrictions can only add edges). Any solution to the original problem is a solution to the relaxed problem (but the relaxed solution may have better solutions). Thus the cost of an optimal solution to the relaxed problem is an admissible heuristic for the original problem. The heuristic also obeys the triangle inequality so it is consistent.\n\nCan combine admissible heuristics into a better admissible heuristic by taking max $h(n) \\max(h_1(n),...,h_k(n))$ (consistent if all $h_i$ are consistent).\n\nCan generate admissible heuristic from a **subproblem** (fewer states). Can store subproblem solutions in **pattern database** (generated using DP) and look up subproblem for heuristic. Can add together heuristic values from **disjoint pattern database** (solutions to disjoint subproblems) for admissible heuristic. \n\nTo speed up shortest path queries, can **precompute** optimal path costs between landmark states. Inadmissible (but good) heuristic: take min of optimal path cost to landmark and then to goal node for each landmark. Similarly can use admissible/efficient **differential heuristic** $h_{DH} = \\max_{L\\in Landmarks}|C^*(n, L)-C^*(goal, L)|$. Should spread landmarks out (greedy pick farthest node from landmark at each step) and coincide with popular states in queries. For DH, good to spread landmarks around perimeter (find the centroid, arrange $k$ fans around the centroid, select vertex farthest from center in each).\n\nOther optimization: add **shortcut** edges in graph corresponding to an optimal multi-action path between states.\n\nCan learn to search better with **metalevel state space** (states capture internal computational state of a searching program) as opposed to **object-level state space** (normal state space). Learn what program steps are unpromising, minimize total cost (trade off computational expense and path cost).\n\nCan learn a good heuristic from experience (using ML techniques). May work better with **features** of a state, relevant to predicting heuristic value.\n\n\n## Module 4 Lecture Notes\n\n**Heuristic knowledge** is useful, but not necessarily correct. **Heuristic algorithms** use heuristic knowledge to solve a problem. A **heuristic function** $h(n)$ estimates distance from $n$ to goal.\n\n**Oracle heuristic** $h^*(n)$ is true distance from $n$ to goal (dominates all other admissible heuristics). $h_{teleportation}(n) = 0$ dominated by all heuristics.\n\n\n## Module 4 Definitions\n* **Informed search strategy** - uses domain-specific hints about the location of goals to find solutions more efficiently\n* **Heuristic function** - the estimated cost of the cheapest path from the state at node $n$ to a goal state\n* **Admissible heuristic** - a heuristic that never overestimates the cost to reach a goal, i.e. an optimistic heuristic\n* **Consistent heuristic** - $h(n) \\leq c(n, a, n') + h(n')$, i.e. triangle inequality\n* **A* surely expanded nodes** - surely reached nodes with $f(n) < C^*$\n* **Goal contour** - nodes where $f(n) = C^*$\n* **Optimally efficient** - any search algorithm with same heuristic would have to expand A*'s surely expanded nodes\n* **Satisficing solutions** - not optimal, but 'good enough'\n* **Beam search** - only keep the $k$ nodes with the best $f$-scores, or keep nodes within $\\delta$ of best $f$-score\n* **Iterative deepening a* search** - only keeps nodes with $f$-cost below cutoff (cutoff value is smallest $f$-cost of nodes that exceeded cutoff in previous iteration)\n* **Recursive best-first search** - DFS but stops digging if $f$-value exceeds the $f$-value of the best alternative path available from an ancestor\n* **Backed-up value (rbfs)** - the best $f$-value of a node's children (replaces $f$-value of parent as RBFS unwinds)\n* **Simplified memory-bounded a*** - runs A* until OOM, then backs-up $f$-value of worst leaf to its parent (regenerates only when all other paths worse)\n* **Effective branching factor $b^*$** - $N+1=1+b^*+(b^*)^2+...+(b^*)^d$, i.e. $N=x\\cdot((b^*)^d-1)/(b^*-1)$ where $N$ is number of nodes generated by A* and $d$ is solution depth\n* **Heuristic domination** - if we have $h_1(n) \\leq h_2(n)$ for all $n$, we say heuristic $h_2$ **dominates** $h_1$\n* **Relaxed problem** - problem with fewer restrictions, i.e. more edges in state-space graph\n* **Subproblem** - problem with fewer states\n* **Differential heuristic** - $h_{DH} = \\max_{L\\in Landmarks}|C^*(n, L) - C^*(goal, L)|$\n* **Shortcut edges** - edges in graph corresponding to an optimal multi-action path between states\n* **Metalevel state space** - states capture internal computational state of a searching program\n* **Heuristic** - A rule of thumb, simplification, or educated guess that reduces/limits the search for solutions in difficult/poorly understood domains\n* **Oracle heuristic** - $h^*(n)$ is true distance from $n$ to goal\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",
        "Multi-agent environments: consider in aggregate as an **economy**, consider adversarial agents as nondeterministic part of the environment, or \\\n",
        "model the adversarial agents using adversarial game-tree search.\n",
        "\n",
        "Convention: two players max and min, max moves first.\n",
        "\n",
        "**Game** has the following elements: an **initial state** $S_0$, $ToMove(S)$ (whose player's turn it is to move in state $s$), $Actions(s)$ (set of legal moves in state $s$), \\\n",
        "**transition model** $Result(s, a)$ (state resulting from taking action $a$ in state $s$), **terminal test** $IsTerminal(s)$ (indicates if game is over; states where the game has ended \\\n",
        "are called **terminal states**), a **utility function** $Utility(s, p)$ (also called objective function or payoff function), defining the numeric value to player $p$ when the game ends in terminal state $s$. \\\n",
        "Initial state, actions function, and transition model define the **state space graph**. We can superimpose a **search tree** over part of the graph when determining a move. We define the complete \\\n",
        "**game tree** as a search tree that includes every possible sequence of moves (may be infinite).\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Strategy must be a conditional plan (contingent strategy specifying a response to each of other player's possible moves).\n",
        "\n",
        "**Minimax search** can be used to solve perfect-information, zero-sum games. The **minimax value** $Minimax(s)$ is the utility for Max of being in state $s$, assuming both players play optimally. \\\n",
        "The minimax value of a terminal state is just its utility for Max. Otherwise, \\\n",
        "$Minimax(s) = \\max_{a\\in Actions(s)}Minimax(Result(s,a)) if ToMove(s) is Max, else \\min_{a\\in Actions(s)}Minimax(Result(s,a))$. The **minimax decision** at a state is the choice at that state that \\\n",
        "leads to the state with the highest minimax value. If playing suboptimal opponent, minimax move might not be optimal (high-risk high-reward move might be better). \\\n",
        "Minimax algorithm explores tree like DFS, **backing up** the minimax values as the recursion unwinds. \n",
        "\n",
        "In 3+ player games, each node has a vector of utility values (payoff values in \\\n",
        "terminal state, otherwise backed-up value at node $n$ is the utility vector of the successor state with the highest value for the player choosing at $n$). \\\n",
        "3+ player games can involve **alliances** and collaboration (formal or informal). Collaboration can also emerge in non-zero-sum 2-player games.\n",
        "\n",
        "**Alpha-beta pruning** improves efficiency of minimax search by ignoring sections of the tree that make no difference to the outcome. \\\n",
        "Let $alpha$ represent the value of the best (highest-value) choice we have found so far at any point along the path for Max (think \"at least\"). \\\n",
        "Min should stop Minimax search from a node if it knows it can guarantee a score of less than $alpha$ (Max won't choose this node). \\\n",
        "Let $\\beta$ represent the value of the best (lowest-value) choice we have found so far at any point along the path for Min (think \"at most\"). \\\n",
        "Max should stop Minimax search from a node if it knows it can guarantee a score of more than $\\beta$ (Min won't choose this node).\n",
        "\n",
        "Effectiveness of alpha-beta pruning depends on order in which states are examined (want to examine best moves first). Done perfectly, alpha-beta only examines $O(b^{m/2})$ nodes. \\\n",
        "The best moves are called **killer moves**, and trying them first is the **killer move heuristic**. With random move ordering, it examines roughly $O(b^{3m/4})$ nodes. \\\n",
        "Can do **iterative deepening** and rank moves at each node according to score at previous depth of analysis.\n",
        "\n",
        "In game-tree search, repeated states can occur because of **transpositions** (different permutations of move sequences that end up in the same position); can be addressed with a \\\n",
        "**transposition table** that caches the heuristic value of states.\n",
        "\n",
        "Two strategies for minimax in intractably large game trees: **Type A strategy** considers all moves to certain depth and then uses heuristic evaluation function to estimate utility \\\n",
        "(considers wide but shallow portion of the tree). A **Type B strategy** ignores moves that look bad and follows promising lines \"as far as possible\" (explores deep but narrow portion).\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "At depth limit, can replace utility function with **heuristic evaluation function** to estimate expected utility of state (must be between min and max utility). \\\n",
        "Can replace terminal test with **cutoff test**, which returns true for \\\n",
        "terminal states, and otherwise decides how to cut off the search (e.g. after max depth). Most evaluation functions work based on various **features** of the state. \\\n",
        "Features can define **categories** or **equivalence classes** of states (groups of states with same value for all features). Evaluation function can estimate proportion of \\\n",
        "outcomes from an equivalence class that wins, loses, and draws. In practice this requires consideration of too many equivalence classes. Alternatively just compute \\\n",
        "mathematical function from features (i.e. **material value** in chess, a **weighted linear function** of the features). Other function might be **nonlinear combination** of features \\\n",
        "(e.g. bishop pair more valuable than twice value of single bishop, bishop worth more in endgame, etc). Evaluation function can be estimated with ML techniques.\n",
        "\n",
        "The evaluation function should only be applied to **quiescent** positions (ones where there is no pending move that would wildly swing the evaluation). Extra **quiescent search** sometimes \\\n",
        "restricted to just considering certain types of moves (like captures in chess) that will resolve the quiescence of the position.\n",
        "\n",
        "The **horizon effect** arises when the program faces an opponent's move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of \\\n",
        "delaying tactics (so the search algorithm will think those delaying tactics are optimal play, when in fact they may be suboptimal moves that just delay the inevitable). Can mitigate this \\\n",
        "by allowing **singular extensions** to continue search with \"clearly better\" moves.\n",
        "\n",
        "**Forward pruning** prunes moves that appear to be poor (but may possibly be good); saves computation time at risk of making an error (type B strategy).\n",
        "\n",
        "**Beam search** considers only a \"beam\" of the $k$ best moves (dangerous like forward pruning bc you might prune away an underrated move).\n",
        "\n",
        "**ProbCut** (probabilistic cut) algorithm is forward pruning with statistics gained from prior experience to reduce chance of pruning best move. Prunes nodes that are \\\n",
        "probably outside of $(alpha,beta)$ window in addition to those that are definitely outside.\n",
        "\n",
        "**late move reduction** assumes move ordering has been done well, so reduces depth for probably worse moves.\n",
        "\n",
        "Can use **table lookup** in portions of the game that can be precomputed (opening or endgame). Build endgame tablebases with **retrograde** minimax search (apply reverse moves starting from terminal states).\n",
        "\"\"\"\n",
        "chapter5_4 = \"\"\"\n",
        "Some games with very high branching factors and no good heuristic evaluation functions (like Go) are not fit for alpha-beta minimax. Better strategy is **Monte Carlo tree search (MCTS)**. \\\n",
        "Value of a state is estimated as the average utility over a number of **simulations** (also called **playout** or **rollout**) of complete games starting from the state. \\\n",
        "Use a **playout policy** that biases the moves towards good ones. Can be learned using ML techniques like neural networks.\n",
        "\n",
        "In **pure Monte Carlo search** you do $N$ simulations starting from the current state and chose move with highest win percentage. Better strategy is to use **selection policy** that focuses resources \\\n",
        "on the important parts of the game tree. Balances **exploration** of states that have had few playouts and **exploitation** of states that have done well in past playouts.\n",
        "\n",
        "MCTS follows four steps: **selection** (choose a move guided by selection policy leading to successor node, repeatedly, until you reach terminal state), **expansion** (grow search tree by \\\n",
        "generating new child of selected node), **simulation** (perform a playout from the newly generated child node, choosing moves for both players according to the playout policy; \\\n",
        "moves not recorded in the search tree), and **back-propagation** (use the result of the simulation to update all search tree nodes going up to the root). Repeat these steps for a set number \\\n",
        "of iterations or until allotted time has expired, then return move with highest number of playouts.\n",
        "\n",
        "Effective selection policy: \"upper confidence bounds applied to trees\" (**UCT**), ranks each move based on upper confidence bound formula (**UCB1**). For a node $n$, the formula is \\\n",
        "$UCB1(n)=\\frac{U(n)}{N(n)}+C\\cdot\\sqrt{\\log(N(Parent(n)))/N(n)}$ where $U(n)$ is total utility of all playouts that went through node $n$, $N(n)$ is number of playouts through node $n$, \\\n",
        "$Parent(n)$ is the parent node of $n$ in the tree. $\\frac{U(n)}{N(n)}$ is the expoitation term, square root is exploration term, $C$ is a constant that balances exploration and exploitation \\\n",
        "($\\sqrt{2}$ is good theoretically, usually $C$ is tuned in practice to achieve optimal results).\n",
        "\n",
        "Can use MCTS with evaluation function (terminate single simulation using cutoff test and then apply evaluation function; **early playout termination**) in games that can have sequences \\\n",
        "of very many moves in some situations.\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "**Stochastic games** include random elements. Game tree includes **chance nodes** in addition to Max and Min nodes. Can only compute **expected value** of a position. We use \\\n",
        "the **expectiminimax value** (generalization of minimax value). Terminal nodes and deterministic nodes work as with minimax, and chance nodes compute expected minimax value of successor. \\\n",
        "Now evaluation values matter, not just ordering. Evaluation function must return values that are a positive linear transformation of the state's expected value. \\\n",
        "Usually much harder to get deep search due to extra branching introduced by chance nodes.\n",
        "\n",
        "Can apply alpha-beta pruning: same logic for Min and Max nodes, and in chance node consider partial weighted averages as you explore children to return early in some situations.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Situation: agent assigns probability $P(s)$ to each possible current state $s$, transition model given by $P(s'\\mid s, a)$ (probability that action $a$ in state $s$ reaches $s'$), \\\n",
        "$P(Result(a)=s'):=\\sum_{s}P(s)P(s\\mid s,a)$. Decision theory deals with choosing actions based on desirability of immediate outcomes (episodic environment). Preferences captured by \\\n",
        "**utility function** $U(s)$ which values a state. The **expected utility** of an action given the evidence $EU(a) := \\sum_{s'}P(Result(a)=s')U(s')$. The principle of **maximum expected utility (MEU)** \\\n",
        "says that a rational agent should act to maximize expected utility; $action=\\argmax_a EU(a)$. MEU principle formalizes goal, but doesn't operationalize the advice. MEU maximizes expected performance measure \\\n",
        "if the utility function correctly reflects the performance measure.\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Can think of set of outcomes for each action as a **lottery** $L$ with possible outcomes $S_1,...,S_n$ (could be atomic states or other lotteries) and probabilities \\\n",
        "$p_1,...,p_n$ (written as $L=[p_1,S_1;p_2,S_2;...;p_n,S_n]$).\n",
        "\n",
        "**Axioms of utility theory**: **observability** (given two lotteries, a rational agent must prefer one or rate them \\\n",
        "as equally preferrable), **transitivity** (if prefer lottery A to B and B to C, prefers A to C), **continuity** (if lottery B is between A and C in preference, there is some probability $p$ \\\n",
        "for which the agent will be indifferent between getting B for sure and the lottery that yields A with probability $p$ and C with probability $1-p$), **substitutability** (if an agent is indifferent \\\n",
        "between A and B, it is indifferent between two lotteries that are the same except B is substituted for A in one), **monotonicity** (given two lotteries with same two possible outcomes A and B, \\\n",
        "if agent prefers A to B then agent must prefer lottery that has a higher probability for A), **decomposability** (compound lotteries can be reduced to simpler ones using laws of probability). \n",
        "\n",
        "Axioms of utility theory have the following consequences: **existence of utility function** (there exists a utility function $U$ such that $U(A)>U(B)$ iff A is preferred to B and $U(A)=U(B)$ iff \\\n",
        "agent is indifferent between A and B), **expected utility of a lottery** ($U([p_1,S_1;...;p_n,S_n])=\\sum_i p_i U(S_i)$), and the MEU principle.\n",
        "\n",
        "Agent's behavior unchanged if utility function transformed according to $U'(S) = aU(S)+b$ with $a > 0$.\n",
        "\n",
        "In a deterministic environment agent only needs preference ranking on states (**value function** or **ordinal utility function**). \n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Determining an agent's utility function is called **preference elicitation** (present choices and use observed preferences to determine underlying utility function).\n",
        "\n",
        "Typically we fix worst outcome at $u_{bot}$ and best outcome at $u_{top}$ (**normalized utilities** use $u_{bot}=0, u_{top}=1$). Can assess utility of prize $S$ by asking agent to \\\n",
        "choose between $S$ and a **standard lottery** $[p,u_{top}; (1-p),u_{bot}]$ (binary search with $p$ to find utility of $S$).\n",
        "\n",
        "Govt agencies use **value of a statistical life**. A **micromort** is value of a 1-in-million chance of death. Another measure is quality-adjusted life-year (**QALY**).\n",
        "\n",
        "Money may or may not work as an accurate utility function (could have **monotonic preference** but violate characteristics of utility function in lotteries). \\\n",
        "Can compute **expected monetary value** (EMV) of a lottery. Utility function is often roughly logarithm of money (diminishing marginal utility). \\\n",
        "Diminishing marginal utility equivalent to **risk aversion** (utility of lottery less than EMV), increasing marginal utility equivalent to **risk seeking**, linear equivalent to **risk neutral**. \\\n",
        "The value an agent will accept in lieu of a lottery is called the **certainty equivalent** of the lottery. Difference between EMV and certainty equivalent is called the **insurance premium** \\\n",
        "(risk aversion basis for insurance industry). \\\n",
        "\n",
        "Agent may have to work with estimate $\\hat{EU}(a)$ of true EU function due to practical limitations. We assume that the estimates are **unbiased** ($E(\\hat{EU}(a)-EU(a))=0$). Still, \\\n",
        "expected utility of best choice tends to be an overestimate (**optimizer's curse**), assuming gaussian EU errors. Can be avoided with a Bayesian approach that uses a model $P(\\hat{EU}\\mid EU)$ of the error \\\n",
        "in the utility estimates. Can treat utility estimate as evidence and compute the posterior using Bayes' rule.\n",
        "\n",
        "Decision theory is a **normative theory** (describes how a rational agent should act). A **descriptive theory** describes how actual agents (e.g. humans) act. Humans are predictibly irrational \\\n",
        "(e.g. **certainty effect**: people attracted to certain gains, **ambiguity aversion**, **framing effect**: wording of problem can influence decision, **anchoring effect**: people prefer making \\\n",
        "relative utility decisions over absolute ones).\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Objectivist/frequentist interpretation of probability: averages over repeated experiments.\n",
        "\n",
        "Subjectivist / Bayesian interpretation of probability: degrees of belief about unobserved variables.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "  \"perfect information\" : \"synonym for fully observable\",\n",
        "  \"zero-sum\" : \"all agents' utilities sum to 0 in any outcome\",\n",
        "  \"move\" : \"synonym for action (or in some contexts, an action by each player)\",\n",
        "  \"ply\": \"a single action taken by a single player\",\n",
        "  \"position\" : \"synonym for state\",\n",
        "  \"$Minimax(s)$\" : \"\\max_{a\\in Actions(s)}Minimax(Result(s,a)) if ToMove(s) is Max, else \\min_{a\\in Actions(s)}Minimax(Result(s,a))\",\n",
        "  \"killer moves\" : \"best moves\",\n",
        "  \"killer move heuristic\" : \"a-b pruning heuristic that tries best moves first\",\n",
        "  \"transpositions\" : \"different permutations of move sequences that end up in the same position\",\n",
        "  \"Type A strategy\" : \"considers all moves to certain depth and then uses heuristic evaluation function to estimate utility\",\n",
        "  \"Type B strategy\" : \"ignores moves that look bad and follows promising lines 'as far as possible' (explores deep but narrow portion)\",\n",
        "  \"quiescent position\" : \"position where there is no pending move that would wildly swing the evaluation\",\n",
        "  \"expectiminimax value\" : \"generalization of minimax value to games with chance nodes\",\n",
        "  \"principle of maximum expected utility\" : \"a rational agent should act to maximize expected utility; $action=\\argmax_a EU(a)$\",\n",
        "  \"axioms of utility theory\" : \"observability, transitivity, continuity, substitutability, monotonicity, decomposability\",\n",
        "  \"preference elicitation\" : \"present choices and use observed preferences to determine underlying utility function\",\n",
        "  \"micromort\" : \"value of a 1-in-million chance of death\",\n",
        "  \"certainty equivalent\": \"the value an agent will accept in lieu of a lottery\",\n",
        "  \"insurance premium\" : \"difference between expected monetary value and certainty equivalent\",   \n",
        "  \"unbiased expected utility estimate\" : \"$E(\\hat{EU}(a)-EU(a))=0$\",\n",
        "  \"optimizer's curse\" : \"expected utility of best choice tends to be an overestimate\",\n",
        "  \"normative theory\" : \"describes how a rational agent should act\",\n",
        "  \"descriptive theory\" : \"describes how actual agents (e.g. humans) act\",\n",
        "  \"objectivist/frequentist interpretation\" : \"averages over repeated experiments\",\n",
        "  \"subjectivist / Bayesian interpretation\" : \"degrees of belief about unobserved variables\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1009aafb-dc13-467e-8135-91c363a5cbe2"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nMulti-agent environments: consider in aggregate as an **economy**, consider adversarial agents as nondeterministic part of the environment, or model the adversarial agents using adversarial game-tree search.\n\nConvention: two players max and min, max moves first.\n\n**Game** has the following elements: an **initial state** $S_0$, $ToMove(S)$ (whose player's turn it is to move in state $s$), $Actions(s)$ (set of legal moves in state $s$), **transition model** $Result(s, a)$ (state resulting from taking action $a$ in state $s$), **terminal test** $IsTerminal(s)$ (indicates if game is over; states where the game has ended are called **terminal states**), a **utility function** $Utility(s, p)$ (also called objective function or payoff function), defining the numeric value to player $p$ when the game ends in terminal state $s$. Initial state, actions function, and transition model define the **state space graph**. We can superimpose a **search tree** over part of the graph when determining a move. We define the complete **game tree** as a search tree that includes every possible sequence of moves (may be infinite).\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nStrategy must be a conditional plan (contingent strategy specifying a response to each of other player's possible moves).\n\n**Minimax search** can be used to solve perfect-information, zero-sum games. The **minimax value** $Minimax(s)$ is the utility for Max of being in state $s$, assuming both players play optimally. The minimax value of a terminal state is just its utility for Max. Otherwise, $Minimax(s) = \\max_{a\\in Actions(s)}Minimax(Result(s,a)) if ToMove(s) is Max, else \\min_{a\\in Actions(s)}Minimax(Result(s,a))$. The **minimax decision** at a state is the choice at that state that leads to the state with the highest minimax value. If playing suboptimal opponent, minimax move might not be optimal (high-risk high-reward move might be better). Minimax algorithm explores tree like DFS, **backing up** the minimax values as the recursion unwinds. \n\nIn 3+ player games, each node has a vector of utility values (payoff values in terminal state, otherwise backed-up value at node $n$ is the utility vector of the successor state with the highest value for the player choosing at $n$). 3+ player games can involve **alliances** and collaboration (formal or informal). Collaboration can also emerge in non-zero-sum 2-player games.\n\n**Alpha-beta pruning** improves efficiency of minimax search by ignoring sections of the tree that make no difference to the outcome. Let $alpha$ represent the value of the best (highest-value) choice we have found so far at any point along the path for Max (think \"at least\"). Min should stop Minimax search from a node if it knows it can guarantee a score of less than $alpha$ (Max won't choose this node). Let $\beta$ represent the value of the best (lowest-value) choice we have found so far at any point along the path for Min (think \"at most\"). Max should stop Minimax search from a node if it knows it can guarantee a score of more than $\beta$ (Min won't choose this node).\n\nEffectiveness of alpha-beta pruning depends on order in which states are examined (want to examine best moves first). Done perfectly, alpha-beta only examines $O(b^{m/2})$ nodes. The best moves are called **killer moves**, and trying them first is the **killer move heuristic**. With random move ordering, it examines roughly $O(b^{3m/4})$ nodes. Can do **iterative deepening** and rank moves at each node according to score at previous depth of analysis.\n\nIn game-tree search, repeated states can occur because of **transpositions** (different permutations of move sequences that end up in the same position); can be addressed with a **transposition table** that caches the heuristic value of states.\n\nTwo strategies for minimax in intractably large game trees: **Type A strategy** considers all moves to certain depth and then uses heuristic evaluation function to estimate utility (considers wide but shallow portion of the tree). A **Type B strategy** ignores moves that look bad and follows promising lines \"as far as possible\" (explores deep but narrow portion).\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nAt depth limit, can replace utility function with **heuristic evaluation function** to estimate expected utility of state (must be between min and max utility). Can replace terminal test with **cutoff test**, which returns true for terminal states, and otherwise decides how to cut off the search (e.g. after max depth). Most evaluation functions work based on various **features** of the state. Features can define **categories** or **equivalence classes** of states (groups of states with same value for all features). Evaluation function can estimate proportion of outcomes from an equivalence class that wins, loses, and draws. In practice this requires consideration of too many equivalence classes. Alternatively just compute mathematical function from features (i.e. **material value** in chess, a **weighted linear function** of the features). Other function might be **nonlinear combination** of features (e.g. bishop pair more valuable than twice value of single bishop, bishop worth more in endgame, etc). Evaluation function can be estimated with ML techniques.\n\nThe evaluation function should only be applied to **quiescent** positions (ones where there is no pending move that would wildly swing the evaluation). Extra **quiescent search** sometimes restricted to just considering certain types of moves (like captures in chess) that will resolve the quiescence of the position.\n\nThe **horizon effect** arises when the program faces an opponent's move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics (so the search algorithm will think those delaying tactics are optimal play, when in fact they may be suboptimal moves that just delay the inevitable). Can mitigate this by allowing **singular extensions** to continue search with \"clearly better\" moves.\n\n**Forward pruning** prunes moves that appear to be poor (but may possibly be good); saves computation time at risk of making an error (type B strategy).\n\n**Beam search** considers only a \"beam\" of the $k$ best moves (dangerous like forward pruning bc you might prune away an underrated move).\n\n**ProbCut** (probabilistic cut) algorithm is forward pruning with statistics gained from prior experience to reduce chance of pruning best move. Prunes nodes that are probably outside of $(alpha,beta)$ window in addition to those that are definitely outside.\n\n**late move reduction** assumes move ordering has been done well, so reduces depth for probably worse moves.\n\nCan use **table lookup** in portions of the game that can be precomputed (opening or endgame). Build endgame tablebases with **retrograde** minimax search (apply reverse moves starting from terminal states).\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n**Stochastic games** include random elements. Game tree includes **chance nodes** in addition to Max and Min nodes. Can only compute **expected value** of a position. We use the **expectiminimax value** (generalization of minimax value). Terminal nodes and deterministic nodes work as with minimax, and chance nodes compute expected minimax value of successor. Now evaluation values matter, not just ordering. Evaluation function must return values that are a positive linear transformation of the state's expected value. Usually much harder to get deep search due to extra branching introduced by chance nodes.\n\nCan apply alpha-beta pruning: same logic for Min and Max nodes, and in chance node consider partial weighted averages as you explore children to return early in some situations.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nSituation: agent assigns probability $P(s)$ to each possible current state $s$, transition model given by $P(s'\\mid s, a)$ (probability that action $a$ in state $s$ reaches $s'$), $P(Result(a)=s'):=\\sum_{s}P(s)P(s\\mid s,a)$. Decision theory deals with choosing actions based on desirability of immediate outcomes (episodic environment). Preferences captured by **utility function** $U(s)$ which values a state. The **expected utility** of an action given the evidence $EU(a) := \\sum_{s'}P(Result(a)=s')U(s')$. The principle of **maximum expected utility (MEU)** says that a rational agent should act to maximize expected utility; $action=\u0007rgmax_a EU(a)$. MEU principle formalizes goal, but doesn't operationalize the advice. MEU maximizes expected performance measure if the utility function correctly reflects the performance measure.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nCan think of set of outcomes for each action as a **lottery** $L$ with possible outcomes $S_1,...,S_n$ (could be atomic states or other lotteries) and probabilities $p_1,...,p_n$ (written as $L=[p_1,S_1;p_2,S_2;...;p_n,S_n]$).\n\n**Axioms of utility theory**: **observability** (given two lotteries, a rational agent must prefer one or rate them as equally preferrable), **transitivity** (if prefer lottery A to B and B to C, prefers A to C), **continuity** (if lottery B is between A and C in preference, there is some probability $p$ for which the agent will be indifferent between getting B for sure and the lottery that yields A with probability $p$ and C with probability $1-p$), **substitutability** (if an agent is indifferent between A and B, it is indifferent between two lotteries that are the same except B is substituted for A in one), **monotonicity** (given two lotteries with same two possible outcomes A and B, if agent prefers A to B then agent must prefer lottery that has a higher probability for A), **decomposability** (compound lotteries can be reduced to simpler ones using laws of probability). \n\nAxioms of utility theory have the following consequences: **existence of utility function** (there exists a utility function $U$ such that $U(A)>U(B)$ iff A is preferred to B and $U(A)=U(B)$ iff agent is indifferent between A and B), **expected utility of a lottery** ($U([p_1,S_1;...;p_n,S_n])=\\sum_i p_i U(S_i)$), and the MEU principle.\n\nAgent's behavior unchanged if utility function transformed according to $U'(S) = aU(S)+b$ with $a > 0$.\n\nIn a deterministic environment agent only needs preference ranking on states (**value function** or **ordinal utility function**). \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nDetermining an agent's utility function is called **preference elicitation** (present choices and use observed preferences to determine underlying utility function).\n\nTypically we fix worst outcome at $u_{bot}$ and best outcome at $u_{top}$ (**normalized utilities** use $u_{bot}=0, u_{top}=1$). Can assess utility of prize $S$ by asking agent to choose between $S$ and a **standard lottery** $[p,u_{top}; (1-p),u_{bot}]$ (binary search with $p$ to find utility of $S$).\n\nGovt agencies use **value of a statistical life**. A **micromort** is value of a 1-in-million chance of death. Another measure is quality-adjusted life-year (**QALY**).\n\nMoney may or may not work as an accurate utility function (could have **monotonic preference** but violate characteristics of utility function in lotteries). Can compute **expected monetary value** (EMV) of a lottery. Utility function is often roughly logarithm of money (diminishing marginal utility). Diminishing marginal utility equivalent to **risk aversion** (utility of lottery less than EMV), increasing marginal utility equivalent to **risk seeking**, linear equivalent to **risk neutral**. The value an agent will accept in lieu of a lottery is called the **certainty equivalent** of the lottery. Difference between EMV and certainty equivalent is called the **insurance premium** (risk aversion basis for insurance industry). \nAgent may have to work with estimate $\\hat{EU}(a)$ of true EU function due to practical limitations. We assume that the estimates are **unbiased** ($E(\\hat{EU}(a)-EU(a))=0$). Still, expected utility of best choice tends to be an overestimate (**optimizer's curse**), assuming gaussian EU errors. Can be avoided with a Bayesian approach that uses a model $P(\\hat{EU}\\mid EU)$ of the error in the utility estimates. Can treat utility estimate as evidence and compute the posterior using Bayes' rule.\n\nDecision theory is a **normative theory** (describes how a rational agent should act). A **descriptive theory** describes how actual agents (e.g. humans) act. Humans are predictibly irrational (e.g. **certainty effect**: people attracted to certain gains, **ambiguity aversion**, **framing effect**: wording of problem can influence decision, **anchoring effect**: people prefer making relative utility decisions over absolute ones).\n\n\n## Module 5 Lecture Notes\n\nObjectivist/frequentist interpretation of probability: averages over repeated experiments.\n\nSubjectivist / Bayesian interpretation of probability: degrees of belief about unobserved variables.\n\n\n## Module 5 Definitions\n* **Perfect information** - synonym for fully observable\n* **Zero-sum** - all agents' utilities sum to 0 in any outcome\n* **Move** - synonym for action (or in some contexts, an action by each player)\n* **Ply** - a single action taken by a single player\n* **Position** - synonym for state\n* **$minimax(s)$** - \\max_{a\\in Actions(s)}Minimax(Result(s,a)) if ToMove(s) is Max, else \\min_{a\\in Actions(s)}Minimax(Result(s,a))\n* **Killer moves** - best moves\n* **Killer move heuristic** - a-b pruning heuristic that tries best moves first\n* **Transpositions** - different permutations of move sequences that end up in the same position\n* **Type a strategy** - considers all moves to certain depth and then uses heuristic evaluation function to estimate utility\n* **Type b strategy** - ignores moves that look bad and follows promising lines 'as far as possible' (explores deep but narrow portion)\n* **Quiescent position** - position where there is no pending move that would wildly swing the evaluation\n* **Expectiminimax value** - generalization of minimax value to games with chance nodes\n* **Principle of maximum expected utility** - a rational agent should act to maximize expected utility; $action=\u0007rgmax_a EU(a)$\n* **Axioms of utility theory** - observability, transitivity, continuity, substitutability, monotonicity, decomposability\n* **Preference elicitation** - present choices and use observed preferences to determine underlying utility function\n* **Micromort** - value of a 1-in-million chance of death\n* **Certainty equivalent** - the value an agent will accept in lieu of a lottery\n* **Insurance premium** - difference between expected monetary value and certainty equivalent\n* **Unbiased expected utility estimate** - $E(\\hat{EU}(a)-EU(a))=0$\n* **Optimizer's curse** - expected utility of best choice tends to be an overestimate\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents (e.g. humans) act\n* **Objectivist/frequentist interpretation** - averages over repeated experiments\n* **Subjectivist / bayesian interpretation** - degrees of belief about unobserved variables\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",
        "CSPs: treating states as more than black boxes can lead to new search methods and deeper understanding of problem structure.\n",
        "\n",
        "A CSP consists of 3 components: X, D, and C: $X$ is a set of **variables**, $\\{X_1,...,X_n\\}$, $D$ is a set of **domains** $\\{D_1,...,D_n\\}$, $C$ is a set of **constraints** that specify allowable \\\n",
        "combinations of values. A domain $D_i$ consists of a set of allowable values $\\{v_1,...,v_k\\}$ for variable $X_i$. Each constraint $C_i$ is a pair $(scope, rel)$ where \\\n",
        "$scope$ is a tuple of variables that participate in the constraint and $rel$ is a **relation** that defines the values that those variables can take on (set of all tuples of values, or function \\\n",
        "that computes whether given tuple satisfies constraint).\n",
        "\n",
        "CSPs deal with **assignments** of values to variables. An assignment that doesn't violate constraints is called a **consistent** or legal assignment. A **complete assignment** has every variable assigned \\\n",
        "a value. A **solution** to a CSP is a consistent, complete assignment. A **partial assignment** is one that leaves some variables unassigned, and a **partial solution** is a consistent partial assignment.\n",
        "\n",
        "Can be helpful to visualize a CSP as a **constraint graph** (nodes as variables, edges as constraints).\n",
        "\n",
        "The simplest CSPs involve variables that have **discrete**, **finite** domains. Domains can be **infinite**. Solvers exist for **linear constraints** on integer variables. Impossible \\\n",
        "for algorithm to solve **nonlinear constraints** on integer variables. CSPs with **continuous domains** are common in the real world (e.g. **linear programming**, quadratic programming, etc).\n",
        "\n",
        "Simplest constraint is **unary constraint** that restricts value of single value. A **binary constraint** relates 2 variables. A **binary CSP** is one with only unary and binary constraints \\\n",
        "(can be represented as a constraint graph). A constraint involving an arbitrary number of variables is a **global constraint** (can be represented as a **constraint hypergraph**, containing \\\n",
        "normal nodes and hypernodes representing n-ary constraints involving n variables). Every finite-domain constraint can be reduced to a set of binary constraints with enough auxiliary variables. \\\n",
        "Can use the **dual graph** transformation (new graph, one variable for each original constraint, one binary constraint for each pair of constraints that share variables).\n",
        "\n",
        "Many real-world CSPs include **preference constraints** indicating which solutions are preferred (can be encoded as costs on variable assignments): **constrained optimization problem** (COP).\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "CSP algorithm can generate successors by choosing a new variable assignment, or it can do a type of **inference** called **constraint propagation**: using the constraints to reduce \\\n",
        "the number of legal values for a variable (and propagate changes). Constraint propagation can be intertwined with search or done as a preprocessing step.\n",
        "\n",
        "Key idea is **local consistency**. A single variable is **node-consistent** if all the values in the variable's domain satisfy the variable's unary constraints. \\\n",
        "A graph is node-consistent if every node is node-consistent. \\\n",
        "A variable is **arc-consistent** if every value in its domain satisfies the variable's binary constraints ($X_i$ is arc-consistent w.r.t. $X_j$ if for all values in $D_i$, exists some value in $D_j$ \\\n",
        "that satisfies the binary constraint on the arc $(X_i,X_j)$). A graph is arc-consistent if variables are pairwise arc-consistent. \\\n",
        "\n",
        "Most popular algo for enforcing arc-consistency is **AC-3**. Maintains a queue of arcs to consider (initially all arcs), pops off an arc, \\\n",
        "makes $X_i$ arc-consistent w.r.t. $X_j$, and if this revises $D_i$ (makes the domain smaller), then we add all arcs $(X_k,X_i)$ to the queue where $X_k$ is a neighbor of $X_i$. \\\n",
        "If CSP has $n$ variables, with domain size at most $d$, with $c$ binary constraints (arcs), AC-3 runs in $O(cd^3)$ time (checking consistency of arc done in $O(d^2)$ time, each arc \\\n",
        "inserted to queue at most $d$ times).\n",
        "\n",
        "Stronger notion of consistency: **path consistency**, tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. \\\n",
        "A two-variable set $\\{X_i,X_j\\}$ is path-consistent w.r.t. $X_m$ if for every assignment $\\{X_i=a,X_j=b\\}$ consistent with any constraints between $X_i$ and $X_j$, there is \\\n",
        "an assignment to $X_m$ that satisfies the constraints on $\\{X_i,X_m\\}$ and $\\{X_m,X_j\\}$.\n",
        "\n",
        "Stronger notion of consistency: **k-consistency**. A CSP is k-consistent iff for any set of $k-1$ variables and for any consistent assignment to those variables, a consistent value can always \\\n",
        "be assigned to any $k$th variable. Node-consistency is 1-consistency, arc-consistency is 2-consistency, path-consistency is 3-consistency. A CSP is **strongly k-consistent** iff it is $k$-consistent, \\\n",
        "$(k-1)$-consistent, ..., $1$-consistent. We can solve a strongly $n$-consistent graph in $O(n^2d)$ time by choosing a consistent value for each node in arbitrary order (guaranteed solution).\n",
        "\n",
        "Global constraint strategies. Alldiff: delete singleton domain value and delete variable, propagate. **Resource constraint**: delete \\\n",
        "max value in domain if violates resource constraint with minimum value of each other domain. \n",
        "\n",
        "Large integer domains represented with bounds and managed by **bounds propagation**. CSP is **bounds-consistent** if for every variable $X_i$ and for both the lower and upper bound values of $X_i$, \\\n",
        "for every other variable $Y$, exists some value of $Y$ that satisfies the constraint between $X$ and $Y$.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Even after constraint propagation, may still have variables with multiple possible values (must search for solution). Crucial property of CSPs: **commutativity** (problem is commutative \\\n",
        "iff the order of application of any given set of actions doesn't matter). Can fix arbitrary ordering of variables to assign values to in search (makes search $O(d^n)$ time, $O(n)$ space with backtracking).\n",
        "\n",
        "**Domain-independent** heuristics can be applied in CSP search. \n",
        "\n",
        "Ordering variables to assign can affect performance. **Minimum-remaining-values** (MRV) heuristic: choose variable with smallest domain. **Degree heuristic**: select variable \\\n",
        "involved in largest number of constraints with other unassigned variables.\n",
        "\n",
        "Ordering values to try assigning to a variable can affect performance. The **least-constraining-value** heuristic prefers the value that rules out the fewest choices for neighboring variables \\\n",
        "in the constraint graph (leave maximum flexibility for subsequent variable assignments). Note variable assignment is fail-first but value selection is fail-last (every variable has to be \\\n",
        "assigned eventually, but only need one value assignment).\n",
        "\n",
        "Inference can be powerful tool to interleave with search. **Forward checking** establishes arc-consistency for a variable when it is assigned (for each neighbor Y, delete from Y's domain any \\\n",
        "value inconsistent with the value chosen for X). **Maintaining Arc Consistency (MAC)** calls AC-3 after variable assignment but queue starts only with arcs $(X_j,X_i)$ for all unasigned variables \\\n",
        "$X_j$ that are neighbors of $X_i$.\n",
        "\n",
        "In **chronological backtracking**, we revisit the most recent previous decision point after failure. Better approach: backtrack to a variable that might fix the problem. Keep track of **conflict set** of \\\n",
        "assignments that are in conflict with some value (add to this set when you delete value from domain due to assignment). The **backjumping** method backtracks to the most recent assignment in the conflict set. \\\n",
        "This is redundant if you already do forward checking or MAC. Better/stronger idea: **conflict-directed backjumping** (conflict sets of preceding variables that caused conflict). \n",
        "\n",
        "Can do **constraint learning** to avoid running into the same problem again; find minimum set of variables from the conflict set that cause the problem. This set of variables/values is called a **no-good** \\\n",
        "(can be cached).\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "**Local search** can be effective for CSPs. Start with assignment, choose variable with conflict and change assignment. **Min-conflicts** heuristic is to try value that causes fewest number of conflicts. \\\n",
        "**Tabu search** keeps a small list of recently visited states and forbids the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus. \\\n",
        "**Constraint weighing** aims to concentrate the search on the important constraints (initialize constraint weights to 1, choose variable/value pair change that minimizes total weight of all violated \\\n",
        "constraints, then increment weight of each constraint violated by current assignment); learns what constraints are difficult. \n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "CSPs can contain **independent subproblems**, which can be ascertained by finding **connected components** of the constraint graph (reduces time to $O(d^cn/c)$). A constraint graph is a **tree** \\\n",
        "when any 2 variables are connected by only 1 path. A tree-structured CSP can be solved in linear time in the number of variables. **Directional arc-consistency** (DAC): CSP is DAC under an ordering \\\n",
        "of variables $X_1,...,X_n$ iff every $X_i$ is arc-consistent wit heach $X_j$ for $j>i$. To solve a tree-structured CSP, choose any variable as root and perform **topological sort**, then \\\n",
        "make tree DAC in $O(n)$ steps, each comparing up to $d$ domain values for 2 variables, for a total time of $O(nd^2)$. Once tree is DAC, can just march down and choose any remaining values.\n",
        "\n",
        "First way to reduce graph to tree involves assigning values to some variables so the remaining variables form a tree. **Cutset conditioning**: choose subset $S$ of the CSP's variables \\\n",
        "such that remainder of graph is a tree. $S$ is called a **cycle cutset**. For each possible assignment of the variables in $S$ that satisfies constraints over $S$, remove \\\n",
        "from domains of remaining variables any inconsistent values, and if solution found return it. Takes $O(d^c\\cdot (n-c)d^2)$ time where $c$ is the size of the cycle cutset, but finding the \\\n",
        "smallest cycle cutset is NP hard (many efficient approximation algorithms are known though). Big advantage is it runs in linear memory.\n",
        "\n",
        "Second way to reduce graph to tree constructs a **tree decomposition** of the constraint graph (transformation into tree where each node in the tree consists of a set of \\\n",
        "variables). Every variable in the original problem must appear in at least one tree node, two variables connected by constraint in original problem must appear together (with the constraint) \\\n",
        "in at least one of the tree nodes, and if a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes (variable must have same value wherever it appears). \\\n",
        "Once we have a tree-structured graph, can solve in $O(nd^2)$ time where $n$ is number of tree nodes and $d$ is max domain size (domain in tree is set of tuples of values). We choose a tree decomposition \\\n",
        "to make the subproblems as small as possible. The **tree width** of a tree decomposition is size of largest node minus 1. The tree width of the graph is the minimum width amonst all tree decompositions. \\\n",
        "If a graph has tree width $w$ then can be solved in $O(nd^{w+1})$ time given the corresponding tree decomposition (faster than cutset conditioning), but requires exponential memory. \\\n",
        "Finding the tree decomposition with minimal tree width is NP hard but there are efficient heuristic methods.\n",
        "\n",
        "There can be **value symmetry** in a CSP, and we can reduce search space by introducing a **symmetry-breaking constraint** (impose arbitrary ordering, fix some value, etc). \\\n",
        "NP hard to eliminate all symmetry.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Covered by textbook\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "  \"domain\": \"a set of allowable values $\\{v_1,...,v_k\\}$ for variable $X_i$\",\n",
        "  \"constraint\": \"$C_i$ is a pair $(scope, rel)$ where $scope$ is set of variables and $rel$ is a relation among variables/values\",\n",
        "  \"consistent assignment\": \"doesn't violate any constraints\",\n",
        "  \"complete assignment\": \"all variables are assigned\",\n",
        "  \"CSP solution\": \"complete, consistent assignment\",\n",
        "  \"partial assignment\": \"some variables are assigned\",\n",
        "  \"partial solution\": \"consistent partial assignment\",\n",
        "  \"constraint graph\": \"nodes as variables, edges as constraints\",\n",
        "  \"unary constraint\": \"restricts value of single value\",\n",
        "  \"binary constraint\": \"relates 2 variables\",\n",
        "  \"binary CSP\": \"one with only unary and binary constraints (can be represented as a constraint graph)\",\n",
        "  \"global constraint\": \"constraint involving an arbitrary number of variables (represented as constraint hypergraph)\",\n",
        "  \"dual graph transformation\": \"new graph, one variable for each original constraint, one binary constraint for each pair of constraints that share variables\",\n",
        "  \"preference constraints\": \"preferences among satisfying assignments\",\n",
        "  \"constrained optimization problem\": \"CSP with preference constraints\",\n",
        "  \"constraint propagation\": \"using the constraints to reduce the number of legal values for a variable (and propagate changes)\",\n",
        "  \"node-consistent\": \"all the values in the variable's domain satisfy the variable's unary constraints (1-consistent)\",\n",
        "  \"arc-consistent\": \"for all values in $D_i$, exists some value in $D_j$ that satisfies the binary constraint on the arc $(X_i,X_j)$ (2-consistent)\",\n",
        "  \"path consistency\": \"for every consistent assignment to 2 nodes, exists a consistent assignment to a 3rd node (3-consistency)\",\n",
        "  \"k-consistency\": \"for any consistent assignment to $k-1$ variables, a consistent value can always be assigned to any $k$th variable\",\n",
        "  \"strongly k-consistent\": \"$k$-consistent, $(k-1)$-consistent, ..., $1$-consistent\",\n",
        "  \"commutativity\": \"order of application of any given set of actions doesn't matter\",\n",
        "  \"tree width of tree decomposition\": \"size of largest node minus 1\",\n",
        "  \"tree width of graph\": \"minimum width amonst all tree decompositions\",\n",
        "}\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0156d27a-6d2e-4751-e034-0fe1dc92ab6b"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs: treating states as more than black boxes can lead to new search methods and deeper understanding of problem structure.\n\nA CSP consists of 3 components: X, D, and C: $X$ is a set of **variables**, $\\{X_1,...,X_n\\}$, $D$ is a set of **domains** $\\{D_1,...,D_n\\}$, $C$ is a set of **constraints** that specify allowable combinations of values. A domain $D_i$ consists of a set of allowable values $\\{v_1,...,v_k\\}$ for variable $X_i$. Each constraint $C_i$ is a pair $(scope, rel)$ where $scope$ is a tuple of variables that participate in the constraint and $rel$ is a **relation** that defines the values that those variables can take on (set of all tuples of values, or function that computes whether given tuple satisfies constraint).\n\nCSPs deal with **assignments** of values to variables. An assignment that doesn't violate constraints is called a **consistent** or legal assignment. A **complete assignment** has every variable assigned a value. A **solution** to a CSP is a consistent, complete assignment. A **partial assignment** is one that leaves some variables unassigned, and a **partial solution** is a consistent partial assignment.\n\nCan be helpful to visualize a CSP as a **constraint graph** (nodes as variables, edges as constraints).\n\nThe simplest CSPs involve variables that have **discrete**, **finite** domains. Domains can be **infinite**. Solvers exist for **linear constraints** on integer variables. Impossible for algorithm to solve **nonlinear constraints** on integer variables. CSPs with **continuous domains** are common in the real world (e.g. **linear programming**, quadratic programming, etc).\n\nSimplest constraint is **unary constraint** that restricts value of single value. A **binary constraint** relates 2 variables. A **binary CSP** is one with only unary and binary constraints (can be represented as a constraint graph). A constraint involving an arbitrary number of variables is a **global constraint** (can be represented as a **constraint hypergraph**, containing normal nodes and hypernodes representing n-ary constraints involving n variables). Every finite-domain constraint can be reduced to a set of binary constraints with enough auxiliary variables. Can use the **dual graph** transformation (new graph, one variable for each original constraint, one binary constraint for each pair of constraints that share variables).\n\nMany real-world CSPs include **preference constraints** indicating which solutions are preferred (can be encoded as costs on variable assignments): **constrained optimization problem** (COP).\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nCSP algorithm can generate successors by choosing a new variable assignment, or it can do a type of **inference** called **constraint propagation**: using the constraints to reduce the number of legal values for a variable (and propagate changes). Constraint propagation can be intertwined with search or done as a preprocessing step.\n\nKey idea is **local consistency**. A single variable is **node-consistent** if all the values in the variable's domain satisfy the variable's unary constraints. A graph is node-consistent if every node is node-consistent. A variable is **arc-consistent** if every value in its domain satisfies the variable's binary constraints ($X_i$ is arc-consistent w.r.t. $X_j$ if for all values in $D_i$, exists some value in $D_j$ that satisfies the binary constraint on the arc $(X_i,X_j)$). A graph is arc-consistent if variables are pairwise arc-consistent. \nMost popular algo for enforcing arc-consistency is **AC-3**. Maintains a queue of arcs to consider (initially all arcs), pops off an arc, makes $X_i$ arc-consistent w.r.t. $X_j$, and if this revises $D_i$ (makes the domain smaller), then we add all arcs $(X_k,X_i)$ to the queue where $X_k$ is a neighbor of $X_i$. If CSP has $n$ variables, with domain size at most $d$, with $c$ binary constraints (arcs), AC-3 runs in $O(cd^3)$ time (checking consistency of arc done in $O(d^2)$ time, each arc inserted to queue at most $d$ times).\n\nStronger notion of consistency: **path consistency**, tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. A two-variable set $\\{X_i,X_j\\}$ is path-consistent w.r.t. $X_m$ if for every assignment $\\{X_i=a,X_j=b\\}$ consistent with any constraints between $X_i$ and $X_j$, there is an assignment to $X_m$ that satisfies the constraints on $\\{X_i,X_m\\}$ and $\\{X_m,X_j\\}$.\n\nStronger notion of consistency: **k-consistency**. A CSP is k-consistent iff for any set of $k-1$ variables and for any consistent assignment to those variables, a consistent value can always be assigned to any $k$th variable. Node-consistency is 1-consistency, arc-consistency is 2-consistency, path-consistency is 3-consistency. A CSP is **strongly k-consistent** iff it is $k$-consistent, $(k-1)$-consistent, ..., $1$-consistent. We can solve a strongly $n$-consistent graph in $O(n^2d)$ time by choosing a consistent value for each node in arbitrary order (guaranteed solution).\n\nGlobal constraint strategies. Alldiff: delete singleton domain value and delete variable, propagate. **Resource constraint**: delete max value in domain if violates resource constraint with minimum value of each other domain. \n\nLarge integer domains represented with bounds and managed by **bounds propagation**. CSP is **bounds-consistent** if for every variable $X_i$ and for both the lower and upper bound values of $X_i$, for every other variable $Y$, exists some value of $Y$ that satisfies the constraint between $X$ and $Y$.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nEven after constraint propagation, may still have variables with multiple possible values (must search for solution). Crucial property of CSPs: **commutativity** (problem is commutative iff the order of application of any given set of actions doesn't matter). Can fix arbitrary ordering of variables to assign values to in search (makes search $O(d^n)$ time, $O(n)$ space with backtracking).\n\n**Domain-independent** heuristics can be applied in CSP search. \n\nOrdering variables to assign can affect performance. **Minimum-remaining-values** (MRV) heuristic: choose variable with smallest domain. **Degree heuristic**: select variable involved in largest number of constraints with other unassigned variables.\n\nOrdering values to try assigning to a variable can affect performance. The **least-constraining-value** heuristic prefers the value that rules out the fewest choices for neighboring variables in the constraint graph (leave maximum flexibility for subsequent variable assignments). Note variable assignment is fail-first but value selection is fail-last (every variable has to be assigned eventually, but only need one value assignment).\n\nInference can be powerful tool to interleave with search. **Forward checking** establishes arc-consistency for a variable when it is assigned (for each neighbor Y, delete from Y's domain any value inconsistent with the value chosen for X). **Maintaining Arc Consistency (MAC)** calls AC-3 after variable assignment but queue starts only with arcs $(X_j,X_i)$ for all unasigned variables $X_j$ that are neighbors of $X_i$.\n\nIn **chronological backtracking**, we revisit the most recent previous decision point after failure. Better approach: backtrack to a variable that might fix the problem. Keep track of **conflict set** of assignments that are in conflict with some value (add to this set when you delete value from domain due to assignment). The **backjumping** method backtracks to the most recent assignment in the conflict set. This is redundant if you already do forward checking or MAC. Better/stronger idea: **conflict-directed backjumping** (conflict sets of preceding variables that caused conflict). \n\nCan do **constraint learning** to avoid running into the same problem again; find minimum set of variables from the conflict set that cause the problem. This set of variables/values is called a **no-good** (can be cached).\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n**Local search** can be effective for CSPs. Start with assignment, choose variable with conflict and change assignment. **Min-conflicts** heuristic is to try value that causes fewest number of conflicts. **Tabu search** keeps a small list of recently visited states and forbids the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus. **Constraint weighing** aims to concentrate the search on the important constraints (initialize constraint weights to 1, choose variable/value pair change that minimizes total weight of all violated constraints, then increment weight of each constraint violated by current assignment); learns what constraints are difficult. \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nCSPs can contain **independent subproblems**, which can be ascertained by finding **connected components** of the constraint graph (reduces time to $O(d^cn/c)$). A constraint graph is a **tree** when any 2 variables are connected by only 1 path. A tree-structured CSP can be solved in linear time in the number of variables. **Directional arc-consistency** (DAC): CSP is DAC under an ordering of variables $X_1,...,X_n$ iff every $X_i$ is arc-consistent wit heach $X_j$ for $j>i$. To solve a tree-structured CSP, choose any variable as root and perform **topological sort**, then make tree DAC in $O(n)$ steps, each comparing up to $d$ domain values for 2 variables, for a total time of $O(nd^2)$. Once tree is DAC, can just march down and choose any remaining values.\n\nFirst way to reduce graph to tree involves assigning values to some variables so the remaining variables form a tree. **Cutset conditioning**: choose subset $S$ of the CSP's variables such that remainder of graph is a tree. $S$ is called a **cycle cutset**. For each possible assignment of the variables in $S$ that satisfies constraints over $S$, remove from domains of remaining variables any inconsistent values, and if solution found return it. Takes $O(d^c\\cdot (n-c)d^2)$ time where $c$ is the size of the cycle cutset, but finding the smallest cycle cutset is NP hard (many efficient approximation algorithms are known though). Big advantage is it runs in linear memory.\n\nSecond way to reduce graph to tree constructs a **tree decomposition** of the constraint graph (transformation into tree where each node in the tree consists of a set of variables). Every variable in the original problem must appear in at least one tree node, two variables connected by constraint in original problem must appear together (with the constraint) in at least one of the tree nodes, and if a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes (variable must have same value wherever it appears). Once we have a tree-structured graph, can solve in $O(nd^2)$ time where $n$ is number of tree nodes and $d$ is max domain size (domain in tree is set of tuples of values). We choose a tree decomposition to make the subproblems as small as possible. The **tree width** of a tree decomposition is size of largest node minus 1. The tree width of the graph is the minimum width amonst all tree decompositions. If a graph has tree width $w$ then can be solved in $O(nd^{w+1})$ time given the corresponding tree decomposition (faster than cutset conditioning), but requires exponential memory. Finding the tree decomposition with minimal tree width is NP hard but there are efficient heuristic methods.\n\nThere can be **value symmetry** in a CSP, and we can reduce search space by introducing a **symmetry-breaking constraint** (impose arbitrary ordering, fix some value, etc). NP hard to eliminate all symmetry.\n\n\n## Module 6 Lecture Notes\n\nCovered by textbook\n\n\n## Module 6 Definitions\n* **Domain** - a set of allowable values $\\{v_1,...,v_k\\}$ for variable $X_i$\n* **Constraint** - $C_i$ is a pair $(scope, rel)$ where $scope$ is set of variables and $rel$ is a relation among variables/values\n* **Consistent assignment** - doesn't violate any constraints\n* **Complete assignment** - all variables are assigned\n* **Csp solution** - complete, consistent assignment\n* **Partial assignment** - some variables are assigned\n* **Partial solution** - consistent partial assignment\n* **Constraint graph** - nodes as variables, edges as constraints\n* **Unary constraint** - restricts value of single value\n* **Binary constraint** - relates 2 variables\n* **Binary csp** - one with only unary and binary constraints (can be represented as a constraint graph)\n* **Global constraint** - constraint involving an arbitrary number of variables (represented as constraint hypergraph)\n* **Dual graph transformation** - new graph, one variable for each original constraint, one binary constraint for each pair of constraints that share variables\n* **Preference constraints** - preferences among satisfying assignments\n* **Constrained optimization problem** - CSP with preference constraints\n* **Constraint propagation** - using the constraints to reduce the number of legal values for a variable (and propagate changes)\n* **Node-consistent** - all the values in the variable's domain satisfy the variable's unary constraints (1-consistent)\n* **Arc-consistent** - for all values in $D_i$, exists some value in $D_j$ that satisfies the binary constraint on the arc $(X_i,X_j)$ (2-consistent)\n* **Path consistency** - for every consistent assignment to 2 nodes, exists a consistent assignment to a 3rd node (3-consistency)\n* **K-consistency** - for any consistent assignment to $k-1$ variables, a consistent value can always be assigned to any $k$th variable\n* **Strongly k-consistent** - $k$-consistent, $(k-1)$-consistent, ..., $1$-consistent\n* **Commutativity** - order of application of any given set of actions doesn't matter\n* **Tree width of tree decomposition** - size of largest node minus 1\n* **Tree width of graph** - minimum width amonst all tree decompositions\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "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 Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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": 236
        },
        "id": "T3cm1WV542_a",
        "outputId": "22a0d8c3-2188-4635-ee7b-c22e29c2b0bd"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-7-197fd754e469>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# This will generate the full set of notes that you can use for your exam.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m full_markdown = \"\\n\\n\".join([module1_markdown, \n\u001b[0m\u001b[1;32m      3\u001b[0m                              \u001b[0mmodule2_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m                              \u001b[0mmodule3_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m                              \u001b[0mmodule4_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mNameError\u001b[0m: name 'module1_markdown' is not defined"
          ]
        }
      ]
    }
  ]
}