{
  "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": "5f472a5f-b24f-400e-a1e9-f818103a2c5d"
      },
      "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": 82,
      "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": "9b12e1e2-fb5a-473b-fae7-bb3659032caf"
      },
      "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": 83,
      "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": 84,
      "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",
        "- Two dimensions (4 combos): Human vs. Rational and Thought vs. Behavior\n",
        "- Turing test: computer passes if human interrogator cannot tell if responses come from person or computer (viewed physical simulation of person as unnecessary to demonstrate intelligence)\n",
        "- Computer needs: NLP, knowledge representation, automated reasoning, machine learning\n",
        "- Total Turing test: requires interaction with objects & people in real world (need computer vision & robotics)\n",
        "\n",
        "- Learn about human thought: introspection, psychological experiments, brain imaging\n",
        "- Program's input-output behavior matches human's: evidence program's mechanisms might operate in humans\n",
        "\n",
        "- Logic requires knowledge of world that is certain (seldom happens): Theory of probability fills this gap -- allows construction of comprehensive model of rational though, but does not generate intelligent behavior\n",
        "\n",
        "- Making correct inferences: part of being rational agent, but sometimes there are ways of acting rationally that cannot involve inference\n",
        "- Skills needed for Turing test also allow agent to act rationally\n",
        "- Rational-agent approach to AI: more general than \"laws of thought\" approach and more amenable to scientific development\n",
        "- Standard model: AI has focused on the study and construction of agents that do the right thing (what counts as right thing is defined by objective we provide to agent)\n",
        "- Perfect rationality too high of computational costs: limited rationality is fine\n",
        "\n",
        "- Standard model not great in long-run because assumes we supply fully specified objective to the machine\n",
        "- Value alignment problem: Problem of achieving agreement between true preferences & the objective we put into machine -- those put into machine must align with that of human\n",
        "- 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: distinction between weak AI (machines act as if they're intelligent) and strong AI (machines that do so are actually consciously thinking)\n",
        "- Turing's \"argument from informality of behavior\": human behavior is far too complex to be captured by any formal set of rules (must use informal guidelines)\n",
        "- Good Old-Fashioned AI (GOFAI): corresponds to simplest logical agent\n",
        "- Embodied cognition approach: makes no sense to consider brain separately\n",
        "\n",
        "- \"Argument from disability\": claim that a machine can never do X (be kind, resourceful, beautiful, etc)\n",
        "- For any formal axiomatic framework F powerful enough to do arithmetic, possible to construct Godel sentence G(F) with properties: G(F) is a sentence of F, but cannot be proved with F & if F is consistent, then G(F) is true\n",
        "- (Lucas) Machines are formal systems that are limited by incompleteness theorem (cannot establish the truth of their own Godel sentence)\n",
        "- 3problems with Lucas claim: agent should not be ashamed that it cannot establish the truth of some sentence while other agents can; Godel's incompleteness theorem & related results apply to math, not computers and technically applies only to formal systems that're powerful enough to do arithmetic\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "- Turing: usual to have polite convention that everyone thinks\n",
        "- Searle rejects polite convention: Chinese room does same as computer, therefore computers generate no understanding\n",
        "- Searle proponent of biological naturalism: mental states are high-level emergent features that are caused by low-level physical processes in the neurons\n",
        "- Qualia: term for intrinsic nature of experiences\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "- Agent's choice of action at any given instance can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived\n",
        "- Agent's behavior: described by agent function that maps any given percept sequence to an action\n",
        "- Can tabulate all possible percept sequences and recording which actions agent does in response (external characterization)\n",
        "- Internal characterization: agent function for an artificial agent will be implemented by agent program\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "- Rational agent: does right thing, but what is right thing?\n",
        "- AI usually concerned with consequentialism: evaluate an agent's behavior by its consequences\n",
        "- Desirability of sequence of actions through a sequence of states: captured by performance measure that evals any given sequence of environment states\n",
        "- Machines do not have desires/preferences of their own: performance measure is in the mind of the designer of the machine (initially)\n",
        "- Better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave\n",
        "\n",
        "- Rational depends on 4things: 1) performance measure that defines criterion of success; 2) agent's prior knowledge of environment; 3) actions agent can perform; 4) agent's percept sequence to date\n",
        "- Rational agent: for each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has\n",
        "- Rationality maximizes expected performance, while perfection maximizes actual performance\n",
        "- Rationality does not require omniscience because the rational choice depends only on the percept sequence to date\n",
        "- Information gathering: important part of rationality\n",
        "- Want rational agent not only to gather information, but also to learn as much as possible from what it perceives\n",
        "- RA should be autonomous: learn what it can to compensate for partial or incorrect prior knowledge\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- Task environment: the 'problems' to which rational agents are the 'solutions'\n",
        "- Grouped under task environment: PEAS (Performance, Environment, Actuators, Sensors)\n",
        "- Fully observable vs partially observable: fully if sensors give agent access to complete state of environment at each point in time\n",
        "  - If sensors detect all aspects that are relevant to the choice of action (relevance depends on performance measure)\n",
        "  - Convenient in that agent doesn't need to maintain any internal state to keep track of the world\n",
        "  - No sensors: unobservable\n",
        "- Single-agent vs multiagent: treat an object B as an agent if B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior\n",
        "  - Chess: competitive multiagent environment\n",
        "    - In some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability \n",
        "  - Taxi-driving: cooperative multiagent environment\n",
        "- Deterministic vs nondeterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say deterministic\n",
        "  - Stochastic: if it explicitly deals with probabilities\n",
        "  - Nondeterministic: if possibilities are listed without being quantified\n",
        "- Episodic vs sequential: agent's experience divided into atomic episodes; in each episode, agent receives a percept and then performs a single action\n",
        "  - Sequential: current decision could affect all future decisions\n",
        "- Static vs dynamic: dynamic if environment can change while agent deliberates\n",
        "  - Semidynamic if environment doesn't change with passage of time, but agent's performance score does (i.e. chess w/ clock)\n",
        "- Discrete vs continuous: applies to state of environment, the way time is handled, and to the percepts & actions of agent\n",
        "- Known vs unknown: refers not to environment itself, but to agent's state of knowledge about the 'laws of physics' of the environment\n",
        "- Hardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous and unknown\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- 4kinds of agent programs that embody principles underlying almost all intelligent systems: simple reflex; model-based reflex; goal-based; utility-based agents\n",
        "- Simple reflex agent\n",
        "  - Simple reflex behaviors occur even in more complex environment (condition-action rule, i.e. if-then)\n",
        "  - Will work only if correct decision can be made on basis of just current percept (only if environment is fully observable)\n",
        "  - Infinite loops often unavoidable for SRA operating in partially observable environments\n",
        "    - Escape possible if agent can randomize actions\n",
        "    - Randomized SRA might outperform deterministic SRA\n",
        "  - In single-agent environments, randomization usually not rational\n",
        "- Model-based reflex agents: use transition model and sensor model which allow agent to keep track of state of world\n",
        "  - Most effective way to handle partial observability is for agent to keep track of the part of the world it can't see now\n",
        "  - Maintain internal state that depends on percept history (thereby reflects at least some of unobserved aspects of current state)\n",
        "    - Need info about how world changes over time (2parts)\n",
        "      - Effects of agent's actions\n",
        "      - How world evolves independently of agent\n",
        "      - 'How world works': transition model of world\n",
        "    - Need info about how state of world is reflected in agent's percepts (sensor model)\n",
        "  - Agent best guesses current state of partially observable environment\n",
        "- Goal-based agents\n",
        "  - Different from condition-action rules -> involves consideration of future\n",
        "  - Less efficient, but more flexible because knowledge that supports its decisions is represented explicitly and can be modified\n",
        "- Utility-based agents: has to model and keep track of its environment\n",
        "  - General performance measure should allow a comparison of different world states according to utility function\n",
        "  - 2cases where goals inadequate but utility-based can still make rational decisions:\n",
        "    - When conflicting goals, utility function specifies appropriate tradeoff\n",
        "    - When several goals, utility provides way in which likelihood of success can be weighed against importance of goals\n",
        "  - Maximize expected utility due to partial observability and nondeterminism\n",
        "- Learning agent can be divided into 4conceptual components:\n",
        "  - Learning element: responsible for making improvements\n",
        "    - Uses feedback from critic and determines how the performance element should be modified to do better in future\n",
        "    - Design depends very much on design of performance element\n",
        "  - Performance element: responsible for selecting external actions\n",
        "  - Critic: tells learning element how well agent is doing with respect to fixed performance standard (percepts themselves provide no indication of agent's success)\n",
        "  - Problem generator: responsible for suggesting actions that will lead to new and informative experiences\n",
        "    - If agent willing to explore little in short run, might discover better actions for long run\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "- Rene Descartes (1596-1650): principle of dualism that the mind or thinking self is essentially incorporeal or spiritual (that mind exists separately from body)\n",
        "  - How can I know you are not an automaton?\n",
        "- Alan Turing (1912-1954): 'Are there imaginable digital computers which would do well in the imitation game?'\n",
        "  - Human evaluator judge text-based conversations between a human and machine designed to generate human-like responses\n",
        "  - If cannot tell machine from human, machine passes test\n",
        "  - Does not depend on correctness of answers, just how closely answer resembles those a human would give\n",
        "- John Searle (1932-): Chinese room: machines don't possess intelligence, it just gave impression of intelligence through simple symbol manipulation\n",
        "  - Strong AI: computer really is a mind (can be literally said to understand and have other cognitive states)\n",
        "  - Weak AI: computer just simulates thought (seeming understanding isn't true understanding)\n",
        "  - Biological brains cause minds\n",
        "- Daniel Dennett (1942-): Brain in vat\n",
        "- AI: science of making machines that think and act like people\n",
        "- Agent is specified by agent function f:P->a that maps a sequence of percept vectors P to an action a from a set of A\n",
        "- 'Easy' solution: giant table that maps every possible sequence P to an action a (Problem: exponential in length of P)\n",
        "- Rational agent: agent that perceives its environment and behaves rationally\n",
        "  - For each possible percept sequence P, a rational agent selects an action a to maximizes expected value of its performance measure\n",
        "- Does the 'right thing': define performance measure which is\n",
        "  - an objective criterion for success of an agent's behavior\n",
        "  - given the evidence provided by the percept sequence\n",
        "- Ideal agent maximizes actual performance, but needs to be omniscient (usually impossible)\n",
        "  - Computational limitations make complete rationality unachievable: design best program for given machine resources\n",
        "- Goal of AI practitioner who designs rational agents: given PEAS task environment:\n",
        "  - Construct agent function f that maximizes expected value of the performance measure\n",
        "  - Design agent program that implements f on particular architecture\n",
        "- When something's behavior can best be described as having its own performance measure -> consider to be agent\n",
        "- Simple reflex agent: select actions on basis of current percept, ignoring rest of percept history\n",
        "- Problem-solving agent must plan ahead\n",
        "  - will consider a sequence of actions that form a path to a goal state\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",
        "\"rational agent\": \"agent that acts to obtain best expected outcome\",\n",
        "\"omniscient agent\": \"knows the actual outcome of its actions and can act accordingly (impossible in reality)\",\n",
        "\"perfect rationality\": \"always take optimal action\",\n",
        "\"limited rationality\": \"acting appropriately when there's computational time limitations on deciding what to do\",\n",
        "\"qualification problem\": \"difficult to capture every combo of appropriate behavior\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"what an agent's sensors perceived\",\n",
        "\"percept sequence\" : \"complete history of what has ever been perceived by agent\",\n",
        "\"agent function\": \"abstract mathematical description\",\n",
        "\"agent program\": \"actual implementation\",\n",
        "\"performance measure\": \"measure that evaluates given sequence of states\",\n",
        "\"information gathering\": \"doing actions in order to modify future percepts\",\n",
        "\"agent architecture\": \"agent = architecture + program\",\n",
        "\"atomic representation\": \"each state is indivisible (has no internal structure)\",\n",
        "\"factored representation\": \"each state split up into fixed set of variables where each can have a value\",\n",
        "\"structured representation\": \"objects and their varying relationships are described explicitly\",\n",
        "\"localist representation\": \"one-to-one mapping between concepts and memory locations\",\n",
        "\"distributed representation\": \"representation of concept spread over many memory locations and each part of representation of multiple different concepts\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 85,
      "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": "3c5d7f21-f848-4c19-eea6-a6aba30c9a2c"
      },
      "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.2 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": 86,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- Two dimensions (4 combos): Human vs. Rational and Thought vs. Behavior\n- Turing test: computer passes if human interrogator cannot tell if responses come from person or computer (viewed physical simulation of person as unnecessary to demonstrate intelligence)\n- Computer needs: NLP, knowledge representation, automated reasoning, machine learning\n- Total Turing test: requires interaction with objects & people in real world (need computer vision & robotics)\n\n- Learn about human thought: introspection, psychological experiments, brain imaging\n- Program's input-output behavior matches human's: evidence program's mechanisms might operate in humans\n\n- Logic requires knowledge of world that is certain (seldom happens): Theory of probability fills this gap -- allows construction of comprehensive model of rational though, but does not generate intelligent behavior\n\n- Making correct inferences: part of being rational agent, but sometimes there are ways of acting rationally that cannot involve inference\n- Skills needed for Turing test also allow agent to act rationally\n- Rational-agent approach to AI: more general than \"laws of thought\" approach and more amenable to scientific development\n- Standard model: AI has focused on the study and construction of agents that do the right thing (what counts as right thing is defined by objective we provide to agent)\n- Perfect rationality too high of computational costs: limited rationality is fine\n\n- Standard model not great in long-run because assumes we supply fully specified objective to the machine\n- Value alignment problem: Problem of achieving agreement between true preferences & the objective we put into machine -- those put into machine must align with that of human\n- Want agents that are provably beneficial to humans\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n- John Searle: distinction between weak AI (machines act as if they're intelligent) and strong AI (machines that do so are actually consciously thinking)\n- Turing's \"argument from informality of behavior\": human behavior is far too complex to be captured by any formal set of rules (must use informal guidelines)\n- Good Old-Fashioned AI (GOFAI): corresponds to simplest logical agent\n- Embodied cognition approach: makes no sense to consider brain separately\n\n- \"Argument from disability\": claim that a machine can never do X (be kind, resourceful, beautiful, etc)\n- For any formal axiomatic framework F powerful enough to do arithmetic, possible to construct Godel sentence G(F) with properties: G(F) is a sentence of F, but cannot be proved with F & if F is consistent, then G(F) is true\n- (Lucas) Machines are formal systems that are limited by incompleteness theorem (cannot establish the truth of their own Godel sentence)\n- 3problems with Lucas claim: agent should not be ashamed that it cannot establish the truth of some sentence while other agents can; Godel's incompleteness theorem & related results apply to math, not computers and technically applies only to formal systems that're powerful enough to do arithmetic\n\n\n## AIMA Chapter 27.2 Can Machines Really Think?\n\n- Turing: usual to have polite convention that everyone thinks\n- Searle rejects polite convention: Chinese room does same as computer, therefore computers generate no understanding\n- Searle proponent of biological naturalism: mental states are high-level emergent features that are caused by low-level physical processes in the neurons\n- Qualia: term for intrinsic nature of experiences\n\n\n## AIMA 2.1 Agents and Environments\n\n- Agent's choice of action at any given instance can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived\n- Agent's behavior: described by agent function that maps any given percept sequence to an action\n- Can tabulate all possible percept sequences and recording which actions agent does in response (external characterization)\n- Internal characterization: agent function for an artificial agent will be implemented by agent program\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- Rational agent: does right thing, but what is right thing?\n- AI usually concerned with consequentialism: evaluate an agent's behavior by its consequences\n- Desirability of sequence of actions through a sequence of states: captured by performance measure that evals any given sequence of environment states\n- Machines do not have desires/preferences of their own: performance measure is in the mind of the designer of the machine (initially)\n- Better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave\n\n- Rational depends on 4things: 1) performance measure that defines criterion of success; 2) agent's prior knowledge of environment; 3) actions agent can perform; 4) agent's percept sequence to date\n- Rational agent: for each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has\n- Rationality maximizes expected performance, while perfection maximizes actual performance\n- Rationality does not require omniscience because the rational choice depends only on the percept sequence to date\n- Information gathering: important part of rationality\n- Want rational agent not only to gather information, but also to learn as much as possible from what it perceives\n- RA should be autonomous: learn what it can to compensate for partial or incorrect prior knowledge\n\n\n## AIMA 2.3 The Nature of Environments\n\n- Task environment: the 'problems' to which rational agents are the 'solutions'\n- Grouped under task environment: PEAS (Performance, Environment, Actuators, Sensors)\n- Fully observable vs partially observable: fully if sensors give agent access to complete state of environment at each point in time\n  - If sensors detect all aspects that are relevant to the choice of action (relevance depends on performance measure)\n  - Convenient in that agent doesn't need to maintain any internal state to keep track of the world\n  - No sensors: unobservable\n- Single-agent vs multiagent: treat an object B as an agent if B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior\n  - Chess: competitive multiagent environment\n    - In some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability \n  - Taxi-driving: cooperative multiagent environment\n- Deterministic vs nondeterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say deterministic\n  - Stochastic: if it explicitly deals with probabilities\n  - Nondeterministic: if possibilities are listed without being quantified\n- Episodic vs sequential: agent's experience divided into atomic episodes; in each episode, agent receives a percept and then performs a single action\n  - Sequential: current decision could affect all future decisions\n- Static vs dynamic: dynamic if environment can change while agent deliberates\n  - Semidynamic if environment doesn't change with passage of time, but agent's performance score does (i.e. chess w/ clock)\n- Discrete vs continuous: applies to state of environment, the way time is handled, and to the percepts & actions of agent\n- Known vs unknown: refers not to environment itself, but to agent's state of knowledge about the 'laws of physics' of the environment\n- Hardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous and unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- 4kinds of agent programs that embody principles underlying almost all intelligent systems: simple reflex; model-based reflex; goal-based; utility-based agents\n- Simple reflex agent\n  - Simple reflex behaviors occur even in more complex environment (condition-action rule, i.e. if-then)\n  - Will work only if correct decision can be made on basis of just current percept (only if environment is fully observable)\n  - Infinite loops often unavoidable for SRA operating in partially observable environments\n    - Escape possible if agent can randomize actions\n    - Randomized SRA might outperform deterministic SRA\n  - In single-agent environments, randomization usually not rational\n- Model-based reflex agents: use transition model and sensor model which allow agent to keep track of state of world\n  - Most effective way to handle partial observability is for agent to keep track of the part of the world it can't see now\n  - Maintain internal state that depends on percept history (thereby reflects at least some of unobserved aspects of current state)\n    - Need info about how world changes over time (2parts)\n      - Effects of agent's actions\n      - How world evolves independently of agent\n      - 'How world works': transition model of world\n    - Need info about how state of world is reflected in agent's percepts (sensor model)\n  - Agent best guesses current state of partially observable environment\n- Goal-based agents\n  - Different from condition-action rules -> involves consideration of future\n  - Less efficient, but more flexible because knowledge that supports its decisions is represented explicitly and can be modified\n- Utility-based agents: has to model and keep track of its environment\n  - General performance measure should allow a comparison of different world states according to utility function\n  - 2cases where goals inadequate but utility-based can still make rational decisions:\n    - When conflicting goals, utility function specifies appropriate tradeoff\n    - When several goals, utility provides way in which likelihood of success can be weighed against importance of goals\n  - Maximize expected utility due to partial observability and nondeterminism\n- Learning agent can be divided into 4conceptual components:\n  - Learning element: responsible for making improvements\n    - Uses feedback from critic and determines how the performance element should be modified to do better in future\n    - Design depends very much on design of performance element\n  - Performance element: responsible for selecting external actions\n  - Critic: tells learning element how well agent is doing with respect to fixed performance standard (percepts themselves provide no indication of agent's success)\n  - Problem generator: responsible for suggesting actions that will lead to new and informative experiences\n    - If agent willing to explore little in short run, might discover better actions for long run\n\n\n## Module 1 Lecture Notes\n\n- Rene Descartes (1596-1650): principle of dualism that the mind or thinking self is essentially incorporeal or spiritual (that mind exists separately from body)\n  - How can I know you are not an automaton?\n- Alan Turing (1912-1954): 'Are there imaginable digital computers which would do well in the imitation game?'\n  - Human evaluator judge text-based conversations between a human and machine designed to generate human-like responses\n  - If cannot tell machine from human, machine passes test\n  - Does not depend on correctness of answers, just how closely answer resembles those a human would give\n- John Searle (1932-): Chinese room: machines don't possess intelligence, it just gave impression of intelligence through simple symbol manipulation\n  - Strong AI: computer really is a mind (can be literally said to understand and have other cognitive states)\n  - Weak AI: computer just simulates thought (seeming understanding isn't true understanding)\n  - Biological brains cause minds\n- Daniel Dennett (1942-): Brain in vat\n- AI: science of making machines that think and act like people\n- Agent is specified by agent function f:P->a that maps a sequence of percept vectors P to an action a from a set of A\n- 'Easy' solution: giant table that maps every possible sequence P to an action a (Problem: exponential in length of P)\n- Rational agent: agent that perceives its environment and behaves rationally\n  - For each possible percept sequence P, a rational agent selects an action a to maximizes expected value of its performance measure\n- Does the 'right thing': define performance measure which is\n  - an objective criterion for success of an agent's behavior\n  - given the evidence provided by the percept sequence\n- Ideal agent maximizes actual performance, but needs to be omniscient (usually impossible)\n  - Computational limitations make complete rationality unachievable: design best program for given machine resources\n- Goal of AI practitioner who designs rational agents: given PEAS task environment:\n  - Construct agent function f that maximizes expected value of the performance measure\n  - Design agent program that implements f on particular architecture\n- When something's behavior can best be described as having its own performance measure -> consider to be agent\n- Simple reflex agent: select actions on basis of current percept, ignoring rest of percept history\n- Problem-solving agent must plan ahead\n  - will consider a sequence of actions that form a path to a goal state\n\n\n## Module 1 Definitions\n* **Rational agent** - agent that acts to obtain best expected outcome\n* **Omniscient agent** - knows the actual outcome of its actions and can act accordingly (impossible in reality)\n* **Perfect rationality** - always take optimal action\n* **Limited rationality** - acting appropriately when there's computational time limitations on deciding what to do\n* **Qualification problem** - difficult to capture every combo of appropriate behavior\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - what an agent's sensors perceived\n* **Percept sequence** - complete history of what has ever been perceived by agent\n* **Agent function** - abstract mathematical description\n* **Agent program** - actual implementation\n* **Performance measure** - measure that evaluates given sequence of states\n* **Information gathering** - doing actions in order to modify future percepts\n* **Agent architecture** - agent = architecture + program\n* **Atomic representation** - each state is indivisible (has no internal structure)\n* **Factored representation** - each state split up into fixed set of variables where each can have a value\n* **Structured representation** - objects and their varying relationships are described explicitly\n* **Localist representation** - one-to-one mapping between concepts and memory locations\n* **Distributed representation** - representation of concept spread over many memory locations and each part of representation of multiple different concepts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "- Developed by Guido van Rossum in 1989\n",
        "- Python inspired by ABC language\n",
        "- Positive features: fast development (concise, intuitive, garbage collected); portable (progs run on major platforms w/o change); various built-in types; large collection of support libraries\n",
        "- PEP: Python Enhancement Proposals\n",
        "- REPL: Read-Evaluate-Print Loop (type python3 in terminal)\n",
        "- Scripts: create .py file and run python3 file.py\n",
        "- Objects & Types\n",
        "  - All data treated as objects\n",
        "  - Strongly typed: every object has a fixed type, interpreter doesn't allow things incompatible with that type\n",
        "    - Check using type(object) or isinstance(object, type)\n",
        "    - Types: int, float, str, tuple, dict, list, bool, None, generator, function\n",
        "  - Python: dynamic typing - variables come into existence when first assigned\n",
        "    - Java: static typing - variables need type to be explicitly defined\n",
        "    - Functions have no type signatures\n",
        "    - Con: type errors only caught at runtime\n",
        "- Strings: print(\"%s can speak %d languages\" %(\"C3PO\", 5000))\n",
        "  - Immutable\n",
        "    - '==' checks whether variables point to objects of same value\n",
        "    - 'is' checks whether variables point to same object\n",
        "- Lists are mutable\n",
        "  - y=x[:] gets shallow copy of any sequence\n",
        "  - Operations: .append(), .insert(2,'i'), .index('b'), .count('b'), .remove('b'), .reverse(); .sort()\n",
        "- Dictionaries\n",
        "  - Unordered & work by hashing (so keys must be immutable)\n",
        "  - from collections import defaultdict, Counter\n",
        "    - defaultdict automatically initializes nonexistent dictionary values\n",
        "    - if d=Counter, d['dog'] += 10; d['dog'] would print dog\n",
        "- Functions\n",
        "  - Returns None if no return defined\n",
        "  - No declaration of types of arguments or result\n",
        "  - Python allows you to return multiple values (tuple)\n",
        "  - Python does not allow function overloading like Java (which allows add(int) and add(int,int))\n",
        "    - Allows operator overloading (+, ==, -, etc)\n",
        "  - Can specify default values for function's arguments\n",
        "    - Non-default argument should always precede default arguments; otherwise SyntaxError\n",
        "  - *args: suppose you want to accept a variable # of non-keyword arguments to your function\n",
        "    - args = tuple of arguments passed to fn\n",
        "    - Can just pass in parameters\n",
        "    - Can pass in list of parameters: when called, precede with * (print_everything(*lst))\n",
        "  - **kwargs: suppose you want to accept a variable # of keyword arguments to your function\n",
        "    - kwargs = dict of keyword args pass to fn\n",
        "    - example(first='John', last='Doe') => {'first':'John', 'last':'Doe'}\n",
        "    - Can pass in dictionary of parameters (print_everything(**my_dict))\n",
        "  - Uses dynamic scope: function sees most current value of variables (even if not defined within function)\n",
        "  - Memoization: optimization technique used to store the results of expensive function calls and returns a cached result\n",
        "  - \"First-class\" objects: entity can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n",
        "- Classes & Inheritance\n",
        "  - Subclass extends parent/ancestor/superclass\n",
        "    - To define: put name of superclass in parentheses after subclass's name on first line of definition (class AI_Student(Student):)\n",
        "    - To override method in parent class: just use same name of method\n",
        "    - If need to call parent's method version, explicitly pass in 'self' as argument: parentClass.methodName(self,a,b,c)\n",
        "- \"Magic\" methods: \\\\_\\\\_init\\\\_\\\\_, \\\\_\\\\_len\\\\_\\\\_, \\\\_\\\\_copy\\\\_\\\\_, \\\\_\\\\_cmp\\\\_\\\\_ (==), \\\\_\\\\_add\\\\_\\\\_, \\\\_\\\\_neg\\\\_\\\\_\n",
        "- if \\\\_\\\\_name\\\\_\\\\_ == '\\\\_\\\\_main\\\\_\\\\_':\n",
        "  - \\\\_\\\\_name\\\\_\\\\_: built-in variable which evaluates to the name of the current module\n",
        "  - Interpreter sets \\\\_\\\\_name\\\\_\\\\_ variable to have value '\\\\_\\\\_main\\\\_\\\\_' for source file that is being executed on command line\n",
        "  - No built-in main method (no \"def main()\")\n",
        "- Duck typing: establishes suitability of an object by determining presence of methods\n",
        "- Generators: iterators (with \\\\_\\\\_next()\\\\_\\\\_ method) using yield keyword\n",
        "  - Each time we call \\\\_\\\\_next\\\\_\\\\_ method of generator, method runs until it encounters a yield statement, stops, and returns value that was yielded\n",
        "  - Next time, resumes where it left off\n",
        "  - Benefits:\n",
        "    - Less code than writing a standard iterator\n",
        "    - Maintains local state automatically\n",
        "    - Values are computed one at a time as needed\n",
        "    - Avoids storing entire sequence in memory\n",
        "    - Good for aggregating (summing, counting) items. One pass\n",
        "    - Curcial for infinite sequences\n",
        "    - Bad if need to inspect individual values\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 87,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b09d6005-e3d4-49c1-b363-e6282c349e57"
      },
      "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": 88,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n- Developed by Guido van Rossum in 1989\n- Python inspired by ABC language\n- Positive features: fast development (concise, intuitive, garbage collected); portable (progs run on major platforms w/o change); various built-in types; large collection of support libraries\n- PEP: Python Enhancement Proposals\n- REPL: Read-Evaluate-Print Loop (type python3 in terminal)\n- Scripts: create .py file and run python3 file.py\n- Objects & Types\n  - All data treated as objects\n  - Strongly typed: every object has a fixed type, interpreter doesn't allow things incompatible with that type\n    - Check using type(object) or isinstance(object, type)\n    - Types: int, float, str, tuple, dict, list, bool, None, generator, function\n  - Python: dynamic typing - variables come into existence when first assigned\n    - Java: static typing - variables need type to be explicitly defined\n    - Functions have no type signatures\n    - Con: type errors only caught at runtime\n- Strings: print(\"%s can speak %d languages\" %(\"C3PO\", 5000))\n  - Immutable\n    - '==' checks whether variables point to objects of same value\n    - 'is' checks whether variables point to same object\n- Lists are mutable\n  - y=x[:] gets shallow copy of any sequence\n  - Operations: .append(), .insert(2,'i'), .index('b'), .count('b'), .remove('b'), .reverse(); .sort()\n- Dictionaries\n  - Unordered & work by hashing (so keys must be immutable)\n  - from collections import defaultdict, Counter\n    - defaultdict automatically initializes nonexistent dictionary values\n    - if d=Counter, d['dog'] += 10; d['dog'] would print dog\n- Functions\n  - Returns None if no return defined\n  - No declaration of types of arguments or result\n  - Python allows you to return multiple values (tuple)\n  - Python does not allow function overloading like Java (which allows add(int) and add(int,int))\n    - Allows operator overloading (+, ==, -, etc)\n  - Can specify default values for function's arguments\n    - Non-default argument should always precede default arguments; otherwise SyntaxError\n  - *args: suppose you want to accept a variable # of non-keyword arguments to your function\n    - args = tuple of arguments passed to fn\n    - Can just pass in parameters\n    - Can pass in list of parameters: when called, precede with * (print_everything(*lst))\n  - **kwargs: suppose you want to accept a variable # of keyword arguments to your function\n    - kwargs = dict of keyword args pass to fn\n    - example(first='John', last='Doe') => {'first':'John', 'last':'Doe'}\n    - Can pass in dictionary of parameters (print_everything(**my_dict))\n  - Uses dynamic scope: function sees most current value of variables (even if not defined within function)\n  - Memoization: optimization technique used to store the results of expensive function calls and returns a cached result\n  - \"First-class\" objects: entity can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n- Classes & Inheritance\n  - Subclass extends parent/ancestor/superclass\n    - To define: put name of superclass in parentheses after subclass's name on first line of definition (class AI_Student(Student):)\n    - To override method in parent class: just use same name of method\n    - If need to call parent's method version, explicitly pass in 'self' as argument: parentClass.methodName(self,a,b,c)\n- \"Magic\" methods: \\_\\_init\\_\\_, \\_\\_len\\_\\_, \\_\\_copy\\_\\_, \\_\\_cmp\\_\\_ (==), \\_\\_add\\_\\_, \\_\\_neg\\_\\_\n- if \\_\\_name\\_\\_ == '\\_\\_main\\_\\_':\n  - \\_\\_name\\_\\_: built-in variable which evaluates to the name of the current module\n  - Interpreter sets \\_\\_name\\_\\_ variable to have value '\\_\\_main\\_\\_' for source file that is being executed on command line\n  - No built-in main method (no \"def main()\")\n- Duck typing: establishes suitability of an object by determining presence of methods\n- Generators: iterators (with \\_\\_next()\\_\\_ method) using yield keyword\n  - Each time we call \\_\\_next\\_\\_ method of generator, method runs until it encounters a yield statement, stops, and returns value that was yielded\n  - Next time, resumes where it left off\n  - Benefits:\n    - Less code than writing a standard iterator\n    - Maintains local state automatically\n    - Values are computed one at a time as needed\n    - Avoids storing entire sequence in memory\n    - Good for aggregating (summing, counting) items. One pass\n    - Curcial for infinite sequences\n    - Bad if need to inspect individual values\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "- Four-phase problem-solving process:\n",
        "  - Goal formulation\n",
        "  - Problem formulation\n",
        "  - Search (simulate sequences of actions in its model)\n",
        "  - Execution (execuate actions in solution one at a time)\n",
        "- Total cost of path=sum of individual action costs\n",
        "- State space represented as graph (vertices=states; directed edges=actions)\n",
        "- Abstraction=valid if can elaborate any abstract solution into solution in more detailed world\n",
        "- Abstraction=useful if carrying out each action in solution is easier than original problem\n",
        "- Choice of good abstraction: remove as much detail as possible while retaining validity and ensuring abstract actions are easy to carry out\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "- Every problem formulation involves abstractions\n",
        "- Touring problems: describe a set of locations that must be visited rather than a single goal destination\n",
        "- VLSI (Very large-scale integration) layout problem: split into cell layout and channel routing\n",
        "- Other types: robot navigation, automatic assembly sequencing\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "- How do we decide which node from the frontier to expand next?\n",
        "  - Best-first search: choose a node n with minimum value of some evaluation function f(n)\n",
        "    - On each iteration, we choose a node on the frontier with minimum f(n) value, return it if its state is a goal state; otherwise apply expand to generate child nodes\n",
        "    - Each child node added to frontier: either never been visited or re-added if now being reached with path with lower path cost than previous path\n",
        "    - Return indication of failure or node that represents a path to goal\n",
        "- Node represented by: state, parent, action, path cost (total cost of path from initial state to this node)\n",
        "- 3approaches to remembering previous states:\n",
        "  - Remember all previously reached states: appropriate when many redundant paths & preferred when table of reached states fit in memory\n",
        "  - Just not worry about repeating past: use when reaching same state is rare; save memory space and don't check for redundant paths\n",
        "    - Graph search: checks for redundant paths\n",
        "    - Tree-like search: does not check\n",
        "  - Check for cycles but not redundant paths in general\n",
        "    - Can check for cycles with no need for additional memory by following up chain of parents to see if the state at end of path has appeared earlier in path\n",
        "- Complete algorithm must be capable of systematically exploring every state that is reachable from initial state\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "- Uninformed search algorithm: given no clue about how close a state is to goals\n",
        "- BFS: reached can be set of states rather than mapping from states to nodes because once we've reached a state, we can never find a better path to the state\n",
        "  - Early goal test: checking whether a node is a solution as soon as it's generated\n",
        "  - Best-first search uses late goal test (waiting until node is popped off queue)\n",
        "  - Cost-optimal for problems where all actions have same cost; otherwise no\n",
        "  - Memory requirements are bigger problem than execution time\n",
        "- Dijkstra's algorithm / uniform-cost search: when actions have different costs-> use best-first search where eval function is cost of path from root to current node\n",
        "  - Uniform-cost search spreads out in waves of uniform path-cost\n",
        "  - Complete and is cost-optimal because the first solution it finds will have a cost that is at least as low as the cost of any other node in frontier\n",
        "- DFS: variant called backtracking search uses even less memory\n",
        "  - Only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next\n",
        "  - Successors are generated by modifying the current state description directly rather than allocating memory for a brand-new state\n",
        "  - Reduces memory requirements to just O(m)\n",
        "- Bidirectional search: simultaneously searches forward from initial state and backwards from goal state, hoping that two searches will meet\n",
        "  - Need to keep track of two frontiers and two tables of reached states\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "- Problem-solving agent plans ahead and considers a sequence of actions that form a path to a goal state (search for a solution)\n",
        "- If environment is fully observable, deterministic, known: solution=fixed sequence of actions\n",
        "- If partially observable or nondeterministic: solution must recommend different future actions depending on what the percept receives (could be form of branching strategy)\n",
        "- Defining search problem: states, initial state, actions, transition model, path cost (performance measure), goal test\n",
        "  - Path cost: sum of all action costs along a path\n",
        "- When formulating search problem, decide:\n",
        "  - Which properties matter & how to represent (initial/intermediate/goal states)\n",
        "  - Which actions are possible & how to represent (actions/transition model)\n",
        "  - Which action is next (path cost function)\n",
        "- Formulation greatly affects combinatorics of search space and therefore speed of search\n",
        "- State space: set of all states reachable from initial state by any sequence of actions\n",
        "  - When several operators can apply to each state, this gets large very quickly\n",
        "  - Might be proper subset of the set of configurations\n",
        "- Path: sequence of actions leading from one state sj -> state sk\n",
        "- Solution: path from initial state si to state sf that satisfies the goal test\n",
        "- Search tree: way of representing paths that search algorithm has explored. Root=initial state, leaves=successors.\n",
        "- Frontier: those states that are available for expanding (for applying legal actions to)\n",
        "- Optimal solution: if no solution has lower path cost\n",
        "- Generalized algorithm to solve searches: enumerate in some order all possible paths from initial state\n",
        "- State=physical configuration (no parents,children,etc); node=data structure constituting part of search tree\n",
        "- Failure to detect repeated states-> turn linear problem into exponential\n",
        "  - Graph search: check if node has been visited before adding to search queue\n",
        "- Uninformed: all non-goal nodes in frontier look equally good; Informed: some non-goal nodes can be ranked higher\n",
        "- Dimensions for evaluation: completeness (always solution?), optimality (lowest path cost first?), time (# nodes generated) & space (# nodes simultaneously in memory) complexity\n",
        "- Time/space variables: b(max branching factor); d(depth of shallowest goal node); m(max length of any path in state space)\n",
        "- BFS(FIFO): expand shallowest unexpanded node; use if: possible infinite paths; some solutions have short paths and wrong paths are usually terminated quickly; can quickly discard unlikely paths\n",
        "- DFS(LIFO): expand deepest unexpanded node; use if: space is restricted; many possible solutions with long paths; search can be fine-tuned quickly\n",
        "- Depth-limited: DFS with depthlimit 1; if l<d:incomplete; l>d:not optimal\n",
        "- Iterative deepening search: depth-limited as subroutine with increasing l\n",
        "  - Complete & optimal: goal always found at depth d\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",
        "\"open-loop approach\": \"agent executes action in solutions without monitoring percepts (risky if model incorrect)\",\n",
        "\"closed-loop approach\": \"agent monitors percepts (necessary for nondeterministic)\",\n",
        "\"state space\": \"set of possible states of environment\",\n",
        "\"transition model\": \"describes what an action in a given state does\",\n",
        "\"action cost function\": \"assigns numeric cost of doing action a in state s to reach s'\",\n",
        "\"abstraction\": \"removing detail from representation\",\n",
        "\"standardized problem\": \"used to show various problem-solving methods\",\n",
        "\"real-world problem\": \"solutions are actually applicable and formulation are unique (not standardized)\",\n",
        "\"absolute actions\": \"actions of absolute values\",\n",
        "\"egocentric actions\": \"defined relative to viewpoint of agent\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 89,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "04e4e5bd-94bb-4d07-8bfb-e1a771d891a7"
      },
      "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": 90,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n- Four-phase problem-solving process:\n  - Goal formulation\n  - Problem formulation\n  - Search (simulate sequences of actions in its model)\n  - Execution (execuate actions in solution one at a time)\n- Total cost of path=sum of individual action costs\n- State space represented as graph (vertices=states; directed edges=actions)\n- Abstraction=valid if can elaborate any abstract solution into solution in more detailed world\n- Abstraction=useful if carrying out each action in solution is easier than original problem\n- Choice of good abstraction: remove as much detail as possible while retaining validity and ensuring abstract actions are easy to carry out\n\n\n## AIMA Chapter 3.2 Example Problems\n\n- Every problem formulation involves abstractions\n- Touring problems: describe a set of locations that must be visited rather than a single goal destination\n- VLSI (Very large-scale integration) layout problem: split into cell layout and channel routing\n- Other types: robot navigation, automatic assembly sequencing\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n- How do we decide which node from the frontier to expand next?\n  - Best-first search: choose a node n with minimum value of some evaluation function f(n)\n    - On each iteration, we choose a node on the frontier with minimum f(n) value, return it if its state is a goal state; otherwise apply expand to generate child nodes\n    - Each child node added to frontier: either never been visited or re-added if now being reached with path with lower path cost than previous path\n    - Return indication of failure or node that represents a path to goal\n- Node represented by: state, parent, action, path cost (total cost of path from initial state to this node)\n- 3approaches to remembering previous states:\n  - Remember all previously reached states: appropriate when many redundant paths & preferred when table of reached states fit in memory\n  - Just not worry about repeating past: use when reaching same state is rare; save memory space and don't check for redundant paths\n    - Graph search: checks for redundant paths\n    - Tree-like search: does not check\n  - Check for cycles but not redundant paths in general\n    - Can check for cycles with no need for additional memory by following up chain of parents to see if the state at end of path has appeared earlier in path\n- Complete algorithm must be capable of systematically exploring every state that is reachable from initial state\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- Uninformed search algorithm: given no clue about how close a state is to goals\n- BFS: reached can be set of states rather than mapping from states to nodes because once we've reached a state, we can never find a better path to the state\n  - Early goal test: checking whether a node is a solution as soon as it's generated\n  - Best-first search uses late goal test (waiting until node is popped off queue)\n  - Cost-optimal for problems where all actions have same cost; otherwise no\n  - Memory requirements are bigger problem than execution time\n- Dijkstra's algorithm / uniform-cost search: when actions have different costs-> use best-first search where eval function is cost of path from root to current node\n  - Uniform-cost search spreads out in waves of uniform path-cost\n  - Complete and is cost-optimal because the first solution it finds will have a cost that is at least as low as the cost of any other node in frontier\n- DFS: variant called backtracking search uses even less memory\n  - Only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next\n  - Successors are generated by modifying the current state description directly rather than allocating memory for a brand-new state\n  - Reduces memory requirements to just O(m)\n- Bidirectional search: simultaneously searches forward from initial state and backwards from goal state, hoping that two searches will meet\n  - Need to keep track of two frontiers and two tables of reached states\n\n\n## Module 3 Lecture Notes\n\n- Problem-solving agent plans ahead and considers a sequence of actions that form a path to a goal state (search for a solution)\n- If environment is fully observable, deterministic, known: solution=fixed sequence of actions\n- If partially observable or nondeterministic: solution must recommend different future actions depending on what the percept receives (could be form of branching strategy)\n- Defining search problem: states, initial state, actions, transition model, path cost (performance measure), goal test\n  - Path cost: sum of all action costs along a path\n- When formulating search problem, decide:\n  - Which properties matter & how to represent (initial/intermediate/goal states)\n  - Which actions are possible & how to represent (actions/transition model)\n  - Which action is next (path cost function)\n- Formulation greatly affects combinatorics of search space and therefore speed of search\n- State space: set of all states reachable from initial state by any sequence of actions\n  - When several operators can apply to each state, this gets large very quickly\n  - Might be proper subset of the set of configurations\n- Path: sequence of actions leading from one state sj -> state sk\n- Solution: path from initial state si to state sf that satisfies the goal test\n- Search tree: way of representing paths that search algorithm has explored. Root=initial state, leaves=successors.\n- Frontier: those states that are available for expanding (for applying legal actions to)\n- Optimal solution: if no solution has lower path cost\n- Generalized algorithm to solve searches: enumerate in some order all possible paths from initial state\n- State=physical configuration (no parents,children,etc); node=data structure constituting part of search tree\n- Failure to detect repeated states-> turn linear problem into exponential\n  - Graph search: check if node has been visited before adding to search queue\n- Uninformed: all non-goal nodes in frontier look equally good; Informed: some non-goal nodes can be ranked higher\n- Dimensions for evaluation: completeness (always solution?), optimality (lowest path cost first?), time (# nodes generated) & space (# nodes simultaneously in memory) complexity\n- Time/space variables: b(max branching factor); d(depth of shallowest goal node); m(max length of any path in state space)\n- BFS(FIFO): expand shallowest unexpanded node; use if: possible infinite paths; some solutions have short paths and wrong paths are usually terminated quickly; can quickly discard unlikely paths\n- DFS(LIFO): expand deepest unexpanded node; use if: space is restricted; many possible solutions with long paths; search can be fine-tuned quickly\n- Depth-limited: DFS with depthlimit 1; if l<d:incomplete; l>d:not optimal\n- Iterative deepening search: depth-limited as subroutine with increasing l\n  - Complete & optimal: goal always found at depth d\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop approach** - agent executes action in solutions without monitoring percepts (risky if model incorrect)\n* **Closed-loop approach** - agent monitors percepts (necessary for nondeterministic)\n* **State space** - set of possible states of environment\n* **Transition model** - describes what an action in a given state does\n* **Action cost function** - assigns numeric cost of doing action a in state s to reach s'\n* **Abstraction** - removing detail from representation\n* **Standardized problem** - used to show various problem-solving methods\n* **Real-world problem** - solutions are actually applicable and formulation are unique (not standardized)\n* **Absolute actions** - actions of absolute values\n* **Egocentric actions** - defined relative to viewpoint of agent\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Qr3RpTvLpi-B"
      },
      "source": [
        "| Criterion   | BFS   | DFS   | Depth-Limited   | Iterative deepening | Uniform-Cost | Bidirectional |\n",
        "| ----------- | :---: | :---: | :-------------: | :-----------------: | :---: | :---: |\n",
        "| Complete?   | Yes (if b finite)  | No (unless m bounded)   | No              | Yes (if b finite) | Yes (b finite) | Yes (b finite; both directions BFS or uniform)\n",
        "| Time        | b^d   | b^m  (terrible if m>>d) | b^l             | b^d | b^(l+[C*/error]) | b^(d/2) |\n",
        "| Space       | b^d   | bm    | bl              | bd  | b^(l+[C*/error]) | b^(d/2) |\n",
        "| Optimal?    | Yes (if costs identical)   | No    | No (unless l=d)             | Yes (if step cost=1) | Yes | Yes (costs identical, both directions BFS or uniform)"
      ]
    },
    {
      "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 first node with lowest h(n) (likely find sol quickly)\n",
        "  - Straight-line distance for route-finding probs \n",
        "\t- Complete only in finite \n",
        "\t- Worst-case time/space complexity: O(|V|)\n",
        "- A* search: complete\n",
        "\t- Cost-optimal depends on admissibility & consistency of h(n)\n",
        "\t\t- If admissible, A*=cost-optimal\n",
        "\t\t- Every consistent h(n) is admissible (not vice versa) therefore cost-optimal\n",
        "\t\t- 1st time reach state-> on optimal path so never have to re-add state to frontier or change entry in reached\n",
        "\t\t- If inadmissible, may be cost-optimal if:\n",
        "\t\t\t- There's even 1 cost-optimal path on which h(n) is admissible for all nodes n on path, then that path will be found, no matter what h(n) says for states off path\n",
        "\t\t\t- Optimal sol has cost C*, 2nd best=C2, & if h(n) overestimates some costs but never by more than C2-C*, then A* guaranteed to return cost-optimal sols\n",
        "- f=g+h cost monotonically increase iff h consistent\n",
        "- A*=efficient bc prunes away search tree nodes not necessary for finding optimal sol\n",
        "- Satisficing sols: suboptimal, but \"good enough\" (explore fewer nodes, saving time/space)\n",
        "\t- Using inadmissible h(n), risk missing optimal sol, but may be more accurate\n",
        "- Weighted A*: weight h(n) more heavily (Somewhat-greedy: Like greedy best-first search, focus search towards goal but won't ignore path cost completely & will suspend path that's making little progress at great cost)\n",
        "- Suboptimal search alg:\n",
        "\t- Bounded: look for sol guaranteed to be within constant factor of optimal cost\n",
        "\t- Bounded-cost: look for sol where cost < constant\n",
        "\t- Unbounded-cost: accept sol of any cost just find quickly\n",
        "\t\t- Speedy search: version of greedy best-first where h(n)=est.# actions required to reach goal, regardless of cost of actions\n",
        "- A* memory-intensive\n",
        "- Beam search limits size of frontier by keeping only k-nodes w/ best f-scores\n",
        "\t- Incomplete & suboptimal, but better use of memory & faster\n",
        "\t- Alt: keep node whose f-score is within x of the best f-score\n",
        "- Iterative-deepening A*: A* w/o requirement to keep all reached states in memory at cost of visiting some states multiple times\n",
        "- Recursive best-first search: mimic operation of standard best-first search but only using linear space\n",
        "  - Like recursive DFS, but use f_limit variable to track f of best alt path avail. from any ancestor of current node\n",
        "  - If current node > limit, recursion unwinds back to alt path; as unwinds, RBFS replaces f for each node along path w/ backed-up val (best f of children)\n",
        "\t- Bit more efficient than IDA*, but still suffers from excessive node generation\n",
        "\t- Optimal if h(n) admissible\n",
        "  - Space complexity=linear (time hard to say)\n",
        "- IDA & RBFS use too little memory: try use all\n",
        "\t- Simplified MA*: like A*, expand best leaf until memory full, drop oldest worst leaf node (one w/ highest f), then back up val of forgotten node (like RBFS)\n",
        "    - Complete if any reachable sol (d < memory size)\n",
        "    - Optimal if any optimal sol is reachable; else returns best reachable sol\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "- One way to characterize quality of a heuristic is the effective branching factor b*\n",
        "\t- Well-designed heuristic: b* close to 1, allowing fairly large problems to be solved at reasonable computational cost\n",
        "- Better way to characterize effect of A* pruning w/ a given heuristic is that it reduces the effective depth by a constant k compared to the true depth\n",
        "  - Total search cost: O(b^(d-k)) instead of O(b^d)\n",
        "- If one heuristic basically always outperforms another, we say it dominates\n",
        "\t- Domination translates directly into efficiency (A* using dominating heuristic will never expand more nodes than A* using other heuristic)\n",
        "- Generally better to use heuristic function with higher values, provided it is consistent and that the computation time for the heuristic is not too long\n",
        "- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "- Can generate relaxed problems by removing one or multiple conditions\n",
        "  - Crucial that relaxed problems generated by this technique can be solved essentially without search bc relaxed rules allow the problem to be decomposed into independent problems\n",
        "\t  - If the relaxed problem is hard to solve, then values of the corresponding heuristic will be expensive to obtain\n",
        "- Program called ABSOLVER can generate heuristics automatically from problem definitions\n",
        "- Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem\n",
        "  - Cost of optimal solution of subproblem is a lower bound on the cost of the complete problem\n",
        "- Use pattern databases: compute admissible heuristic for each state encountered during a search simply by looking up the corresponding subproblem config in database\n",
        "  - Each database yields admissible heuristic, and these heuristics can be combined by taking the maximum value\n",
        "- Precomputation takes time, but only needs to be done once\n",
        "\t- Could generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices, but would be very expensive\n",
        "\t- Better approach: choose a few landmark points from the vertices\n",
        "\t\t- For each landmark L and for each other vertex v in the graph, we compute and store C*(v,L), the exact cost of the optimal path from v to L\n",
        "- Pick landmark points that are pretty spread out (can use greedy approach)\n",
        "- Agents can learn how to search better -- metalevel state space\n",
        "\t- Each state in a metalevel state space captures the internal state of a program that is searching in an ordinary state space\n",
        "- Goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost\n",
        "- Some ML techniques work better when supplied with features of a state that are relevant to predicting the state's heuristic value, rather than with just the raw state description\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "- Uniform-cost search (UCS): \"Uniform\" means going to uniformly explore the space before exploring next batch\n",
        "- UCS= extension of BFS except expand node with lowest path cost\n",
        "  - Frontier: priority queue ordered by g(n)\n",
        "  - Different form BFS in that test if node=goal when selected for expansion, not when added to frontier\n",
        "- Best-first search: node selected for expansion based on evaluation function f(n) (priority queue uses f(n))\n",
        "  - Greedy best-first search: f(n) = h(n)\n",
        "    - Not optimal or complete (get stuck in loops)\n",
        "- A* search: avoid expanding paths that are already expensive, but expand most promising first (f(n)=g(n)+h(n))\n",
        "  - g(n): path cost from initial state to node n\n",
        "\t- h(n): est cost of shortest path from n to goal state\n",
        "\t- f(n): est cost of best path that continues from n to goal\n",
        "  - Admissible: never overestimates cost to reach goal\n",
        "    - If admissible, A*=optimal\n",
        "    - Inadmissible (pessimistic): break optimality by trapping good plans on frontier\n",
        "    - Admissible (optimistic): heuristics slow down bad plans but never outweigh true costs\n",
        "- Relaxed problem: problem with fewer restrictions on actions than original\n",
        "- Cost of optimal solution to relaxed problem is admissible heuristic for original problem\n",
        "- If h2>=h1 for all n, h2 dominates h1\n",
        "- A* expands mainly toward the goal unlike UCS which expands equally in all directions\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible\": \"never overestimates cost to reach goal\",\n",
        "\"consistency\": \"for every node n and every successor n' of n generated by an action a, we have h(n)<=c(n,a,n')+h(n')\",\n",
        "\"relaxed problem\": \"problem with fewer restrictions on actions\",\n",
        "\"pattern databases\": \"store solution costs for every subproblem\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 91,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qjf8GUzuMsSk",
        "outputId": "6dee3e92-a022-4529-efcc-a1f9c9ad3653"
      },
      "source": [
        "len(chapter3_5.split(\" \"))\n",
        "len(chapter3_5)"
      ],
      "execution_count": 92,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2999"
            ]
          },
          "metadata": {},
          "execution_count": 92
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "32e2c96f-a110-4fbd-b6b1-4b530d30bb1d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 93,
      "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 first node with lowest h(n) (likely find sol quickly)\n  - Straight-line distance for route-finding probs \n\t- Complete only in finite \n\t- Worst-case time/space complexity: O(|V|)\n- A* search: complete\n\t- Cost-optimal depends on admissibility & consistency of h(n)\n\t\t- If admissible, A*=cost-optimal\n\t\t- Every consistent h(n) is admissible (not vice versa) therefore cost-optimal\n\t\t- 1st time reach state-> on optimal path so never have to re-add state to frontier or change entry in reached\n\t\t- If inadmissible, may be cost-optimal if:\n\t\t\t- There's even 1 cost-optimal path on which h(n) is admissible for all nodes n on path, then that path will be found, no matter what h(n) says for states off path\n\t\t\t- Optimal sol has cost C*, 2nd best=C2, & if h(n) overestimates some costs but never by more than C2-C*, then A* guaranteed to return cost-optimal sols\n- f=g+h cost monotonically increase iff h consistent\n- A*=efficient bc prunes away search tree nodes not necessary for finding optimal sol\n- Satisficing sols: suboptimal, but \"good enough\" (explore fewer nodes, saving time/space)\n\t- Using inadmissible h(n), risk missing optimal sol, but may be more accurate\n- Weighted A*: weight h(n) more heavily (Somewhat-greedy: Like greedy best-first search, focus search towards goal but won't ignore path cost completely & will suspend path that's making little progress at great cost)\n- Suboptimal search alg:\n\t- Bounded: look for sol guaranteed to be within constant factor of optimal cost\n\t- Bounded-cost: look for sol where cost < constant\n\t- Unbounded-cost: accept sol of any cost just find quickly\n\t\t- Speedy search: version of greedy best-first where h(n)=est.# actions required to reach goal, regardless of cost of actions\n- A* memory-intensive\n- Beam search limits size of frontier by keeping only k-nodes w/ best f-scores\n\t- Incomplete & suboptimal, but better use of memory & faster\n\t- Alt: keep node whose f-score is within x of the best f-score\n- Iterative-deepening A*: A* w/o requirement to keep all reached states in memory at cost of visiting some states multiple times\n- Recursive best-first search: mimic operation of standard best-first search but only using linear space\n  - Like recursive DFS, but use f_limit variable to track f of best alt path avail. from any ancestor of current node\n  - If current node > limit, recursion unwinds back to alt path; as unwinds, RBFS replaces f for each node along path w/ backed-up val (best f of children)\n\t- Bit more efficient than IDA*, but still suffers from excessive node generation\n\t- Optimal if h(n) admissible\n  - Space complexity=linear (time hard to say)\n- IDA & RBFS use too little memory: try use all\n\t- Simplified MA*: like A*, expand best leaf until memory full, drop oldest worst leaf node (one w/ highest f), then back up val of forgotten node (like RBFS)\n    - Complete if any reachable sol (d < memory size)\n    - Optimal if any optimal sol is reachable; else returns best reachable sol\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- One way to characterize quality of a heuristic is the effective branching factor b*\n\t- Well-designed heuristic: b* close to 1, allowing fairly large problems to be solved at reasonable computational cost\n- Better way to characterize effect of A* pruning w/ a given heuristic is that it reduces the effective depth by a constant k compared to the true depth\n  - Total search cost: O(b^(d-k)) instead of O(b^d)\n- If one heuristic basically always outperforms another, we say it dominates\n\t- Domination translates directly into efficiency (A* using dominating heuristic will never expand more nodes than A* using other heuristic)\n- Generally better to use heuristic function with higher values, provided it is consistent and that the computation time for the heuristic is not too long\n- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n- Can generate relaxed problems by removing one or multiple conditions\n  - Crucial that relaxed problems generated by this technique can be solved essentially without search bc relaxed rules allow the problem to be decomposed into independent problems\n\t  - If the relaxed problem is hard to solve, then values of the corresponding heuristic will be expensive to obtain\n- Program called ABSOLVER can generate heuristics automatically from problem definitions\n- Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem\n  - Cost of optimal solution of subproblem is a lower bound on the cost of the complete problem\n- Use pattern databases: compute admissible heuristic for each state encountered during a search simply by looking up the corresponding subproblem config in database\n  - Each database yields admissible heuristic, and these heuristics can be combined by taking the maximum value\n- Precomputation takes time, but only needs to be done once\n\t- Could generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices, but would be very expensive\n\t- Better approach: choose a few landmark points from the vertices\n\t\t- For each landmark L and for each other vertex v in the graph, we compute and store C*(v,L), the exact cost of the optimal path from v to L\n- Pick landmark points that are pretty spread out (can use greedy approach)\n- Agents can learn how to search better -- metalevel state space\n\t- Each state in a metalevel state space captures the internal state of a program that is searching in an ordinary state space\n- Goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost\n- Some ML techniques work better when supplied with features of a state that are relevant to predicting the state's heuristic value, rather than with just the raw state description\n\n\n## Module 4 Lecture Notes\n\n- Problem-solving agent plans ahead and considers a sequence of actions that form a path to a goal state (search for a solution)\n- If environment is fully observable, deterministic, known: solution=fixed sequence of actions\n- If partially observable or nondeterministic: solution must recommend different future actions depending on what the percept receives (could be form of branching strategy)\n- Defining search problem: states, initial state, actions, transition model, path cost (performance measure), goal test\n  - Path cost: sum of all action costs along a path\n- When formulating search problem, decide:\n  - Which properties matter & how to represent (initial/intermediate/goal states)\n  - Which actions are possible & how to represent (actions/transition model)\n  - Which action is next (path cost function)\n- Formulation greatly affects combinatorics of search space and therefore speed of search\n- State space: set of all states reachable from initial state by any sequence of actions\n  - When several operators can apply to each state, this gets large very quickly\n  - Might be proper subset of the set of configurations\n- Path: sequence of actions leading from one state sj -> state sk\n- Solution: path from initial state si to state sf that satisfies the goal test\n- Search tree: way of representing paths that search algorithm has explored. Root=initial state, leaves=successors.\n- Frontier: those states that are available for expanding (for applying legal actions to)\n- Optimal solution: if no solution has lower path cost\n- Generalized algorithm to solve searches: enumerate in some order all possible paths from initial state\n- State=physical configuration (no parents,children,etc); node=data structure constituting part of search tree\n- Failure to detect repeated states-> turn linear problem into exponential\n  - Graph search: check if node has been visited before adding to search queue\n- Uninformed: all non-goal nodes in frontier look equally good; Informed: some non-goal nodes can be ranked higher\n- Dimensions for evaluation: completeness (always solution?), optimality (lowest path cost first?), time (# nodes generated) & space (# nodes simultaneously in memory) complexity\n- Time/space variables: b(max branching factor); d(depth of shallowest goal node); m(max length of any path in state space)\n- BFS(FIFO): expand shallowest unexpanded node; use if: possible infinite paths; some solutions have short paths and wrong paths are usually terminated quickly; can quickly discard unlikely paths\n- DFS(LIFO): expand deepest unexpanded node; use if: space is restricted; many possible solutions with long paths; search can be fine-tuned quickly\n- Depth-limited: DFS with depthlimit 1; if l<d:incomplete; l>d:not optimal\n- Iterative deepening search: depth-limited as subroutine with increasing l\n  - Complete & optimal: goal always found at depth d\n\n\n## Module 4 Definitions\n* **Admissible** - never overestimates cost to reach goal\n* **Consistency** - for every node n and every successor n' of n generated by an action a, we have h(n)<=c(n,a,n')+h(n')\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Pattern databases** - store solution costs for every subproblem\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",
        "- 3 stances we can take towards multiagent environments:\n",
        "  - Aggregate as economy: appropriate when large \\# of agents; allows us to predict on aggregate w/o having to predict action of any individual agent\n",
        "  - Consider adversarial agents as just part of environment (makes it nondeterministic)\n",
        "  - Explicitly model aversarial agents with techniques of adversarial game-tree search\n",
        "- Won't have enough time to be sure of optimal move (even with pruning) in nontrivial games; need to cut off search at some point\n",
        "  - For each state where choose to stop searching, ask who's winning:\n",
        "    - Apply eval function\n",
        "    - Avg outcomes of many fast simulations of the game from that state all the way to end\n",
        "- State space graph: initial state, actions function and result\n",
        "- Can superimpose search tree over part of graph to determine\n",
        "- Complete game tree: search tree that follows every sequence of moves all the way to terminal state \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "- Use minimax search for games with multiple outcome scores\n",
        "- \"move\" means that both players have taken an action; \"ply\" means that one player made a move\n",
        "- Given game tree, optimal strategy can be determined by working out the minimax value of each state in the tree [Minimax(s)]\n",
        "\t- Minimax value: utility of being in state, assuming that both players play optimally from there to end of game\n",
        "- Best play not always to make optimal move when facing suboptimal opponent (making riskier move might lead to win instead of draw)\n",
        "- Minimax alg: recursive alg that proceeds all the way down to leaves of tree, then backs up the minimax values through the tree as recursion unwinds\n",
        "  - Performs complete depth-first exploration of game tree\n",
        "\t- If max depth of tree is m and there are b legal moves at each point:\n",
        "\t\t- Time complexity: O(bm)\n",
        "\t\t- Space complexity: O(bm) for alg that generates all actions at once; O(m) for alg that generates actions one at a time\n",
        "- Optimal decisions in multiplayer games\n",
        "  - Must replace the single value for each node with a vector of values (Have utility function return vector of utilities)\n",
        "  - Alliances can be natural consequence of optimal strategies for each player\n",
        "- \\# of game states: exponential in depth of tree\n",
        "\t- Alpha-beta pruning: consider that player has choice of moving to node n\n",
        "    - If player has a better choice either at the same level or at any point higher up in tree, then player will never move to n\n",
        "    - So once we've found out enough about n to reach this conclusion => prune it\n",
        "- Alpha-beta parameters: the value of the best choice we have found so far at any choice point along the path for…\n",
        "\t\t- alpha: MAX (at least)\n",
        "\t\t- beta: MIN (at most)\n",
        "- Effectiveness of alpha-beta pruning is highly dependent on order in which states are examined (could do it in O(b^(m/2)) instead of O(b^m))\n",
        "\t- Iterative deepening: search one ply deep & record ranking of moves based on evaluations; then search one ply deeper using previous ranking to inform move ordering, etc\n",
        "    - Increased search time from this can be more than made up from move ordering\n",
        "\t- Repeated states can occur because of transpositions which can cause exponential increase in search cost\n",
        "\t  - Address problem with transposition table that caches the heuristic value of states\n",
        "\t- Too many states to explore in the time available. Two strategies:\n",
        "\t\t- Type A: considers all possible moves to a certain depth in the search tree and then uses a heuristic evaluation function to estimate the utility of states at that depth\n",
        "\t\t\t- Explores a wide but shallow portion of the tree\n",
        "\t\t\t- Chess\n",
        "\t\t- Type B: ignores moves that look bad and follows promising lines \"as far as possible\"\n",
        "\t\t\t- Explores a deep but narrow portion of the tree\n",
        "      - Go\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "- To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n",
        "\t- Replace utility function with eval (which estimates a state's utility)\n",
        "\t- Replace terminal test by a cutoff test, which must return true for terminal states but is otherwise free to decide when to cut off the search\n",
        "- Heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p\n",
        "\t- What else makes for a good eval function?\n",
        "\t\t- Computation must not take too long\n",
        "\t\t- Eval function should be strongly correlated with the actual chances of winning\n",
        "\t- Most eval functions work by calculating various features of the state: can be too costly\n",
        "    - Eval function doesn't know which states are which, but can return a single value that estimates the proportion of states with each outcome\n",
        "\t\t- Therefore, most in practice compute separate numerical contributions from each feature and then combine them to find the total value\n",
        "\t\t\t- However, assumes that contribution of each feature is independent of values of other features --> can use nonlinear combination of features\n",
        "- When is it appropriate to cut off search?\n",
        "\t- Eval function should only be applied to positions that are quiescent -- positions in which there is no pending move (such as a capturing the queen) that would wildly swing the eval\n",
        "\t\t- Quiescence search is sometimes restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position\n",
        "- Horizon effect: when program is facing an opponent's move that causes serious damage and is ultimately unavoidable but can be temporarily avoided by the use of delaying tactics\n",
        "\t- One way to mitigate: allow singular extensions even when the search would normally be cut off at that point\n",
        "\t\t- Singular extensions: moves that are \"clearly better\" than all other moves in a given position\n",
        "- Forward pruning prunes moves that appear to be poor moves, but might possibly be good ones\n",
        "\t- Saves computation time at risk of making an error (Type B strategy)\n",
        "    - Beam search but no way to guarantee that the best move will not be pruned away\n",
        "\t\t- Probabilistic cut: forward-pruning version of alpha-beta search that uses statistics gained from prior experience to lessen the chance that the best move will be pruned\n",
        "\t\t\t- Computes probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (alpha, beta)\n",
        "\t\t- Late move reduction: moves that appear later in the list of possible moves are less likely to be good moves, so reduce the depth to which we search these moves (instead of pruning away completely)\n",
        "- Search versus lookup: Lookup initial and very end moves because they're easier to anticipate; start searching when state is new and unseen\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- Stochastic games: Games with chance incorporated\n",
        "- Game tree must include chance nodes in addition to max and min nodes\n",
        "- Positions do not have definite minimax values: calculate expected value (average over all possible outcomes of the chance nodes)\n",
        "\t- Expectiminimax value: generalization of minimax value for deterministic games\n",
        "    - For chance nodes: compute expected value (sum of values over all outcomes) weighted by probability of each chance action\n",
        "- To avoid problems where program behaves totally differently if we make a change to some of the eval values (even if preference order is the same)\n",
        "  - Eval function must return values that are a positive linear transformation of probability of winning\n",
        "- Whenever uncertainty enters the picture: possibilities are multiplied enormously and forming detailed plans of action becomes pointless bc the world probably will not play along\n",
        "  - Something like alpha-beta pruning could be applied\n",
        "  - If we put bounds on possible values of utility function, can arrive at bounds for the avg without looking at every number\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "- Agent assigns probability P(s) to each possible current state s\n",
        "- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n",
        "- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n",
        "- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n",
        "- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n",
        "- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n",
        "  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n",
        "- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "- Constraints on rational preferences\n",
        "\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n",
        "\t- Primary issue for utility theory: understand how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n",
        "\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n",
        "\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n",
        "\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
        "\t\t\t- Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p\n",
        "\t\t\t- Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n",
        "\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n",
        "\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n",
        "- 16.2.2 Rational preferences lead to utility\n",
        "\t- From axioms of utility, can derive the following:\n",
        "    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a 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\n",
        "    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n",
        "  - Once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n",
        "\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n",
        "\t\t- Called a value function or ordinal utility function\n",
        "  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "- Preference elicitation: process to work out what a human's utility function is by presenting choices to them and using observed preferences to pin down the underlying utility function\n",
        "- Useful to establish some scale on which utilities can be recorded and compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n",
        "\t- Normalized utilities: scale between 0 and 1\n",
        "- Utility of money almost exactly proportional to log of the amount\n",
        "  - Most people have a utility function that is concave for positive wealth\n",
        "  - Agent with linear curve: risk-neutral\n",
        "- Expected utility and post-decision disappointment\n",
        "\t- Rational way to choose best action: maximize expected utility\n",
        "\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n",
        "\t\t- Therefore working with estimates of true expected utility\n",
        "\t\t- Assume estimates are unbiased: expected value of error is zero\n",
        "- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n",
        "\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n",
        "\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n",
        "- Decision theory = normative theory: describes how a rational agent should act\n",
        "- Descriptive theory: describes how actual agents really do act\n",
        "- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n",
        "\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n",
        "\t- People may distrust the legitimacy of the stated probabilities\n",
        "\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n",
        "- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n",
        "- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n",
        "- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "- Simplest game environment: multiagent, static, discrete, fully observable, strategic (next state is determined by current state and action executed by agent and that of one other agent)\n",
        "- Key properties of game:\n",
        "  - Two players alternate moves\n",
        "  - Zero-sum: one player's loss is another's gain\n",
        "  - Clear set of legal moves\n",
        "  - Well-defined outcomes (win, lose, draw)\n",
        "- General scheme:\n",
        "  - Consider all legal successors to current state (board position)\n",
        "  - Evaluate each successor board position\n",
        "  - Pick move which leads to best board position\n",
        "  - After opponent moves, repeat\n",
        "- Game trees: nodes repesent board positions; edges represent legal moves\n",
        "  - Root node: first position in which a decision must be made\n",
        "  - Eval function f assigns real-number scores to board positions without reference to path\n",
        "    - Based on static features of board alone\n",
        "    - Zero-sum assumption lets us use one function to describe goodness for both players\n",
        "      - f(n)>0 if MAX winning in position n; f(n)=0 if position n is tied; f(n)<0 if MIN winning in position n \n",
        "  - Terminal nodes: represent ways game could end, labeled w/ desirability of that ending\n",
        "- MAX & MIN: MAX attempts to MAXimize MAX's outcome and MIN attempts to MINimize MAX's outcome\n",
        "- Minimax: make best move for MAX assuming that MIN always replies with best move for MIN\n",
        "  - Backed-up value of each node: determined by values of its children\n",
        "    - MAX: max of values of its children\n",
        "    - MIN: min of values of its children\n",
        "- Minimax procedure: Until game is over do:\n",
        "  - Start with current position as MAX node\n",
        "  - Expand game tree a fixed number of ply\n",
        "  - Apply eval function to leaf positions\n",
        "  - Calculate back-up values bottom-up\n",
        "  - Pick move assigned to MAX at the root\n",
        "  - Wait for MIN to respond\n",
        "- Keep track of 2 additional values: alpha & beta\n",
        "  - alpha: MAX's current lower bound on MAX's outcome (MAX will never allow a move that could lead to a worse score for MAX than alpha)\n",
        "  - beta: MIN's current upper bound on MIN's outcome (MIN will never allow a move that could lead to a better score for MAX than beta)\n",
        "- Stop eval a branch whenever:\n",
        "  - For MAX node: v >= beta is backed-up (MIN will never select that MAX node)\n",
        "  - For MIN node: v <= alpha is found (MAX will never select that MIN node)\n",
        "- Expectimax when we don't know what result of action will be (explicit randomness, unpredictable opponents, actions can fail)\n",
        "- Expectimax search: compute avg score under optimal play\n",
        "  - Add chance nodes (like min nodes) except outcome is uncertain -> calculate expected utilities\n",
        "  - No pruning since expected utility might be lower than node before\n",
        "  - Environment is an extra \"random agent\" player tha moves after each min/max agent\n",
        "- Random variable: event whose outcome is unknown\n",
        "- Probability distribution: assignment of weights to outcomes\n",
        "- Expected value of function of RV= avg weighted by prob. distribution over outcomes\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"ignores parts of the search tree that makes no difference\",\n",
        "\"evaluation function\": \"estimates current winner based on features of state\",\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"zero-sum\": \"good for one player is bad for the other\",\n",
        "\"transition model\": \"defines the state after taking an action in a given state\",\n",
        "\"utility function\": \"defines the numeric value for a player when the game ends in terminal state\",\n",
        "\"killer moves\" : \"best moves\",\n",
        "\"transpositions\" : \"different permutations of move sequence that end up in the same position\",\n",
        "\"micromort\": \"one in million chance of death\",\n",
        "\"QALY\": \"quality-adjusted life year\",\n",
        "\"certainty equivalent\": \"value agent accepts in lieu of lottery\",\n",
        "\"insurance premium\":\"EMV of lottery - certainty equivalent\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 94,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "10e54b34-9387-47df-d071-f3c24ced1629"
      },
      "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": 95,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- 3 stances we can take towards multiagent environments:\n  - Aggregate as economy: appropriate when large \\# of agents; allows us to predict on aggregate w/o having to predict action of any individual agent\n  - Consider adversarial agents as just part of environment (makes it nondeterministic)\n  - Explicitly model aversarial agents with techniques of adversarial game-tree search\n- Won't have enough time to be sure of optimal move (even with pruning) in nontrivial games; need to cut off search at some point\n  - For each state where choose to stop searching, ask who's winning:\n    - Apply eval function\n    - Avg outcomes of many fast simulations of the game from that state all the way to end\n- State space graph: initial state, actions function and result\n- Can superimpose search tree over part of graph to determine\n- Complete game tree: search tree that follows every sequence of moves all the way to terminal state \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n- Use minimax search for games with multiple outcome scores\n- \"move\" means that both players have taken an action; \"ply\" means that one player made a move\n- Given game tree, optimal strategy can be determined by working out the minimax value of each state in the tree [Minimax(s)]\n\t- Minimax value: utility of being in state, assuming that both players play optimally from there to end of game\n- Best play not always to make optimal move when facing suboptimal opponent (making riskier move might lead to win instead of draw)\n- Minimax alg: recursive alg that proceeds all the way down to leaves of tree, then backs up the minimax values through the tree as recursion unwinds\n  - Performs complete depth-first exploration of game tree\n\t- If max depth of tree is m and there are b legal moves at each point:\n\t\t- Time complexity: O(bm)\n\t\t- Space complexity: O(bm) for alg that generates all actions at once; O(m) for alg that generates actions one at a time\n- Optimal decisions in multiplayer games\n  - Must replace the single value for each node with a vector of values (Have utility function return vector of utilities)\n  - Alliances can be natural consequence of optimal strategies for each player\n- \\# of game states: exponential in depth of tree\n\t- Alpha-beta pruning: consider that player has choice of moving to node n\n    - If player has a better choice either at the same level or at any point higher up in tree, then player will never move to n\n    - So once we've found out enough about n to reach this conclusion => prune it\n- Alpha-beta parameters: the value of the best choice we have found so far at any choice point along the path for…\n\t\t- alpha: MAX (at least)\n\t\t- beta: MIN (at most)\n- Effectiveness of alpha-beta pruning is highly dependent on order in which states are examined (could do it in O(b^(m/2)) instead of O(b^m))\n\t- Iterative deepening: search one ply deep & record ranking of moves based on evaluations; then search one ply deeper using previous ranking to inform move ordering, etc\n    - Increased search time from this can be more than made up from move ordering\n\t- Repeated states can occur because of transpositions which can cause exponential increase in search cost\n\t  - Address problem with transposition table that caches the heuristic value of states\n\t- Too many states to explore in the time available. Two strategies:\n\t\t- Type A: considers all possible moves to a certain depth in the search tree and then uses a heuristic evaluation function to estimate the utility of states at that depth\n\t\t\t- Explores a wide but shallow portion of the tree\n\t\t\t- Chess\n\t\t- Type B: ignores moves that look bad and follows promising lines \"as far as possible\"\n\t\t\t- Explores a deep but narrow portion of the tree\n      - Go\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n\t- Replace utility function with eval (which estimates a state's utility)\n\t- Replace terminal test by a cutoff test, which must return true for terminal states but is otherwise free to decide when to cut off the search\n- Heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p\n\t- What else makes for a good eval function?\n\t\t- Computation must not take too long\n\t\t- Eval function should be strongly correlated with the actual chances of winning\n\t- Most eval functions work by calculating various features of the state: can be too costly\n    - Eval function doesn't know which states are which, but can return a single value that estimates the proportion of states with each outcome\n\t\t- Therefore, most in practice compute separate numerical contributions from each feature and then combine them to find the total value\n\t\t\t- However, assumes that contribution of each feature is independent of values of other features --> can use nonlinear combination of features\n- When is it appropriate to cut off search?\n\t- Eval function should only be applied to positions that are quiescent -- positions in which there is no pending move (such as a capturing the queen) that would wildly swing the eval\n\t\t- Quiescence search is sometimes restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position\n- Horizon effect: when program is facing an opponent's move that causes serious damage and is ultimately unavoidable but can be temporarily avoided by the use of delaying tactics\n\t- One way to mitigate: allow singular extensions even when the search would normally be cut off at that point\n\t\t- Singular extensions: moves that are \"clearly better\" than all other moves in a given position\n- Forward pruning prunes moves that appear to be poor moves, but might possibly be good ones\n\t- Saves computation time at risk of making an error (Type B strategy)\n    - Beam search but no way to guarantee that the best move will not be pruned away\n\t\t- Probabilistic cut: forward-pruning version of alpha-beta search that uses statistics gained from prior experience to lessen the chance that the best move will be pruned\n\t\t\t- Computes probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (alpha, beta)\n\t\t- Late move reduction: moves that appear later in the list of possible moves are less likely to be good moves, so reduce the depth to which we search these moves (instead of pruning away completely)\n- Search versus lookup: Lookup initial and very end moves because they're easier to anticipate; start searching when state is new and unseen\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- Stochastic games: Games with chance incorporated\n- Game tree must include chance nodes in addition to max and min nodes\n- Positions do not have definite minimax values: calculate expected value (average over all possible outcomes of the chance nodes)\n\t- Expectiminimax value: generalization of minimax value for deterministic games\n    - For chance nodes: compute expected value (sum of values over all outcomes) weighted by probability of each chance action\n- To avoid problems where program behaves totally differently if we make a change to some of the eval values (even if preference order is the same)\n  - Eval function must return values that are a positive linear transformation of probability of winning\n- Whenever uncertainty enters the picture: possibilities are multiplied enormously and forming detailed plans of action becomes pointless bc the world probably will not play along\n  - Something like alpha-beta pruning could be applied\n  - If we put bounds on possible values of utility function, can arrive at bounds for the avg without looking at every number\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- Agent assigns probability P(s) to each possible current state s\n- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- Constraints on rational preferences\n\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n\t- Primary issue for utility theory: understand how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n\t\t\t- Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p\n\t\t\t- Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n- 16.2.2 Rational preferences lead to utility\n\t- From axioms of utility, can derive the following:\n    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a 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\n    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n  - Once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n\t\t- Called a value function or ordinal utility function\n  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- Preference elicitation: process to work out what a human's utility function is by presenting choices to them and using observed preferences to pin down the underlying utility function\n- Useful to establish some scale on which utilities can be recorded and compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n\t- Normalized utilities: scale between 0 and 1\n- Utility of money almost exactly proportional to log of the amount\n  - Most people have a utility function that is concave for positive wealth\n  - Agent with linear curve: risk-neutral\n- Expected utility and post-decision disappointment\n\t- Rational way to choose best action: maximize expected utility\n\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n\t\t- Therefore working with estimates of true expected utility\n\t\t- Assume estimates are unbiased: expected value of error is zero\n- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n- Decision theory = normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really do act\n- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n\t- People may distrust the legitimacy of the stated probabilities\n\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n\n\n## Module 5 Lecture Notes\n\n- Simplest game environment: multiagent, static, discrete, fully observable, strategic (next state is determined by current state and action executed by agent and that of one other agent)\n- Key properties of game:\n  - Two players alternate moves\n  - Zero-sum: one player's loss is another's gain\n  - Clear set of legal moves\n  - Well-defined outcomes (win, lose, draw)\n- General scheme:\n  - Consider all legal successors to current state (board position)\n  - Evaluate each successor board position\n  - Pick move which leads to best board position\n  - After opponent moves, repeat\n- Game trees: nodes repesent board positions; edges represent legal moves\n  - Root node: first position in which a decision must be made\n  - Eval function f assigns real-number scores to board positions without reference to path\n    - Based on static features of board alone\n    - Zero-sum assumption lets us use one function to describe goodness for both players\n      - f(n)>0 if MAX winning in position n; f(n)=0 if position n is tied; f(n)<0 if MIN winning in position n \n  - Terminal nodes: represent ways game could end, labeled w/ desirability of that ending\n- MAX & MIN: MAX attempts to MAXimize MAX's outcome and MIN attempts to MINimize MAX's outcome\n- Minimax: make best move for MAX assuming that MIN always replies with best move for MIN\n  - Backed-up value of each node: determined by values of its children\n    - MAX: max of values of its children\n    - MIN: min of values of its children\n- Minimax procedure: Until game is over do:\n  - Start with current position as MAX node\n  - Expand game tree a fixed number of ply\n  - Apply eval function to leaf positions\n  - Calculate back-up values bottom-up\n  - Pick move assigned to MAX at the root\n  - Wait for MIN to respond\n- Keep track of 2 additional values: alpha & beta\n  - alpha: MAX's current lower bound on MAX's outcome (MAX will never allow a move that could lead to a worse score for MAX than alpha)\n  - beta: MIN's current upper bound on MIN's outcome (MIN will never allow a move that could lead to a better score for MAX than beta)\n- Stop eval a branch whenever:\n  - For MAX node: v >= beta is backed-up (MIN will never select that MAX node)\n  - For MIN node: v <= alpha is found (MAX will never select that MIN node)\n- Expectimax when we don't know what result of action will be (explicit randomness, unpredictable opponents, actions can fail)\n- Expectimax search: compute avg score under optimal play\n  - Add chance nodes (like min nodes) except outcome is uncertain -> calculate expected utilities\n  - No pruning since expected utility might be lower than node before\n  - Environment is an extra \"random agent\" player tha moves after each min/max agent\n- Random variable: event whose outcome is unknown\n- Probability distribution: assignment of weights to outcomes\n- Expected value of function of RV= avg weighted by prob. distribution over outcomes\n\n\n## Module 5 Definitions\n* **Pruning** - ignores parts of the search tree that makes no difference\n* **Evaluation function** - estimates current winner based on features of state\n* **Perfect information** - fully observable\n* **Zero-sum** - good for one player is bad for the other\n* **Transition model** - defines the state after taking an action in a given state\n* **Utility function** - defines the numeric value for a player when the game ends in terminal state\n* **Killer moves** - best moves\n* **Transpositions** - different permutations of move sequence that end up in the same position\n* **Micromort** - one in million chance of death\n* **Qaly** - quality-adjusted life year\n* **Certainty equivalent** - value agent accepts in lieu of lottery\n* **Insurance premium** - EMV of lottery - certainty equivalent\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",
        "- Constraint satisfaction problem consists of 3 components:\n",
        "\t- X: set of variables\n",
        "\t- D: set of domains (set of allowable values), one for each variable\n",
        "\t- C: set of constraints that specify allowable combinations of values\n",
        "\t\t- <scope, rel> where scope = tuple of variables that participate in the constraint and rel is a relation that defines the values that those variables can take on\n",
        "\t\t- For example: if X1 and X2 both have the domain {1,2,3}, then the constraint saying that X1 must be greater than X2 can be written as: <(X1,X2), {(3,1),(3,2),(3,1),(2,1)})> or <(X1,X2), X1>X2 >\n",
        "- CSP deal with assignments of values to variables\n",
        "- Why formulate problem as CSP?\n",
        "\t- Often easy to do\n",
        "\t- Years of development work have gone into making CSP solvers fast and efficient\n",
        "\t- CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot\n",
        "- With CSPs, once we find out that a partial assignment violates a constraint, we can immediately discard further refinements of the partial assignment\n",
        "- Can specify precedence constraints between individual tasks (one must come before the other) and disjunctive constraint (tasks cannot overlap in time)\n",
        "- Variations on the CSP formalism\n",
        "\t- Simplest kind of CSP involves variables that have discrete, finite domains\n",
        "  - No alg exists for solving general nonlinear constraints on integer variables\n",
        "\t- Best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities\n",
        "\t- Types of variables: discrete, continuous\n",
        "\t- Types of constraints: unary (restricts value of a single variable) and binary (relates two variables), higher-order constraints\n",
        "\t\t- Global: constraint involving an arbitrary number of variables\n",
        "- Binary CSP: one with only unary and binary constraints\n",
        "- Constraint hypergraph: consists of ordinary nodes and hypernodes which represent n-ary constraints (constraints involving n variables)\n",
        "\t- Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced\n",
        "\t\t- Can transform any CSP into one with only binary constraints\n",
        "    - Another way to convert n-ary CSP to binary: dual graph transformation (create new graph where there is one variable for each constraint in original graph and one binary constraint for each pair of constraints in original graph that share variables)\n",
        "\t- Why we might prefer global constraint rather than binary:\n",
        "\t\t- Easier and less error-prone to write the problem description using Alldiff (which says that all variables involved must have distinct values)\n",
        "\t\t- Possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints\n",
        "- Preference constraints: indicate which solutions are preferred\n",
        "\t- Absolute: violation of which rules out a potential solution\n",
        "  - Can be encoded as costs on individual variable assignments (constrained optimization problem)\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- CSP alg has choices when making progress\n",
        "\t- Can generate successors by choosing new variable assignment\n",
        "\t- Constraint propagation: type of inference that uses constraints to reduce number of legal values for a variable (can be intertwined with search or done as preprocessing step)\n",
        "\t\t- Preprocessing may solve whole problem so no search required\n",
        "- Key idea: Local consistency\n",
        "\t- Node: one variable = node-consistent if all values in variable's domain satisfy variable's unary constraints\n",
        "\t\t- Graph node-consistent if every variable in graph is node-consistent\n",
        "\t  - Easy to eliminate all unary constraints in CSP by reducing domain of variables with unary constraints at start of solving process\n",
        "\t- Arc: variable in CSP is arc-consistent if every value in its domain satisfies variable's binary constraints (AC-3)\n",
        "\t\t- Maintains queue of arcs to consider: initially contains all the arcs in CSP\n",
        "\t\t- Then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi arc-consistent with respect to Xj\n",
        "\t\t\t- If Di left unchanged, move on to next arc\n",
        "\t\t\t- If Di changed, then we add to queue all arcs (Xk, Xi) where Xk is a neighbor of Xi\n",
        "\t\t\t\t- Change might enable further reductions in Dk even if we have previously considered Xk\n",
        "\t\t\t- If Di revised down to nothing => know the whole CSP has no consistent solution and AC-3 can immediately return failure\n",
        "\t\t- Otherwise, keep checking\n",
        "\t\t- Checking consistency of an arc can be done in O(d^2), so we get O(cd^3) total worst-case time\n",
        "\t- Path: tightens binary constraints by using constraints that are inferred by looking at triples of variables\n",
        "\t\t- Two-variable set {Xi, Xj} is path-consistent wrt third variable Xm if, for every assignment {Xi=a, Xj=b} consistent with constraints (if any) on {Xi, Xj}, there's an assignment to Xm that satisifes constraints on {Xi, Xm} and {Xm, Xj}\n",
        "\t- K-consistency: CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n",
        "\t\t- Strongly k-consistent if k-consistent, (k-1)-consistent, (k-2)-consistent,…, down to 1-consistent\n",
        "\t\t- Total run time: O((n^2)d)\n",
        "\t- Global constraints\n",
        "\t\t- If m variables are involved in constraint, and if they have n possible distinct values altogether, and m > n, then Alldiff constraint cannot be satisfied\n",
        "\t\t- Algorithm:\n",
        "\t\t\t- Remove any variable in the constraint that has a singleton domain\n",
        "\t\t\t- Delete that variable's value from domains of remaining variables\n",
        "\t\t\t- Repeat as long as there are singleton variables\n",
        "\t\t\t- If at any point an empty domain is produced or there are more variables than domain values left, then inconsistency has been detected\n",
        "\t- Resource constraint (Atmost): detect inconsistency simply by checking sum of minimum values of current domains\n",
        "\t\t- CSP is bounds-consistent if for every variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisifies the constraint between X and Y for every variable Y\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "- Must search for solution if we still have variables with multiple possible values after finishing constraint propagation process\n",
        "- CSPs are commutative (order of actions applied does not matter)\n",
        "- Backtracking search: keeps only single representation of state and alters it rather than creating new ones\n",
        "  - Can be improved using domain-independent heuristics that take advantage of factored representation of CSPs\n",
        "- Variable selection\n",
        "  - Simplest: static ordering (choose variables in order) or choose randomly => neither optimal\n",
        "  - Minimum-remaining-values (MRV) heuristic: choosing variable with the fewest \"legal\" values\n",
        "\t- Degree heuristic: attempts to reduce branching factor on future choices by selecting variable that's involved in largest number of constraints on other unassigned variables\n",
        "\t- MRV is usually more powerful guide, but degree heuristic useful as tie-breaker\n",
        "- Once variable has been selected, must decide on order to examine its values\n",
        "\t- Least-constraining-value: prefers value that rules out the fewest choices for the neighboring variables in the constraint graph\n",
        "- Variable selection: fail-first; value selection: fail-last\n",
        "- Inference can be even more powerful during course of search\n",
        "\t- Every time we make a choice of value for a variable, have brand-new opportunity to infer new domain reductions on neighboring variables\n",
        "\t- Forward checking: whenever a variable X is assigned, forward-checking process establishes arc consistency for it\n",
        "\t\t- For each unassigned variable Y that is connected to X by constraint, delete from Y's domain any value that's inconsistent with value chosen for X\n",
        "\t- For many problems, search will be more effective if combine MRV heuristic with forward checking\n",
        "\t- Maintaining Arc Consistency (MAC) detects inconsistencies not found by forward checking\n",
        "\t\t- After a variable Xi is assigned a value, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, start with only the arcs (Xj, Xi) for all Xj that are unassigned variables that are neighbors of Xi\n",
        "\t\t- From there AC-3 does constraint propagation in usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately\n",
        "\t\t- More powerful than forward checking: forward checking does not recursively propagate constraints when changes are made to the domains of variables\n",
        "- Original idea: just back up to preceding variable and try diff value for it (chronological backtracking: most recent decision point is revisted)\n",
        "  - Better possibilities\n",
        "    - Backtrack to variable that's responsible for making one of possible values for variable impossible\n",
        "    - Keep track of conflict set (set of assignments that're in conflict for some value)\n",
        "      - Backjumping: backtracks to most recent assignment in conflict set\n",
        "      - Forward checking can supply conflict set with no extra work\n",
        "- Constraint learning: idea of finding min set of variables from conflict set that causes the problem (no-good)\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "- Local search algorithms: use a complete-state formulation where each state assigns a value to every variable, and the search changes the value of one variable at a time\n",
        "- Min-conflicts heuristic: select value that results in min number of conflicts with other variables \n",
        "  - Run time is roughly independent of problem size\n",
        "- May be millions of variable assignments only one conflict away from solution\n",
        "  - Plateau search: allowing sideways moves to another state with same score (can help local search find way off plateau)\n",
        "\t\t- Tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states (technique to direct wandering on plateau)\n",
        "\t- Constraint weighting: aims to concentrate the search on the important constraints\n",
        "    - Weights adjusted by incrementing weight of each constraint that is violated by current assignment\n",
        "    - Benefits: adds topography to plateaus (makes sure it's possible to improve from current state) and adds learning (over time, difficult constraints are assigned higher weights)\n",
        "- Local search can also be used in an online setting when the problem changes\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "- Structure of problem (represented by constraint graph) can be used to find solutions quickly\n",
        "- Independence can be ascertained simply by finding connected components of the constraint graph\n",
        "- Any tree-structured CSP can be solved in time linear in the number of variables\n",
        "\t- Key: directional arc consistency (DAC)\n",
        "\t\t- CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, …, Xn if and only if every Xi is arc-consistent with each Xj for j > i.\n",
        "- Two ways to reduce constraint graph to tree: cutset conditioning & tree decomposition\n",
        "- Cutset conditioning algorithm:\n",
        "\t- Choose a subset S of the CSP's variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset\n",
        "\t- For each possible assignment to the variables in S that satisfies all constraints on S:\n",
        "\t\t- Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S\n",
        "\t\t- If the remaining CSP has a solution, return it together with the assignment for S\n",
        "\t- If the cycle cutset has size c, then total run time is O(dc * (n-c)d2)\n",
        "- Tree decomposition\n",
        "\t- Construct tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
        "\t- Must satisfy 3 requirements:\n",
        "\t\t- Every variable in the original problem appears in at least one of the tree nodes\n",
        "\t\t- If two variables are connected by a constraint in original problem, they must appear together (along with the constraint) in at least one of the three nodes\n",
        "\t\t- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n",
        "  - First two conditions: ensure all variables and constraints are represented in tree decomposition\n",
        "  - 3rd condition: allows us to say that any variable from original problem must have the same value wherever it appears\n",
        "\t- Have tree-structured graph: can then apply Tree-CSP-solver to get solution in O(nd^2) time (n is # of tree nodes; d is size of largest domain)\n",
        "    - Efficient as long as d remains small\n",
        "\t- In choosing decomp: aim is to make subproblems as small as possible\n",
        "\t- CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n",
        "    - Tree width of tree decomp of graph: size of largest node - 1\n",
        "    - Tree width of graph itself: min width among all its tree decompositions\n",
        "- Value symmetry\n",
        "  - Can be important structure in values of variables or constraint relations themselves\n",
        "  - Breaking value symmetry useful in reducing search space (symmetry-breaking constraint)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "- Assumptions about world: single agent, deterministic actions, fully observable, discrete state space\n",
        "- Search used for:\n",
        "  - Planning (sequence of actions)\n",
        "    - Most important: Path to goal\n",
        "    - Paths have various costs, depths\n",
        "    - Heuristics give problem-specific guidance\n",
        "  - Identification (assignments to variables)\n",
        "    - Most important: just goal\n",
        "    - All paths have same depth (for some formulations)\n",
        "    - CSPs are specialized for ID problems\n",
        "- Big idea\n",
        "  - Represent constraints that solutions must satisfy in a uniform declarative language\n",
        "  - Find solutions by general purpose search algs with no changes from problem to problem (no hand-built transition functions or heuristics)\n",
        "  - Just specify problem in formal declarative language & a general-purpose alg does everything else!\n",
        "- CSP consists of: finite set of variables; nonempty domain of possible values for each variable; finite set of constraints\n",
        "  - Each constraint limits the values that variables can take\n",
        "  - State: assignment of values to some or all variables\n",
        "- Consistent assignment: constraints not violated\n",
        "- Complete assignment: every variable is assigned a value\n",
        "- Solution to CSP: complete, consistent assignment\n",
        "  - Can be founded by a completely general purpose alg, given only formal specification of CSP\n",
        "- Benefits of CSP\n",
        "  - Clean specification of many problems, generic goal, successor function & heuristics\n",
        "  - CSP \"knows\" which variables violate a constraint (hence where to focus search)\n",
        "  - Automatically prune off all branches that violate constraints (state space search: only does this by hand-building constraints into successor function)\n",
        "- CSP Representations\n",
        "  - Constraint graph: nodes=variables; arcs=binary constraints; simplifies search\n",
        "  - Standard representation pattern: variables with values\n",
        "  - Binary CSP: each constraint relates two variables\n",
        "- CSPs deal with both discrete (finite & infite) and continuous variables\n",
        "- Unary constraint=single variable; binary=pairs of variables; higher-order=3=< variables\n",
        "- Preference (soft constraints): represented by cost for each variable assignment\n",
        "- CSP as search: initial state={}; successor function= assign value to any unassigned variable provided no constraint conflict; goal test=assignment is complete; path cost=constant for each step\n",
        "  - Solution always found at depth n for n variables (DFS can be used)\n",
        "  - n variables of domain size d\n",
        "    - Branching factor at root: n*d\n",
        "    - Branching factor at next level: (n-1)*d\n",
        "    - Tree has n!*d^n leaves\n",
        "  - Only need to consider assignments to a single variable at each node\n",
        "- Backtracking search: DFS for CSPs with single-variable assignments\n",
        "  - Chooses vals for one variable at a time and backtracks when variable has no legal values left to assign\n",
        "  - Basic uninformed alg for CSPs\n",
        "- Improve backtracking efficiency: general-purpose methods & heuristics can give huge gains in speed on average\n",
        "- Minimum remaining values (MRV) heuristic: Choose variable with fewest legal moves (tiebreaker: choose with most constraints on remaining variables)\n",
        "- Least constraining value: given variable, choose one that rules out the fewest values in remaining variables\n",
        "- Forward checking: keep track of remaining legal values for unassigned variables; terminate search when any unassigned variables has no remaining legal values\n",
        "  - Constraint propagation (inference) eliminates possible values for a variable if value would violate local consistency\n",
        "    - Node consistency: satisifies unary constraints\n",
        "    - Arc consistency: satisifies binary constraints\n",
        "      - Xi arc-consistent wrt Xj if for every value in Di, there's some value in Dj that satisfies binary constraint on arc between Xi and Xj\n",
        "      - To make an arc (i,j) arc-consistent, for each value v on Xi: if no label on Yj consistent with v, remove v from Xi\n",
        "- X->Y is consistent iff for every value x of X there is some allowed y\n",
        "- Waltz/Mackworth Constraint Prop Alg:\n",
        "  - Assign every node in constraint graph a set of all possible values\n",
        "  - Repeat until there is no change in set of values associated with any node:\n",
        "    - For each node i and for each neighboring node j: remove any value from i which is not arc consistent with j\n",
        "- Inefficiencies\n",
        "  - At each iteration, only examine those Xi where 1=< neighbor of Xi has lost a value in previous iteration\n",
        "  - If Xi loses value bc of arc inconsistencies with Yj: don't need to check Yj on next iteration\n",
        "  - Removing value on Xi can only make Yj arc-inconsistent with respect to Xi itself: only need to check that (j,i) is still arc-consistent\n",
        "- AC-3: keep track of what arcs we need to process; add back arcs to neighbors whenever a node had values removed\n",
        "  - Total # of arcs: 2*n*(n-1) (O(n^2))\n",
        "  - Given d values, checking takes O(d^2) time\n",
        "  - Worst-case complexity: O(n^2 * d^3)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent assignment\": \"assignment doesn't violate any constraints\",\n",
        "\"complete assignment\": \"every variable is assigned a value\",\n",
        "\"solution\": \"consistent, complete assignment\",\n",
        "\"partial assignment\": \"leaves some variables unassigned\",\n",
        "\"partial solution\": \"partial assignment that is consistent\",\n",
        "\"constraint propagation\": \"use constraints to reduce \\# of legal values for a variable\"\n",
        "}\n"
      ],
      "execution_count": 96,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1ea18760-7d5d-4bef-a7bc-69e27e67f0e5"
      },
      "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": 97,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- Constraint satisfaction problem consists of 3 components:\n\t- X: set of variables\n\t- D: set of domains (set of allowable values), one for each variable\n\t- C: set of constraints that specify allowable combinations of values\n\t\t- <scope, rel> where scope = tuple of variables that participate in the constraint and rel is a relation that defines the values that those variables can take on\n\t\t- For example: if X1 and X2 both have the domain {1,2,3}, then the constraint saying that X1 must be greater than X2 can be written as: <(X1,X2), {(3,1),(3,2),(3,1),(2,1)})> or <(X1,X2), X1>X2 >\n- CSP deal with assignments of values to variables\n- Why formulate problem as CSP?\n\t- Often easy to do\n\t- Years of development work have gone into making CSP solvers fast and efficient\n\t- CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot\n- With CSPs, once we find out that a partial assignment violates a constraint, we can immediately discard further refinements of the partial assignment\n- Can specify precedence constraints between individual tasks (one must come before the other) and disjunctive constraint (tasks cannot overlap in time)\n- Variations on the CSP formalism\n\t- Simplest kind of CSP involves variables that have discrete, finite domains\n  - No alg exists for solving general nonlinear constraints on integer variables\n\t- Best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities\n\t- Types of variables: discrete, continuous\n\t- Types of constraints: unary (restricts value of a single variable) and binary (relates two variables), higher-order constraints\n\t\t- Global: constraint involving an arbitrary number of variables\n- Binary CSP: one with only unary and binary constraints\n- Constraint hypergraph: consists of ordinary nodes and hypernodes which represent n-ary constraints (constraints involving n variables)\n\t- Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced\n\t\t- Can transform any CSP into one with only binary constraints\n    - Another way to convert n-ary CSP to binary: dual graph transformation (create new graph where there is one variable for each constraint in original graph and one binary constraint for each pair of constraints in original graph that share variables)\n\t- Why we might prefer global constraint rather than binary:\n\t\t- Easier and less error-prone to write the problem description using Alldiff (which says that all variables involved must have distinct values)\n\t\t- Possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints\n- Preference constraints: indicate which solutions are preferred\n\t- Absolute: violation of which rules out a potential solution\n  - Can be encoded as costs on individual variable assignments (constrained optimization problem)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- CSP alg has choices when making progress\n\t- Can generate successors by choosing new variable assignment\n\t- Constraint propagation: type of inference that uses constraints to reduce number of legal values for a variable (can be intertwined with search or done as preprocessing step)\n\t\t- Preprocessing may solve whole problem so no search required\n- Key idea: Local consistency\n\t- Node: one variable = node-consistent if all values in variable's domain satisfy variable's unary constraints\n\t\t- Graph node-consistent if every variable in graph is node-consistent\n\t  - Easy to eliminate all unary constraints in CSP by reducing domain of variables with unary constraints at start of solving process\n\t- Arc: variable in CSP is arc-consistent if every value in its domain satisfies variable's binary constraints (AC-3)\n\t\t- Maintains queue of arcs to consider: initially contains all the arcs in CSP\n\t\t- Then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi arc-consistent with respect to Xj\n\t\t\t- If Di left unchanged, move on to next arc\n\t\t\t- If Di changed, then we add to queue all arcs (Xk, Xi) where Xk is a neighbor of Xi\n\t\t\t\t- Change might enable further reductions in Dk even if we have previously considered Xk\n\t\t\t- If Di revised down to nothing => know the whole CSP has no consistent solution and AC-3 can immediately return failure\n\t\t- Otherwise, keep checking\n\t\t- Checking consistency of an arc can be done in O(d^2), so we get O(cd^3) total worst-case time\n\t- Path: tightens binary constraints by using constraints that are inferred by looking at triples of variables\n\t\t- Two-variable set {Xi, Xj} is path-consistent wrt third variable Xm if, for every assignment {Xi=a, Xj=b} consistent with constraints (if any) on {Xi, Xj}, there's an assignment to Xm that satisifes constraints on {Xi, Xm} and {Xm, Xj}\n\t- K-consistency: CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\t\t- Strongly k-consistent if k-consistent, (k-1)-consistent, (k-2)-consistent,…, down to 1-consistent\n\t\t- Total run time: O((n^2)d)\n\t- Global constraints\n\t\t- If m variables are involved in constraint, and if they have n possible distinct values altogether, and m > n, then Alldiff constraint cannot be satisfied\n\t\t- Algorithm:\n\t\t\t- Remove any variable in the constraint that has a singleton domain\n\t\t\t- Delete that variable's value from domains of remaining variables\n\t\t\t- Repeat as long as there are singleton variables\n\t\t\t- If at any point an empty domain is produced or there are more variables than domain values left, then inconsistency has been detected\n\t- Resource constraint (Atmost): detect inconsistency simply by checking sum of minimum values of current domains\n\t\t- CSP is bounds-consistent if for every variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisifies the constraint between X and Y for every variable Y\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- Must search for solution if we still have variables with multiple possible values after finishing constraint propagation process\n- CSPs are commutative (order of actions applied does not matter)\n- Backtracking search: keeps only single representation of state and alters it rather than creating new ones\n  - Can be improved using domain-independent heuristics that take advantage of factored representation of CSPs\n- Variable selection\n  - Simplest: static ordering (choose variables in order) or choose randomly => neither optimal\n  - Minimum-remaining-values (MRV) heuristic: choosing variable with the fewest \"legal\" values\n\t- Degree heuristic: attempts to reduce branching factor on future choices by selecting variable that's involved in largest number of constraints on other unassigned variables\n\t- MRV is usually more powerful guide, but degree heuristic useful as tie-breaker\n- Once variable has been selected, must decide on order to examine its values\n\t- Least-constraining-value: prefers value that rules out the fewest choices for the neighboring variables in the constraint graph\n- Variable selection: fail-first; value selection: fail-last\n- Inference can be even more powerful during course of search\n\t- Every time we make a choice of value for a variable, have brand-new opportunity to infer new domain reductions on neighboring variables\n\t- Forward checking: whenever a variable X is assigned, forward-checking process establishes arc consistency for it\n\t\t- For each unassigned variable Y that is connected to X by constraint, delete from Y's domain any value that's inconsistent with value chosen for X\n\t- For many problems, search will be more effective if combine MRV heuristic with forward checking\n\t- Maintaining Arc Consistency (MAC) detects inconsistencies not found by forward checking\n\t\t- After a variable Xi is assigned a value, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, start with only the arcs (Xj, Xi) for all Xj that are unassigned variables that are neighbors of Xi\n\t\t- From there AC-3 does constraint propagation in usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately\n\t\t- More powerful than forward checking: forward checking does not recursively propagate constraints when changes are made to the domains of variables\n- Original idea: just back up to preceding variable and try diff value for it (chronological backtracking: most recent decision point is revisted)\n  - Better possibilities\n    - Backtrack to variable that's responsible for making one of possible values for variable impossible\n    - Keep track of conflict set (set of assignments that're in conflict for some value)\n      - Backjumping: backtracks to most recent assignment in conflict set\n      - Forward checking can supply conflict set with no extra work\n- Constraint learning: idea of finding min set of variables from conflict set that causes the problem (no-good)\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- Local search algorithms: use a complete-state formulation where each state assigns a value to every variable, and the search changes the value of one variable at a time\n- Min-conflicts heuristic: select value that results in min number of conflicts with other variables \n  - Run time is roughly independent of problem size\n- May be millions of variable assignments only one conflict away from solution\n  - Plateau search: allowing sideways moves to another state with same score (can help local search find way off plateau)\n\t\t- Tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states (technique to direct wandering on plateau)\n\t- Constraint weighting: aims to concentrate the search on the important constraints\n    - Weights adjusted by incrementing weight of each constraint that is violated by current assignment\n    - Benefits: adds topography to plateaus (makes sure it's possible to improve from current state) and adds learning (over time, difficult constraints are assigned higher weights)\n- Local search can also be used in an online setting when the problem changes\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- Structure of problem (represented by constraint graph) can be used to find solutions quickly\n- Independence can be ascertained simply by finding connected components of the constraint graph\n- Any tree-structured CSP can be solved in time linear in the number of variables\n\t- Key: directional arc consistency (DAC)\n\t\t- CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, …, Xn if and only if every Xi is arc-consistent with each Xj for j > i.\n- Two ways to reduce constraint graph to tree: cutset conditioning & tree decomposition\n- Cutset conditioning algorithm:\n\t- Choose a subset S of the CSP's variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset\n\t- For each possible assignment to the variables in S that satisfies all constraints on S:\n\t\t- Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S\n\t\t- If the remaining CSP has a solution, return it together with the assignment for S\n\t- If the cycle cutset has size c, then total run time is O(dc * (n-c)d2)\n- Tree decomposition\n\t- Construct tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n\t- Must satisfy 3 requirements:\n\t\t- Every variable in the original problem appears in at least one of the tree nodes\n\t\t- If two variables are connected by a constraint in original problem, they must appear together (along with the constraint) in at least one of the three nodes\n\t\t- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n  - First two conditions: ensure all variables and constraints are represented in tree decomposition\n  - 3rd condition: allows us to say that any variable from original problem must have the same value wherever it appears\n\t- Have tree-structured graph: can then apply Tree-CSP-solver to get solution in O(nd^2) time (n is # of tree nodes; d is size of largest domain)\n    - Efficient as long as d remains small\n\t- In choosing decomp: aim is to make subproblems as small as possible\n\t- CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n    - Tree width of tree decomp of graph: size of largest node - 1\n    - Tree width of graph itself: min width among all its tree decompositions\n- Value symmetry\n  - Can be important structure in values of variables or constraint relations themselves\n  - Breaking value symmetry useful in reducing search space (symmetry-breaking constraint)\n\n\n## Module 6 Lecture Notes\n\n- Assumptions about world: single agent, deterministic actions, fully observable, discrete state space\n- Search used for:\n  - Planning (sequence of actions)\n    - Most important: Path to goal\n    - Paths have various costs, depths\n    - Heuristics give problem-specific guidance\n  - Identification (assignments to variables)\n    - Most important: just goal\n    - All paths have same depth (for some formulations)\n    - CSPs are specialized for ID problems\n- Big idea\n  - Represent constraints that solutions must satisfy in a uniform declarative language\n  - Find solutions by general purpose search algs with no changes from problem to problem (no hand-built transition functions or heuristics)\n  - Just specify problem in formal declarative language & a general-purpose alg does everything else!\n- CSP consists of: finite set of variables; nonempty domain of possible values for each variable; finite set of constraints\n  - Each constraint limits the values that variables can take\n  - State: assignment of values to some or all variables\n- Consistent assignment: constraints not violated\n- Complete assignment: every variable is assigned a value\n- Solution to CSP: complete, consistent assignment\n  - Can be founded by a completely general purpose alg, given only formal specification of CSP\n- Benefits of CSP\n  - Clean specification of many problems, generic goal, successor function & heuristics\n  - CSP \"knows\" which variables violate a constraint (hence where to focus search)\n  - Automatically prune off all branches that violate constraints (state space search: only does this by hand-building constraints into successor function)\n- CSP Representations\n  - Constraint graph: nodes=variables; arcs=binary constraints; simplifies search\n  - Standard representation pattern: variables with values\n  - Binary CSP: each constraint relates two variables\n- CSPs deal with both discrete (finite & infite) and continuous variables\n- Unary constraint=single variable; binary=pairs of variables; higher-order=3=< variables\n- Preference (soft constraints): represented by cost for each variable assignment\n- CSP as search: initial state={}; successor function= assign value to any unassigned variable provided no constraint conflict; goal test=assignment is complete; path cost=constant for each step\n  - Solution always found at depth n for n variables (DFS can be used)\n  - n variables of domain size d\n    - Branching factor at root: n*d\n    - Branching factor at next level: (n-1)*d\n    - Tree has n!*d^n leaves\n  - Only need to consider assignments to a single variable at each node\n- Backtracking search: DFS for CSPs with single-variable assignments\n  - Chooses vals for one variable at a time and backtracks when variable has no legal values left to assign\n  - Basic uninformed alg for CSPs\n- Improve backtracking efficiency: general-purpose methods & heuristics can give huge gains in speed on average\n- Minimum remaining values (MRV) heuristic: Choose variable with fewest legal moves (tiebreaker: choose with most constraints on remaining variables)\n- Least constraining value: given variable, choose one that rules out the fewest values in remaining variables\n- Forward checking: keep track of remaining legal values for unassigned variables; terminate search when any unassigned variables has no remaining legal values\n  - Constraint propagation (inference) eliminates possible values for a variable if value would violate local consistency\n    - Node consistency: satisifies unary constraints\n    - Arc consistency: satisifies binary constraints\n      - Xi arc-consistent wrt Xj if for every value in Di, there's some value in Dj that satisfies binary constraint on arc between Xi and Xj\n      - To make an arc (i,j) arc-consistent, for each value v on Xi: if no label on Yj consistent with v, remove v from Xi\n- X->Y is consistent iff for every value x of X there is some allowed y\n- Waltz/Mackworth Constraint Prop Alg:\n  - Assign every node in constraint graph a set of all possible values\n  - Repeat until there is no change in set of values associated with any node:\n    - For each node i and for each neighboring node j: remove any value from i which is not arc consistent with j\n- Inefficiencies\n  - At each iteration, only examine those Xi where 1=< neighbor of Xi has lost a value in previous iteration\n  - If Xi loses value bc of arc inconsistencies with Yj: don't need to check Yj on next iteration\n  - Removing value on Xi can only make Yj arc-inconsistent with respect to Xi itself: only need to check that (j,i) is still arc-consistent\n- AC-3: keep track of what arcs we need to process; add back arcs to neighbors whenever a node had values removed\n  - Total # of arcs: 2*n*(n-1) (O(n^2))\n  - Given d values, checking takes O(d^2) time\n  - Worst-case complexity: O(n^2 * d^3)\n\n\n## Module 6 Definitions\n* **Consistent assignment** - assignment doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint propagation** - use constraints to reduce \\# of legal values for a variable\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "- Central component of knowledge-based agent: knowledge base (KB)\n",
        "\t- KB may initially contain some background knowledge\n",
        "\t- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world\n",
        "- Tell & Ask: ways to add new sentences to KB and a way to query what's known\n",
        "\t- Both may involve inference\n",
        "- Each time agent program is called:\n",
        "\t- Tells KB what it perceives\n",
        "\t- Asks KB what action it should perform\n",
        "\t- Tells KB which action was chosen and returns the action to be executed\n",
        "- Details of representation language are hidden inside 3 functions that implement the interface between the sensors and actuators on one side and core representation and reasoning system on the other:\n",
        "\t- Make-percept-sentence: constructs a sentence asserting that the agent perceived the given percept at the given time\n",
        "\t- Make-action-query: constructs a sentence that asks what action should be done at the current time\n",
        "\t- Make-action-sentence: constructs a sentence asserting that the chosen action was executed\n",
        "- Declarative approach: knowledge-based agent can be built simply by telling it what it needs to know\n",
        "\t- Agent designer can tell sentences one by one until the agent knows how to operate in its environment\n",
        "- Procedural approach: encodes desired behaviors directly as program code\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "- Wumpus environment: deterministic, discrete, static, single-agent, sequential (rewards only come after actions are taken), partially observable\n",
        "- Transition model is unknown bc agent doesn't know which forward actions are fatal\n",
        "- Fundamental property of logical reasoning: in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "- KB consist of sentences which are expressed according to syntax of representation language\n",
        "\t- Logic must also define semantics (meaning) of sentences\n",
        "\t\t- Semantics defines truth of each sentence with respect to each possible world\n",
        "\t\t- Every sentence must be either true or false in each possible world -- there is no \"in between\"\n",
        "\t\t\t- Use \"model\" (mathematical abstractions of \"possible world\")\n",
        "\t\t- If a sentence alpha is true in model m, we say that m satisifies alpha or sometimes m is a model of alpha\n",
        "\t\t\t- M(alpha) = set of all models of alpha\n",
        "- Logical entailment between sentences: idea that a sentence follows logically from another sentence\n",
        "\t- Definition of entailment can be applied to derive conclusions (logical inference)\n",
        "  - Model checking: enumerates all possible models to check that alpha is true in all models in which KB is true\n",
        "\t- Sound / truth-preserving inference algorithm: one that derives only entailed sentences\n",
        "\t- Complete inference algorithm: if it can derive any sentence that is entailed\n",
        "- Grounding: connection between logical reasoning processes and the real environment in which the agent exists (how do we know that KB is true in the real world?)\n",
        "  - Agent's sensors create the connection\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "- Syntax of propositional logic defines the allowable sentences\n",
        "- Atomic sentences consist of a single proposition symbol\n",
        "\t- Two proposition symbols with fixed meanings:\n",
        "\t\t- True: always-true proposition\n",
        "\t\t- False: always-false proposition\n",
        "- Complex sentences: constructed from simpler sentences, using parentheses and operators called logical connectives\n",
        "\t- 5 connectives in common use: Not, And, Or, Implies (if-then), IFF (if and only if: biconditional)\n",
        "- Semantics define rules for determining the truth of a sentence wrt a particular model\n",
        "\t- In propositional logic: model simply sets the truth value (T or F) for every proposition model\n",
        "\t- Must specify how to compute the truth value of any sentence given a model (done recursively)\n",
        "\t\t- All sentences are constructed from atomic sentences and five connectives\n",
        "\t\t- Rules can be expressed with truth tables\n",
        "\t- For implies: propositional logic does not require any relation of causation or relevance between P and Q\n",
        "\t\t- Also, any implication is true whenever its antecedent (left-hand side) is false\n",
        "- Does KB entail sentence alpha? Inference alg:\n",
        "\t- Model-checking approach: enumerate the models and check that alpha is true in every model in which KB is true\n",
        "    - Sound: implements definition of entailment directly\n",
        "    - Complete: works for any KB and alpha and always terminates\n",
        "\t- Time complexity: O(2^n) (n=\\# of symbols)\n",
        "\t- Space complexity: O(n) (enumeration is depth-first)\n",
        "\t- Every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "- Entailment done by theorem proving: applying rules of inference directly to sents in KB to construct proof of desired sent w/o consulting models\n",
        "- Deduction theorem: for sents x and y, x|=y iff x=>y is valid\n",
        "- Satisfiability: checked by enumerating possible models until one is found that satisfies sent (NP-complete)\n",
        "  - Validity & satisfiability= connected (a is valid iff !a is unsatisfiable)\n",
        "- Inference rules can be applied to derive proofs\n",
        "\t- Searching for proofs = alternative to enumerating models\n",
        "    - Finding proof can be more efficient bc proof can ignore irrelevant propositions\n",
        "\t- Proof by resolution: yields a complete inference alg when coupled with any complete search alg\n",
        "\t\t- Unit resolution inference rule: takes clause and literal and produces new clause\n",
        "\t\t\t- Unit clause: single literal can be viewed as a disjunction of one literal\n",
        "\t\t- Resolve complementary literals and through factoring\n",
        "\t- Resolution-based theorem prover can, for any sents a and b in propositional logic, decide whether a entails b\n",
        "\t- Every sent of propositional logic is logically equivalent to conjunction of clauses (CNF) (only ands, ors, or nots)\n",
        "\t- Completeness of resolution\n",
        "\t\t- Resolution closure RC(S): set of clauses S which is set of all clauses derivable by repeated application of resolution rule to clauses in S or their derivatives\n",
        "\t\t- Ground resolution theorem: if set of clauses is unsatisfiable, then RC(S) of those clauses contains empty clause\n",
        "\t\t\t- Proved by demonstrating its contrapositive: if closure RC(S) doesn't contain empty clause, then S is satisfiable\n",
        "- Full power of resolution not needed (Horn & definite clauses)\n",
        "\t- Resolve 2 Horn clauses => get back a Horn clause\n",
        "\t- k-CNF sent (where each clause has at most k literals)\n",
        "\t- KB containing only definite clauses: interesting for 3 reasons:\n",
        "\t\t- Every definite clause can be written as implication whose premise(body) = conjunction of positive literals and whose conclusion(head) = single positive literal\n",
        "\t\t- Inference with Horn clauses can be done through forward-chaining and backward-chaining alg\n",
        "\t\t- Deciding entailment with Horn clauses => done in linear time in size of KB\n",
        "- Forward-chaining alg determines if single proposition symbol q (query) is entailed by KB of definite clauses\n",
        "\t- Begins from known facts (positive literals) in KB\n",
        "\t- If all premises of implication are known, then its conclusion is added to set of known facts\n",
        "\t- Process continues until query q is added or until no further inferences can be made\n",
        "\t- Runs in linear time, sound & complete\n",
        "\t- Example of general concept of data-driven reasoning (in which focus of attention starts with known data)\n",
        "- Backward-chaining alg works backward from the query\n",
        "\t- If query q known to be true, no work needed\n",
        "\t- Otherwise, alg finds those implications in KB whose conclusion is q\n",
        "\t\t- If all premises of one of those implications can be proved true (by backward chaining), then q is true\n",
        "\t- Runs in linear time\n",
        "  - Form of goal-directed reasoning\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "- Knowledge-based agents: use process of reasoning over an internal representation of knowledge to decide what action to take\n",
        "- Knowledge base (KB): contains a set of sentence that are written in a knowledge representation language\n",
        "  - Sentence contains some assertion about the world. Two kinds:\n",
        "    - Axioms: sentence that's given\n",
        "    - Derived: sentence derived from other sentences (inference)\n",
        "  - Contains background info about world and KB agent can add to info in KB through observations\n",
        "    - Can also query KB and ask it to derive new knowledge in order to select what action it should take\n",
        "- Logic: serve as general class of representations of KB agents\n",
        "  - Sentences: in representation language that has a syntax that specifies setences that are well-formed\n",
        "  - Logic defines semantics (meaning) of sentence which defines model (truth of each sentence wrt possible world)\n",
        "- Models: mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence\n",
        "- If sentence x is true in model m then:\n",
        "  - m satisfies x or\n",
        "  - m is a model of x\n",
        "- M(x): set of all models of x\n",
        "- Logical entailment: idea that a sentence follows logically from another sentence\n",
        "  - x |= y: sentence x entails sentence y\n",
        "    - x is more specific/stronger than y\n",
        "- Logical inference: entailment applied to derive conclusions\n",
        "  - \"KB |-i x\" means \"x is derived from KB by inference algorithm i\"\n",
        "- Propositional logic\n",
        "  - Atomic sentences: represented with single propositional symbols (which stand for a statement that can be T/F)\n",
        "  - Complex sentences: constructed from simpler ones using parentheses and logical connectives (not, and, or, implies, iff)\n",
        "- Sound: inference alg should only derive entailed sentences\n",
        "- Complete: inference alg can derive all sentences that are entailed\n",
        "- Logical equivalence: two sentences are logically equivalent if they are true in same set of models\n",
        "  - Also iff x|=y and y|=x\n",
        "  - Rules\n",
        "    - Contraposition: (x=>y) == (!y=>!x)\n",
        "    - Implication elimination: (x=>y) == (!x or y)\n",
        "    - Biconditional elimination: (x<=>y) == ((x=>y) and (y=>x))\n",
        "    - De Morgan: !(x and y) == (!x or !y)\n",
        "    - De Morgan: !(x or y) == (!x and !y)\n",
        "    - Distributivity of and over or: ((x and y) or z) == ((x and y) or (x and z))\n",
        "    - Distributivity of or over and: ((x or y) and z) == ((x or y) and (x or z))\n",
        "- Inference rules: used to derive proofs\n",
        "  - Modus Ponens(sound): $$\\\\frac{\\\\alpha \\\\implies \\\\beta, \\\\alpha}{\\\\beta}$$\n",
        "    - Whenever sentences of form alpha=>beta and alpha are given, sentence beta can be inferred\n",
        "  - Biconditional Elimination: $$\\\\frac{\\\\alpha \\\\iff \\\\beta}{(\\\\alpha \\\\implies \\\\beta) \\\\land (\\\\beta \\\\implies \\\\alpha)}$$\n",
        "  - $$\\\\frac{(\\\\alpha \\\\implies \\\\beta) \\\\land (\\\\beta \\\\implies \\\\alpha)}{\\\\alpha \\\\iff \\\\beta}$$\n",
        "  - And Elimination(sound): $$\\\\frac{\\\\alpha \\\\land \\\\beta}{\\\\alpha}$$\n",
        "- Monotonicity: If KB|=a then KB&b|=a\n",
        "  - Can safely add to KB without invalidating anything else that we inferred\n",
        "  - Implies soundness\n",
        "  - Single inference rule, resolution, which yields a complete inference alg when coupled with any complete search alg\n",
        "- Resolution: if l and m are complementary literals (one is the negation of the other), can eliminate them via unit resolution\n",
        "  - Only applies to clauses (disjunctions of literals)\n",
        "- Conjunctive Normal Form (CNF)\n",
        "  - Eliminate <=> by replacing x<=>y with (x=>y) and (y=>x)\n",
        "  - Eliminate => by replace x=>y with (!x or y)\n",
        "  - Move ! inwards (eliminate double negation and apply De Morgan's rules)\n",
        "  - Sentence will contain nested and/or operators: apply distributivity law to distribute or over and wherever possible\n",
        "- Resolution alg (complete): inference procedures based on resolution work using the principle of proof by contradiction\n",
        "  - To show KB|=x, we can show that KB and !x is unsatisfiable\n",
        "    - Convert (KB and !x) into CNF\n",
        "    - Apply resolution rule to resulting clauses\n",
        "    - Resolve every pair that contains complementary literals to produce a new clause\n",
        "    - If new clause isn't already present, add to the set\n",
        "    - Continue until either:\n",
        "      - No new clauses that can be added (KB does not entail x)\n",
        "      - Two clauses resolve to yield emply clause (KB does entail x)\n",
        "        - Empty clause: arises from resolving two contradictory unit clauses like P and !P\n",
        "- Don't always need full power resolution: some KBs formulated in more restrictive form (enables them to use more efficient inference alg)\n",
        "  - Definite clause: disjunction of literals where exactly one is positive\n",
        "  - Horn clause: disjunction of literals where at MOST one is positive\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\": \"set of sentences\",\n",
        "\"sentence\": \"represents some truth about world\",\n",
        "\"inference\": \"deriving new sentences from old\",\n",
        "\"knowledge level\": \"specifying what agent knows and what its goals are are enough to determine its behavior\",\n",
        "\"axiom\": \"sentence is taken as given (not derived)\",\n",
        "\"logical equivalence\": \"if two sentences a and b true in the same set of models\",\n",
        "\"validity\": \"if sentence it is true in all models (tautologies)\",\n",
        "\"satisfiable\": \"if sentence is true in, or satisfied by, some model\",\n",
        "\"clause\": \"disjunction of literals\",\n",
        "\"complementary literals\": \"literal and the negation of the literal\",\n",
        "\"factoring\": \"removal of multiple copies of literals\",\n",
        "\"goal clauses\": \"have no positive literals\",\n",
        "\"fact\":\"sentence of a single positive literal\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 98,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XBDcNxcVe-MN",
        "outputId": "d1dea20b-36ce-43c3-bd3e-cb97bf72b716"
      },
      "source": [
        "len(chapter7_5.split(\" \"))\n",
        "len(chapter7_5)"
      ],
      "execution_count": 99,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2988"
            ]
          },
          "metadata": {},
          "execution_count": 99
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b40ba4d5-6a9d-4424-a602-7a168c4932fc"
      },
      "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": 100,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n- Central component of knowledge-based agent: knowledge base (KB)\n\t- KB may initially contain some background knowledge\n\t- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world\n- Tell & Ask: ways to add new sentences to KB and a way to query what's known\n\t- Both may involve inference\n- Each time agent program is called:\n\t- Tells KB what it perceives\n\t- Asks KB what action it should perform\n\t- Tells KB which action was chosen and returns the action to be executed\n- Details of representation language are hidden inside 3 functions that implement the interface between the sensors and actuators on one side and core representation and reasoning system on the other:\n\t- Make-percept-sentence: constructs a sentence asserting that the agent perceived the given percept at the given time\n\t- Make-action-query: constructs a sentence that asks what action should be done at the current time\n\t- Make-action-sentence: constructs a sentence asserting that the chosen action was executed\n- Declarative approach: knowledge-based agent can be built simply by telling it what it needs to know\n\t- Agent designer can tell sentences one by one until the agent knows how to operate in its environment\n- Procedural approach: encodes desired behaviors directly as program code\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Wumpus environment: deterministic, discrete, static, single-agent, sequential (rewards only come after actions are taken), partially observable\n- Transition model is unknown bc agent doesn't know which forward actions are fatal\n- Fundamental property of logical reasoning: in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct\n\n\n## AIMA Chapter 7.3 Logic\n\n- KB consist of sentences which are expressed according to syntax of representation language\n\t- Logic must also define semantics (meaning) of sentences\n\t\t- Semantics defines truth of each sentence with respect to each possible world\n\t\t- Every sentence must be either true or false in each possible world -- there is no \"in between\"\n\t\t\t- Use \"model\" (mathematical abstractions of \"possible world\")\n\t\t- If a sentence alpha is true in model m, we say that m satisifies alpha or sometimes m is a model of alpha\n\t\t\t- M(alpha) = set of all models of alpha\n- Logical entailment between sentences: idea that a sentence follows logically from another sentence\n\t- Definition of entailment can be applied to derive conclusions (logical inference)\n  - Model checking: enumerates all possible models to check that alpha is true in all models in which KB is true\n\t- Sound / truth-preserving inference algorithm: one that derives only entailed sentences\n\t- Complete inference algorithm: if it can derive any sentence that is entailed\n- Grounding: connection between logical reasoning processes and the real environment in which the agent exists (how do we know that KB is true in the real world?)\n  - Agent's sensors create the connection\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- Syntax of propositional logic defines the allowable sentences\n- Atomic sentences consist of a single proposition symbol\n\t- Two proposition symbols with fixed meanings:\n\t\t- True: always-true proposition\n\t\t- False: always-false proposition\n- Complex sentences: constructed from simpler sentences, using parentheses and operators called logical connectives\n\t- 5 connectives in common use: Not, And, Or, Implies (if-then), IFF (if and only if: biconditional)\n- Semantics define rules for determining the truth of a sentence wrt a particular model\n\t- In propositional logic: model simply sets the truth value (T or F) for every proposition model\n\t- Must specify how to compute the truth value of any sentence given a model (done recursively)\n\t\t- All sentences are constructed from atomic sentences and five connectives\n\t\t- Rules can be expressed with truth tables\n\t- For implies: propositional logic does not require any relation of causation or relevance between P and Q\n\t\t- Also, any implication is true whenever its antecedent (left-hand side) is false\n- Does KB entail sentence alpha? Inference alg:\n\t- Model-checking approach: enumerate the models and check that alpha is true in every model in which KB is true\n    - Sound: implements definition of entailment directly\n    - Complete: works for any KB and alpha and always terminates\n\t- Time complexity: O(2^n) (n=\\# of symbols)\n\t- Space complexity: O(n) (enumeration is depth-first)\n\t- Every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- Entailment done by theorem proving: applying rules of inference directly to sents in KB to construct proof of desired sent w/o consulting models\n- Deduction theorem: for sents x and y, x|=y iff x=>y is valid\n- Satisfiability: checked by enumerating possible models until one is found that satisfies sent (NP-complete)\n  - Validity & satisfiability= connected (a is valid iff !a is unsatisfiable)\n- Inference rules can be applied to derive proofs\n\t- Searching for proofs = alternative to enumerating models\n    - Finding proof can be more efficient bc proof can ignore irrelevant propositions\n\t- Proof by resolution: yields a complete inference alg when coupled with any complete search alg\n\t\t- Unit resolution inference rule: takes clause and literal and produces new clause\n\t\t\t- Unit clause: single literal can be viewed as a disjunction of one literal\n\t\t- Resolve complementary literals and through factoring\n\t- Resolution-based theorem prover can, for any sents a and b in propositional logic, decide whether a entails b\n\t- Every sent of propositional logic is logically equivalent to conjunction of clauses (CNF) (only ands, ors, or nots)\n\t- Completeness of resolution\n\t\t- Resolution closure RC(S): set of clauses S which is set of all clauses derivable by repeated application of resolution rule to clauses in S or their derivatives\n\t\t- Ground resolution theorem: if set of clauses is unsatisfiable, then RC(S) of those clauses contains empty clause\n\t\t\t- Proved by demonstrating its contrapositive: if closure RC(S) doesn't contain empty clause, then S is satisfiable\n- Full power of resolution not needed (Horn & definite clauses)\n\t- Resolve 2 Horn clauses => get back a Horn clause\n\t- k-CNF sent (where each clause has at most k literals)\n\t- KB containing only definite clauses: interesting for 3 reasons:\n\t\t- Every definite clause can be written as implication whose premise(body) = conjunction of positive literals and whose conclusion(head) = single positive literal\n\t\t- Inference with Horn clauses can be done through forward-chaining and backward-chaining alg\n\t\t- Deciding entailment with Horn clauses => done in linear time in size of KB\n- Forward-chaining alg determines if single proposition symbol q (query) is entailed by KB of definite clauses\n\t- Begins from known facts (positive literals) in KB\n\t- If all premises of implication are known, then its conclusion is added to set of known facts\n\t- Process continues until query q is added or until no further inferences can be made\n\t- Runs in linear time, sound & complete\n\t- Example of general concept of data-driven reasoning (in which focus of attention starts with known data)\n- Backward-chaining alg works backward from the query\n\t- If query q known to be true, no work needed\n\t- Otherwise, alg finds those implications in KB whose conclusion is q\n\t\t- If all premises of one of those implications can be proved true (by backward chaining), then q is true\n\t- Runs in linear time\n  - Form of goal-directed reasoning\n\n\n## Module 7 Lecture Notes\n\n- Knowledge-based agents: use process of reasoning over an internal representation of knowledge to decide what action to take\n- Knowledge base (KB): contains a set of sentence that are written in a knowledge representation language\n  - Sentence contains some assertion about the world. Two kinds:\n    - Axioms: sentence that's given\n    - Derived: sentence derived from other sentences (inference)\n  - Contains background info about world and KB agent can add to info in KB through observations\n    - Can also query KB and ask it to derive new knowledge in order to select what action it should take\n- Logic: serve as general class of representations of KB agents\n  - Sentences: in representation language that has a syntax that specifies setences that are well-formed\n  - Logic defines semantics (meaning) of sentence which defines model (truth of each sentence wrt possible world)\n- Models: mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence\n- If sentence x is true in model m then:\n  - m satisfies x or\n  - m is a model of x\n- M(x): set of all models of x\n- Logical entailment: idea that a sentence follows logically from another sentence\n  - x |= y: sentence x entails sentence y\n    - x is more specific/stronger than y\n- Logical inference: entailment applied to derive conclusions\n  - \"KB |-i x\" means \"x is derived from KB by inference algorithm i\"\n- Propositional logic\n  - Atomic sentences: represented with single propositional symbols (which stand for a statement that can be T/F)\n  - Complex sentences: constructed from simpler ones using parentheses and logical connectives (not, and, or, implies, iff)\n- Sound: inference alg should only derive entailed sentences\n- Complete: inference alg can derive all sentences that are entailed\n- Logical equivalence: two sentences are logically equivalent if they are true in same set of models\n  - Also iff x|=y and y|=x\n  - Rules\n    - Contraposition: (x=>y) == (!y=>!x)\n    - Implication elimination: (x=>y) == (!x or y)\n    - Biconditional elimination: (x<=>y) == ((x=>y) and (y=>x))\n    - De Morgan: !(x and y) == (!x or !y)\n    - De Morgan: !(x or y) == (!x and !y)\n    - Distributivity of and over or: ((x and y) or z) == ((x and y) or (x and z))\n    - Distributivity of or over and: ((x or y) and z) == ((x or y) and (x or z))\n- Inference rules: used to derive proofs\n  - Modus Ponens(sound): $$\\frac{\\alpha \\implies \\beta, \\alpha}{\\beta}$$\n    - Whenever sentences of form alpha=>beta and alpha are given, sentence beta can be inferred\n  - Biconditional Elimination: $$\\frac{\\alpha \\iff \\beta}{(\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)}$$\n  - $$\\frac{(\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)}{\\alpha \\iff \\beta}$$\n  - And Elimination(sound): $$\\frac{\\alpha \\land \\beta}{\\alpha}$$\n- Monotonicity: If KB|=a then KB&b|=a\n  - Can safely add to KB without invalidating anything else that we inferred\n  - Implies soundness\n  - Single inference rule, resolution, which yields a complete inference alg when coupled with any complete search alg\n- Resolution: if l and m are complementary literals (one is the negation of the other), can eliminate them via unit resolution\n  - Only applies to clauses (disjunctions of literals)\n- Conjunctive Normal Form (CNF)\n  - Eliminate <=> by replacing x<=>y with (x=>y) and (y=>x)\n  - Eliminate => by replace x=>y with (!x or y)\n  - Move ! inwards (eliminate double negation and apply De Morgan's rules)\n  - Sentence will contain nested and/or operators: apply distributivity law to distribute or over and wherever possible\n- Resolution alg (complete): inference procedures based on resolution work using the principle of proof by contradiction\n  - To show KB|=x, we can show that KB and !x is unsatisfiable\n    - Convert (KB and !x) into CNF\n    - Apply resolution rule to resulting clauses\n    - Resolve every pair that contains complementary literals to produce a new clause\n    - If new clause isn't already present, add to the set\n    - Continue until either:\n      - No new clauses that can be added (KB does not entail x)\n      - Two clauses resolve to yield emply clause (KB does entail x)\n        - Empty clause: arises from resolving two contradictory unit clauses like P and !P\n- Don't always need full power resolution: some KBs formulated in more restrictive form (enables them to use more efficient inference alg)\n  - Definite clause: disjunction of literals where exactly one is positive\n  - Horn clause: disjunction of literals where at MOST one is positive\n\n\n## Module 7 Definitions\n* **Knowledge base** - set of sentences\n* **Sentence** - represents some truth about world\n* **Inference** - deriving new sentences from old\n* **Knowledge level** - specifying what agent knows and what its goals are are enough to determine its behavior\n* **Axiom** - sentence is taken as given (not derived)\n* **Logical equivalence** - if two sentences a and b true in the same set of models\n* **Validity** - if sentence it is true in all models (tautologies)\n* **Satisfiable** - if sentence is true in, or satisfied by, some model\n* **Clause** - disjunction of literals\n* **Complementary literals** - literal and the negation of the literal\n* **Factoring** - removal of multiple copies of literals\n* **Goal clauses** - have no positive literals\n* **Fact** - sentence of a single positive literal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Hr0I5ddrBU0K"
      },
      "source": [
        "|  P  |  Q  | P => Q | P <=> Q |\n",
        "| :-: | :-: | :----: | :-----: |\n",
        "|  T  |  T  |   T   |  T  |\n",
        "|  T  |  F  |   F   |  F  |\n",
        "|  F  |  T  |   T   |  F  |\n",
        "|  F  |  F  |   T   |  T  |"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "2b816794-0d88-4c82-8843-c308ddea62a9"
      },
      "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": 101,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- Two dimensions (4 combos): Human vs. Rational and Thought vs. Behavior\n- Turing test: computer passes if human interrogator cannot tell if responses come from person or computer (viewed physical simulation of person as unnecessary to demonstrate intelligence)\n- Computer needs: NLP, knowledge representation, automated reasoning, machine learning\n- Total Turing test: requires interaction with objects & people in real world (need computer vision & robotics)\n\n- Learn about human thought: introspection, psychological experiments, brain imaging\n- Program's input-output behavior matches human's: evidence program's mechanisms might operate in humans\n\n- Logic requires knowledge of world that is certain (seldom happens): Theory of probability fills this gap -- allows construction of comprehensive model of rational though, but does not generate intelligent behavior\n\n- Making correct inferences: part of being rational agent, but sometimes there are ways of acting rationally that cannot involve inference\n- Skills needed for Turing test also allow agent to act rationally\n- Rational-agent approach to AI: more general than \"laws of thought\" approach and more amenable to scientific development\n- Standard model: AI has focused on the study and construction of agents that do the right thing (what counts as right thing is defined by objective we provide to agent)\n- Perfect rationality too high of computational costs: limited rationality is fine\n\n- Standard model not great in long-run because assumes we supply fully specified objective to the machine\n- Value alignment problem: Problem of achieving agreement between true preferences & the objective we put into machine -- those put into machine must align with that of human\n- Want agents that are provably beneficial to humans\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n- John Searle: distinction between weak AI (machines act as if they're intelligent) and strong AI (machines that do so are actually consciously thinking)\n- Turing's \"argument from informality of behavior\": human behavior is far too complex to be captured by any formal set of rules (must use informal guidelines)\n- Good Old-Fashioned AI (GOFAI): corresponds to simplest logical agent\n- Embodied cognition approach: makes no sense to consider brain separately\n\n- \"Argument from disability\": claim that a machine can never do X (be kind, resourceful, beautiful, etc)\n- For any formal axiomatic framework F powerful enough to do arithmetic, possible to construct Godel sentence G(F) with properties: G(F) is a sentence of F, but cannot be proved with F & if F is consistent, then G(F) is true\n- (Lucas) Machines are formal systems that are limited by incompleteness theorem (cannot establish the truth of their own Godel sentence)\n- 3problems with Lucas claim: agent should not be ashamed that it cannot establish the truth of some sentence while other agents can; Godel's incompleteness theorem & related results apply to math, not computers and technically applies only to formal systems that're powerful enough to do arithmetic\n\n\n## AIMA Chapter 27.2 Can Machines Really Think?\n\n- Turing: usual to have polite convention that everyone thinks\n- Searle rejects polite convention: Chinese room does same as computer, therefore computers generate no understanding\n- Searle proponent of biological naturalism: mental states are high-level emergent features that are caused by low-level physical processes in the neurons\n- Qualia: term for intrinsic nature of experiences\n\n\n## AIMA 2.1 Agents and Environments\n\n- Agent's choice of action at any given instance can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived\n- Agent's behavior: described by agent function that maps any given percept sequence to an action\n- Can tabulate all possible percept sequences and recording which actions agent does in response (external characterization)\n- Internal characterization: agent function for an artificial agent will be implemented by agent program\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- Rational agent: does right thing, but what is right thing?\n- AI usually concerned with consequentialism: evaluate an agent's behavior by its consequences\n- Desirability of sequence of actions through a sequence of states: captured by performance measure that evals any given sequence of environment states\n- Machines do not have desires/preferences of their own: performance measure is in the mind of the designer of the machine (initially)\n- Better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave\n\n- Rational depends on 4things: 1) performance measure that defines criterion of success; 2) agent's prior knowledge of environment; 3) actions agent can perform; 4) agent's percept sequence to date\n- Rational agent: for each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has\n- Rationality maximizes expected performance, while perfection maximizes actual performance\n- Rationality does not require omniscience because the rational choice depends only on the percept sequence to date\n- Information gathering: important part of rationality\n- Want rational agent not only to gather information, but also to learn as much as possible from what it perceives\n- RA should be autonomous: learn what it can to compensate for partial or incorrect prior knowledge\n\n\n## AIMA 2.3 The Nature of Environments\n\n- Task environment: the 'problems' to which rational agents are the 'solutions'\n- Grouped under task environment: PEAS (Performance, Environment, Actuators, Sensors)\n- Fully observable vs partially observable: fully if sensors give agent access to complete state of environment at each point in time\n  - If sensors detect all aspects that are relevant to the choice of action (relevance depends on performance measure)\n  - Convenient in that agent doesn't need to maintain any internal state to keep track of the world\n  - No sensors: unobservable\n- Single-agent vs multiagent: treat an object B as an agent if B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior\n  - Chess: competitive multiagent environment\n    - In some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability \n  - Taxi-driving: cooperative multiagent environment\n- Deterministic vs nondeterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say deterministic\n  - Stochastic: if it explicitly deals with probabilities\n  - Nondeterministic: if possibilities are listed without being quantified\n- Episodic vs sequential: agent's experience divided into atomic episodes; in each episode, agent receives a percept and then performs a single action\n  - Sequential: current decision could affect all future decisions\n- Static vs dynamic: dynamic if environment can change while agent deliberates\n  - Semidynamic if environment doesn't change with passage of time, but agent's performance score does (i.e. chess w/ clock)\n- Discrete vs continuous: applies to state of environment, the way time is handled, and to the percepts & actions of agent\n- Known vs unknown: refers not to environment itself, but to agent's state of knowledge about the 'laws of physics' of the environment\n- Hardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous and unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- 4kinds of agent programs that embody principles underlying almost all intelligent systems: simple reflex; model-based reflex; goal-based; utility-based agents\n- Simple reflex agent\n  - Simple reflex behaviors occur even in more complex environment (condition-action rule, i.e. if-then)\n  - Will work only if correct decision can be made on basis of just current percept (only if environment is fully observable)\n  - Infinite loops often unavoidable for SRA operating in partially observable environments\n    - Escape possible if agent can randomize actions\n    - Randomized SRA might outperform deterministic SRA\n  - In single-agent environments, randomization usually not rational\n- Model-based reflex agents: use transition model and sensor model which allow agent to keep track of state of world\n  - Most effective way to handle partial observability is for agent to keep track of the part of the world it can't see now\n  - Maintain internal state that depends on percept history (thereby reflects at least some of unobserved aspects of current state)\n    - Need info about how world changes over time (2parts)\n      - Effects of agent's actions\n      - How world evolves independently of agent\n      - 'How world works': transition model of world\n    - Need info about how state of world is reflected in agent's percepts (sensor model)\n  - Agent best guesses current state of partially observable environment\n- Goal-based agents\n  - Different from condition-action rules -> involves consideration of future\n  - Less efficient, but more flexible because knowledge that supports its decisions is represented explicitly and can be modified\n- Utility-based agents: has to model and keep track of its environment\n  - General performance measure should allow a comparison of different world states according to utility function\n  - 2cases where goals inadequate but utility-based can still make rational decisions:\n    - When conflicting goals, utility function specifies appropriate tradeoff\n    - When several goals, utility provides way in which likelihood of success can be weighed against importance of goals\n  - Maximize expected utility due to partial observability and nondeterminism\n- Learning agent can be divided into 4conceptual components:\n  - Learning element: responsible for making improvements\n    - Uses feedback from critic and determines how the performance element should be modified to do better in future\n    - Design depends very much on design of performance element\n  - Performance element: responsible for selecting external actions\n  - Critic: tells learning element how well agent is doing with respect to fixed performance standard (percepts themselves provide no indication of agent's success)\n  - Problem generator: responsible for suggesting actions that will lead to new and informative experiences\n    - If agent willing to explore little in short run, might discover better actions for long run\n\n\n## Module 1 Lecture Notes\n\n- Rene Descartes (1596-1650): principle of dualism that the mind or thinking self is essentially incorporeal or spiritual (that mind exists separately from body)\n  - How can I know you are not an automaton?\n- Alan Turing (1912-1954): 'Are there imaginable digital computers which would do well in the imitation game?'\n  - Human evaluator judge text-based conversations between a human and machine designed to generate human-like responses\n  - If cannot tell machine from human, machine passes test\n  - Does not depend on correctness of answers, just how closely answer resembles those a human would give\n- John Searle (1932-): Chinese room: machines don't possess intelligence, it just gave impression of intelligence through simple symbol manipulation\n  - Strong AI: computer really is a mind (can be literally said to understand and have other cognitive states)\n  - Weak AI: computer just simulates thought (seeming understanding isn't true understanding)\n  - Biological brains cause minds\n- Daniel Dennett (1942-): Brain in vat\n- AI: science of making machines that think and act like people\n- Agent is specified by agent function f:P->a that maps a sequence of percept vectors P to an action a from a set of A\n- 'Easy' solution: giant table that maps every possible sequence P to an action a (Problem: exponential in length of P)\n- Rational agent: agent that perceives its environment and behaves rationally\n  - For each possible percept sequence P, a rational agent selects an action a to maximizes expected value of its performance measure\n- Does the 'right thing': define performance measure which is\n  - an objective criterion for success of an agent's behavior\n  - given the evidence provided by the percept sequence\n- Ideal agent maximizes actual performance, but needs to be omniscient (usually impossible)\n  - Computational limitations make complete rationality unachievable: design best program for given machine resources\n- Goal of AI practitioner who designs rational agents: given PEAS task environment:\n  - Construct agent function f that maximizes expected value of the performance measure\n  - Design agent program that implements f on particular architecture\n- When something's behavior can best be described as having its own performance measure -> consider to be agent\n- Simple reflex agent: select actions on basis of current percept, ignoring rest of percept history\n- Problem-solving agent must plan ahead\n  - will consider a sequence of actions that form a path to a goal state\n\n\n## Module 1 Definitions\n* **Rational agent** - agent that acts to obtain best expected outcome\n* **Omniscient agent** - knows the actual outcome of its actions and can act accordingly (impossible in reality)\n* **Perfect rationality** - always take optimal action\n* **Limited rationality** - acting appropriately when there's computational time limitations on deciding what to do\n* **Qualification problem** - difficult to capture every combo of appropriate behavior\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - what an agent's sensors perceived\n* **Percept sequence** - complete history of what has ever been perceived by agent\n* **Agent function** - abstract mathematical description\n* **Agent program** - actual implementation\n* **Performance measure** - measure that evaluates given sequence of states\n* **Information gathering** - doing actions in order to modify future percepts\n* **Agent architecture** - agent = architecture + program\n* **Atomic representation** - each state is indivisible (has no internal structure)\n* **Factored representation** - each state split up into fixed set of variables where each can have a value\n* **Structured representation** - objects and their varying relationships are described explicitly\n* **Localist representation** - one-to-one mapping between concepts and memory locations\n* **Distributed representation** - representation of concept spread over many memory locations and each part of representation of multiple different concepts\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n- Developed by Guido van Rossum in 1989\n- Python inspired by ABC language\n- Positive features: fast development (concise, intuitive, garbage collected); portable (progs run on major platforms w/o change); various built-in types; large collection of support libraries\n- PEP: Python Enhancement Proposals\n- REPL: Read-Evaluate-Print Loop (type python3 in terminal)\n- Scripts: create .py file and run python3 file.py\n- Objects & Types\n  - All data treated as objects\n  - Strongly typed: every object has a fixed type, interpreter doesn't allow things incompatible with that type\n    - Check using type(object) or isinstance(object, type)\n    - Types: int, float, str, tuple, dict, list, bool, None, generator, function\n  - Python: dynamic typing - variables come into existence when first assigned\n    - Java: static typing - variables need type to be explicitly defined\n    - Functions have no type signatures\n    - Con: type errors only caught at runtime\n- Strings: print(\"%s can speak %d languages\" %(\"C3PO\", 5000))\n  - Immutable\n    - '==' checks whether variables point to objects of same value\n    - 'is' checks whether variables point to same object\n- Lists are mutable\n  - y=x[:] gets shallow copy of any sequence\n  - Operations: .append(), .insert(2,'i'), .index('b'), .count('b'), .remove('b'), .reverse(); .sort()\n- Dictionaries\n  - Unordered & work by hashing (so keys must be immutable)\n  - from collections import defaultdict, Counter\n    - defaultdict automatically initializes nonexistent dictionary values\n    - if d=Counter, d['dog'] += 10; d['dog'] would print dog\n- Functions\n  - Returns None if no return defined\n  - No declaration of types of arguments or result\n  - Python allows you to return multiple values (tuple)\n  - Python does not allow function overloading like Java (which allows add(int) and add(int,int))\n    - Allows operator overloading (+, ==, -, etc)\n  - Can specify default values for function's arguments\n    - Non-default argument should always precede default arguments; otherwise SyntaxError\n  - *args: suppose you want to accept a variable # of non-keyword arguments to your function\n    - args = tuple of arguments passed to fn\n    - Can just pass in parameters\n    - Can pass in list of parameters: when called, precede with * (print_everything(*lst))\n  - **kwargs: suppose you want to accept a variable # of keyword arguments to your function\n    - kwargs = dict of keyword args pass to fn\n    - example(first='John', last='Doe') => {'first':'John', 'last':'Doe'}\n    - Can pass in dictionary of parameters (print_everything(**my_dict))\n  - Uses dynamic scope: function sees most current value of variables (even if not defined within function)\n  - Memoization: optimization technique used to store the results of expensive function calls and returns a cached result\n  - \"First-class\" objects: entity can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n- Classes & Inheritance\n  - Subclass extends parent/ancestor/superclass\n    - To define: put name of superclass in parentheses after subclass's name on first line of definition (class AI_Student(Student):)\n    - To override method in parent class: just use same name of method\n    - If need to call parent's method version, explicitly pass in 'self' as argument: parentClass.methodName(self,a,b,c)\n- \"Magic\" methods: \\_\\_init\\_\\_, \\_\\_len\\_\\_, \\_\\_copy\\_\\_, \\_\\_cmp\\_\\_ (==), \\_\\_add\\_\\_, \\_\\_neg\\_\\_\n- if \\_\\_name\\_\\_ == '\\_\\_main\\_\\_':\n  - \\_\\_name\\_\\_: built-in variable which evaluates to the name of the current module\n  - Interpreter sets \\_\\_name\\_\\_ variable to have value '\\_\\_main\\_\\_' for source file that is being executed on command line\n  - No built-in main method (no \"def main()\")\n- Duck typing: establishes suitability of an object by determining presence of methods\n- Generators: iterators (with \\_\\_next()\\_\\_ method) using yield keyword\n  - Each time we call \\_\\_next\\_\\_ method of generator, method runs until it encounters a yield statement, stops, and returns value that was yielded\n  - Next time, resumes where it left off\n  - Benefits:\n    - Less code than writing a standard iterator\n    - Maintains local state automatically\n    - Values are computed one at a time as needed\n    - Avoids storing entire sequence in memory\n    - Good for aggregating (summing, counting) items. One pass\n    - Curcial for infinite sequences\n    - Bad if need to inspect individual values\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n- Four-phase problem-solving process:\n  - Goal formulation\n  - Problem formulation\n  - Search (simulate sequences of actions in its model)\n  - Execution (execuate actions in solution one at a time)\n- Total cost of path=sum of individual action costs\n- State space represented as graph (vertices=states; directed edges=actions)\n- Abstraction=valid if can elaborate any abstract solution into solution in more detailed world\n- Abstraction=useful if carrying out each action in solution is easier than original problem\n- Choice of good abstraction: remove as much detail as possible while retaining validity and ensuring abstract actions are easy to carry out\n\n\n## AIMA Chapter 3.2 Example Problems\n\n- Every problem formulation involves abstractions\n- Touring problems: describe a set of locations that must be visited rather than a single goal destination\n- VLSI (Very large-scale integration) layout problem: split into cell layout and channel routing\n- Other types: robot navigation, automatic assembly sequencing\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n- How do we decide which node from the frontier to expand next?\n  - Best-first search: choose a node n with minimum value of some evaluation function f(n)\n    - On each iteration, we choose a node on the frontier with minimum f(n) value, return it if its state is a goal state; otherwise apply expand to generate child nodes\n    - Each child node added to frontier: either never been visited or re-added if now being reached with path with lower path cost than previous path\n    - Return indication of failure or node that represents a path to goal\n- Node represented by: state, parent, action, path cost (total cost of path from initial state to this node)\n- 3approaches to remembering previous states:\n  - Remember all previously reached states: appropriate when many redundant paths & preferred when table of reached states fit in memory\n  - Just not worry about repeating past: use when reaching same state is rare; save memory space and don't check for redundant paths\n    - Graph search: checks for redundant paths\n    - Tree-like search: does not check\n  - Check for cycles but not redundant paths in general\n    - Can check for cycles with no need for additional memory by following up chain of parents to see if the state at end of path has appeared earlier in path\n- Complete algorithm must be capable of systematically exploring every state that is reachable from initial state\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- Uninformed search algorithm: given no clue about how close a state is to goals\n- BFS: reached can be set of states rather than mapping from states to nodes because once we've reached a state, we can never find a better path to the state\n  - Early goal test: checking whether a node is a solution as soon as it's generated\n  - Best-first search uses late goal test (waiting until node is popped off queue)\n  - Cost-optimal for problems where all actions have same cost; otherwise no\n  - Memory requirements are bigger problem than execution time\n- Dijkstra's algorithm / uniform-cost search: when actions have different costs-> use best-first search where eval function is cost of path from root to current node\n  - Uniform-cost search spreads out in waves of uniform path-cost\n  - Complete and is cost-optimal because the first solution it finds will have a cost that is at least as low as the cost of any other node in frontier\n- DFS: variant called backtracking search uses even less memory\n  - Only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next\n  - Successors are generated by modifying the current state description directly rather than allocating memory for a brand-new state\n  - Reduces memory requirements to just O(m)\n- Bidirectional search: simultaneously searches forward from initial state and backwards from goal state, hoping that two searches will meet\n  - Need to keep track of two frontiers and two tables of reached states\n\n\n## Module 3 Lecture Notes\n\n- Problem-solving agent plans ahead and considers a sequence of actions that form a path to a goal state (search for a solution)\n- If environment is fully observable, deterministic, known: solution=fixed sequence of actions\n- If partially observable or nondeterministic: solution must recommend different future actions depending on what the percept receives (could be form of branching strategy)\n- Defining search problem: states, initial state, actions, transition model, path cost (performance measure), goal test\n  - Path cost: sum of all action costs along a path\n- When formulating search problem, decide:\n  - Which properties matter & how to represent (initial/intermediate/goal states)\n  - Which actions are possible & how to represent (actions/transition model)\n  - Which action is next (path cost function)\n- Formulation greatly affects combinatorics of search space and therefore speed of search\n- State space: set of all states reachable from initial state by any sequence of actions\n  - When several operators can apply to each state, this gets large very quickly\n  - Might be proper subset of the set of configurations\n- Path: sequence of actions leading from one state sj -> state sk\n- Solution: path from initial state si to state sf that satisfies the goal test\n- Search tree: way of representing paths that search algorithm has explored. Root=initial state, leaves=successors.\n- Frontier: those states that are available for expanding (for applying legal actions to)\n- Optimal solution: if no solution has lower path cost\n- Generalized algorithm to solve searches: enumerate in some order all possible paths from initial state\n- State=physical configuration (no parents,children,etc); node=data structure constituting part of search tree\n- Failure to detect repeated states-> turn linear problem into exponential\n  - Graph search: check if node has been visited before adding to search queue\n- Uninformed: all non-goal nodes in frontier look equally good; Informed: some non-goal nodes can be ranked higher\n- Dimensions for evaluation: completeness (always solution?), optimality (lowest path cost first?), time (# nodes generated) & space (# nodes simultaneously in memory) complexity\n- Time/space variables: b(max branching factor); d(depth of shallowest goal node); m(max length of any path in state space)\n- BFS(FIFO): expand shallowest unexpanded node; use if: possible infinite paths; some solutions have short paths and wrong paths are usually terminated quickly; can quickly discard unlikely paths\n- DFS(LIFO): expand deepest unexpanded node; use if: space is restricted; many possible solutions with long paths; search can be fine-tuned quickly\n- Depth-limited: DFS with depthlimit 1; if l<d:incomplete; l>d:not optimal\n- Iterative deepening search: depth-limited as subroutine with increasing l\n  - Complete & optimal: goal always found at depth d\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop approach** - agent executes action in solutions without monitoring percepts (risky if model incorrect)\n* **Closed-loop approach** - agent monitors percepts (necessary for nondeterministic)\n* **State space** - set of possible states of environment\n* **Transition model** - describes what an action in a given state does\n* **Action cost function** - assigns numeric cost of doing action a in state s to reach s'\n* **Abstraction** - removing detail from representation\n* **Standardized problem** - used to show various problem-solving methods\n* **Real-world problem** - solutions are actually applicable and formulation are unique (not standardized)\n* **Absolute actions** - actions of absolute values\n* **Egocentric actions** - defined relative to viewpoint of agent\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n- Greedy best-first search: expands first node with lowest h(n) (likely find sol quickly)\n  - Straight-line distance for route-finding probs \n\t- Complete only in finite \n\t- Worst-case time/space complexity: O(|V|)\n- A* search: complete\n\t- Cost-optimal depends on admissibility & consistency of h(n)\n\t\t- If admissible, A*=cost-optimal\n\t\t- Every consistent h(n) is admissible (not vice versa) therefore cost-optimal\n\t\t- 1st time reach state-> on optimal path so never have to re-add state to frontier or change entry in reached\n\t\t- If inadmissible, may be cost-optimal if:\n\t\t\t- There's even 1 cost-optimal path on which h(n) is admissible for all nodes n on path, then that path will be found, no matter what h(n) says for states off path\n\t\t\t- Optimal sol has cost C*, 2nd best=C2, & if h(n) overestimates some costs but never by more than C2-C*, then A* guaranteed to return cost-optimal sols\n- f=g+h cost monotonically increase iff h consistent\n- A*=efficient bc prunes away search tree nodes not necessary for finding optimal sol\n- Satisficing sols: suboptimal, but \"good enough\" (explore fewer nodes, saving time/space)\n\t- Using inadmissible h(n), risk missing optimal sol, but may be more accurate\n- Weighted A*: weight h(n) more heavily (Somewhat-greedy: Like greedy best-first search, focus search towards goal but won't ignore path cost completely & will suspend path that's making little progress at great cost)\n- Suboptimal search alg:\n\t- Bounded: look for sol guaranteed to be within constant factor of optimal cost\n\t- Bounded-cost: look for sol where cost < constant\n\t- Unbounded-cost: accept sol of any cost just find quickly\n\t\t- Speedy search: version of greedy best-first where h(n)=est.# actions required to reach goal, regardless of cost of actions\n- A* memory-intensive\n- Beam search limits size of frontier by keeping only k-nodes w/ best f-scores\n\t- Incomplete & suboptimal, but better use of memory & faster\n\t- Alt: keep node whose f-score is within x of the best f-score\n- Iterative-deepening A*: A* w/o requirement to keep all reached states in memory at cost of visiting some states multiple times\n- Recursive best-first search: mimic operation of standard best-first search but only using linear space\n  - Like recursive DFS, but use f_limit variable to track f of best alt path avail. from any ancestor of current node\n  - If current node > limit, recursion unwinds back to alt path; as unwinds, RBFS replaces f for each node along path w/ backed-up val (best f of children)\n\t- Bit more efficient than IDA*, but still suffers from excessive node generation\n\t- Optimal if h(n) admissible\n  - Space complexity=linear (time hard to say)\n- IDA & RBFS use too little memory: try use all\n\t- Simplified MA*: like A*, expand best leaf until memory full, drop oldest worst leaf node (one w/ highest f), then back up val of forgotten node (like RBFS)\n    - Complete if any reachable sol (d < memory size)\n    - Optimal if any optimal sol is reachable; else returns best reachable sol\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- One way to characterize quality of a heuristic is the effective branching factor b*\n\t- Well-designed heuristic: b* close to 1, allowing fairly large problems to be solved at reasonable computational cost\n- Better way to characterize effect of A* pruning w/ a given heuristic is that it reduces the effective depth by a constant k compared to the true depth\n  - Total search cost: O(b^(d-k)) instead of O(b^d)\n- If one heuristic basically always outperforms another, we say it dominates\n\t- Domination translates directly into efficiency (A* using dominating heuristic will never expand more nodes than A* using other heuristic)\n- Generally better to use heuristic function with higher values, provided it is consistent and that the computation time for the heuristic is not too long\n- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n- Can generate relaxed problems by removing one or multiple conditions\n  - Crucial that relaxed problems generated by this technique can be solved essentially without search bc relaxed rules allow the problem to be decomposed into independent problems\n\t  - If the relaxed problem is hard to solve, then values of the corresponding heuristic will be expensive to obtain\n- Program called ABSOLVER can generate heuristics automatically from problem definitions\n- Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem\n  - Cost of optimal solution of subproblem is a lower bound on the cost of the complete problem\n- Use pattern databases: compute admissible heuristic for each state encountered during a search simply by looking up the corresponding subproblem config in database\n  - Each database yields admissible heuristic, and these heuristics can be combined by taking the maximum value\n- Precomputation takes time, but only needs to be done once\n\t- Could generate a perfect heuristic by precomputing and storing the cost of the optimal path between every pair of vertices, but would be very expensive\n\t- Better approach: choose a few landmark points from the vertices\n\t\t- For each landmark L and for each other vertex v in the graph, we compute and store C*(v,L), the exact cost of the optimal path from v to L\n- Pick landmark points that are pretty spread out (can use greedy approach)\n- Agents can learn how to search better -- metalevel state space\n\t- Each state in a metalevel state space captures the internal state of a program that is searching in an ordinary state space\n- Goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost\n- Some ML techniques work better when supplied with features of a state that are relevant to predicting the state's heuristic value, rather than with just the raw state description\n\n\n## Module 4 Lecture Notes\n\n- Problem-solving agent plans ahead and considers a sequence of actions that form a path to a goal state (search for a solution)\n- If environment is fully observable, deterministic, known: solution=fixed sequence of actions\n- If partially observable or nondeterministic: solution must recommend different future actions depending on what the percept receives (could be form of branching strategy)\n- Defining search problem: states, initial state, actions, transition model, path cost (performance measure), goal test\n  - Path cost: sum of all action costs along a path\n- When formulating search problem, decide:\n  - Which properties matter & how to represent (initial/intermediate/goal states)\n  - Which actions are possible & how to represent (actions/transition model)\n  - Which action is next (path cost function)\n- Formulation greatly affects combinatorics of search space and therefore speed of search\n- State space: set of all states reachable from initial state by any sequence of actions\n  - When several operators can apply to each state, this gets large very quickly\n  - Might be proper subset of the set of configurations\n- Path: sequence of actions leading from one state sj -> state sk\n- Solution: path from initial state si to state sf that satisfies the goal test\n- Search tree: way of representing paths that search algorithm has explored. Root=initial state, leaves=successors.\n- Frontier: those states that are available for expanding (for applying legal actions to)\n- Optimal solution: if no solution has lower path cost\n- Generalized algorithm to solve searches: enumerate in some order all possible paths from initial state\n- State=physical configuration (no parents,children,etc); node=data structure constituting part of search tree\n- Failure to detect repeated states-> turn linear problem into exponential\n  - Graph search: check if node has been visited before adding to search queue\n- Uninformed: all non-goal nodes in frontier look equally good; Informed: some non-goal nodes can be ranked higher\n- Dimensions for evaluation: completeness (always solution?), optimality (lowest path cost first?), time (# nodes generated) & space (# nodes simultaneously in memory) complexity\n- Time/space variables: b(max branching factor); d(depth of shallowest goal node); m(max length of any path in state space)\n- BFS(FIFO): expand shallowest unexpanded node; use if: possible infinite paths; some solutions have short paths and wrong paths are usually terminated quickly; can quickly discard unlikely paths\n- DFS(LIFO): expand deepest unexpanded node; use if: space is restricted; many possible solutions with long paths; search can be fine-tuned quickly\n- Depth-limited: DFS with depthlimit 1; if l<d:incomplete; l>d:not optimal\n- Iterative deepening search: depth-limited as subroutine with increasing l\n  - Complete & optimal: goal always found at depth d\n\n\n## Module 4 Definitions\n* **Admissible** - never overestimates cost to reach goal\n* **Consistency** - for every node n and every successor n' of n generated by an action a, we have h(n)<=c(n,a,n')+h(n')\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Pattern databases** - store solution costs for every subproblem\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- 3 stances we can take towards multiagent environments:\n  - Aggregate as economy: appropriate when large \\# of agents; allows us to predict on aggregate w/o having to predict action of any individual agent\n  - Consider adversarial agents as just part of environment (makes it nondeterministic)\n  - Explicitly model aversarial agents with techniques of adversarial game-tree search\n- Won't have enough time to be sure of optimal move (even with pruning) in nontrivial games; need to cut off search at some point\n  - For each state where choose to stop searching, ask who's winning:\n    - Apply eval function\n    - Avg outcomes of many fast simulations of the game from that state all the way to end\n- State space graph: initial state, actions function and result\n- Can superimpose search tree over part of graph to determine\n- Complete game tree: search tree that follows every sequence of moves all the way to terminal state \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n- Use minimax search for games with multiple outcome scores\n- \"move\" means that both players have taken an action; \"ply\" means that one player made a move\n- Given game tree, optimal strategy can be determined by working out the minimax value of each state in the tree [Minimax(s)]\n\t- Minimax value: utility of being in state, assuming that both players play optimally from there to end of game\n- Best play not always to make optimal move when facing suboptimal opponent (making riskier move might lead to win instead of draw)\n- Minimax alg: recursive alg that proceeds all the way down to leaves of tree, then backs up the minimax values through the tree as recursion unwinds\n  - Performs complete depth-first exploration of game tree\n\t- If max depth of tree is m and there are b legal moves at each point:\n\t\t- Time complexity: O(bm)\n\t\t- Space complexity: O(bm) for alg that generates all actions at once; O(m) for alg that generates actions one at a time\n- Optimal decisions in multiplayer games\n  - Must replace the single value for each node with a vector of values (Have utility function return vector of utilities)\n  - Alliances can be natural consequence of optimal strategies for each player\n- \\# of game states: exponential in depth of tree\n\t- Alpha-beta pruning: consider that player has choice of moving to node n\n    - If player has a better choice either at the same level or at any point higher up in tree, then player will never move to n\n    - So once we've found out enough about n to reach this conclusion => prune it\n- Alpha-beta parameters: the value of the best choice we have found so far at any choice point along the path for…\n\t\t- alpha: MAX (at least)\n\t\t- beta: MIN (at most)\n- Effectiveness of alpha-beta pruning is highly dependent on order in which states are examined (could do it in O(b^(m/2)) instead of O(b^m))\n\t- Iterative deepening: search one ply deep & record ranking of moves based on evaluations; then search one ply deeper using previous ranking to inform move ordering, etc\n    - Increased search time from this can be more than made up from move ordering\n\t- Repeated states can occur because of transpositions which can cause exponential increase in search cost\n\t  - Address problem with transposition table that caches the heuristic value of states\n\t- Too many states to explore in the time available. Two strategies:\n\t\t- Type A: considers all possible moves to a certain depth in the search tree and then uses a heuristic evaluation function to estimate the utility of states at that depth\n\t\t\t- Explores a wide but shallow portion of the tree\n\t\t\t- Chess\n\t\t- Type B: ignores moves that look bad and follows promising lines \"as far as possible\"\n\t\t\t- Explores a deep but narrow portion of the tree\n      - Go\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n\t- Replace utility function with eval (which estimates a state's utility)\n\t- Replace terminal test by a cutoff test, which must return true for terminal states but is otherwise free to decide when to cut off the search\n- Heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p\n\t- What else makes for a good eval function?\n\t\t- Computation must not take too long\n\t\t- Eval function should be strongly correlated with the actual chances of winning\n\t- Most eval functions work by calculating various features of the state: can be too costly\n    - Eval function doesn't know which states are which, but can return a single value that estimates the proportion of states with each outcome\n\t\t- Therefore, most in practice compute separate numerical contributions from each feature and then combine them to find the total value\n\t\t\t- However, assumes that contribution of each feature is independent of values of other features --> can use nonlinear combination of features\n- When is it appropriate to cut off search?\n\t- Eval function should only be applied to positions that are quiescent -- positions in which there is no pending move (such as a capturing the queen) that would wildly swing the eval\n\t\t- Quiescence search is sometimes restricted to consider only certain types of moves, such as capture moves, that will quickly resolve the uncertainties in the position\n- Horizon effect: when program is facing an opponent's move that causes serious damage and is ultimately unavoidable but can be temporarily avoided by the use of delaying tactics\n\t- One way to mitigate: allow singular extensions even when the search would normally be cut off at that point\n\t\t- Singular extensions: moves that are \"clearly better\" than all other moves in a given position\n- Forward pruning prunes moves that appear to be poor moves, but might possibly be good ones\n\t- Saves computation time at risk of making an error (Type B strategy)\n    - Beam search but no way to guarantee that the best move will not be pruned away\n\t\t- Probabilistic cut: forward-pruning version of alpha-beta search that uses statistics gained from prior experience to lessen the chance that the best move will be pruned\n\t\t\t- Computes probability by doing a shallow search to compute the backed-up value v of a node and then using past experience to estimate how likely it is that a score of v at depth d in the tree would be outside (alpha, beta)\n\t\t- Late move reduction: moves that appear later in the list of possible moves are less likely to be good moves, so reduce the depth to which we search these moves (instead of pruning away completely)\n- Search versus lookup: Lookup initial and very end moves because they're easier to anticipate; start searching when state is new and unseen\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- Stochastic games: Games with chance incorporated\n- Game tree must include chance nodes in addition to max and min nodes\n- Positions do not have definite minimax values: calculate expected value (average over all possible outcomes of the chance nodes)\n\t- Expectiminimax value: generalization of minimax value for deterministic games\n    - For chance nodes: compute expected value (sum of values over all outcomes) weighted by probability of each chance action\n- To avoid problems where program behaves totally differently if we make a change to some of the eval values (even if preference order is the same)\n  - Eval function must return values that are a positive linear transformation of probability of winning\n- Whenever uncertainty enters the picture: possibilities are multiplied enormously and forming detailed plans of action becomes pointless bc the world probably will not play along\n  - Something like alpha-beta pruning could be applied\n  - If we put bounds on possible values of utility function, can arrive at bounds for the avg without looking at every number\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- Agent assigns probability P(s) to each possible current state s\n- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- Constraints on rational preferences\n\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n\t- Primary issue for utility theory: understand how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n\t\t\t- Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p\n\t\t\t- Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n- 16.2.2 Rational preferences lead to utility\n\t- From axioms of utility, can derive the following:\n    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a 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\n    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n  - Once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n\t\t- Called a value function or ordinal utility function\n  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- Preference elicitation: process to work out what a human's utility function is by presenting choices to them and using observed preferences to pin down the underlying utility function\n- Useful to establish some scale on which utilities can be recorded and compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n\t- Normalized utilities: scale between 0 and 1\n- Utility of money almost exactly proportional to log of the amount\n  - Most people have a utility function that is concave for positive wealth\n  - Agent with linear curve: risk-neutral\n- Expected utility and post-decision disappointment\n\t- Rational way to choose best action: maximize expected utility\n\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n\t\t- Therefore working with estimates of true expected utility\n\t\t- Assume estimates are unbiased: expected value of error is zero\n- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n- Decision theory = normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really do act\n- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n\t- People may distrust the legitimacy of the stated probabilities\n\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n\n\n## Module 5 Lecture Notes\n\n- Simplest game environment: multiagent, static, discrete, fully observable, strategic (next state is determined by current state and action executed by agent and that of one other agent)\n- Key properties of game:\n  - Two players alternate moves\n  - Zero-sum: one player's loss is another's gain\n  - Clear set of legal moves\n  - Well-defined outcomes (win, lose, draw)\n- General scheme:\n  - Consider all legal successors to current state (board position)\n  - Evaluate each successor board position\n  - Pick move which leads to best board position\n  - After opponent moves, repeat\n- Game trees: nodes repesent board positions; edges represent legal moves\n  - Root node: first position in which a decision must be made\n  - Eval function f assigns real-number scores to board positions without reference to path\n    - Based on static features of board alone\n    - Zero-sum assumption lets us use one function to describe goodness for both players\n      - f(n)>0 if MAX winning in position n; f(n)=0 if position n is tied; f(n)<0 if MIN winning in position n \n  - Terminal nodes: represent ways game could end, labeled w/ desirability of that ending\n- MAX & MIN: MAX attempts to MAXimize MAX's outcome and MIN attempts to MINimize MAX's outcome\n- Minimax: make best move for MAX assuming that MIN always replies with best move for MIN\n  - Backed-up value of each node: determined by values of its children\n    - MAX: max of values of its children\n    - MIN: min of values of its children\n- Minimax procedure: Until game is over do:\n  - Start with current position as MAX node\n  - Expand game tree a fixed number of ply\n  - Apply eval function to leaf positions\n  - Calculate back-up values bottom-up\n  - Pick move assigned to MAX at the root\n  - Wait for MIN to respond\n- Keep track of 2 additional values: alpha & beta\n  - alpha: MAX's current lower bound on MAX's outcome (MAX will never allow a move that could lead to a worse score for MAX than alpha)\n  - beta: MIN's current upper bound on MIN's outcome (MIN will never allow a move that could lead to a better score for MAX than beta)\n- Stop eval a branch whenever:\n  - For MAX node: v >= beta is backed-up (MIN will never select that MAX node)\n  - For MIN node: v <= alpha is found (MAX will never select that MIN node)\n- Expectimax when we don't know what result of action will be (explicit randomness, unpredictable opponents, actions can fail)\n- Expectimax search: compute avg score under optimal play\n  - Add chance nodes (like min nodes) except outcome is uncertain -> calculate expected utilities\n  - No pruning since expected utility might be lower than node before\n  - Environment is an extra \"random agent\" player tha moves after each min/max agent\n- Random variable: event whose outcome is unknown\n- Probability distribution: assignment of weights to outcomes\n- Expected value of function of RV= avg weighted by prob. distribution over outcomes\n\n\n## Module 5 Definitions\n* **Pruning** - ignores parts of the search tree that makes no difference\n* **Evaluation function** - estimates current winner based on features of state\n* **Perfect information** - fully observable\n* **Zero-sum** - good for one player is bad for the other\n* **Transition model** - defines the state after taking an action in a given state\n* **Utility function** - defines the numeric value for a player when the game ends in terminal state\n* **Killer moves** - best moves\n* **Transpositions** - different permutations of move sequence that end up in the same position\n* **Micromort** - one in million chance of death\n* **Qaly** - quality-adjusted life year\n* **Certainty equivalent** - value agent accepts in lieu of lottery\n* **Insurance premium** - EMV of lottery - certainty equivalent\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- Constraint satisfaction problem consists of 3 components:\n\t- X: set of variables\n\t- D: set of domains (set of allowable values), one for each variable\n\t- C: set of constraints that specify allowable combinations of values\n\t\t- <scope, rel> where scope = tuple of variables that participate in the constraint and rel is a relation that defines the values that those variables can take on\n\t\t- For example: if X1 and X2 both have the domain {1,2,3}, then the constraint saying that X1 must be greater than X2 can be written as: <(X1,X2), {(3,1),(3,2),(3,1),(2,1)})> or <(X1,X2), X1>X2 >\n- CSP deal with assignments of values to variables\n- Why formulate problem as CSP?\n\t- Often easy to do\n\t- Years of development work have gone into making CSP solvers fast and efficient\n\t- CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot\n- With CSPs, once we find out that a partial assignment violates a constraint, we can immediately discard further refinements of the partial assignment\n- Can specify precedence constraints between individual tasks (one must come before the other) and disjunctive constraint (tasks cannot overlap in time)\n- Variations on the CSP formalism\n\t- Simplest kind of CSP involves variables that have discrete, finite domains\n  - No alg exists for solving general nonlinear constraints on integer variables\n\t- Best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities\n\t- Types of variables: discrete, continuous\n\t- Types of constraints: unary (restricts value of a single variable) and binary (relates two variables), higher-order constraints\n\t\t- Global: constraint involving an arbitrary number of variables\n- Binary CSP: one with only unary and binary constraints\n- Constraint hypergraph: consists of ordinary nodes and hypernodes which represent n-ary constraints (constraints involving n variables)\n\t- Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced\n\t\t- Can transform any CSP into one with only binary constraints\n    - Another way to convert n-ary CSP to binary: dual graph transformation (create new graph where there is one variable for each constraint in original graph and one binary constraint for each pair of constraints in original graph that share variables)\n\t- Why we might prefer global constraint rather than binary:\n\t\t- Easier and less error-prone to write the problem description using Alldiff (which says that all variables involved must have distinct values)\n\t\t- Possible to design special-purpose inference algorithms for global constraints that are more efficient than operating with primitive constraints\n- Preference constraints: indicate which solutions are preferred\n\t- Absolute: violation of which rules out a potential solution\n  - Can be encoded as costs on individual variable assignments (constrained optimization problem)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- CSP alg has choices when making progress\n\t- Can generate successors by choosing new variable assignment\n\t- Constraint propagation: type of inference that uses constraints to reduce number of legal values for a variable (can be intertwined with search or done as preprocessing step)\n\t\t- Preprocessing may solve whole problem so no search required\n- Key idea: Local consistency\n\t- Node: one variable = node-consistent if all values in variable's domain satisfy variable's unary constraints\n\t\t- Graph node-consistent if every variable in graph is node-consistent\n\t  - Easy to eliminate all unary constraints in CSP by reducing domain of variables with unary constraints at start of solving process\n\t- Arc: variable in CSP is arc-consistent if every value in its domain satisfies variable's binary constraints (AC-3)\n\t\t- Maintains queue of arcs to consider: initially contains all the arcs in CSP\n\t\t- Then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi arc-consistent with respect to Xj\n\t\t\t- If Di left unchanged, move on to next arc\n\t\t\t- If Di changed, then we add to queue all arcs (Xk, Xi) where Xk is a neighbor of Xi\n\t\t\t\t- Change might enable further reductions in Dk even if we have previously considered Xk\n\t\t\t- If Di revised down to nothing => know the whole CSP has no consistent solution and AC-3 can immediately return failure\n\t\t- Otherwise, keep checking\n\t\t- Checking consistency of an arc can be done in O(d^2), so we get O(cd^3) total worst-case time\n\t- Path: tightens binary constraints by using constraints that are inferred by looking at triples of variables\n\t\t- Two-variable set {Xi, Xj} is path-consistent wrt third variable Xm if, for every assignment {Xi=a, Xj=b} consistent with constraints (if any) on {Xi, Xj}, there's an assignment to Xm that satisifes constraints on {Xi, Xm} and {Xm, Xj}\n\t- K-consistency: CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\t\t- Strongly k-consistent if k-consistent, (k-1)-consistent, (k-2)-consistent,…, down to 1-consistent\n\t\t- Total run time: O((n^2)d)\n\t- Global constraints\n\t\t- If m variables are involved in constraint, and if they have n possible distinct values altogether, and m > n, then Alldiff constraint cannot be satisfied\n\t\t- Algorithm:\n\t\t\t- Remove any variable in the constraint that has a singleton domain\n\t\t\t- Delete that variable's value from domains of remaining variables\n\t\t\t- Repeat as long as there are singleton variables\n\t\t\t- If at any point an empty domain is produced or there are more variables than domain values left, then inconsistency has been detected\n\t- Resource constraint (Atmost): detect inconsistency simply by checking sum of minimum values of current domains\n\t\t- CSP is bounds-consistent if for every variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisifies the constraint between X and Y for every variable Y\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- Must search for solution if we still have variables with multiple possible values after finishing constraint propagation process\n- CSPs are commutative (order of actions applied does not matter)\n- Backtracking search: keeps only single representation of state and alters it rather than creating new ones\n  - Can be improved using domain-independent heuristics that take advantage of factored representation of CSPs\n- Variable selection\n  - Simplest: static ordering (choose variables in order) or choose randomly => neither optimal\n  - Minimum-remaining-values (MRV) heuristic: choosing variable with the fewest \"legal\" values\n\t- Degree heuristic: attempts to reduce branching factor on future choices by selecting variable that's involved in largest number of constraints on other unassigned variables\n\t- MRV is usually more powerful guide, but degree heuristic useful as tie-breaker\n- Once variable has been selected, must decide on order to examine its values\n\t- Least-constraining-value: prefers value that rules out the fewest choices for the neighboring variables in the constraint graph\n- Variable selection: fail-first; value selection: fail-last\n- Inference can be even more powerful during course of search\n\t- Every time we make a choice of value for a variable, have brand-new opportunity to infer new domain reductions on neighboring variables\n\t- Forward checking: whenever a variable X is assigned, forward-checking process establishes arc consistency for it\n\t\t- For each unassigned variable Y that is connected to X by constraint, delete from Y's domain any value that's inconsistent with value chosen for X\n\t- For many problems, search will be more effective if combine MRV heuristic with forward checking\n\t- Maintaining Arc Consistency (MAC) detects inconsistencies not found by forward checking\n\t\t- After a variable Xi is assigned a value, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, start with only the arcs (Xj, Xi) for all Xj that are unassigned variables that are neighbors of Xi\n\t\t- From there AC-3 does constraint propagation in usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately\n\t\t- More powerful than forward checking: forward checking does not recursively propagate constraints when changes are made to the domains of variables\n- Original idea: just back up to preceding variable and try diff value for it (chronological backtracking: most recent decision point is revisted)\n  - Better possibilities\n    - Backtrack to variable that's responsible for making one of possible values for variable impossible\n    - Keep track of conflict set (set of assignments that're in conflict for some value)\n      - Backjumping: backtracks to most recent assignment in conflict set\n      - Forward checking can supply conflict set with no extra work\n- Constraint learning: idea of finding min set of variables from conflict set that causes the problem (no-good)\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- Local search algorithms: use a complete-state formulation where each state assigns a value to every variable, and the search changes the value of one variable at a time\n- Min-conflicts heuristic: select value that results in min number of conflicts with other variables \n  - Run time is roughly independent of problem size\n- May be millions of variable assignments only one conflict away from solution\n  - Plateau search: allowing sideways moves to another state with same score (can help local search find way off plateau)\n\t\t- Tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states (technique to direct wandering on plateau)\n\t- Constraint weighting: aims to concentrate the search on the important constraints\n    - Weights adjusted by incrementing weight of each constraint that is violated by current assignment\n    - Benefits: adds topography to plateaus (makes sure it's possible to improve from current state) and adds learning (over time, difficult constraints are assigned higher weights)\n- Local search can also be used in an online setting when the problem changes\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- Structure of problem (represented by constraint graph) can be used to find solutions quickly\n- Independence can be ascertained simply by finding connected components of the constraint graph\n- Any tree-structured CSP can be solved in time linear in the number of variables\n\t- Key: directional arc consistency (DAC)\n\t\t- CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, …, Xn if and only if every Xi is arc-consistent with each Xj for j > i.\n- Two ways to reduce constraint graph to tree: cutset conditioning & tree decomposition\n- Cutset conditioning algorithm:\n\t- Choose a subset S of the CSP's variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset\n\t- For each possible assignment to the variables in S that satisfies all constraints on S:\n\t\t- Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S\n\t\t- If the remaining CSP has a solution, return it together with the assignment for S\n\t- If the cycle cutset has size c, then total run time is O(dc * (n-c)d2)\n- Tree decomposition\n\t- Construct tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n\t- Must satisfy 3 requirements:\n\t\t- Every variable in the original problem appears in at least one of the tree nodes\n\t\t- If two variables are connected by a constraint in original problem, they must appear together (along with the constraint) in at least one of the three nodes\n\t\t- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n  - First two conditions: ensure all variables and constraints are represented in tree decomposition\n  - 3rd condition: allows us to say that any variable from original problem must have the same value wherever it appears\n\t- Have tree-structured graph: can then apply Tree-CSP-solver to get solution in O(nd^2) time (n is # of tree nodes; d is size of largest domain)\n    - Efficient as long as d remains small\n\t- In choosing decomp: aim is to make subproblems as small as possible\n\t- CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n    - Tree width of tree decomp of graph: size of largest node - 1\n    - Tree width of graph itself: min width among all its tree decompositions\n- Value symmetry\n  - Can be important structure in values of variables or constraint relations themselves\n  - Breaking value symmetry useful in reducing search space (symmetry-breaking constraint)\n\n\n## Module 6 Lecture Notes\n\n- Assumptions about world: single agent, deterministic actions, fully observable, discrete state space\n- Search used for:\n  - Planning (sequence of actions)\n    - Most important: Path to goal\n    - Paths have various costs, depths\n    - Heuristics give problem-specific guidance\n  - Identification (assignments to variables)\n    - Most important: just goal\n    - All paths have same depth (for some formulations)\n    - CSPs are specialized for ID problems\n- Big idea\n  - Represent constraints that solutions must satisfy in a uniform declarative language\n  - Find solutions by general purpose search algs with no changes from problem to problem (no hand-built transition functions or heuristics)\n  - Just specify problem in formal declarative language & a general-purpose alg does everything else!\n- CSP consists of: finite set of variables; nonempty domain of possible values for each variable; finite set of constraints\n  - Each constraint limits the values that variables can take\n  - State: assignment of values to some or all variables\n- Consistent assignment: constraints not violated\n- Complete assignment: every variable is assigned a value\n- Solution to CSP: complete, consistent assignment\n  - Can be founded by a completely general purpose alg, given only formal specification of CSP\n- Benefits of CSP\n  - Clean specification of many problems, generic goal, successor function & heuristics\n  - CSP \"knows\" which variables violate a constraint (hence where to focus search)\n  - Automatically prune off all branches that violate constraints (state space search: only does this by hand-building constraints into successor function)\n- CSP Representations\n  - Constraint graph: nodes=variables; arcs=binary constraints; simplifies search\n  - Standard representation pattern: variables with values\n  - Binary CSP: each constraint relates two variables\n- CSPs deal with both discrete (finite & infite) and continuous variables\n- Unary constraint=single variable; binary=pairs of variables; higher-order=3=< variables\n- Preference (soft constraints): represented by cost for each variable assignment\n- CSP as search: initial state={}; successor function= assign value to any unassigned variable provided no constraint conflict; goal test=assignment is complete; path cost=constant for each step\n  - Solution always found at depth n for n variables (DFS can be used)\n  - n variables of domain size d\n    - Branching factor at root: n*d\n    - Branching factor at next level: (n-1)*d\n    - Tree has n!*d^n leaves\n  - Only need to consider assignments to a single variable at each node\n- Backtracking search: DFS for CSPs with single-variable assignments\n  - Chooses vals for one variable at a time and backtracks when variable has no legal values left to assign\n  - Basic uninformed alg for CSPs\n- Improve backtracking efficiency: general-purpose methods & heuristics can give huge gains in speed on average\n- Minimum remaining values (MRV) heuristic: Choose variable with fewest legal moves (tiebreaker: choose with most constraints on remaining variables)\n- Least constraining value: given variable, choose one that rules out the fewest values in remaining variables\n- Forward checking: keep track of remaining legal values for unassigned variables; terminate search when any unassigned variables has no remaining legal values\n  - Constraint propagation (inference) eliminates possible values for a variable if value would violate local consistency\n    - Node consistency: satisifies unary constraints\n    - Arc consistency: satisifies binary constraints\n      - Xi arc-consistent wrt Xj if for every value in Di, there's some value in Dj that satisfies binary constraint on arc between Xi and Xj\n      - To make an arc (i,j) arc-consistent, for each value v on Xi: if no label on Yj consistent with v, remove v from Xi\n- X->Y is consistent iff for every value x of X there is some allowed y\n- Waltz/Mackworth Constraint Prop Alg:\n  - Assign every node in constraint graph a set of all possible values\n  - Repeat until there is no change in set of values associated with any node:\n    - For each node i and for each neighboring node j: remove any value from i which is not arc consistent with j\n- Inefficiencies\n  - At each iteration, only examine those Xi where 1=< neighbor of Xi has lost a value in previous iteration\n  - If Xi loses value bc of arc inconsistencies with Yj: don't need to check Yj on next iteration\n  - Removing value on Xi can only make Yj arc-inconsistent with respect to Xi itself: only need to check that (j,i) is still arc-consistent\n- AC-3: keep track of what arcs we need to process; add back arcs to neighbors whenever a node had values removed\n  - Total # of arcs: 2*n*(n-1) (O(n^2))\n  - Given d values, checking takes O(d^2) time\n  - Worst-case complexity: O(n^2 * d^3)\n\n\n## Module 6 Definitions\n* **Consistent assignment** - assignment doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint propagation** - use constraints to reduce \\# of legal values for a variable\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n- Central component of knowledge-based agent: knowledge base (KB)\n\t- KB may initially contain some background knowledge\n\t- Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world\n- Tell & Ask: ways to add new sentences to KB and a way to query what's known\n\t- Both may involve inference\n- Each time agent program is called:\n\t- Tells KB what it perceives\n\t- Asks KB what action it should perform\n\t- Tells KB which action was chosen and returns the action to be executed\n- Details of representation language are hidden inside 3 functions that implement the interface between the sensors and actuators on one side and core representation and reasoning system on the other:\n\t- Make-percept-sentence: constructs a sentence asserting that the agent perceived the given percept at the given time\n\t- Make-action-query: constructs a sentence that asks what action should be done at the current time\n\t- Make-action-sentence: constructs a sentence asserting that the chosen action was executed\n- Declarative approach: knowledge-based agent can be built simply by telling it what it needs to know\n\t- Agent designer can tell sentences one by one until the agent knows how to operate in its environment\n- Procedural approach: encodes desired behaviors directly as program code\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Wumpus environment: deterministic, discrete, static, single-agent, sequential (rewards only come after actions are taken), partially observable\n- Transition model is unknown bc agent doesn't know which forward actions are fatal\n- Fundamental property of logical reasoning: in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct\n\n\n## AIMA Chapter 7.3 Logic\n\n- KB consist of sentences which are expressed according to syntax of representation language\n\t- Logic must also define semantics (meaning) of sentences\n\t\t- Semantics defines truth of each sentence with respect to each possible world\n\t\t- Every sentence must be either true or false in each possible world -- there is no \"in between\"\n\t\t\t- Use \"model\" (mathematical abstractions of \"possible world\")\n\t\t- If a sentence alpha is true in model m, we say that m satisifies alpha or sometimes m is a model of alpha\n\t\t\t- M(alpha) = set of all models of alpha\n- Logical entailment between sentences: idea that a sentence follows logically from another sentence\n\t- Definition of entailment can be applied to derive conclusions (logical inference)\n  - Model checking: enumerates all possible models to check that alpha is true in all models in which KB is true\n\t- Sound / truth-preserving inference algorithm: one that derives only entailed sentences\n\t- Complete inference algorithm: if it can derive any sentence that is entailed\n- Grounding: connection between logical reasoning processes and the real environment in which the agent exists (how do we know that KB is true in the real world?)\n  - Agent's sensors create the connection\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- Syntax of propositional logic defines the allowable sentences\n- Atomic sentences consist of a single proposition symbol\n\t- Two proposition symbols with fixed meanings:\n\t\t- True: always-true proposition\n\t\t- False: always-false proposition\n- Complex sentences: constructed from simpler sentences, using parentheses and operators called logical connectives\n\t- 5 connectives in common use: Not, And, Or, Implies (if-then), IFF (if and only if: biconditional)\n- Semantics define rules for determining the truth of a sentence wrt a particular model\n\t- In propositional logic: model simply sets the truth value (T or F) for every proposition model\n\t- Must specify how to compute the truth value of any sentence given a model (done recursively)\n\t\t- All sentences are constructed from atomic sentences and five connectives\n\t\t- Rules can be expressed with truth tables\n\t- For implies: propositional logic does not require any relation of causation or relevance between P and Q\n\t\t- Also, any implication is true whenever its antecedent (left-hand side) is false\n- Does KB entail sentence alpha? Inference alg:\n\t- Model-checking approach: enumerate the models and check that alpha is true in every model in which KB is true\n    - Sound: implements definition of entailment directly\n    - Complete: works for any KB and alpha and always terminates\n\t- Time complexity: O(2^n) (n=\\# of symbols)\n\t- Space complexity: O(n) (enumeration is depth-first)\n\t- Every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- Entailment done by theorem proving: applying rules of inference directly to sents in KB to construct proof of desired sent w/o consulting models\n- Deduction theorem: for sents x and y, x|=y iff x=>y is valid\n- Satisfiability: checked by enumerating possible models until one is found that satisfies sent (NP-complete)\n  - Validity & satisfiability= connected (a is valid iff !a is unsatisfiable)\n- Inference rules can be applied to derive proofs\n\t- Searching for proofs = alternative to enumerating models\n    - Finding proof can be more efficient bc proof can ignore irrelevant propositions\n\t- Proof by resolution: yields a complete inference alg when coupled with any complete search alg\n\t\t- Unit resolution inference rule: takes clause and literal and produces new clause\n\t\t\t- Unit clause: single literal can be viewed as a disjunction of one literal\n\t\t- Resolve complementary literals and through factoring\n\t- Resolution-based theorem prover can, for any sents a and b in propositional logic, decide whether a entails b\n\t- Every sent of propositional logic is logically equivalent to conjunction of clauses (CNF) (only ands, ors, or nots)\n\t- Completeness of resolution\n\t\t- Resolution closure RC(S): set of clauses S which is set of all clauses derivable by repeated application of resolution rule to clauses in S or their derivatives\n\t\t- Ground resolution theorem: if set of clauses is unsatisfiable, then RC(S) of those clauses contains empty clause\n\t\t\t- Proved by demonstrating its contrapositive: if closure RC(S) doesn't contain empty clause, then S is satisfiable\n- Full power of resolution not needed (Horn & definite clauses)\n\t- Resolve 2 Horn clauses => get back a Horn clause\n\t- k-CNF sent (where each clause has at most k literals)\n\t- KB containing only definite clauses: interesting for 3 reasons:\n\t\t- Every definite clause can be written as implication whose premise(body) = conjunction of positive literals and whose conclusion(head) = single positive literal\n\t\t- Inference with Horn clauses can be done through forward-chaining and backward-chaining alg\n\t\t- Deciding entailment with Horn clauses => done in linear time in size of KB\n- Forward-chaining alg determines if single proposition symbol q (query) is entailed by KB of definite clauses\n\t- Begins from known facts (positive literals) in KB\n\t- If all premises of implication are known, then its conclusion is added to set of known facts\n\t- Process continues until query q is added or until no further inferences can be made\n\t- Runs in linear time, sound & complete\n\t- Example of general concept of data-driven reasoning (in which focus of attention starts with known data)\n- Backward-chaining alg works backward from the query\n\t- If query q known to be true, no work needed\n\t- Otherwise, alg finds those implications in KB whose conclusion is q\n\t\t- If all premises of one of those implications can be proved true (by backward chaining), then q is true\n\t- Runs in linear time\n  - Form of goal-directed reasoning\n\n\n## Module 7 Lecture Notes\n\n- Knowledge-based agents: use process of reasoning over an internal representation of knowledge to decide what action to take\n- Knowledge base (KB): contains a set of sentence that are written in a knowledge representation language\n  - Sentence contains some assertion about the world. Two kinds:\n    - Axioms: sentence that's given\n    - Derived: sentence derived from other sentences (inference)\n  - Contains background info about world and KB agent can add to info in KB through observations\n    - Can also query KB and ask it to derive new knowledge in order to select what action it should take\n- Logic: serve as general class of representations of KB agents\n  - Sentences: in representation language that has a syntax that specifies setences that are well-formed\n  - Logic defines semantics (meaning) of sentence which defines model (truth of each sentence wrt possible world)\n- Models: mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence\n- If sentence x is true in model m then:\n  - m satisfies x or\n  - m is a model of x\n- M(x): set of all models of x\n- Logical entailment: idea that a sentence follows logically from another sentence\n  - x |= y: sentence x entails sentence y\n    - x is more specific/stronger than y\n- Logical inference: entailment applied to derive conclusions\n  - \"KB |-i x\" means \"x is derived from KB by inference algorithm i\"\n- Propositional logic\n  - Atomic sentences: represented with single propositional symbols (which stand for a statement that can be T/F)\n  - Complex sentences: constructed from simpler ones using parentheses and logical connectives (not, and, or, implies, iff)\n- Sound: inference alg should only derive entailed sentences\n- Complete: inference alg can derive all sentences that are entailed\n- Logical equivalence: two sentences are logically equivalent if they are true in same set of models\n  - Also iff x|=y and y|=x\n  - Rules\n    - Contraposition: (x=>y) == (!y=>!x)\n    - Implication elimination: (x=>y) == (!x or y)\n    - Biconditional elimination: (x<=>y) == ((x=>y) and (y=>x))\n    - De Morgan: !(x and y) == (!x or !y)\n    - De Morgan: !(x or y) == (!x and !y)\n    - Distributivity of and over or: ((x and y) or z) == ((x and y) or (x and z))\n    - Distributivity of or over and: ((x or y) and z) == ((x or y) and (x or z))\n- Inference rules: used to derive proofs\n  - Modus Ponens(sound): $$\\frac{\\alpha \\implies \\beta, \\alpha}{\\beta}$$\n    - Whenever sentences of form alpha=>beta and alpha are given, sentence beta can be inferred\n  - Biconditional Elimination: $$\\frac{\\alpha \\iff \\beta}{(\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)}$$\n  - $$\\frac{(\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)}{\\alpha \\iff \\beta}$$\n  - And Elimination(sound): $$\\frac{\\alpha \\land \\beta}{\\alpha}$$\n- Monotonicity: If KB|=a then KB&b|=a\n  - Can safely add to KB without invalidating anything else that we inferred\n  - Implies soundness\n  - Single inference rule, resolution, which yields a complete inference alg when coupled with any complete search alg\n- Resolution: if l and m are complementary literals (one is the negation of the other), can eliminate them via unit resolution\n  - Only applies to clauses (disjunctions of literals)\n- Conjunctive Normal Form (CNF)\n  - Eliminate <=> by replacing x<=>y with (x=>y) and (y=>x)\n  - Eliminate => by replace x=>y with (!x or y)\n  - Move ! inwards (eliminate double negation and apply De Morgan's rules)\n  - Sentence will contain nested and/or operators: apply distributivity law to distribute or over and wherever possible\n- Resolution alg (complete): inference procedures based on resolution work using the principle of proof by contradiction\n  - To show KB|=x, we can show that KB and !x is unsatisfiable\n    - Convert (KB and !x) into CNF\n    - Apply resolution rule to resulting clauses\n    - Resolve every pair that contains complementary literals to produce a new clause\n    - If new clause isn't already present, add to the set\n    - Continue until either:\n      - No new clauses that can be added (KB does not entail x)\n      - Two clauses resolve to yield emply clause (KB does entail x)\n        - Empty clause: arises from resolving two contradictory unit clauses like P and !P\n- Don't always need full power resolution: some KBs formulated in more restrictive form (enables them to use more efficient inference alg)\n  - Definite clause: disjunction of literals where exactly one is positive\n  - Horn clause: disjunction of literals where at MOST one is positive\n\n\n## Module 7 Definitions\n* **Knowledge base** - set of sentences\n* **Sentence** - represents some truth about world\n* **Inference** - deriving new sentences from old\n* **Knowledge level** - specifying what agent knows and what its goals are are enough to determine its behavior\n* **Axiom** - sentence is taken as given (not derived)\n* **Logical equivalence** - if two sentences a and b true in the same set of models\n* **Validity** - if sentence it is true in all models (tautologies)\n* **Satisfiable** - if sentence is true in, or satisfied by, some model\n* **Clause** - disjunction of literals\n* **Complementary literals** - literal and the negation of the literal\n* **Factoring** - removal of multiple copies of literals\n* **Goal clauses** - have no positive literals\n* **Fact** - sentence of a single positive literal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}