{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b8541b42-4efe-4463-da46-ffae29aafd37"
      },
      "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": 39,
      "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": "ffa6680e-7ffa-437a-93d3-9db5b9155649"
      },
      "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": 40,
      "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 = \"Henry Hung\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 41,
      "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 = \"\"\" There are four major approaches to AI along two dimensions: thought \\\n",
        "vs behavior, and human vs rational. \\n\n",
        "\n",
        "(1) Acting humanly usings Turing Test to verify AI. (e.g.\\\n",
        "Blade Runner - Voight-Kampff Test in lecture) \\n\n",
        "\n",
        "(2) Thinking humanly uses cognitive modeling, applying knowledge gained from introspection, \\\n",
        "psychological experiments, and brain imaging (e.g. General Problem Solver by Newall/Simon, \\\n",
        "computer vision). \\n\n",
        "\n",
        "(3) Thinking rationally, using logic and probability. \\n\n",
        "\n",
        "(4) Acting rationally, \\\n",
        "or the rational agent approach. Advantages of this approach include (a) more general than logical \\\n",
        "apporach since inference is just one mechanism to achieve rationality, (b) easier to integrate \\\n",
        "with scientific development. (4) forms the [standard model] of AI. In AI there is a value alignment problem \\\n",
        " - we want agents to be provably beneficial to us. \"\"\"\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 = \"\"\" Searle: weak vs strong AI. Weak AI acts like it is intelligent, \\\n",
        "and Strong AI actually are conscious. \\n\n",
        "\n",
        "Different objections to AI: \\n\n",
        "1) Argument from informality. Humans use informal guidelines that cannot be captured \\\n",
        "by AI. Hubert Dreyfus's criticism of Good Old-Fashioned AI (GOFAI). Points out qualification problem: \\\n",
        "that it is difficult to capture all conditions of behaviors using necessary and sufficent \\\n",
        "logic rules. Also humans are situated since they have many perceptual inputs, compared \\\n",
        "to just logical sentences \\n\n",
        "\n",
        "- Response: we can introduce probabilistic reasoning, or use deep learning to perform informal \\\n",
        "tasks. Embodied cognition approach emphasizes that robotics, visions, etc. can also \\\n",
        "provide inputs for AI to be situated. \\n\n",
        "\n",
        "2) Argument from disability. Claims that machines cannot do certain things. E.g. Turing: \\\n",
        "machines cannot be kind, have sense of humor, make mistakes. \\n\n",
        "\n",
        "- Response: meta-reasoning allows computers to check their own computations. \\n\n",
        "\n",
        "3) mathematical objection: Godel's incompleteness thoerem. For any axiomatic framework F, \\\n",
        "we can construct a sentence G(F) s.t. G(F) is a sentence within F, but not provable, and if F \\\n",
        "is consistent, then G(F) is true. Penrose, Lucas use it to challenge AI. \\n\n",
        "\n",
        "- Response: agents do not cease to be agents if they can't establish truth of a sentence. \\\n",
        "Secondly, Godel's theorem is about math rather than computers. Even humans cannot overcome \\\n",
        "Godel's incompleteness theorem. Thirdly, Godel's theorem only applies to systems \\\n",
        "powerful enough to do arithmetic. Covers Turing Machiines, but computers are not Turing machines \\\n",
        "as they are finite. It is also not true that computers cannot change their minds \\n\n",
        "\n",
        "Turing test is used to measure AI. Eugene Goostman (2014) fooled 33% of amateur judges, but no \\\n",
        "well trained judges. \n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Turing: we maintain the polite convention that everyone thinks, \\\n",
        "and we should also extend that to machines. Dijkstra: asking if machines can think is \\\n",
        "like asking if submarines can swim\\n\n",
        "\n",
        "Searle: supports biological naturalism: mental states are high-level emergent features \\\n",
        "caused by low-level physical/ neural processes. \\n\n",
        "\n",
        "Response: humans are made of cells and they do not understand either. \\n\n",
        "\n",
        "Intrinsic nature of experiences: qualia. Dividing ideas on consciousness: \\\n",
        "global workspace vs integrated information theory.  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Examples of agents include software, handheld calculators and vacuum cleaners. \\\n",
        "Agents' actions can depend on \\\n",
        "anything it has received up till present. Agent functions have two representations: \\\n",
        "tabulation for external representation and agent program for internal representation.\"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" We need  to know what rational, or [do the right thing] means. \\\n",
        "Consequentialism assesses behaviors by outcomes, using performance measures to capture \\\n",
        "desirability. \\n\n",
        "\n",
        "It is generally better to design performance measures according to our \\\n",
        "desired outcomes then how we want agents to behave. We assume that PMs can be specified \\\n",
        "correctly. \\n\n",
        "\n",
        "Rational agent uses percept sequence and internal knowledge to maximize performance\\\n",
        "measure. \n",
        "\n",
        "Rationality is not omniscience or perfection: does not maximize actual performance. \\n\n",
        "\n",
        "Rational agents may do actions to modify future percepts, called information gathering. \\\n",
        "It also has to learn (i.e augments its internal knowledge). \\n\n",
        "\n",
        "If an agent does not entirely rely\\\n",
        "on prior knowledge (i.e. can learn), it is autonomous. Good to start with initial knowledge \\\n",
        "then gradually gain autonomny.  \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" PEAS: Performance, environment, actuators, sensors. Example PEAS for automated taxi: actuators are the controls for brake, signal, horn,\\\n",
        "sensors are radar, GPS, etc. Software agents can also be as complex as physical ones. \\n\n",
        "\n",
        "Varieties of task environments: \\n\n",
        "\n",
        "(1) fully observable (sensor detects all aspects relevant \\\n",
        "to the choice of action, relevant being dependent on performance measure; no need of \\\n",
        "internal state in that case) vs partially observable \\\n",
        "(inaccurate sensor, missing data) vs unobservable (no sensor),\\n\n",
        "\n",
        "(2) single vs multi-agent\\\n",
        "(can be competitive or cooperative, depending on how A's performance measure depends on B's \\\n",
        ") Deterministic vs stochastic (state changes with quantifiable probability) vs non-deterministic (no quantification of prob) \\n\n",
        "\n",
        "(3) Episodic (actions independent from each other) vs sequential (current decision can affect future) \\n\n",
        "\n",
        "(4) static vs dynamic: can env change while agent is deliberating vs semi-dynamic: env does not change \\\n",
        "but agent's performance score does (e.g. chess with a clock) \\n\n",
        "\n",
        "(5) discrete v continuous: whether the state,\\\n",
        "time, percepts, and actions are discrete or continuous. \\n\n",
        "\n",
        "(6) known vs unknown: whether agent has knowledge of the laws of physics. \\n\n",
        "\n",
        "Most difficult is partially observable, nondeterministic, multi agent, unknown, sequential \\\n",
        "dynamic, and continous. E.g. Taxi driving. Some examples: English tutor TE is partial, multi-agent, stochastic, sequential \\\n",
        "dynamic, discrete; part picking robot is partial, single agent, stochastic, episodic, dynamic, continuous. Experiments with \\\n",
        "environments are mostly carried out for many envs drawn from an environment class.\"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\" Table approach is inefficient: if p is the length of percept sequence and T is lifetime then lookup table will \\\n",
        "have $\\sum_{t = 1}^{T} p ^ t$ entries.\\n\n",
        "\n",
        "Four kinds of agent problems. \\n\n",
        "(1) Simple reflex agent uses current percept without consideration\\\n",
        "of previous sequence, like vacuum agent. Uses condition- action rules, if then statements.\\\n",
        "Mostly uses in fully observable envs because of limited intelligence. Can fall into infinite loops \\\n",
        "in partially observable envs. May escape with randomized actions (randomized can be rational).\\n\n",
        "\n",
        "(2) model based reflex agents (maintain internal states) requires two kinds of knowledge: (a) \\\n",
        "knowledge of how the world works, or transition model. (b) information about how the state of the world \\\n",
        "is reflected in precepts, i.e. sensor model. Uses the knowledge to guess the world's state at the moment. \\\n",
        "(update state using precept, uses actions rules to derive an action).\\n\n",
        "\n",
        "(3) goal based agents: uses goals\\\n",
        "to capture desirable outcomes (e.g. search and planning agents). Differs from (1) and (2) because agents \\\n",
        "knows why it does certain actions \\n\n",
        "\n",
        "(4) utility based agents: uses utility as an internal representation of \\\n",
        "performance measure, has advantage in flexibility and learning. Better than (3) in two ways: (a) helps \\\n",
        "rank different goals, and (b) helps decide which goal to pursue under uncertainty. Not all utility based \\\n",
        "agents are model-based: model free agents can learn what action is best iwthout knowing how it changes \\\n",
        "the environment. \\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Descartes' dualism suggests mind body separation\\\n",
        ", seeing bodies as just complex machines. Descartes suggests that however machines\\\n",
        "can never learn to use languages. Turing proposes an imitation game. Searle however,\n",
        "argues that machines are not thinking but just doing symbol manipulation as in \\\n",
        "Chinese Room (e.g. Eliza, early NLP chatbot). \\n\n",
        "\n",
        "Contrasts strong vs weak AI: strong\\\n",
        "AI has a mind and can understand, while weak AI only simulates thoughts and do not\\\n",
        "have real understanding. Searle thinks that biological brains causes minds. Dennett's \\\n",
        "brain in a vat experiment in [Who Am I?] asks whether a brain in a vat is really different\\ \n",
        "from a machine processing symbols. Current AI endeavors focuses on solving subproblems and\\\n",
        "topping leaderboards, but some wants to develop truly intelligent AI. \\n\n",
        "\n",
        "Agent function f: P->A maps a sequence of percepts (list) to a set of actions. Agent \\\n",
        "program runs on an architecture to implement an agent function. Can do this in a table but \\\n",
        "length will be exponential in len(P). \\n\n",
        "\n",
        "Performance Measure, Environment, Actuators and Sensors specify a task environment. A designer's\\\n",
        "goal is to construct an agent function f that maximizes expected value of performance measure, \\\n",
        "then construct an agent program that implements the function on an architecutre, given a task \\\n",
        "environment. \\n\n",
        "\n",
        "We describe something as an agent when it can be said to have its own perfomance measure.\\n\n",
        "\n",
        "For initial part of course we assume fully observable, static, deterministic, \\\n",
        "and discrete \\n\n",
        "\n",
        "Reflex agent: makes action based on current precept vs problem solving agent: plans ahead\\\n",
        "e.g. searching. It formulates goal, generates a search problem with states, actions, performance\\\n",
        "and come up with a solution. \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content that an agent's sensor receives\",\n",
        "\"percept sequence\": \"complete history of everything the agent has perceived\",\n",
        "\"rational agent\" : \"an agent that acts to achieve the best outcome or best expected outcome (i.e. \\\n",
        "maximize performance measure\",\n",
        "\"agent function\": \"maps any given percept sequence to an action\",\n",
        "\"agent program\" : \"implementation of agent function\",\n",
        "\"standard model\": \"The idea of constructing agents to do the right thing\",\n",
        "\"Turing test\": \"computer test using human-written questions, requiring NLP, \\\n",
        "knowledge representation, automated reasoning, and ML\",\n",
        "\"Total turing test\": \"Enhanced Turing test requiring computer vision and robotics\\\n",
        "interaction with real world\",\n",
        "\"performance measure\": \"an objective yardstick for evaluating performance, using evidence\\\n",
        "from percept sequence\",\n",
        "\"task environment\": \"a problem specification to be solved by the agent, consists of PEAS\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3e727dff-b585-4714-9e42-da7830a67f86"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 43,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n There are four major approaches to AI along two dimensions: thought vs behavior, and human vs rational. \n\n\n(1) Acting humanly usings Turing Test to verify AI. (e.g.Blade Runner - Voight-Kampff Test in lecture) \n\n\n(2) Thinking humanly uses cognitive modeling, applying knowledge gained from introspection, psychological experiments, and brain imaging (e.g. General Problem Solver by Newall/Simon, computer vision). \n\n\n(3) Thinking rationally, using logic and probability. \n\n\n(4) Acting rationally, or the rational agent approach. Advantages of this approach include (a) more general than logical apporach since inference is just one mechanism to achieve rationality, (b) easier to integrate with scientific development. (4) forms the [standard model] of AI. In AI there is a value alignment problem  - we want agents to be provably beneficial to us. \n\n## AIMA Chapter 27.1 The Limits of AI\n Searle: weak vs strong AI. Weak AI acts like it is intelligent, and Strong AI actually are conscious. \n\n\nDifferent objections to AI: \n\n1) Argument from informality. Humans use informal guidelines that cannot be captured by AI. Hubert Dreyfus's criticism of Good Old-Fashioned AI (GOFAI). Points out qualification problem: that it is difficult to capture all conditions of behaviors using necessary and sufficent logic rules. Also humans are situated since they have many perceptual inputs, compared to just logical sentences \n\n\n- Response: we can introduce probabilistic reasoning, or use deep learning to perform informal tasks. Embodied cognition approach emphasizes that robotics, visions, etc. can also provide inputs for AI to be situated. \n\n\n2) Argument from disability. Claims that machines cannot do certain things. E.g. Turing: machines cannot be kind, have sense of humor, make mistakes. \n\n\n- Response: meta-reasoning allows computers to check their own computations. \n\n\n3) mathematical objection: Godel's incompleteness thoerem. For any axiomatic framework F, we can construct a sentence G(F) s.t. G(F) is a sentence within F, but not provable, and if F is consistent, then G(F) is true. Penrose, Lucas use it to challenge AI. \n\n\n- Response: agents do not cease to be agents if they can't establish truth of a sentence. Secondly, Godel's theorem is about math rather than computers. Even humans cannot overcome Godel's incompleteness theorem. Thirdly, Godel's theorem only applies to systems powerful enough to do arithmetic. Covers Turing Machiines, but computers are not Turing machines as they are finite. It is also not true that computers cannot change their minds \n\n\nTuring test is used to measure AI. Eugene Goostman (2014) fooled 33% of amateur judges, but no well trained judges. \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Turing: we maintain the polite convention that everyone thinks, and we should also extend that to machines. Dijkstra: asking if machines can think is like asking if submarines can swim\n\n\nSearle: supports biological naturalism: mental states are high-level emergent features caused by low-level physical/ neural processes. \n\n\nResponse: humans are made of cells and they do not understand either. \n\n\nIntrinsic nature of experiences: qualia. Dividing ideas on consciousness: global workspace vs integrated information theory.  \n\n## AIMA 2.1 Agents and Environments\n Examples of agents include software, handheld calculators and vacuum cleaners. Agents' actions can depend on anything it has received up till present. Agent functions have two representations: tabulation for external representation and agent program for internal representation.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n We need  to know what rational, or [do the right thing] means. Consequentialism assesses behaviors by outcomes, using performance measures to capture desirability. \n\n\nIt is generally better to design performance measures according to our desired outcomes then how we want agents to behave. We assume that PMs can be specified correctly. \n\n\nRational agent uses percept sequence and internal knowledge to maximize performancemeasure. \n\nRationality is not omniscience or perfection: does not maximize actual performance. \n\n\nRational agents may do actions to modify future percepts, called information gathering. It also has to learn (i.e augments its internal knowledge). \n\n\nIf an agent does not entirely relyon prior knowledge (i.e. can learn), it is autonomous. Good to start with initial knowledge then gradually gain autonomny.  \n\n## AIMA 2.3 The Nature of Environments\n PEAS: Performance, environment, actuators, sensors. Example PEAS for automated taxi: actuators are the controls for brake, signal, horn,sensors are radar, GPS, etc. Software agents can also be as complex as physical ones. \n\n\nVarieties of task environments: \n\n\n(1) fully observable (sensor detects all aspects relevant to the choice of action, relevant being dependent on performance measure; no need of internal state in that case) vs partially observable (inaccurate sensor, missing data) vs unobservable (no sensor),\n\n\n(2) single vs multi-agent(can be competitive or cooperative, depending on how A's performance measure depends on B's ) Deterministic vs stochastic (state changes with quantifiable probability) vs non-deterministic (no quantification of prob) \n\n\n(3) Episodic (actions independent from each other) vs sequential (current decision can affect future) \n\n\n(4) static vs dynamic: can env change while agent is deliberating vs semi-dynamic: env does not change but agent's performance score does (e.g. chess with a clock) \n\n\n(5) discrete v continuous: whether the state,time, percepts, and actions are discrete or continuous. \n\n\n(6) known vs unknown: whether agent has knowledge of the laws of physics. \n\n\nMost difficult is partially observable, nondeterministic, multi agent, unknown, sequential dynamic, and continous. E.g. Taxi driving. Some examples: English tutor TE is partial, multi-agent, stochastic, sequential dynamic, discrete; part picking robot is partial, single agent, stochastic, episodic, dynamic, continuous. Experiments with environments are mostly carried out for many envs drawn from an environment class.\n\n## AIMA 2.4 The Structure of Agents\n Table approach is inefficient: if p is the length of percept sequence and T is lifetime then lookup table will have $\\sum_{t = 1}^{T} p ^ t$ entries.\n\n\nFour kinds of agent problems. \n\n(1) Simple reflex agent uses current percept without considerationof previous sequence, like vacuum agent. Uses condition- action rules, if then statements.Mostly uses in fully observable envs because of limited intelligence. Can fall into infinite loops in partially observable envs. May escape with randomized actions (randomized can be rational).\n\n\n(2) model based reflex agents (maintain internal states) requires two kinds of knowledge: (a) knowledge of how the world works, or transition model. (b) information about how the state of the world is reflected in precepts, i.e. sensor model. Uses the knowledge to guess the world's state at the moment. (update state using precept, uses actions rules to derive an action).\n\n\n(3) goal based agents: uses goalsto capture desirable outcomes (e.g. search and planning agents). Differs from (1) and (2) because agents knows why it does certain actions \n\n\n(4) utility based agents: uses utility as an internal representation of performance measure, has advantage in flexibility and learning. Better than (3) in two ways: (a) helps rank different goals, and (b) helps decide which goal to pursue under uncertainty. Not all utility based agents are model-based: model free agents can learn what action is best iwthout knowing how it changes the environment. \n \n\n## Module 1 Lecture Notes\n Descartes' dualism suggests mind body separation, seeing bodies as just complex machines. Descartes suggests that however machinescan never learn to use languages. Turing proposes an imitation game. Searle however,\nargues that machines are not thinking but just doing symbol manipulation as in Chinese Room (e.g. Eliza, early NLP chatbot). \n\n\nContrasts strong vs weak AI: strongAI has a mind and can understand, while weak AI only simulates thoughts and do nothave real understanding. Searle thinks that biological brains causes minds. Dennett's brain in a vat experiment in [Who Am I?] asks whether a brain in a vat is really different\\ \nfrom a machine processing symbols. Current AI endeavors focuses on solving subproblems andtopping leaderboards, but some wants to develop truly intelligent AI. \n\n\nAgent function f: P->A maps a sequence of percepts (list) to a set of actions. Agent program runs on an architecture to implement an agent function. Can do this in a table but length will be exponential in len(P). \n\n\nPerformance Measure, Environment, Actuators and Sensors specify a task environment. A designer'sgoal is to construct an agent function f that maximizes expected value of performance measure, then construct an agent program that implements the function on an architecutre, given a task environment. \n\n\nWe describe something as an agent when it can be said to have its own perfomance measure.\n\n\nFor initial part of course we assume fully observable, static, deterministic, and discrete \n\n\nReflex agent: makes action based on current precept vs problem solving agent: plans aheade.g. searching. It formulates goal, generates a search problem with states, actions, performanceand come up with a solution. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content that an agent's sensor receives\n* **Percept sequence** - complete history of everything the agent has perceived\n* **Rational agent** - an agent that acts to achieve the best outcome or best expected outcome (i.e. maximize performance measure\n* **Agent function** - maps any given percept sequence to an action\n* **Agent program** - implementation of agent function\n* **Standard model** - The idea of constructing agents to do the right thing\n* **Turing test** - computer test using human-written questions, requiring NLP, knowledge representation, automated reasoning, and ML\n* **Total turing test** - Enhanced Turing test requiring computer vision and roboticsinteraction with real world\n* **Performance measure** - an objective yardstick for evaluating performance, using evidencefrom percept sequence\n* **Task environment** - a problem specification to be solved by the agent, consists of PEAS\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 = \"\"\" Features of python: fast development (intuitive syntax, \\\n",
        "whitespace delimited, garbage collected), portable,  built-in types, many supporting \\\n",
        "libraries. \\n\n",
        "\n",
        "REPL environment: Read-evaluate-print loop. e.g. Python3 in terminal. \\n\n",
        "\n",
        "Script: Create file, run script, need to print explicitly \\n\n",
        "\n",
        "Use newline to end line of code, use backslash to continue to next line. Line indentation \\\n",
        "indicates block scope. \\n\n",
        "\n",
        "All data are objects, deleted when unreachable.\\n\n",
        "\n",
        "Prefixing with r creates rawstring, which do not need to escape special chars. \\n\n",
        "\n",
        "String formating: e.g. print(\"%s ... %d\" % (\"abc\", 123))\\n\n",
        "\n",
        "Strings are immutable in python\\n\n",
        "\n",
        "Use \"is\" keyword to check if objects are same, and == to check if values are same \\n\n",
        "\n",
        "y = x[:] gives a shallow copy of sequence: new object with exact same values \\n\n",
        "\n",
        "Tuples \\n\n",
        "- Immutable, ordered sequence\\n\n",
        "- can have mixed type items (including collections)\\n\n",
        "\n",
        "Strings \\n\n",
        "- Immutable \\n\n",
        "- Unicode, Use 2 byte chars (or 8 bit in Python 2)\\n\n",
        "\n",
        "Lists \\n\n",
        "- Mutable \\n\n",
        "- Mixed types \\n\n",
        "\n",
        "Dictionaries \\n\n",
        "- unordered \\n\n",
        "- Keys must be immutable, use hashing \\n\n",
        "- constant average time add, lookup, update \\n\n",
        "- accessing dict with unknown key throws error \\n\n",
        "\n",
        "Slicing always return a copy \\n\n",
        "\n",
        "List methods: li.reverse(), li.remove(item) - gives error, li.count(item), li.index(item), \\\n",
        "li.insert(idx), li.append(item) \\n\n",
        "\n",
        "li.sort() sorts in place, while sorted() returns a copy \\n\n",
        "\n",
        "String methods: s.split(), s.captialize(), s.upper(), s.strip(), s.join(s2) \\n\n",
        "\n",
        "Dict methods: d.keys() returns list of keys, d.values() returns list of current values, \\\n",
        " d.items() returns list of item tuples \\n\n",
        "\n",
        "Defaultdict initializes nonexistent values, similar to Counter \\n\n",
        "\n",
        "Function def: \\n\n",
        "\\t def functionName(arguments): \\n\n",
        "\\t\\t return something, somethingElse \\n\n",
        "\n",
        "No function overloading, two functions cannot have the same name\\n\n",
        "\n",
        "Default values for function should come last - else SyntaxError \\n\n",
        "\n",
        "Keyword arguments allow calling functions with arguments out of order. It should \\\n",
        "be included after all other arguments. \\n\n",
        "\n",
        " \\*args as argument allows variable number of arguments (in the form of tuple) \\\n",
        "to be passed as arguments. Use star operator * to unpack list into tuple.\\n\n",
        "\n",
        "\\*\\*kwargs take variable number of dictionary entries as keyword arguments. \\\n",
        "Use double star * * to unpack dict into positional arguments. args and kwargs can \\\n",
        "be used together. \\n\n",
        "\n",
        "Default arguments in function refers to the same object across all calls, can use for \\\n",
        "memoization \\n\n",
        "\n",
        "Creating class: \\n\n",
        "\\t class Example(superClass, superClass2):\\n\n",
        "\\t\\t def __init__(self, attr):\\n\n",
        "\\t\\t\\t self.attr = attr\\n\n",
        "\\t\\t def func(self): \\n\n",
        "\\t\\t\\t print(self.attr)\\n\n",
        "\n",
        "Redefine methods in subclass: just use the same name. Calling methods in parent class: \\\n",
        "parent.method(self, arg, arg2...)\\n\n",
        "\n",
        "Main method: if __name__ == '__main__':\\n\n",
        "\n",
        "Iterator creation: li.__iter__(), iter(li) returns iter object. Can call next(iter) \\\n",
        "or iter.__next__() or iter.next(). Need to catch StopIteration exception.\\n\n",
        "\n",
        "For loops uses iterators underneath. Iterator needs __next__ and iterable needs __iter__ \\n\n",
        "\n",
        "We can do \\n\n",
        "\\t for elem in Iter(input): \\n\n",
        "\\t\\t print elem \\n\n",
        "\n",
        "more memory efficient than getting the whole list \\n\n",
        "\n",
        "Generators are iterators underneath. Including yield keywords makes a function returns \\\n",
        "a geneator. Each time the next() method of generator is called, the method runs until \\\n",
        "it finds a yield. \\n\n",
        "\n",
        "Generators use less code, auto-maintain local states, compute value one at a time, \\\n",
        "saves memory, provides one-pass aggregation of item, and very useful for infinite sequences \\n\n",
        "\n",
        "Use importlib to reload code. importlib.reload(nameOfModule)\\n\n",
        "\n",
        "pip: package installer for Python. \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"Object cannot be modified after creation\",\n",
        "\"Strong typing\" : \"every object has fixed type, and interpreter enforce type restrictions \\\n",
        "(e.g. string + int)\",\n",
        "\"Static typing\" : \"variables can only refer to objects of declared type, e.g. java; functions \\\n",
        "have type signatures\",\n",
        "\"Dynamic typing\" : \"Variables can take on different types, functions do not have type \\\n",
        "signatures, catch type errors at runtime\",\n",
        "\"Dynamic scope\" : \"functions sees and uses the most current value of variables\",\n",
        "\"First class objects\": \"Programming entities that can be created, destroyed, pass to functions \\\n",
        "return as a value, and be treated like other variables\",\n",
        "\"extension\" : \"One class using methods and attributes defined in another class\",\n",
        "\"magic methods\" : \"methods that allow user defined classes to act like built in types, \\\n",
        "e.g. __copy__, __cmp__\",\n",
        "\"duck typing\" : \"Assess suitability of object by checking whether corresponding method \\\n",
        "exists. Eliminates need of interface\",\n",
        "\"list comprehension\" : \"[exp for x in list if cond(x)]\"\n",
        "}"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1e5b5826-80b8-46b5-fd0d-4ed7d941a65e"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Features of python: fast development (intuitive syntax, whitespace delimited, garbage collected), portable,  built-in types, many supporting libraries. \n\n\nREPL environment: Read-evaluate-print loop. e.g. Python3 in terminal. \n\n\nScript: Create file, run script, need to print explicitly \n\n\nUse newline to end line of code, use backslash to continue to next line. Line indentation indicates block scope. \n\n\nAll data are objects, deleted when unreachable.\n\n\nPrefixing with r creates rawstring, which do not need to escape special chars. \n\n\nString formating: e.g. print(\"%s ... %d\" % (\"abc\", 123))\n\n\nStrings are immutable in python\n\n\nUse \"is\" keyword to check if objects are same, and == to check if values are same \n\n\ny = x[:] gives a shallow copy of sequence: new object with exact same values \n\n\nTuples \n\n- Immutable, ordered sequence\n\n- can have mixed type items (including collections)\n\n\nStrings \n\n- Immutable \n\n- Unicode, Use 2 byte chars (or 8 bit in Python 2)\n\n\nLists \n\n- Mutable \n\n- Mixed types \n\n\nDictionaries \n\n- unordered \n\n- Keys must be immutable, use hashing \n\n- constant average time add, lookup, update \n\n- accessing dict with unknown key throws error \n\n\nSlicing always return a copy \n\n\nList methods: li.reverse(), li.remove(item) - gives error, li.count(item), li.index(item), li.insert(idx), li.append(item) \n\n\nli.sort() sorts in place, while sorted() returns a copy \n\n\nString methods: s.split(), s.captialize(), s.upper(), s.strip(), s.join(s2) \n\n\nDict methods: d.keys() returns list of keys, d.values() returns list of current values,  d.items() returns list of item tuples \n\n\nDefaultdict initializes nonexistent values, similar to Counter \n\n\nFunction def: \n\n\t def functionName(arguments): \n\n\t\t return something, somethingElse \n\n\nNo function overloading, two functions cannot have the same name\n\n\nDefault values for function should come last - else SyntaxError \n\n\nKeyword arguments allow calling functions with arguments out of order. It should be included after all other arguments. \n\n\n \\*args as argument allows variable number of arguments (in the form of tuple) to be passed as arguments. Use star operator * to unpack list into tuple.\n\n\n\\*\\*kwargs take variable number of dictionary entries as keyword arguments. Use double star * * to unpack dict into positional arguments. args and kwargs can be used together. \n\n\nDefault arguments in function refers to the same object across all calls, can use for memoization \n\n\nCreating class: \n\n\t class Example(superClass, superClass2):\n\n\t\t def __init__(self, attr):\n\n\t\t\t self.attr = attr\n\n\t\t def func(self): \n\n\t\t\t print(self.attr)\n\n\nRedefine methods in subclass: just use the same name. Calling methods in parent class: parent.method(self, arg, arg2...)\n\n\nMain method: if __name__ == '__main__':\n\n\nIterator creation: li.__iter__(), iter(li) returns iter object. Can call next(iter) or iter.__next__() or iter.next(). Need to catch StopIteration exception.\n\n\nFor loops uses iterators underneath. Iterator needs __next__ and iterable needs __iter__ \n\n\nWe can do \n\n\t for elem in Iter(input): \n\n\t\t print elem \n\n\nmore memory efficient than getting the whole list \n\n\nGenerators are iterators underneath. Including yield keywords makes a function returns a geneator. Each time the next() method of generator is called, the method runs until it finds a yield. \n\n\nGenerators use less code, auto-maintain local states, compute value one at a time, saves memory, provides one-pass aggregation of item, and very useful for infinite sequences \n\n\nUse importlib to reload code. importlib.reload(nameOfModule)\n\n\npip: package installer for Python. \n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - Object cannot be modified after creation\n* **Strong typing** - every object has fixed type, and interpreter enforce type restrictions (e.g. string + int)\n* **Static typing** - variables can only refer to objects of declared type, e.g. java; functions have type signatures\n* **Dynamic typing** - Variables can take on different types, functions do not have type signatures, catch type errors at runtime\n* **Dynamic scope** - functions sees and uses the most current value of variables\n* **First class objects** - Programming entities that can be created, destroyed, pass to functions return as a value, and be treated like other variables\n* **Extension** - One class using methods and attributes defined in another class\n* **Magic methods** - methods that allow user defined classes to act like built in types, e.g. __copy__, __cmp__\n* **Duck typing** - Assess suitability of object by checking whether corresponding method exists. Eliminates need of interface\n* **List comprehension** - [exp for x in list if cond(x)]\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 = \"\"\" Problem-solving agent plans ahead, considers a sequence of \\\n",
        "actions. It does searching to come up with such a sequence. They use atomic\\\n",
        " representation (e.g. Markov decision, search agent), which have no internal \\\n",
        " structure visible. In contrast, planning agents use factored \\\n",
        " (variables, e.g. CSP, Logic) or structured (e.g. tree, e.g.) representations. \\n\n",
        "\n",
        "Four phase problem solving: Formulating a goal, formulating a problem \\\n",
        "(comes up with state and action representation), search (generate a sequence \\\n",
        "of actions called a solution), and execution. In fully observable, deterministic,\\\n",
        "and known environment, solution is fixed and the system is called an open-loop system,\\\n",
        "since the agent can ignore the precepts. VS closed-loop approach where agent has \\\n",
        "to monitor percepts (e.g. indeterministic env)\\n\n",
        "\n",
        "Problem definition requires (1) state space, (2) initial state, \\\n",
        "(3) goal states, (4) actions available (for every state the actions that are \\\n",
        "applicable in s, ACTIONS(s)), (5) transition model (RESULTS(s, a) -> s’),  \\\n",
        "and (6) action cost function (ACTION-COST(s, a, sp) -> cost). \\n\n",
        "\n",
        "Abstraction is the process of removing details from a representation. \\\n",
        "Abstraction is valid if it can be elaborated into a working solution in a \\\n",
        "more detailed world; it is useful if the actions suggested through abstract \\ \n",
        "is easier than the original problem. \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" A standardised problem is used to illustrate problem solving\\\n",
        " methods. It has a concise exact description and is used as benchmark for \\\n",
        " comparing algos. VS a real-world problem. \n",
        "\n",
        "Grid world puzzles (e.g. vacuum world have n * 2 ^n states \\\n",
        "(n as number of cells)). Actions can be specified as absolute, or egocentric \\\n",
        "(defined relative to agent’s viewpoint).\\n\n",
        "\n",
        "Sokoban puzzle is where an agent needs to push some boxes to locations. For a \\\n",
        "world with n non-obstacle cells and b boxes, there are $n * n! / (b!(n-b)!)$ \\\n",
        "states. \\n\n",
        "\n",
        "Sliding tile puzzles (e.g. 8-puzzle, Rush Hour Puzzle) is another type of standard \\\n",
        "problem.\\n\n",
        "\n",
        "Knuth proposes another problem: using square root, floor, and factorial operations \\\n",
        "to transform number 4 into any number. State space is infinite.\\n\n",
        "\n",
        "Real world problem example: rout-finding (reach a specific location), touring \\\n",
        "(visit a set of locations, e.g. TSP), VLSI layout (cell layout without \\\n",
        "overlapping, channel routing that finds a route for each wire), robot navigation \\\n",
        "(many-dimensional search space, one dimension for each joint angle), automatic \\\n",
        "assembly sequencing (e.g. protein design) \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" Search tree - representation of a state space with each node \\\n",
        "being a state and each edge being an action. Root represents initial state. \\\n",
        "Search tree is not the state space itself - multiple paths may get to any \\\n",
        "particular state, and each node in the tree can get back to the root by a unique \\\n",
        "path. \\n\n",
        "\n",
        "\n",
        "Best-first search algorithm: choose node with minimum value of evaluation \\\n",
        "function. Also: Add initial node to frontier, pop node, if not goal then expand, \\\n",
        "add unvisited node (or visited node with lower cost) to frontier and reached lookup \\\n",
        "table. Continue until goal state found.\\n\n",
        "\n",
        "Best first search uses priority queue; breadth first search uses FIFO queue; \\\n",
        "DFS uses LIFO queue/ stack.\\n\n",
        "\n",
        "Sometimes there can be repeated states. A cycle/ looping part involves coming \\\n",
        "back to the same state, which makes search tree infinite. It is a special case of \\\n",
        "redundant path - two paths with same goal and destination but different lengths.\\n\n",
        "\n",
        "Three approaches to handle repeated states: 1) remember all reached states \\\n",
        "(preferred if many redundant paths), 2) do not worry about repeating (because \\\n",
        "of problem specification), 3) check for cycles but not redundant paths (follow \\\n",
        "up chains of parents to see if the current state has appeared earlier) \\n\n",
        "\n",
        "Graph search checks for redundant paths and tree like search do not. Best first \\\n",
        "search is graph search.\\n\n",
        "\n",
        "Four ways to measure alto’s performance, 1) completeness, 2) cost optimality, \\\n",
        "3) time complexity, 4) space complexity. Completeness requires an algorithm to be \\\n",
        "systematic. If state space is infinite, a sound algorithm has to search forever.  \"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" Breath first search is used when all actions have the same \\\n",
        "costs. It is same as best-first search when f(n) returns the depth of the node. \\\n",
        "Advantages vs Best-first search: (1) FIFO faster than priority queue, (2) \\\n",
        "reached can be a set of state, not a state-to-node mapping (no need of distance \\\n",
        "info), (3) can do an early goal test - testing if a node is goal as soon as it \\\n",
        "is added to frontier, not when it is popped. \\n\n",
        "\n",
        "Dijkstra’s algorithm / uniform cost search is best-first-search with evaluation \\\n",
        "function = cost of path from root to current node. Worst case time and space \\\n",
        "complexity is $O(b^{1+floor(C* / \\epsilon)})$, where C* is cost of optimal solution, \\\n",
        "and epsilon is the lower bound on the cost of each action. It can be much greater than \\\n",
        "b^d, since it can explore large trees with low costs before high costs ones. \\\n",
        "When all action costs are equal, complexity is b^(d+1), similar to breadth-first \\\n",
        "search. It is complete and optimal. It will not get caught going down a single \\\n",
        "infinite path. \\n\n",
        "\n",
        "DFS expands deepest node first. Same as BFS where evaluation function = \\\n",
        "negative of depth of node. Usually implemented as aa tree-like search. For \\\n",
        "tree-like finite state spaces it is efficient and complete. In acyclic spaces \\\n",
        "it may expand same state many times but will explore the entire space. However, \\\n",
        "it can get trapped in infinite loop in cyclic state spaces. In infinite stat \\\n",
        "spaces it is not systematic - can go along infinite path even without cycles. \\\n",
        "It is not optimal, since it will return first solution found. Runtime is O(bm) \\\n",
        "with m = maximum depth of tree. Used for CSP, satisfiability, and logic programming.\\n\n",
        "\n",
        "A variant of DFS is backtracking serach, generating one successor at a time, which is \\\n",
        "done in place (modify current state) rather than constructing new state. \\\n",
        "Reduces memory req to O(m) actions. Also allows using an efficient DS to store \\\n",
        "states on current path with cycle checking in O(1) time. \\n\n",
        "\n",
        "Hybrid approach is to run BFS until all memory is consumed and run iterative deepening \\\n",
        "from all nodes in frontier. When search space is larger than memory, and depth \\\n",
        "of solution is unknown iterative deepening is preferred. \\n\n",
        "\n",
        "Bidirectional best first search reduces space and time complexity to O(b^(d/2)). \\\n",
        "We maintain two lookup tables and two frontiers, and expand in each direction. \\\n",
        "We join paths when one direction expands nodes already in another's path. Need \\\n",
        "a TERMINATED function to decide when to stop. If we do bidirectional uniform cost \\\n",
        "search and optimal path length is C*, then no node with cost C*/2 will be expanded. \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Reflex agent ignores percept history; problem solving \\\n",
        "agents plan ahead using search. \\n\n",
        "\n",
        "BFS pseudocode: \\n\n",
        "\n",
        "def BFS():\\n\n",
        "  \\t node = node with state = initial state, path cost = 0\\n\n",
        "  \\t if goal_test(node): return solution\\n\n",
        "  \\t fronter = FIFO queue with node\\n\n",
        "  \\t explored = empty set \\n\n",
        "  \\t while frontier:\\n\n",
        "  \\t\\t node = frontier.pop() // shallowest node\\n\n",
        "  \\t\\t explored.add(node.state)\\n\n",
        "  \\t\\t for each action in node.state.actions():\\n\n",
        "  \\t\\t\\t child = child-node(problem, node, action)\\n\n",
        "  \\t\\t\\t if child.state not in explored or frontier:\\n\n",
        "  \\t\\t\\t\\t if goal_test(child.state) return solution\\n\n",
        "  \\t\\t\\t\\t frontier.insert(child)\\n\n",
        "\n",
        "BFS is complete and optimal (when cost is constant). Total nodes generated = \\\n",
        "space and time complexity is $1 + b + b^2 + b^3 +… + b^d = O(b^d)$, b = \\\n",
        "branching factor and d = solution depth. Memory requirement is a bigger concern \\\n",
        "than time. Limits BFS to solving uninformed searches for large problems. \\n\n",
        "\n",
        "Depth limited search is O(b^l) time and O(bl) space, l being the depth limit. \\\n",
        "Also tree like search. Can use the diameter of the stae space graph as depth \\\n",
        "(ie how many states). \\n\n",
        "\n",
        "Iterative deepening search has O(bd) memory requirement when there is solution,\n",
        "or O(bm) on finite spaces with no solution (m is max depth, d is depth of shallowest \\\n",
        "solution). Time complexity O(b^d) or O(b^m). Total number of nodes generated is \\\n",
        "db^1 + (d-1)b^2 + (d-2)b^3... + ... b^d \\n\n",
        "\n",
        "Comparing search methods:\\n\n",
        "\n",
        "BFS: complete, $b^d$ time and space, optimal\\n\n",
        "DFS: not complete, not optimal, $b^m$ time, $bm$ space\\n\n",
        "Depth limited: Not complete, not optimal, $b^l$ time, bl space \\n\n",
        "Iterative deepening: complete, optimal, $b^d$ time, $bd$ space\\n\n",
        "\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",
        "\"path\" : \" a sequence of actions\",\n",
        "\"Node Expansion\": \"consider all available actions for that state and generate a new node\",\n",
        "\"Solution\" : \"a path from initial state to goal state\",\n",
        "\"Optimal solution\" : \"solution with lowest path cost\",\n",
        "\"Completeness\" : \"can find a solution if \\\n",
        "there is one, and repeat failure when there is none\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "64c3cb84-0153-413c-a0c0-81aaba133596"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-solving agent plans ahead, considers a sequence of actions. It does searching to come up with such a sequence. They use atomic representation (e.g. Markov decision, search agent), which have no internal  structure visible. In contrast, planning agents use factored  (variables, e.g. CSP, Logic) or structured (e.g. tree, e.g.) representations. \n\n\nFour phase problem solving: Formulating a goal, formulating a problem (comes up with state and action representation), search (generate a sequence of actions called a solution), and execution. In fully observable, deterministic,and known environment, solution is fixed and the system is called an open-loop system,since the agent can ignore the precepts. VS closed-loop approach where agent has to monitor percepts (e.g. indeterministic env)\n\n\nProblem definition requires (1) state space, (2) initial state, (3) goal states, (4) actions available (for every state the actions that are applicable in s, ACTIONS(s)), (5) transition model (RESULTS(s, a) -> s’),  and (6) action cost function (ACTION-COST(s, a, sp) -> cost). \n\n\nAbstraction is the process of removing details from a representation. Abstraction is valid if it can be elaborated into a working solution in a more detailed world; it is useful if the actions suggested through abstract \\ \nis easier than the original problem. \n\n## AIMA Chapter 3.2 Example Problems\n A standardised problem is used to illustrate problem solving methods. It has a concise exact description and is used as benchmark for  comparing algos. VS a real-world problem. \n\nGrid world puzzles (e.g. vacuum world have n * 2 ^n states (n as number of cells)). Actions can be specified as absolute, or egocentric (defined relative to agent’s viewpoint).\n\n\nSokoban puzzle is where an agent needs to push some boxes to locations. For a world with n non-obstacle cells and b boxes, there are $n * n! / (b!(n-b)!)$ states. \n\n\nSliding tile puzzles (e.g. 8-puzzle, Rush Hour Puzzle) is another type of standard problem.\n\n\nKnuth proposes another problem: using square root, floor, and factorial operations to transform number 4 into any number. State space is infinite.\n\n\nReal world problem example: rout-finding (reach a specific location), touring (visit a set of locations, e.g. TSP), VLSI layout (cell layout without overlapping, channel routing that finds a route for each wire), robot navigation (many-dimensional search space, one dimension for each joint angle), automatic assembly sequencing (e.g. protein design) \n\n## AIMA Chapter 3.3 Search Algorithms\n Search tree - representation of a state space with each node being a state and each edge being an action. Root represents initial state. Search tree is not the state space itself - multiple paths may get to any particular state, and each node in the tree can get back to the root by a unique path. \n\n\n\nBest-first search algorithm: choose node with minimum value of evaluation function. Also: Add initial node to frontier, pop node, if not goal then expand, add unvisited node (or visited node with lower cost) to frontier and reached lookup table. Continue until goal state found.\n\n\nBest first search uses priority queue; breadth first search uses FIFO queue; DFS uses LIFO queue/ stack.\n\n\nSometimes there can be repeated states. A cycle/ looping part involves coming back to the same state, which makes search tree infinite. It is a special case of redundant path - two paths with same goal and destination but different lengths.\n\n\nThree approaches to handle repeated states: 1) remember all reached states (preferred if many redundant paths), 2) do not worry about repeating (because of problem specification), 3) check for cycles but not redundant paths (follow up chains of parents to see if the current state has appeared earlier) \n\n\nGraph search checks for redundant paths and tree like search do not. Best first search is graph search.\n\n\nFour ways to measure alto’s performance, 1) completeness, 2) cost optimality, 3) time complexity, 4) space complexity. Completeness requires an algorithm to be systematic. If state space is infinite, a sound algorithm has to search forever.  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breath first search is used when all actions have the same costs. It is same as best-first search when f(n) returns the depth of the node. Advantages vs Best-first search: (1) FIFO faster than priority queue, (2) reached can be a set of state, not a state-to-node mapping (no need of distance info), (3) can do an early goal test - testing if a node is goal as soon as it is added to frontier, not when it is popped. \n\n\nDijkstra’s algorithm / uniform cost search is best-first-search with evaluation function = cost of path from root to current node. Worst case time and space complexity is $O(b^{1+floor(C* / \\epsilon)})$, where C* is cost of optimal solution, and epsilon is the lower bound on the cost of each action. It can be much greater than b^d, since it can explore large trees with low costs before high costs ones. When all action costs are equal, complexity is b^(d+1), similar to breadth-first search. It is complete and optimal. It will not get caught going down a single infinite path. \n\n\nDFS expands deepest node first. Same as BFS where evaluation function = negative of depth of node. Usually implemented as aa tree-like search. For tree-like finite state spaces it is efficient and complete. In acyclic spaces it may expand same state many times but will explore the entire space. However, it can get trapped in infinite loop in cyclic state spaces. In infinite stat spaces it is not systematic - can go along infinite path even without cycles. It is not optimal, since it will return first solution found. Runtime is O(bm) with m = maximum depth of tree. Used for CSP, satisfiability, and logic programming.\n\n\nA variant of DFS is backtracking serach, generating one successor at a time, which is done in place (modify current state) rather than constructing new state. Reduces memory req to O(m) actions. Also allows using an efficient DS to store states on current path with cycle checking in O(1) time. \n\n\nHybrid approach is to run BFS until all memory is consumed and run iterative deepening from all nodes in frontier. When search space is larger than memory, and depth of solution is unknown iterative deepening is preferred. \n\n\nBidirectional best first search reduces space and time complexity to O(b^(d/2)). We maintain two lookup tables and two frontiers, and expand in each direction. We join paths when one direction expands nodes already in another's path. Need a TERMINATED function to decide when to stop. If we do bidirectional uniform cost search and optimal path length is C*, then no node with cost C*/2 will be expanded. \n\n \n\n## Module 3 Lecture Notes\n Reflex agent ignores percept history; problem solving agents plan ahead using search. \n\n\nBFS pseudocode: \n\n\ndef BFS():\n\n  \t node = node with state = initial state, path cost = 0\n\n  \t if goal_test(node): return solution\n\n  \t fronter = FIFO queue with node\n\n  \t explored = empty set \n\n  \t while frontier:\n\n  \t\t node = frontier.pop() // shallowest node\n\n  \t\t explored.add(node.state)\n\n  \t\t for each action in node.state.actions():\n\n  \t\t\t child = child-node(problem, node, action)\n\n  \t\t\t if child.state not in explored or frontier:\n\n  \t\t\t\t if goal_test(child.state) return solution\n\n  \t\t\t\t frontier.insert(child)\n\n\nBFS is complete and optimal (when cost is constant). Total nodes generated = space and time complexity is $1 + b + b^2 + b^3 +… + b^d = O(b^d)$, b = branching factor and d = solution depth. Memory requirement is a bigger concern than time. Limits BFS to solving uninformed searches for large problems. \n\n\nDepth limited search is O(b^l) time and O(bl) space, l being the depth limit. Also tree like search. Can use the diameter of the stae space graph as depth (ie how many states). \n\n\nIterative deepening search has O(bd) memory requirement when there is solution,\nor O(bm) on finite spaces with no solution (m is max depth, d is depth of shallowest solution). Time complexity O(b^d) or O(b^m). Total number of nodes generated is db^1 + (d-1)b^2 + (d-2)b^3... + ... b^d \n\n\nComparing search methods:\n\n\nBFS: complete, $b^d$ time and space, optimal\n\nDFS: not complete, not optimal, $b^m$ time, $bm$ space\n\nDepth limited: Not complete, not optimal, $b^l$ time, bl space \n\nIterative deepening: complete, optimal, $b^d$ time, $bd$ space\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** -  a sequence of actions\n* **Node expansion** - consider all available actions for that state and generate a new node\n* **Solution** - a path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Completeness** - can find a solution if there is one, and repeat failure when there is none\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "Every consistent heuristic is admissible but not vice versa. \\\n",
        "With consitent heuristic we will have optimal path the first time we reach \\\n",
        "a state. \\n\n",
        "\n",
        "\n",
        "If heuristic is inadmissible A * can still be optimal if 1) there is a path where \\\n",
        "it is admissible, or (2) heuristic does not overestimate more than C^2 - C * , with former \\\n",
        "being cost of second best and latter cost of optimal solution. \\\n",
        "\n",
        "\n",
        "g cost is always monotonic - only increase when we go along the path, so contour lines \\\n",
        "never cross. \\n\n",
        "\n",
        "Surely expanded nodes have f(n) < C\\*. A\\* with \\\n",
        "consistent heuristic is optimally efficient since it exapnd all nodes that are surely \\\n",
        "expanded. \\n\n",
        "\n",
        "Drawback is that number of expanded nodes can be exponential in length of solution. \\n\n",
        "\n",
        "To reduce number of nodes expanded we can do satisficing search, producing solutions that\\\n",
        "may not be optimal but are good enough. E.g. multipler SLD by a detour index \\\n",
        "Weighted A * search uses f(n) = g(n) + W * h(n) for some W > 1. \\n\n",
        "\n",
        "\n",
        "Ways to reduce memory req of A *: \\n\n",
        "(1) stores frontier nodes only either on frontier or \\\n",
        "on reached set. \\n\n",
        "\n",
        "(2) keep reference count of # times a state is visited to eliminate state \\ \n",
        "from reached when no longer needed. \\n\n",
        "\n",
        "(3) beam search: keepiing only k nodes with best f scores \\\n",
        "incomplete and suboptimal. \\n\n",
        "\n",
        "(4) alternative beam: keeps all node with f-score within a certain \\\n",
        "limit from optimal. \\n\n",
        "\n",
        "(5) iterative A * search (IDA *) with cutoff value set to certain f-cost (g+h) \\\n",
        "works well when each path has integer f costs. \\n\n",
        "\n",
        "(6) recursive best-first search, uses a f_limit \\\n",
        "variable to keep track of f-value of best alternative path from ancestor. If current node \\\n",
        "goes past the limit, goes back to that alternative, replacing f-value on each \\\n",
        "node with a backed-up value, the best f-value of its children. Helps decide whether \\\n",
        "it is useful to re-expand a subtree. More efficient than IDA *, optimal if h(n) is admissible, \\\n",
        "uses space linear in depth of deepest optimal solution. Time complexity depends on heuristic \\\n",
        "accuracy and how often path changes. \\n\n",
        "\n",
        "(7) (simple) Memory-bounded A\\* (SMA\\*): expand best leaf until memory full, then drop (oldest) worst \\\n",
        "leaf node(highest f value), backs up the value of that node, and regen the subtree only if all \\\n",
        "other paths are found worse. Complete if there is any reachable solution with depth less than memsize. \\\n",
        "Optimal if solution is reachable. \\n\n",
        "\n",
        "(8) bidirectional heuristic search: Two different h and g functions. lowerer bound of solution that goes to m, then n, then goal:\\\n",
        " $lb(m,n) = max(g_F(m)+g_B(n),f_F(m),f_B(n))$ For pair m,n with lb(m,n) less than optimal cost, \\\n",
        " we must expand either m or n to look for potential solutions. Cannot be ensured to be optimally efficient, but can \\\n",
        " be efficient. \\n\n",
        "\n",
        " f2 evaluation function = max(2g(n), g(n)+h(n)). Combined with admissible h, makes bidrectional \\\n",
        " search optimal and complete. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter3_6 = \"\"\" We can use effective branching factor to measure usefulness of heuristic. \\\n",
        "$N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$, where N = number of nodes generated with heuristic, \\\n",
        "d = solution depth. Well designed heuristic should have value ~ 1. \\n\n",
        "\n",
        "Effect of A * search can be captured by reducing effective depth \\\n",
        "of a search tree by a constant k_h. Total search cost bcomes $O(b^{d-k_h})$ instead of \\\n",
        "O(b^d). \\n\n",
        "\n",
        "A heuristic that dominates another usually have lower branching factor and is thus \\\n",
        "better. \\n\n",
        "\n",
        "We can come up with heuristics by reasoning on relaxed problems, with fewer restrictions \\\n",
        "then the original, e.g. with shortcuts. Can auto generate relaxed problems by disjuncting and \\ \n",
        "clauses (e.g. absolver program, found heuristic for Rubrik's) \\n\n",
        "\n",
        "We can also use composite heuristic = max of all available and admissible heuristics \\\n",
        "Takes longer to compute but better than all alternatives.\\n\n",
        "\n",
        "We can come up with heuristics using subproblems (i.e. pattern databases). Store \\\n",
        "costs for subproblems, compute admissible heuristic by looking up subproblem in database \\\n",
        ", which is constructed by searching back from goal and recording cost of each new pattern. \\\n",
        "expense \\n\n",
        "\n",
        "Disjoint pattern databases: divide up problem such that each move only affects one \\\n",
        "subproblem (e.g. in 8 puzzle, record number of moves involving 1-2-3-4, then sum up \\\n",
        "with 5-6-7-8.) \\n\n",
        "\n",
        "Another way to generate heuristics is to use landmarks. Choose a few landmark points, \\\n",
        "for each one compute and store optimal path from all other vertices to landmark (and opposite)\\\n",
        "then construct h(n) = min(C * (n, L) + C * (L, goal)). Efficient but not admissible. \\ \n",
        "If we want admissible we can use instead h(n) = max(abs(C * (n, L) - C * (goal, L))), differential \\\n",
        "heuristic.\\n\n",
        "\n",
        "Can save more time using shortcuts - artificial paths that pre-define optimal multi-action \\\n",
        "path. \\n\n",
        "\n",
        "Selecting landmarks: use peripheral ones for differnetial heuristic, farthest ones, or frequently \\\n",
        "requested ones \\n\n",
        "\n",
        "Final way to generate heuristic is to use ML/RL to learn from experience. Works better \\\n",
        "when we have features of a state (e.g. number misplaced tiles). Combine features linearly \\\n",
        "to produce heuristic\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Dimensions for evaluating search: (1) completeness, \\\n",
        "(2) optimality, (3) time complexity (num nodes generated), (4) space complexity (num nodes in memory). \\n\n",
        "\n",
        "We can use relaxed problems to generate heuristics. Cost of optimal solution to relaxed \\\n",
        "problem is admissible heuristic for original problem. \\n\n",
        "\n",
        "Greedy best first search uses f(n) = h(n). \\\n",
        "It is complete in finite state spaces but not infinite ones. \\\n",
        "Worst case space & time complexity is O(|V|). With good heuristic function \\\n",
        "it can reach O(bm). \\n\n",
        "\n",
        "Greedy Best first search code: \\n\n",
        "\n",
        "def greedy(): \\n\n",
        "  \\t frontier = PriorityQueue() \\n\n",
        "  \\t frontier.put(start, 0) \\n\n",
        "  \\t came_from = {} \\n\n",
        "  \\t came_from[start] = None \\n\n",
        "  \\t while not frontier.empty(): \\n\n",
        "  \\t\\t current = frontier.get() \\n\n",
        "  \\t\\t if current == goal: \\n\n",
        "  \\t\\t\\t break \\n\n",
        "  \\t\\t for next in graph.neighbors(current): \\n\n",
        "  \\t\\t\\t if next not in came_from: \\n\n",
        "  \\t\\t\\t\\t priority = heuristic(goal,next) \\n\n",
        "  \\t\\t\\t\\t frontier.put(next, priority) \\n\n",
        "  \\t\\t\\t\\t came_from[next] = current  \\n\n",
        "\n",
        "A* waits until the goal node is expanded to terminate. \\n\n",
        "\n",
        "A * search is complete. \\\n",
        "Whether it is optimal relates to whether it is admissible/optimistic. \\n\n",
        "\n",
        "Proof of A star: suppose optimal path has cost B * and algo returns path with cost B > B *. \\\n",
        "There must be some node on optimal path that is unexpanded. \\n\n",
        "\n",
        "\n",
        "If g * (n) = cost of optimal path since start state, h * (n) = cost \\\n",
        "of optimal path to nearest goal: \\n\n",
        "\n",
        "\n",
        "$f(n) > C*$ or n would have been expanded \\n\n",
        "\n",
        "\n",
        "$f(n) = g(n) + h(n)$ by definition \\n\n",
        "\n",
        "\n",
        "$f(n) = g*(n) + h(n)$ since n is on optimal path \\n\n",
        "\n",
        "\n",
        "$f(n) \\leq g*(n) + h*(n)$ since admissibility \\n\n",
        "\n",
        "\n",
        "$f(n) \\leq C*$ by definition \\n\n",
        "\n",
        "Alternative (word based proof):\\n\n",
        "\n",
        "Let A be optimal goal node, B be suboptimal goal node, claim that A will exit \\\n",
        "frontier before B. \\n\n",
        "\n",
        "If B is on frontier, and some ancestor n of A is on the frontier, we try to claim that n will \\\n",
        "be expanded before B. \\n\n",
        "\n",
        "1. $f(n) \\leq f(A)$ \\n\n",
        "\\t\\t - $f(n) \\leq g(A) = f(A)$ \\n\n",
        "2. $f(A) < f(B)$ \\n\n",
        "\\t\\t - $g(A) < g(B) \\implies f(A) < f(B)$ since h = 0 at goal\n",
        "3. so, n expands before B \\n\n",
        "\\t\\t - $f(n) \\leq f(A) < f(B)$\n",
        "4. Since all ancestors of A expand before B, A expand before B.\\n\n",
        "\n",
        "\n",
        "Uniform cost search can be seen as case where W = 0 and A* is W = 1. Greedy is \\\n",
        "W = infinity. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"unbounded cost search\" : \"accepts quick solutions at any cost \",\n",
        "\"bounded cost search\" : \"find solution with cost less than constant C\", \n",
        "\"Bounded suboptimal search\" : \"find solution guaranteed to be within a constant \\\n",
        "factor W of the optimal cost (e.g. weighted A*)\",\n",
        "\"speedy search\" : \"example of unbounded search and greedy, uses h(n) = number of actions \\\n",
        "required to reach goal regardless of cost\", \n",
        "\"a star search\" : \"best first search using f(n) = g(n) + h(n)\",\n",
        "\"heuristic function\" : \"estimates cost of cheapest path from state at node \\\n",
        "n to the goal state\",\n",
        "\"consistent heuristic\" : \"for every node n and every successor n' \\\n",
        "we have $h(n) \\leq c(n, a, n') + h(n')$.\",\n",
        "\"Manhattan distance/ city block distance\" : \"sum of distances from goal positions\",\n",
        "\"effective branching factor\" : \"branching factor that a uniform tree of depth d has s.t. it has \\\n",
        "N + 1 nodes\",\n",
        "\"heuristic domination\" : \"h1 dominates h2 if h2(n) >= h1(n) for any n. Better to use heuristic \\\n",
        "with higher values\",\n",
        "\"metalevel state space\" : \"captures the internal state of a program searching in an object-level\\\n",
        "state space\",\n",
        "\"metalevel learning algorithm\" :\"learn from missteps to avoid exploring unpromising paths, minimzing\\\n",
        "total cost\",\n",
        "\"front to end search\" : \"bidirectional search with heuristics estimating distance to goal/ initial\",\n",
        "\"front-to-front search\" : \"bidrectional search with heuristics estimating distance to the other\\\n",
        " frontier\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "694395de-a434-409c-8703-aacd14bf3a2c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nEvery consistent heuristic is admissible but not vice versa. With consitent heuristic we will have optimal path the first time we reach a state. \n\n\n\nIf heuristic is inadmissible A * can still be optimal if 1) there is a path where it is admissible, or (2) heuristic does not overestimate more than C^2 - C * , with former being cost of second best and latter cost of optimal solution. \n\ng cost is always monotonic - only increase when we go along the path, so contour lines never cross. \n\n\nSurely expanded nodes have f(n) < C\\*. A\\* with consistent heuristic is optimally efficient since it exapnd all nodes that are surely expanded. \n\n\nDrawback is that number of expanded nodes can be exponential in length of solution. \n\n\nTo reduce number of nodes expanded we can do satisficing search, producing solutions thatmay not be optimal but are good enough. E.g. multipler SLD by a detour index Weighted A * search uses f(n) = g(n) + W * h(n) for some W > 1. \n\n\n\nWays to reduce memory req of A *: \n\n(1) stores frontier nodes only either on frontier or on reached set. \n\n\n(2) keep reference count of # times a state is visited to eliminate state \\ \nfrom reached when no longer needed. \n\n\n(3) beam search: keepiing only k nodes with best f scores incomplete and suboptimal. \n\n\n(4) alternative beam: keeps all node with f-score within a certain limit from optimal. \n\n\n(5) iterative A * search (IDA *) with cutoff value set to certain f-cost (g+h) works well when each path has integer f costs. \n\n\n(6) recursive best-first search, uses a f_limit variable to keep track of f-value of best alternative path from ancestor. If current node goes past the limit, goes back to that alternative, replacing f-value on each node with a backed-up value, the best f-value of its children. Helps decide whether it is useful to re-expand a subtree. More efficient than IDA *, optimal if h(n) is admissible, uses space linear in depth of deepest optimal solution. Time complexity depends on heuristic accuracy and how often path changes. \n\n\n(7) (simple) Memory-bounded A\\* (SMA\\*): expand best leaf until memory full, then drop (oldest) worst leaf node(highest f value), backs up the value of that node, and regen the subtree only if all other paths are found worse. Complete if there is any reachable solution with depth less than memsize. Optimal if solution is reachable. \n\n\n(8) bidirectional heuristic search: Two different h and g functions. lowerer bound of solution that goes to m, then n, then goal: $lb(m,n) = max(g_F(m)+g_B(n),f_F(m),f_B(n))$ For pair m,n with lb(m,n) less than optimal cost,  we must expand either m or n to look for potential solutions. Cannot be ensured to be optimally efficient, but can  be efficient. \n\n\n f2 evaluation function = max(2g(n), g(n)+h(n)). Combined with admissible h, makes bidrectional  search optimal and complete. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n We can use effective branching factor to measure usefulness of heuristic. $N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$, where N = number of nodes generated with heuristic, d = solution depth. Well designed heuristic should have value ~ 1. \n\n\nEffect of A * search can be captured by reducing effective depth of a search tree by a constant k_h. Total search cost bcomes $O(b^{d-k_h})$ instead of O(b^d). \n\n\nA heuristic that dominates another usually have lower branching factor and is thus better. \n\n\nWe can come up with heuristics by reasoning on relaxed problems, with fewer restrictions then the original, e.g. with shortcuts. Can auto generate relaxed problems by disjuncting and \\ \nclauses (e.g. absolver program, found heuristic for Rubrik's) \n\n\nWe can also use composite heuristic = max of all available and admissible heuristics Takes longer to compute but better than all alternatives.\n\n\nWe can come up with heuristics using subproblems (i.e. pattern databases). Store costs for subproblems, compute admissible heuristic by looking up subproblem in database , which is constructed by searching back from goal and recording cost of each new pattern. expense \n\n\nDisjoint pattern databases: divide up problem such that each move only affects one subproblem (e.g. in 8 puzzle, record number of moves involving 1-2-3-4, then sum up with 5-6-7-8.) \n\n\nAnother way to generate heuristics is to use landmarks. Choose a few landmark points, for each one compute and store optimal path from all other vertices to landmark (and opposite)then construct h(n) = min(C * (n, L) + C * (L, goal)). Efficient but not admissible. \\ \nIf we want admissible we can use instead h(n) = max(abs(C * (n, L) - C * (goal, L))), differential heuristic.\n\n\nCan save more time using shortcuts - artificial paths that pre-define optimal multi-action path. \n\n\nSelecting landmarks: use peripheral ones for differnetial heuristic, farthest ones, or frequently requested ones \n\n\nFinal way to generate heuristic is to use ML/RL to learn from experience. Works better when we have features of a state (e.g. number misplaced tiles). Combine features linearly to produce heuristic\n\n\n\n## Module 4 Lecture Notes\n Dimensions for evaluating search: (1) completeness, (2) optimality, (3) time complexity (num nodes generated), (4) space complexity (num nodes in memory). \n\n\nWe can use relaxed problems to generate heuristics. Cost of optimal solution to relaxed problem is admissible heuristic for original problem. \n\n\nGreedy best first search uses f(n) = h(n). It is complete in finite state spaces but not infinite ones. Worst case space & time complexity is O(|V|). With good heuristic function it can reach O(bm). \n\n\nGreedy Best first search code: \n\n\ndef greedy(): \n\n  \t frontier = PriorityQueue() \n\n  \t frontier.put(start, 0) \n\n  \t came_from = {} \n\n  \t came_from[start] = None \n\n  \t while not frontier.empty(): \n\n  \t\t current = frontier.get() \n\n  \t\t if current == goal: \n\n  \t\t\t break \n\n  \t\t for next in graph.neighbors(current): \n\n  \t\t\t if next not in came_from: \n\n  \t\t\t\t priority = heuristic(goal,next) \n\n  \t\t\t\t frontier.put(next, priority) \n\n  \t\t\t\t came_from[next] = current  \n\n\nA* waits until the goal node is expanded to terminate. \n\n\nA * search is complete. Whether it is optimal relates to whether it is admissible/optimistic. \n\n\nProof of A star: suppose optimal path has cost B * and algo returns path with cost B > B *. There must be some node on optimal path that is unexpanded. \n\n\n\nIf g * (n) = cost of optimal path since start state, h * (n) = cost of optimal path to nearest goal: \n\n\n\n$f(n) > C*$ or n would have been expanded \n\n\n\n$f(n) = g(n) + h(n)$ by definition \n\n\n\n$f(n) = g*(n) + h(n)$ since n is on optimal path \n\n\n\n$f(n) \\leq g*(n) + h*(n)$ since admissibility \n\n\n\n$f(n) \\leq C*$ by definition \n\n\nAlternative (word based proof):\n\n\nLet A be optimal goal node, B be suboptimal goal node, claim that A will exit frontier before B. \n\n\nIf B is on frontier, and some ancestor n of A is on the frontier, we try to claim that n will be expanded before B. \n\n\n1. $f(n) \\leq f(A)$ \n\n\t\t - $f(n) \\leq g(A) = f(A)$ \n\n2. $f(A) < f(B)$ \n\n\t\t - $g(A) < g(B) \\implies f(A) < f(B)$ since h = 0 at goal\n3. so, n expands before B \n\n\t\t - $f(n) \\leq f(A) < f(B)$\n4. Since all ancestors of A expand before B, A expand before B.\n\n\n\nUniform cost search can be seen as case where W = 0 and A* is W = 1. Greedy is W = infinity. \n\n## Module 4 Definitions\n* **Unbounded cost search** - accepts quick solutions at any cost \n* **Bounded cost search** - find solution with cost less than constant C\n* **Bounded suboptimal search** - find solution guaranteed to be within a constant factor W of the optimal cost (e.g. weighted A*)\n* **Speedy search** - example of unbounded search and greedy, uses h(n) = number of actions required to reach goal regardless of cost\n* **A star search** - best first search using f(n) = g(n) + h(n)\n* **Heuristic function** - estimates cost of cheapest path from state at node n to the goal state\n* **Consistent heuristic** - for every node n and every successor n' we have $h(n) \\leq c(n, a, n') + h(n')$.\n* **Manhattan distance/ city block distance** - sum of distances from goal positions\n* **Effective branching factor** - branching factor that a uniform tree of depth d has s.t. it has N + 1 nodes\n* **Heuristic domination** - h1 dominates h2 if h2(n) >= h1(n) for any n. Better to use heuristic with higher values\n* **Metalevel state space** - captures the internal state of a program searching in an object-levelstate space\n* **Metalevel learning algorithm** - learn from missteps to avoid exploring unpromising paths, minimzingtotal cost\n* **Front to end search** - bidirectional search with heuristics estimating distance to goal/ initial\n* **Front-to-front search** - bidrectional search with heuristics estimating distance to the other frontier\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Three stances toward multi-agent environments: (1) consider in aggregate\\\n",
        " as an economy, (2) consider agents as part of env that makes env non-deterministic, (3) \\\n",
        " model agents with game-tree search. For each state we want to stop searching, we either \\\n",
        " use evaluation function as heuristic or average outcomes of many simulations of game. \\n\n",
        " For games move = action and position = state. Definition of game include: initial state,\\\n",
        " TO-MOVE(s), ACTIONS(s), RESULT(s,a), IS_TERMINAL(s), UTILITY(s, player). State space graph\\\n",
        " represent states and connections. We can superimpose search tree/ game tree. \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" If game has binary outocome we can use AND-OR search. Solution \\\n",
        "= solution for a nondeterministic planning problem, guaranteeing reaching terminal state \\\n",
        "regardless of what other does. \\n\n",
        "\n",
        "If games with multiple outcome scores we use minimax search. If opponent plays sub-optimally \\\n",
        "we may not always want to play minimax, preferring risky move to certain sub-par move.\\n\n",
        "\n",
        "Minimax algo: O(b^m) exponential complexity with m = max depth of tree and b = legal moves at each point\\\n",
        "Space complexity = O(bm) if all actions generated together or O(m) with backtracking. \\n\n",
        "\n",
        "For multi-player game, replace value of each node with vectors. Each players chooses \\\n",
        "vector with value higher for themselves. Alliances can emerge out of selfish behaviors. \\\n",
        "In positive sum vgames collaboration can also happen between 2.\\n\n",
        "\n",
        "We cannot eliminate exponent but can cut it in half. Alpha-beta pruning efffectiveness\\\n",
        " dependent on order of examination. Perfect alpha-beta pruning reduces runtime to \\\n",
        " $O(b^{(m/2)})$. Effective branching factor becomes $\\sqrt(b)$. Random move ordering runtime \\\n",
        " becomes $O(b^{(3m/4)})$. We cannot get perfrect ordering function, else we already have \\\n",
        " info to play the game.\\n\n",
        "\n",
        " Ways to improve move ordering/ search efficiency: (1) fnd killer moves using iterative deepending, \\\n",
        " (2) uses transposition table to capture redundant states, \\n\n",
        "\n",
        " Shannon's two strategies: Type A consider wide but shallow portion of tree, considers all \\\n",
        " moves up to certain depth then estimate the lowest level; Type B follows promising lines, deep but \\\n",
        " narrow search. Go problems are typically Type B, chess Type A. \\n\n",
        "\n",
        " AB pseudo-code: \\n\n",
        "\n",
        " \\t function MAX_VALUE(game, state, alpha, beta) returns (utility, move) pair: \\n\n",
        " \\t if state is terminal: return utility, null \\n\n",
        " \\t v = negative inf \\n\n",
        " \\t for each a in actions(state) do: \\n\n",
        " \\t\\t v2, a2 = MIN_VALUE(game, result(state, a), alpha, beta)\\n\n",
        " \\t\\t if v2 > t then:\\n\n",
        " \\t\\t\\t v, move = v2, a\\n\n",
        " \\t\\t\\t alpha = max(alpha, v)\\n\n",
        " \\t\\t if v >= beta then return v, move\\n\n",
        " \\t return v, move\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" We can apply evaluation function to nodes, and replace \\\n",
        "termination test with cutoff test. For non-terminal states, evaluation must be somewhere \\\n",
        "between utility of loss and utility of win (for the player) \\n\n",
        "\n",
        "Requirements for eval function: 1) does not take too long, 2) strongly correlated with \\\n",
        "winning. E.g. use features of the state to delineate several categories/ equivalent classes \\\n",
        "of states, with same value for all features. Any category have some states leading to wins \\\n",
        "draws. and losses. Eval function estimates proportional of states with win, draw, losses \\\n",
        "and calculate expected value. \\n\n",
        "\n",
        "Alternative to classes/categories: compute numerical contributions of each feature and combine. E.g. material value ]\n",
        "of chess pieces, transformed using a weighted linear function (with normalized weights). \\\n",
        "This assumes that contributions are independent. To remove assumption, we can use nonlinear \\\n",
        "combination of states. \\n\n",
        "\n",
        "To adapt alpha-beta algo, we need to keep track of depth/ use iterative deepening. \\\n",
        "Evaluation functions should be applied to quiescent positions: where no next move can \\\n",
        "wildly change evaluation. We can add quiescence search in cutoff test. \\n\n",
        "\n",
        "Also need to take into account horizon effect: when one can delay an opponent's move \\\n",
        "but not prevent it. To mitigate the effect we allow singular extensions, allowing \\\n",
        "beyond-depth moves that are clearly better than others. Usually will not add too much. \\n\n",
        "\n",
        "Forward pruning: prunes moves that do not look good. Type B: exchange risk for time. \\\n",
        "1) E.g. beam search:  consider only best moves. 2) E.g. PROBCUT: use statistics from \\\n",
        "history to reduce chance of pruning best moves, pruning nodes that are probably \\\n",
        "outside the (alpha, beta) range. 3) E.g. late move reduction,  assume that moves are \\\n",
        "well ordered, and reduce the search depth of nodes that come late. \\n\n",
        "\n",
        "Normal Minimax search for chess can look 5 plys, with alpha-beta, transposition table \\\n",
        "we have 14, and with better databases and computers we can go 30 ply. \\n\n",
        "\n",
        "For beginning and ending of games we can do table lookup instead of search. \\\n",
        "Computers can produce a policy, using retrograde minimax search: starting from endgames, \\\n",
        "go backwards to compute sure-win positions.\n",
        "  \"\"\"\n",
        "chapter5_5 = \"\"\" Exampel of stochastic games: backgammon. Roll two dies, then move \\\n",
        "and capture. Calculate expected value of a position/ expectiminimax value. \\\n",
        "Evaluation functions for stochastic games haave stricter requirements: they must \\\n",
        "have values that are positive linear transformation of the probability of winning. \\n\n",
        "\n",
        "Expectiminimax takes $O(b^m n^m)$ time, where n is the number of rolls/ chance events at each \\\n",
        "node. Pruning options are more limited: if we have bounds on the utility value of all outcomes \\\n",
        "then we can use it to yield a bound for the average/ expected utility for pruning. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" $P(RESULT(a) = s') = \\sum_s P(s) P(s' | s, a)$ \\n\n",
        "\n",
        "$Expected Utility = \\sum_s' P(RESULT(a) = s') U(s')$ \\n\n",
        "\n",
        "MEU principle formalizes \"doing the right thing\" but does not operationalize: \\\n",
        "still need to estimate probability of states thruogh learning, and compute P(RESULT(a)=s') \\\n",
        "using a causal model.  \"\"\"\n",
        "chapter16_2 = \"\"\" Constraints/axioms on rational preference relations: (1) orderability \\\n",
        "either two lotteries are indifferent or agent prefers one over other, (2) transitivity \\\n",
        ", (3) continuity: if B is between A and C in preference, there is some probability p \\\n",
        "s.t. agent will be indifferent between B for sure and A / C with probability \\\n",
        "(4) substitutability: If indifferent between A and B, then indifferent between two lotteries \\\n",
        "with only difference being A vs B, (5) Monotonicity: If A $\\succ$ B then agent prefers \\\n",
        "lottery with higher probability for A, (6) decomposability: Compound lotteries can \\\n",
        "be reduced to simpler ones\\n\n",
        "\n",
        "von Neumann & Morgenstern: Existence of Utility function. If agent's preference \\\n",
        "obeys axiom, then there is a function s.t. U(A) > U(B) iff A $\\succ$ B and U(A) = U(B) \\\n",
        "if $A \\sim B$. \"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" Utility of money is not directly proportional to monetary value.\\\n",
        "Value of first million is very high, while marginal value decreases. s shaped curve. \\\n",
        "A billionnaire thus more likely to take a risky but beneficial move than a stable one \\n\n",
        "\n",
        "Grayson study: utility of money almost exactly proportional to log of the amount. \\\n",
        "We typically have concave utility function for positive wealth (facing downwards),\\n\n",
        "\n",
        "People in the slope-decreasing part of utility curve will assign higher utility to \\\n",
        "a guaranteed Expected Monetary Value than a lottery. Risk-avrese agents. Risk-seeking agents \\\n",
        "show up in the negative part of the wealth utility curve. If the changes in wealth are \\\n",
        "small, curve will be nearly linear, and agent will be risk-neutral \\n\n",
        "\n",
        "Most rational action a = $argmax_a EU(a)$. Most of the time we can only estimate EU. \\\n",
        "Unbiased estimate: expected value of error is 0. Since we select action with highest \\\n",
        "EU estimate, we will have an optimistic bias/ optimizer's curse. Bias higher when we \\\n",
        "are choosing among more choices. If variance in utility estimate is high, what appears \\\n",
        "to be the best choice may not even be the best chioce: so make sure sample size is large \\\n",
        "enough for trials. We can avoid it by using a Bayesian model using a probability model \\\n",
        "of the error $P(EU_est | EU)$, updating EU based on our prior knowledge of it.\\\n",
        "\n",
        "Human preferences are predictably irrataional: there may be no utility function consistent with \\\n",
        "our choices. Possible reasons: (1) certainty effect (reduce computational burden, distrust stated probs\\\n",
        "accoutning for emotion) (2) Ellsberg paradox: people have ambiguity aversion, prefer \\\n",
        "known probability. (3) framing effect, (4) anchoring effect. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Hexpawn game (Martin Gardner): pawn moves diagonally to capture opponent \\\n",
        "or forward for one move. Illustrates game tree. Starts from level 0: MAX, then alternate\\\n",
        "Evaluation function assigns real number scores to each board position (node) without reference to \\\n",
        "path (i.e. based on static features). f(n) > 0 if MAX winning at n. Example: tic-tac-toe\\\n",
        "uses f(n) = 3 lengths open for MAX - MIN. \\n\n",
        "\n",
        "Evaluation functions for chess: 1) Turing: each piece has value, sum of Max - sum min. \\\n",
        "2) nowadays: weighted sum of positional features. \\n\n",
        "\n",
        "Minimax rule: assuem that opponent always play best move. If opponent player does not play \\\n",
        "optimally it still works. \\n\n",
        "\n",
        "Alpha beta pruning. Alpha = MAX's lower bound on its outcome. Beta: MIN's upper bound \\\n",
        "on its outcome. MAX will rule out anything worse than Alpha. So, when we are at max node, \\\n",
        "we stop evaluating branch if we get value >= Beta. Stop evaluate MIN branch if value \\\n",
        "<= Alpha. \\n\n",
        "\n",
        "Expectimax search: we look at average-case outcomes rather than worst-case (minimax) \\\n",
        "E.g. random opponents, explicit random games, failed actions. Add chance nodes \\\n",
        "like MIN nodes: when we are at chance node we compute expected utility. May stop at \\\n",
        "some level and estimate expectimax value. Can't really prune as easily. \\n\n",
        "\n",
        "Positive affine transformation (i.e. multiply by positive number then plus any number) \\ \n",
        "does not affect validity of utility function. When only preference ranking is needed, \\\n",
        "it is called a value function / ordinal utility function. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"alpha\" : \"the MAX nodes's current lower bound on MAX's outcome\",\n",
        "\"beta\" : \"the MIN node's current upper bound on MIN's outcome\",\n",
        "\"transpositions in games\": \"different move sequences resulitng in the same position\",\n",
        "\"minimax value\":\"utility of being in a state, assuming optimal decisions from both sides\\\n",
        "till end of game\",\n",
        "\"game tree\": \"search tree following all sequence of moves to a terminal state\",\n",
        "\"Backed-up value\" : \"Optimal value of a node's children\",    \n",
        "\"Random variable\": \"represents events with unknown outcome\", \n",
        "\"Probability distribution\" : \"assignment of weights to outcomes\",\n",
        "\"Expected value of function of random variables\" : \"average value weighted by \\\n",
        "probaility\",\n",
        "\"Objectivism/ frequentism\" : \"Probabilities are averages over repeated experiments. \\\n",
        "Based on new eveidence, which change the reference class. Inherently random events.\",\n",
        "\"Subjectivism/ Bayesianism\" : \"Probabilities are degrees of belief about unobserved variables\\\n",
        ". Learning probabilities and using evidence to updating beliefs.\",\n",
        "\"Goal based agents\": \"Binary distinction between good and bad states\",\n",
        "\"decision theoretic agent\" : \"assign continuous range of values to states\",\n",
        "\"utility function\" : \"assigns a single value representing agent's preference to a \\\n",
        "state\",\n",
        "\"Principle of Maximum expected utility (MEU)\": \"Rational agent should choose action \\\n",
        " that maximizes expected utility\",\n",
        "\"Justification of MEU\" : \"Agents who maximize an expected utility reflecting performance \\\n",
        "measure will achieve highest average performance score \",\n",
        "\"Lottery\" : \"a mapping between a set of outcomes/states/lotteries and probabilities \\\n",
        "with probs summing up to 1\",\n",
        "\"Lottery notation\" : \"$L = [p_1, S_1; p_2, S_2; ... ]$\",\n",
        "\"Preference notation\" : \"indifference: $A \\sim B$, preference A over B: $A \\succ B$ \",\n",
        "\"Expected utility of lottery\" : \"$U([p1, S1 ...]) = \\sum_i p_i U(S_i)$\",\n",
        "\"Prefernece elicitation\" : \"Figure out human's utility function by presenting choices to huamans\",\n",
        "\"Normalized utility\" : \"Utility scaling using 1 as best possible prize and 0 as worst\",\n",
        "\"Standard lottery\" : \"compare s vs L=[$p * best; (1-p) * worst$], utility of S will be \\\n",
        "p if indifferent\",\n",
        "\"Value of statistical life\" : \"$10 million, used by government agents to evaluate regulations\",\n",
        "\"Micromort\" : \"One in a million chance of death = driving car for 230 miles\",\n",
        "\"QALY\" : \"Quality adjusted life year, accouting for disability etc.\",\n",
        "\"Monotonic preference\" : \"Prefer more to less\",\n",
        "\"Certainty equivalent\" : \"value that one will accept instead of a lottery\",\n",
        "\"Insurance premium\" : \"EMV of lottery - certainty equivalent\",\n",
        "\"Order statistic\" : \"distributino of any particular ranked element of a sample\",\n",
        "\"Optimizer's curse\" : \"tendency for expected utility of best choice to be too high\",\n",
        "\"policy\" : \"mapping from possible states to the best move in the state\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b7d3a198-85dc-46d5-e4a7-47baafd01f3c"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Three stances toward multi-agent environments: (1) consider in aggregate as an economy, (2) consider agents as part of env that makes env non-deterministic, (3)  model agents with game-tree search. For each state we want to stop searching, we either  use evaluation function as heuristic or average outcomes of many simulations of game. \n\n For games move = action and position = state. Definition of game include: initial state, TO-MOVE(s), ACTIONS(s), RESULT(s,a), IS_TERMINAL(s), UTILITY(s, player). State space graph represent states and connections. We can superimpose search tree/ game tree. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n If game has binary outocome we can use AND-OR search. Solution = solution for a nondeterministic planning problem, guaranteeing reaching terminal state regardless of what other does. \n\n\nIf games with multiple outcome scores we use minimax search. If opponent plays sub-optimally we may not always want to play minimax, preferring risky move to certain sub-par move.\n\n\nMinimax algo: O(b^m) exponential complexity with m = max depth of tree and b = legal moves at each pointSpace complexity = O(bm) if all actions generated together or O(m) with backtracking. \n\n\nFor multi-player game, replace value of each node with vectors. Each players chooses vector with value higher for themselves. Alliances can emerge out of selfish behaviors. In positive sum vgames collaboration can also happen between 2.\n\n\nWe cannot eliminate exponent but can cut it in half. Alpha-beta pruning efffectiveness dependent on order of examination. Perfect alpha-beta pruning reduces runtime to  $O(b^{(m/2)})$. Effective branching factor becomes $\\sqrt(b)$. Random move ordering runtime  becomes $O(b^{(3m/4)})$. We cannot get perfrect ordering function, else we already have  info to play the game.\n\n\n Ways to improve move ordering/ search efficiency: (1) fnd killer moves using iterative deepending,  (2) uses transposition table to capture redundant states, \n\n\n Shannon's two strategies: Type A consider wide but shallow portion of tree, considers all  moves up to certain depth then estimate the lowest level; Type B follows promising lines, deep but  narrow search. Go problems are typically Type B, chess Type A. \n\n\n AB pseudo-code: \n\n\n \t function MAX_VALUE(game, state, alpha, beta) returns (utility, move) pair: \n\n \t if state is terminal: return utility, null \n\n \t v = negative inf \n\n \t for each a in actions(state) do: \n\n \t\t v2, a2 = MIN_VALUE(game, result(state, a), alpha, beta)\n\n \t\t if v2 > t then:\n\n \t\t\t v, move = v2, a\n\n \t\t\t alpha = max(alpha, v)\n\n \t\t if v >= beta then return v, move\n\n \t return v, move\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can apply evaluation function to nodes, and replace termination test with cutoff test. For non-terminal states, evaluation must be somewhere between utility of loss and utility of win (for the player) \n\n\nRequirements for eval function: 1) does not take too long, 2) strongly correlated with winning. E.g. use features of the state to delineate several categories/ equivalent classes of states, with same value for all features. Any category have some states leading to wins draws. and losses. Eval function estimates proportional of states with win, draw, losses and calculate expected value. \n\n\nAlternative to classes/categories: compute numerical contributions of each feature and combine. E.g. material value ]\nof chess pieces, transformed using a weighted linear function (with normalized weights). This assumes that contributions are independent. To remove assumption, we can use nonlinear combination of states. \n\n\nTo adapt alpha-beta algo, we need to keep track of depth/ use iterative deepening. Evaluation functions should be applied to quiescent positions: where no next move can wildly change evaluation. We can add quiescence search in cutoff test. \n\n\nAlso need to take into account horizon effect: when one can delay an opponent's move but not prevent it. To mitigate the effect we allow singular extensions, allowing beyond-depth moves that are clearly better than others. Usually will not add too much. \n\n\nForward pruning: prunes moves that do not look good. Type B: exchange risk for time. 1) E.g. beam search:  consider only best moves. 2) E.g. PROBCUT: use statistics from history to reduce chance of pruning best moves, pruning nodes that are probably outside the (alpha, beta) range. 3) E.g. late move reduction,  assume that moves are well ordered, and reduce the search depth of nodes that come late. \n\n\nNormal Minimax search for chess can look 5 plys, with alpha-beta, transposition table we have 14, and with better databases and computers we can go 30 ply. \n\n\nFor beginning and ending of games we can do table lookup instead of search. Computers can produce a policy, using retrograde minimax search: starting from endgames, go backwards to compute sure-win positions.\n  \n\n## AIMA Chapter 5.5 Stochastic Games\n Exampel of stochastic games: backgammon. Roll two dies, then move and capture. Calculate expected value of a position/ expectiminimax value. Evaluation functions for stochastic games haave stricter requirements: they must have values that are positive linear transformation of the probability of winning. \n\n\nExpectiminimax takes $O(b^m n^m)$ time, where n is the number of rolls/ chance events at each node. Pruning options are more limited: if we have bounds on the utility value of all outcomes then we can use it to yield a bound for the average/ expected utility for pruning. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(RESULT(a) = s') = \\sum_s P(s) P(s' | s, a)$ \n\n\n$Expected Utility = \\sum_s' P(RESULT(a) = s') U(s')$ \n\n\nMEU principle formalizes \"doing the right thing\" but does not operationalize: still need to estimate probability of states thruogh learning, and compute P(RESULT(a)=s') using a causal model.  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints/axioms on rational preference relations: (1) orderability either two lotteries are indifferent or agent prefers one over other, (2) transitivity , (3) continuity: if B is between A and C in preference, there is some probability p s.t. agent will be indifferent between B for sure and A / C with probability (4) substitutability: If indifferent between A and B, then indifferent between two lotteries with only difference being A vs B, (5) Monotonicity: If A $\\succ$ B then agent prefers lottery with higher probability for A, (6) decomposability: Compound lotteries can be reduced to simpler ones\n\n\nvon Neumann & Morgenstern: Existence of Utility function. If agent's preference obeys axiom, then there is a function s.t. U(A) > U(B) iff A $\\succ$ B and U(A) = U(B) if $A \\sim B$. \n\n## AIMA Chapter 16.3 Utility Functions\n Utility of money is not directly proportional to monetary value.Value of first million is very high, while marginal value decreases. s shaped curve. A billionnaire thus more likely to take a risky but beneficial move than a stable one \n\n\nGrayson study: utility of money almost exactly proportional to log of the amount. We typically have concave utility function for positive wealth (facing downwards),\n\n\nPeople in the slope-decreasing part of utility curve will assign higher utility to a guaranteed Expected Monetary Value than a lottery. Risk-avrese agents. Risk-seeking agents show up in the negative part of the wealth utility curve. If the changes in wealth are small, curve will be nearly linear, and agent will be risk-neutral \n\n\nMost rational action a = $argmax_a EU(a)$. Most of the time we can only estimate EU. Unbiased estimate: expected value of error is 0. Since we select action with highest EU estimate, we will have an optimistic bias/ optimizer's curse. Bias higher when we are choosing among more choices. If variance in utility estimate is high, what appears to be the best choice may not even be the best chioce: so make sure sample size is large enough for trials. We can avoid it by using a Bayesian model using a probability model of the error $P(EU_est | EU)$, updating EU based on our prior knowledge of it.\nHuman preferences are predictably irrataional: there may be no utility function consistent with our choices. Possible reasons: (1) certainty effect (reduce computational burden, distrust stated probsaccoutning for emotion) (2) Ellsberg paradox: people have ambiguity aversion, prefer known probability. (3) framing effect, (4) anchoring effect. \n\n## Module 5 Lecture Notes\n Hexpawn game (Martin Gardner): pawn moves diagonally to capture opponent or forward for one move. Illustrates game tree. Starts from level 0: MAX, then alternateEvaluation function assigns real number scores to each board position (node) without reference to path (i.e. based on static features). f(n) > 0 if MAX winning at n. Example: tic-tac-toeuses f(n) = 3 lengths open for MAX - MIN. \n\n\nEvaluation functions for chess: 1) Turing: each piece has value, sum of Max - sum min. 2) nowadays: weighted sum of positional features. \n\n\nMinimax rule: assuem that opponent always play best move. If opponent player does not play optimally it still works. \n\n\nAlpha beta pruning. Alpha = MAX's lower bound on its outcome. Beta: MIN's upper bound on its outcome. MAX will rule out anything worse than Alpha. So, when we are at max node, we stop evaluating branch if we get value >= Beta. Stop evaluate MIN branch if value <= Alpha. \n\n\nExpectimax search: we look at average-case outcomes rather than worst-case (minimax) E.g. random opponents, explicit random games, failed actions. Add chance nodes like MIN nodes: when we are at chance node we compute expected utility. May stop at some level and estimate expectimax value. Can't really prune as easily. \n\n\nPositive affine transformation (i.e. multiply by positive number then plus any number) \\ \ndoes not affect validity of utility function. When only preference ranking is needed, it is called a value function / ordinal utility function. \n\n\n## Module 5 Definitions\n* **Alpha** - the MAX nodes's current lower bound on MAX's outcome\n* **Beta** - the MIN node's current upper bound on MIN's outcome\n* **Transpositions in games** - different move sequences resulitng in the same position\n* **Minimax value** - utility of being in a state, assuming optimal decisions from both sidestill end of game\n* **Game tree** - search tree following all sequence of moves to a terminal state\n* **Backed-up value** - Optimal value of a node's children\n* **Random variable** - represents events with unknown outcome\n* **Probability distribution** - assignment of weights to outcomes\n* **Expected value of function of random variables** - average value weighted by probaility\n* **Objectivism/ frequentism** - Probabilities are averages over repeated experiments. Based on new eveidence, which change the reference class. Inherently random events.\n* **Subjectivism/ bayesianism** - Probabilities are degrees of belief about unobserved variables. Learning probabilities and using evidence to updating beliefs.\n* **Goal based agents** - Binary distinction between good and bad states\n* **Decision theoretic agent** - assign continuous range of values to states\n* **Utility function** - assigns a single value representing agent's preference to a state\n* **Principle of maximum expected utility (meu)** - Rational agent should choose action  that maximizes expected utility\n* **Justification of meu** - Agents who maximize an expected utility reflecting performance measure will achieve highest average performance score \n* **Lottery** - a mapping between a set of outcomes/states/lotteries and probabilities with probs summing up to 1\n* **Lottery notation** - $L = [p_1, S_1; p_2, S_2; ... ]$\n* **Preference notation** - indifference: $A \\sim B$, preference A over B: $A \\succ B$ \n* **Expected utility of lottery** - $U([p1, S1 ...]) = \\sum_i p_i U(S_i)$\n* **Prefernece elicitation** - Figure out human's utility function by presenting choices to huamans\n* **Normalized utility** - Utility scaling using 1 as best possible prize and 0 as worst\n* **Standard lottery** - compare s vs L=[$p * best; (1-p) * worst$], utility of S will be p if indifferent\n* **Value of statistical life** - $10 million, used by government agents to evaluate regulations\n* **Micromort** - One in a million chance of death = driving car for 230 miles\n* **Qaly** - Quality adjusted life year, accouting for disability etc.\n* **Monotonic preference** - Prefer more to less\n* **Certainty equivalent** - value that one will accept instead of a lottery\n* **Insurance premium** - EMV of lottery - certainty equivalent\n* **Order statistic** - distributino of any particular ranked element of a sample\n* **Optimizer's curse** - tendency for expected utility of best choice to be too high\n* **Policy** - mapping from possible states to the best move in the state\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 = \"\"\" For search algorithms the state is atomic/ black box without internal \\\n",
        "structure. Need domain specific information of transitions between states. CSP uses factored \\\n",
        "representation: variables with values, solved when vars are assigned consistent values. CSPs \\\n",
        "use structure of states to design general heuristics for solutions. \\n\n",
        "\n",
        "Each constraint in CSP is a pair <scope, relationship> where relationship can be binary,\\\n",
        "unary, etc. Partial assignment vs complete assignment. \\n\n",
        "\n",
        "CSP solving is generally NP-complete. \\n\n",
        "\n",
        "Examples of CSPs: map coloring, job scheduling (with precedence constraints, disjunctive \\\n",
        "constraints (no overlaps)), cryptarithmetic puzzles, linear programming (continuous domain, \\\n",
        "constraints are linear equalities and inequalities).\\n\n",
        "\n",
        "Infinite domains require implict constraints (e.g. T1 value bigger than T2) rather than explict \\\n",
        "relationship between value tuples. If we have linear constraints on integer variabless \\\n",
        "there are special algorithms. But if constraints are nonlinear, problem is undecidable.\\n\n",
        "\n",
        "Constraints can be represented in hypergraph: with n-ary constraints as n-ary nodes. \\n\n",
        "\n",
        "Every constraint with finite domain can be reduced into a set of binary constraints \\\n",
        ", so we can convert any CSP into binary constraint questions. We can also use \\\n",
        "dual graph transformation: one variable for each constraint, and one binary constraint for \\\n",
        "each constraint that share variables. Domain of the variables will be the set of tuples \\\n",
        "that satisfy the constraint. \\n\n",
        "\n",
        "Why global constraint is better than binary: (1) less error-prone, (2) we can design \\\n",
        "special-purpose inference algo for global constraints.  \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" Constraint propagation \\n\n",
        "If a graph with k nodes is strongly k consistent, then we can choose a value for 1st, \\\n",
        "choose one for second, and so on without worrying about inconsistency. Only have to search \\\n",
        "d values in domain and check consistency (n^2 time). Runtime is O(n^2 d).\\n\n",
        "\n",
        "However, to establish n-consistency we need exponential time and space in n.\\n\n",
        "\n",
        "Algorithm for global constraints: remove domains with just one value, then propagate until \\\n",
        "no single value domain. \\n\n",
        "\n",
        "Sometimes there are resource constraints or atmost constraints. We can do bounds propagation, \\\n",
        "using upper and lower bounds to represent domains. Check for bound-consistency: for every variable X, \\\n",
        "for both the lower and upper bound value of X, there is some value for Y that satisfy the constraint between \\\n",
        "X and Y. \\n\n",
        "\n",
        "Sudoku solvers: AC-3 for easier puzzles, PC-2 for slightly harder ones. More tricks e.g.\\\n",
        "naked triples: find three cells in a unit that share same subset of 3 numbers. Eliminate \\\n",
        "those numbers from other cells. \n",
        " \"\"\"\n",
        " \n",
        "chapter6_3 = \"\"\" Backtracking search\\n\n",
        "When inference is insufficient we alternate search with inference. Backtracking search \\\n",
        "uses DFS, has only one representation of the state, and modifies the representation instead of \\\n",
        "creating a new one. \\n\n",
        "\n",
        "Heuristics: \\n\n",
        "1) Minimum remaining values (MRV) \\n\n",
        "2) degree heuristic (select vars involved in largest num of constraints \\n\n",
        "3) least constraining value \\n\n",
        "\n",
        "Forward check: when X is assigned, check arc consistency with all neighbors \\n\n",
        "\n",
        "MAC (Maintaining arc consistency): AC-3 constraint propgation, with checks on whether \\\n",
        "any domains become empty. Strictly more powerful than forward checking. \\n\n",
        "\n",
        "Chronological backtracking: basic backtracking, revisiting most recent \\\n",
        "decision point.\\n\n",
        "\n",
        "Better alternative (backjumping) is to backtrack to a variable that rules out \\\n",
        "one of the values of the empty var. Set of assignments in conflict with a value of variable \\\n",
        "is called a conflict set. Bacjump to most recent assignment in conflict set. \\n\n",
        "\n",
        "Forward checking can supply the conflict set. Every branch eliminated by backjumping \\\n",
        "is also elimed by forward checking. So the two are redundant. \\n\n",
        "\n",
        "Strongly conflict set tracking (conflict directed backjumping) : track \\\n",
        "the set of variables that cause the empty var, and any subsequent vars to have no \\\n",
        "consistent solution. In this case, we establish conflict set with a prior node absorbing \\ \n",
        "the conflict set of a (failed) child node. \\n\n",
        "\n",
        "After backjumping to most recent node in conflict set we updating that node's \\\n",
        "conflict set : conflict_set(X_i) = conflict_set(X_i) union conflict_set(X_j) - {X_i} if X_j backjumps\n",
        "to Xi.\\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" Local saerch approach: start with complete assignment, randomly choose \\\n",
        "a conflicted variable, then change it to something with minimum number of conflicts \\n\n",
        "\n",
        "Min conflict heuristic local search has runtime independent of problem size for n-queens \\\n",
        "Local search works well for problems where solutions are densely distributed throughout state \\\n",
        "space. \\n\n",
        "\n",
        "Plateau saerch: allow side-way moves to another state with the same score, can help \\\n",
        "local saerch get out of plateaus (space with few solutions). Tabu search: keeping list of \\\n",
        "recently visited states and forbidding return, or simulated annealing, can help escape \\\n",
        "from plateaus \\n\n",
        "\n",
        "Constraint weighting focuses ssaerch on important constraints. We try to change variable/value \\\n",
        "such that lowest total weight will result. Then adjust weights by incrementing weight of \\\n",
        "violated constraints. Two benefits: (1) adding topography to platueas, and (2) adds learning. \\n\n",
        "\n",
        "Local search also can easily adapt to situations where the problem conditions change, e.g.\\\n",
        "schedule changes. \"\"\"\n",
        "\n",
        "\n",
        "chapter6_5 = \"\"\" We can improve efficiency by identifying independent subproblems. \\n\n",
        "\n",
        "Connected components on constraint graph indicates independent subproblems. When we \\\n",
        "decompose problems into $n/c$ subproblems, each takes $d^c$ work to solve, so total work is \\\n",
        "$O(d^c n/c)$, linear in n vs exponential O(d^n). \\n\n",
        "\n",
        "Slightly weaker than independent subproblems are tree-like CSPs, where any two vars are \\\n",
        "only connected by a path. Tree like CSPs can be solved in time linear to number of variables n, \\\n",
        "using directional arc consistency. A CSP is DAC iff every X_i is arc consistent with X_j for j > i.\\n\n",
        "\n",
        "Solution to tree-like CSP:\\n\n",
        "1) pick a var to be root, produce a topological sort\\n\n",
        "2) Make the graph directed arc-consistent in O(nd^2) times (check n edges, for each edge \\\n",
        "compare d domain values for two vars) \\n\n",
        "3) Go down list of variables and choose any value. Value cascade down and will be consistent \\n\n",
        "\n",
        "Cutset conditioning:\\n\n",
        "1. Choose a cycle cutset S such that after removing S, the graph becomes a tree\\n\n",
        "2. For each assignment to S that satisfy constraints in S:\\n\n",
        "\\t remove inconsistent values from remaining vars\\n\n",
        "\\t if remaining CSP has solution, return \\n\n",
        "\n",
        "Total run time is $O(d^c * (n-c)d^2)$, c = size of cycle cutset. IF the graph is almost, \\\n",
        "a tree, then will save a lot of time. However, finding the smallest cycle cutset is NP-hard, \\\n",
        "although there are approx algos. \\n\n",
        "\n",
        "Tree decomposition: \\n\n",
        "Transform graph into a tree where each node is a set of (potentially overlapping) variables \\n\n",
        "Three requirements for tree decomposition: \\n\n",
        "1. Every variable appears at least once in one of the tree nodes \\n\n",
        "2. If two variables are in same constraint, they must appear with that constraint in \\\n",
        "at least one tree node \\n\n",
        "3. If a varable appears in two tree nodes, it must appear in all node in between those two nodes\\n\n",
        "\n",
        "With the tree graph, we can solve in O(nd^2) time, but d will be larger (domain is \\\n",
        "set of tuples of values). So if the nodes have small variables, solving will be efficient. \\n\n",
        "\n",
        "Tree width = [size of largest node - 1] determines efficiency of tree decomposition. \\\n",
        "Tree width of a CSP graph is the minimum width all all tree decompositions. Finding the decomposition \\\n",
        "with minimum tree width is NP-hard. \\n\n",
        "\n",
        "With tree width w and the corresponding decomposition, we can solve problem \\\n",
        "in $O(nd^{w+1})$ time i.e. polynomial time when tree width is bounded. \\n\n",
        "\n",
        "Whenever we have cycle-cuteset of size c, there is also a tree width of size w < c+ 1, \\\n",
        "so tree decomposition is better time wise. But cycle cuteset requires just linear memory, while \\\n",
        "tree decomposition requires exponential memory in w. \n",
        "\n",
        "Value symmetry: If we have d colors for assignment, then for every \\\n",
        "consistent solution, there is d! solutions that we can get by just permuting colors \\\n",
        "We can include a symmetry-breaking constraint to reduce search space by d! . But in \\\n",
        "general it is NP-hard to eliminate all symmetry. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Two kinds of search: planning (find path) and identification \\\n",
        "(assign values to variables). In CSP we represent constraints with a declarative language \\\n",
        "and devise general purpose search algorithms to solve them. \\n\n",
        "\n",
        "CSP components: (1) finite set of variables, (2) non-empty domain of values for each varaible \\\n",
        "(3) finite set of constrants. A CSP state is an assignment of value to some/all variables.\\n\n",
        "\n",
        "Benefits of CSP: (1) easy to represent many problems, (2) know where to focus search, \\\n",
        "(3) can effectively prune off branches that violate constraints.\\n\n",
        "\n",
        "Use a constraint graph to represent CSPs. Variables can be discrete (with finite \\\n",
        "or infinite domains (e.g. integers)) or continuous (time). Constraints can be unary, \\\n",
        "binary, higher-order, or preference-based (soft) constraints. \\n\n",
        "\n",
        "CSP can be represented as a search problem, with constant path cost at each step, and \\\n",
        "value assignment as moves. Solutions have constant depth (num of variables). Rrepresented \\\n",
        "as such, the search tree has $n! d^n$ leaves (first-level branching factor nd, second-level \\\n",
        "(n-1)d, etc.), d being domain size and n being no. variables. However, since assignment is \\\n",
        "commutative, the effective leaves since is $d^n$. We do not have to consider \\\n",
        "all nodes at one step, just one, so branching factor = d. We can do a tree \\\n",
        "search rather than a graph search. \\n\n",
        "\n",
        "Basic DFS approach to CSP is backtracking. We can improve its efficiency by using \\\n",
        "heuristics: (1) most constrained variable (fewest legal values in domain) / minimum \\\n",
        "remaining values (MRV), (2) most constraining variable tie-breaker (impose most constraints) \\\n",
        "on remaining variebls, (3) least constraining value assignment, (4) forward checking \\\n",
        "(keeping track of legal values for unassigned vars, terminate when there are none) \\\n",
        "\n",
        "Forward check only propagates from assigned vars to unassigned ones. Constraint propagation \\\n",
        "uses inference to enforce local consistency, eliminating values that violate local \\\n",
        "consistency. \\n\n",
        "\n",
        "In checking arc consistency we change undirected edges to directed arcs (one pair between \\\n",
        "each pair of variables). Checking each arc takes $O(d^2)$ time. \\\n",
        "If x loses a value, we check neighbors of X. \\n\n",
        "\n",
        "Example of arc consistency: Waltz Algorithm. USes to interpret 3D drawings. \\\n",
        "Intersections as variables, constraints between adjacent intersections. Waltz/ \\\n",
        "Mackworth Algorithm: (1) assign every node with all possible values, (2) Repeat until \\\n",
        "values do not change, (3) Enforce arc consistency. \\n\n",
        "\n",
        "Improvements over Waltz-Mackworth: (1) only check those variables where its neighbors \\\n",
        "have lost a value. (2) No need to check Y if X loses a value because of Y, (3) if we remove X, \\\n",
        "it can only make Z inconsistent with X, so just check (z, x) is arc-consistent. \\n\n",
        "\n",
        "Improved algo - AC-3:\\n\n",
        "\\t def AC-3(csp):\\n\n",
        "\\t\\t while queue is not empty do:\\n\n",
        "\\t\\t\\t (X_i, X_j) = queue.pop()\\n\n",
        "\\t\\t\\t if REMOVE-INCONSISTENT(X_i, X_j):\\n\n",
        "\\t\\t\\t\\t for each X_k in Neighbors(X_i) - {X_j}:\\n\n",
        "\\t\\t\\t\\t\\t queue.add(X_k, X_i)\\n\n",
        "\n",
        "\\t def REMOVE_INCONSISTENT(X_i, X_j):\\n\n",
        "\\t\\t removed = false\\n\n",
        "\\t\\t for each x in DOMAIN[X_i]:\\n\n",
        "\\t\\t\\t if no value in DOMAIN[X_j] makes (x, y) satify constraints\\n\n",
        "\\t\\t\\t\\t delete x from DOMAIN[X_i]\\n\n",
        "\\t\\t\\t\\t removed = true\\n\n",
        "\\t\\t return removed \\n\n",
        "\n",
        "Total number of arcs: $2n(n-1)$, $O(n^2)$ \\n\n",
        "Checking each arc is $O(d^2)$ \\n\n",
        "Each arc can be inserted d times \\n\n",
        "Worst case runtime: $O(n^2d^3)$ \\n\n",
        "\n",
        "If constraint graph is planar (edges do not intersect), number of arcs will be linear in N, so \\\n",
        "time complexity is $O(nd^3)$ \\n\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Complete assignment\" : \"all variables assigned\",\n",
        "\"Consistent assignment\" : \"does not violate constraint\",\n",
        "\"Backtracking search\" : \"DFS for CSPs with single value assignments\",\n",
        "\"Xi Arc consistency with Xj\" : \"For every value in domain_i, there is some value in \\\n",
        "domain_j that satifies binary constraint between Xi and Xj\",\n",
        "\"global constraint\" : \"a constraint that can involve an arbitrary number of variables \\\n",
        "(but not necessarily all), e.g. Alldiff\",\n",
        "\"Node consistency\" : \"var is node consistent if all values in domain satisfy unary constraints\",\n",
        "\"Path consistency\" : \"Two vars are PC with K if every consistent assignment \\\n",
        "to IJ is consistent with a value in K \",\n",
        "\"k consistency\" : \"If there is consistent assignment to k-1 vars there is a consistent\\\n",
        "val for the kth var\",\n",
        "\"Strong k consistency\" : \"k-consistent, k-1 consistent, and so on\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "731ef671-f0ba-4a91-cd91-a2097eba32fd"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n For search algorithms the state is atomic/ black box without internal structure. Need domain specific information of transitions between states. CSP uses factored representation: variables with values, solved when vars are assigned consistent values. CSPs use structure of states to design general heuristics for solutions. \n\n\nEach constraint in CSP is a pair <scope, relationship> where relationship can be binary,unary, etc. Partial assignment vs complete assignment. \n\n\nCSP solving is generally NP-complete. \n\n\nExamples of CSPs: map coloring, job scheduling (with precedence constraints, disjunctive constraints (no overlaps)), cryptarithmetic puzzles, linear programming (continuous domain, constraints are linear equalities and inequalities).\n\n\nInfinite domains require implict constraints (e.g. T1 value bigger than T2) rather than explict relationship between value tuples. If we have linear constraints on integer variabless there are special algorithms. But if constraints are nonlinear, problem is undecidable.\n\n\nConstraints can be represented in hypergraph: with n-ary constraints as n-ary nodes. \n\n\nEvery constraint with finite domain can be reduced into a set of binary constraints , so we can convert any CSP into binary constraint questions. We can also use dual graph transformation: one variable for each constraint, and one binary constraint for each constraint that share variables. Domain of the variables will be the set of tuples that satisfy the constraint. \n\n\nWhy global constraint is better than binary: (1) less error-prone, (2) we can design special-purpose inference algo for global constraints.  \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation \n\nIf a graph with k nodes is strongly k consistent, then we can choose a value for 1st, choose one for second, and so on without worrying about inconsistency. Only have to search d values in domain and check consistency (n^2 time). Runtime is O(n^2 d).\n\n\nHowever, to establish n-consistency we need exponential time and space in n.\n\n\nAlgorithm for global constraints: remove domains with just one value, then propagate until no single value domain. \n\n\nSometimes there are resource constraints or atmost constraints. We can do bounds propagation, using upper and lower bounds to represent domains. Check for bound-consistency: for every variable X, for both the lower and upper bound value of X, there is some value for Y that satisfy the constraint between X and Y. \n\n\nSudoku solvers: AC-3 for easier puzzles, PC-2 for slightly harder ones. More tricks e.g.naked triples: find three cells in a unit that share same subset of 3 numbers. Eliminate those numbers from other cells. \n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking search\n\nWhen inference is insufficient we alternate search with inference. Backtracking search uses DFS, has only one representation of the state, and modifies the representation instead of creating a new one. \n\n\nHeuristics: \n\n1) Minimum remaining values (MRV) \n\n2) degree heuristic (select vars involved in largest num of constraints \n\n3) least constraining value \n\n\nForward check: when X is assigned, check arc consistency with all neighbors \n\n\nMAC (Maintaining arc consistency): AC-3 constraint propgation, with checks on whether any domains become empty. Strictly more powerful than forward checking. \n\n\nChronological backtracking: basic backtracking, revisiting most recent decision point.\n\n\nBetter alternative (backjumping) is to backtrack to a variable that rules out one of the values of the empty var. Set of assignments in conflict with a value of variable is called a conflict set. Bacjump to most recent assignment in conflict set. \n\n\nForward checking can supply the conflict set. Every branch eliminated by backjumping is also elimed by forward checking. So the two are redundant. \n\n\nStrongly conflict set tracking (conflict directed backjumping) : track the set of variables that cause the empty var, and any subsequent vars to have no consistent solution. In this case, we establish conflict set with a prior node absorbing \\ \nthe conflict set of a (failed) child node. \n\n\nAfter backjumping to most recent node in conflict set we updating that node's conflict set : conflict_set(X_i) = conflict_set(X_i) union conflict_set(X_j) - {X_i} if X_j backjumps\nto Xi.\n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local saerch approach: start with complete assignment, randomly choose a conflicted variable, then change it to something with minimum number of conflicts \n\n\nMin conflict heuristic local search has runtime independent of problem size for n-queens Local search works well for problems where solutions are densely distributed throughout state space. \n\n\nPlateau saerch: allow side-way moves to another state with the same score, can help local saerch get out of plateaus (space with few solutions). Tabu search: keeping list of recently visited states and forbidding return, or simulated annealing, can help escape from plateaus \n\n\nConstraint weighting focuses ssaerch on important constraints. We try to change variable/value such that lowest total weight will result. Then adjust weights by incrementing weight of violated constraints. Two benefits: (1) adding topography to platueas, and (2) adds learning. \n\n\nLocal search also can easily adapt to situations where the problem conditions change, e.g.schedule changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can improve efficiency by identifying independent subproblems. \n\n\nConnected components on constraint graph indicates independent subproblems. When we decompose problems into $n/c$ subproblems, each takes $d^c$ work to solve, so total work is $O(d^c n/c)$, linear in n vs exponential O(d^n). \n\n\nSlightly weaker than independent subproblems are tree-like CSPs, where any two vars are only connected by a path. Tree like CSPs can be solved in time linear to number of variables n, using directional arc consistency. A CSP is DAC iff every X_i is arc consistent with X_j for j > i.\n\n\nSolution to tree-like CSP:\n\n1) pick a var to be root, produce a topological sort\n\n2) Make the graph directed arc-consistent in O(nd^2) times (check n edges, for each edge compare d domain values for two vars) \n\n3) Go down list of variables and choose any value. Value cascade down and will be consistent \n\n\nCutset conditioning:\n\n1. Choose a cycle cutset S such that after removing S, the graph becomes a tree\n\n2. For each assignment to S that satisfy constraints in S:\n\n\t remove inconsistent values from remaining vars\n\n\t if remaining CSP has solution, return \n\n\nTotal run time is $O(d^c * (n-c)d^2)$, c = size of cycle cutset. IF the graph is almost, a tree, then will save a lot of time. However, finding the smallest cycle cutset is NP-hard, although there are approx algos. \n\n\nTree decomposition: \n\nTransform graph into a tree where each node is a set of (potentially overlapping) variables \n\nThree requirements for tree decomposition: \n\n1. Every variable appears at least once in one of the tree nodes \n\n2. If two variables are in same constraint, they must appear with that constraint in at least one tree node \n\n3. If a varable appears in two tree nodes, it must appear in all node in between those two nodes\n\n\nWith the tree graph, we can solve in O(nd^2) time, but d will be larger (domain is set of tuples of values). So if the nodes have small variables, solving will be efficient. \n\n\nTree width = [size of largest node - 1] determines efficiency of tree decomposition. Tree width of a CSP graph is the minimum width all all tree decompositions. Finding the decomposition with minimum tree width is NP-hard. \n\n\nWith tree width w and the corresponding decomposition, we can solve problem in $O(nd^{w+1})$ time i.e. polynomial time when tree width is bounded. \n\n\nWhenever we have cycle-cuteset of size c, there is also a tree width of size w < c+ 1, so tree decomposition is better time wise. But cycle cuteset requires just linear memory, while tree decomposition requires exponential memory in w. \n\nValue symmetry: If we have d colors for assignment, then for every consistent solution, there is d! solutions that we can get by just permuting colors We can include a symmetry-breaking constraint to reduce search space by d! . But in general it is NP-hard to eliminate all symmetry. \n\n\n## Module 6 Lecture Notes\n Two kinds of search: planning (find path) and identification (assign values to variables). In CSP we represent constraints with a declarative language and devise general purpose search algorithms to solve them. \n\n\nCSP components: (1) finite set of variables, (2) non-empty domain of values for each varaible (3) finite set of constrants. A CSP state is an assignment of value to some/all variables.\n\n\nBenefits of CSP: (1) easy to represent many problems, (2) know where to focus search, (3) can effectively prune off branches that violate constraints.\n\n\nUse a constraint graph to represent CSPs. Variables can be discrete (with finite or infinite domains (e.g. integers)) or continuous (time). Constraints can be unary, binary, higher-order, or preference-based (soft) constraints. \n\n\nCSP can be represented as a search problem, with constant path cost at each step, and value assignment as moves. Solutions have constant depth (num of variables). Rrepresented as such, the search tree has $n! d^n$ leaves (first-level branching factor nd, second-level (n-1)d, etc.), d being domain size and n being no. variables. However, since assignment is commutative, the effective leaves since is $d^n$. We do not have to consider all nodes at one step, just one, so branching factor = d. We can do a tree search rather than a graph search. \n\n\nBasic DFS approach to CSP is backtracking. We can improve its efficiency by using heuristics: (1) most constrained variable (fewest legal values in domain) / minimum remaining values (MRV), (2) most constraining variable tie-breaker (impose most constraints) on remaining variebls, (3) least constraining value assignment, (4) forward checking (keeping track of legal values for unassigned vars, terminate when there are none) \nForward check only propagates from assigned vars to unassigned ones. Constraint propagation uses inference to enforce local consistency, eliminating values that violate local consistency. \n\n\nIn checking arc consistency we change undirected edges to directed arcs (one pair between each pair of variables). Checking each arc takes $O(d^2)$ time. If x loses a value, we check neighbors of X. \n\n\nExample of arc consistency: Waltz Algorithm. USes to interpret 3D drawings. Intersections as variables, constraints between adjacent intersections. Waltz/ Mackworth Algorithm: (1) assign every node with all possible values, (2) Repeat until values do not change, (3) Enforce arc consistency. \n\n\nImprovements over Waltz-Mackworth: (1) only check those variables where its neighbors have lost a value. (2) No need to check Y if X loses a value because of Y, (3) if we remove X, it can only make Z inconsistent with X, so just check (z, x) is arc-consistent. \n\n\nImproved algo - AC-3:\n\n\t def AC-3(csp):\n\n\t\t while queue is not empty do:\n\n\t\t\t (X_i, X_j) = queue.pop()\n\n\t\t\t if REMOVE-INCONSISTENT(X_i, X_j):\n\n\t\t\t\t for each X_k in Neighbors(X_i) - {X_j}:\n\n\t\t\t\t\t queue.add(X_k, X_i)\n\n\n\t def REMOVE_INCONSISTENT(X_i, X_j):\n\n\t\t removed = false\n\n\t\t for each x in DOMAIN[X_i]:\n\n\t\t\t if no value in DOMAIN[X_j] makes (x, y) satify constraints\n\n\t\t\t\t delete x from DOMAIN[X_i]\n\n\t\t\t\t removed = true\n\n\t\t return removed \n\n\nTotal number of arcs: $2n(n-1)$, $O(n^2)$ \n\nChecking each arc is $O(d^2)$ \n\nEach arc can be inserted d times \n\nWorst case runtime: $O(n^2d^3)$ \n\n\nIf constraint graph is planar (edges do not intersect), number of arcs will be linear in N, so time complexity is $O(nd^3)$ \n\n  \n\n## Module 6 Definitions\n* **Complete assignment** - all variables assigned\n* **Consistent assignment** - does not violate constraint\n* **Backtracking search** - DFS for CSPs with single value assignments\n* **Xi arc consistency with xj** - For every value in domain_i, there is some value in domain_j that satifies binary constraint between Xi and Xj\n* **Global constraint** - a constraint that can involve an arbitrary number of variables (but not necessarily all), e.g. Alldiff\n* **Node consistency** - var is node consistent if all values in domain satisfy unary constraints\n* **Path consistency** - Two vars are PC with K if every consistent assignment to IJ is consistent with a value in K \n* **K consistency** - If there is consistent assignment to k-1 vars there is a consistentval for the kth var\n* **Strong k consistency** - k-consistent, k-1 consistent, and so on\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 = \"\"\" Knowledge based agent program: \\n\n",
        "\\t def KB-agent(percept): \\n\n",
        "\\t\\t TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))\\n\n",
        "\\t\\t action = ASK(KB, MAKE-ACTION-QUERY(t))\\n\n",
        "\\t\\t TELL(KB, MAKE-ACTION-SENTENCE(action, t))\\n\n",
        "\\t\\t t = t+1\\n\n",
        "\\t\\t return action \\n\n",
        "\n",
        "includes a TELL action that informs \\\n",
        "the knowledge base of percepts, and a ASKS action that queries a rational action.\\\n",
        "MAKE-PERCEPT sentence builds a sentence about percept, MAKE-ACTION-QUERY builds a sentence \\\n",
        "to ask appropriate question at time t, MAKE-ACTION-SENTENCE asserts that action is executed. \\n\n",
        "\n",
        "Knowledge level specifies what the agent knows and what its goals are, while implementation \\\n",
        "level implements it. Analysis of knowledge level is independent of implementation. \\n\n",
        "\n",
        "Declarative approach to system building proceed by telling agents what to do. Procedural \\\n",
        "approach encodes behaviors directly. Successful agents combine both. \"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" Wumpus world (with gold as goal instead of rescuing). Actions are going \\\n",
        "forward, turing left or turning right. Sense stench, breeze, glitter, bump, scream, represented \\\n",
        "as a list of current percepts.  \"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\" Modeling checking inference algorithm: examines whether M(KB) is subset of M(a) \\n\n",
        "\n",
        "Grounding is the connection between the world and logical reasonning. Agent's sensor creates the \\\n",
        "connection by telling it what happens in the real world. Prodcues learning rules.  \"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" TT-entails algorithm: recursive enumeration of assignments to symbols. Sound \\\n",
        "since it implements entailment, and completes since it always terminates. \\n\n",
        "\n",
        "\\t def TT-Entails(KB, a):\\n\n",
        "\\t\\t symbols = list of proposition symbols in KB and a\\n\n",
        "\\t\\t return TT-CHECK-ALL(KB, A=a, symbols, {})\\n\n",
        "\n",
        "\\t def TT-CHECK-ALL(KB, a, symbols, model):\\n\n",
        "\\t\\t if symbols.empty() then:\\n\n",
        "\\t\\t\\t if PL-TRUE(KB, model) then return PL-TRUE(A, model)\\n\n",
        "\\t\\t\\t else return true \\n\n",
        "\\t\\t else \\n\n",
        "\\t\\t\\t p = symbols.first()\\n\n",
        "\\t\\t\\t rest = symbols.rest()\\n\n",
        "\\t\\t\\t return(TT-CHECK-ALL(KB, a, rest, model union {P = true}) and \\n\n",
        "\\t\\t\\t TT-CHECK-ALL(KB, a, rest, model union {P = false})) \\n\n",
        "\n",
        "Time complexity is O(2^n) when there are n symbols in KB and a (since there are 2^n) \\\n",
        "possible models. Space complexity is just O(n) \\n\n",
        "\n",
        "Propositional entailment is co-NP-complete: every known inference algo has worst-case \\\n",
        "complexity that is exponential. \"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" Proof that resolution is complete, or the ground resolution theorem: \\\n",
        "if a set of clauses is unsatifiable, then resolution closure contains the empty clause \\n\n",
        "\n",
        "Resoution closure RC(S) = set of all clauses that can be derived by applying resoluton \\\n",
        "to clauses in S. S must be finite, so Resolution always terminates. \\n\n",
        "\n",
        "We prove by contrapositive: if RC(S) does not contain empty clause then S is satisfiable. \\\n",
        "We construct a model for S with truth values t1, t2 ...., assign false to ti if and only if \\\n",
        "a clause contains -Pi and all other literals are false. Otherwise assign true. \\ \n",
        "We can show that the assignment is a model of S, by assuming (to the contrary) that at some stage i \\\n",
        "we first see a false clause. Then the clause would like like either (f or f or f or Pi) or (f or f or f or -Pi) \\\n",
        "and both of them have to be in RC(s). But if both are present, then the resolvent will be already falsfied at \\\n",
        "a prior stage, which yields a contradiction. \\n\n",
        "\n",
        "We can use AND-OR graph to illustrate forward chaining. We start from known facts \\\n",
        "then propagates thorugh the graph. Forward chaining is sound because of modus ponens. \\\n",
        "COmplete beacuse at the end, the inferred table will have true for all symbols inferred \\n\n",
        "  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Knowledge-based agents: uses reasoning on internal \\\n",
        "representation of messages (which are non-atomic). Have knowledge base (KB) with \\\n",
        "a set of sentences written in a knowledge representation language. Two kinds of setences: \\\n",
        "(1) axioms and (2) derived sentences \\n\n",
        "Example - Wampa world. 4 times 4 grid with 20% probability of pit. -1 point for each \\\n",
        "action, -10 for using fire. Perceives stench (near wampa), breeze (pit), bump (wall), \\\n",
        "scream (killing wampa). World is deterministic, discrete, static, single-agent, sequential \\\n",
        "partially observable.\\n\n",
        "\n",
        "Set of all models of a = M(a). \\n\n",
        "\n",
        "Entailment is the idea that a follows logically from b. $a \\models b$ iff $M(a) \\subset M(b).$\\\n",
        "i.e. a is more specific than b. \\n\n",
        "\n",
        "Inference is the process of using entailment to draw conclusions. KB single-turnstile_i a = \\\n",
        "a is derived from KB by i.\\n\n",
        "\n",
        "Propositional logic uses single symbols to represent atomic sentences that can be true or false. \\\n",
        "Complex sentences = atomic sentences + Logical connectives. \\n\n",
        "\n",
        "An inference algorithm is sound if it only derives entailed sentences. Complete if it \\\n",
        "can derive all entailed sentences. \\n\n",
        "\n",
        "$a \\equiv b$ iff they are true in the same set of models, and iff they entail each other. \\n\n",
        "\n",
        "Inference rules: conditions on top and conclusion belwo. Logical equivalence rules can all \\\n",
        "be rewritten as inference rules. \\n\n",
        "\n",
        "We can use search algorithms to find proofs. Initial state = KB. Actions are applications of \\\n",
        "inference rules, results are additional of sentences. Goal state = state where KB contains conclusion. \\n\n",
        "\n",
        "Logical rules: \\n\n",
        "\\t Associativity of $\\lor$: ((a $\\lor$ b) $\\lor$ y ) $\\equiv$ (a $\\lor$ (B $\\lor$ Y))\\n\n",
        "\\t Associativity of $\\wedge$: ((a $\\wedge$ b) $\\wedge$ y ) $\\equiv$ (a $\\wedge$ (B $\\wedge$ Y))\\n\n",
        "\\t contraposition: a $\\implies$ b $\\equiv$ -b $\\implies$ -a \\n\n",
        "\\t implication elim: a $\\implies$ b $\\equiv$ -a $\\lor$ b \\n\n",
        "\\t distributivity of $\\lor$ over $\\wedge$: (a $\\lor$ (b $\\wedge$ y)) $\\equiv$ (a  $\\lor$ b) $\\wedge$ (a  $\\lor$ y)\\n\n",
        "\\t distributivity of $\\wedge$ over $\\lor$: (a $\\wedge$ (b $\\lor$ y)) $\\equiv$ (a  $\\wedge$ b) $\\lor$ (a  $\\wedge$ y)\\n\n",
        "\n",
        "Monotonicity impllies soundness, set of entailed sentences can only increase. \\n\n",
        "\n",
        "Resoluton rule gives a complete inference algorithm when paired with any complete search \\\n",
        "algorithm. Idea: We can eliminate a literal in disjunctino and the negative of the same literal in \\\n",
        "conjunction. Unit resolution: If we have (l1 $\\lor$ l2, ..., lk) and -lk, we can eliminate lk and -lk. \\\n",
        "Only applies to clauses, i.e. disjunction of literals. \\n\n",
        "\n",
        "Every sentence can be reformulated as conjunction of clauses, thus applicable for resolution. \\\n",
        "Conjunctive normal form: start by eliminating implications, then move negative sign inwards. \\\n",
        "Application distributivity of $\\lor$ over $\\wedge$. \\n\n",
        "\n",
        "Proof by resolution: To show $KB \\models a$ we show that $KB \\wedge a$ is unsatisifiable. \\\n",
        "Convert $KB \\wedge a$ to CNF, applies resolution rule, continues until either (1) no new clause can be \\\n",
        "added (i.e. KB does not entail a), or (2) two (unit) clauses resolve to give empty clause (i.e. KB entails a). \\n\n",
        "\n",
        "Resolution algo: \\n\n",
        "\\t def resolution(KB, a) returns true or false: \\n\n",
        "\\t\\t clauses = CNF clauses of KB $\\wedge$ -a \\n\n",
        "\\t\\t new = set()\\n\n",
        "\\t\\t while true do:\\n\n",
        "\\t\\t\\t for each pair of clauses:\\n\n",
        "\\t\\t\\t\\t resolvents = PL-RESOLVE(pair)\\n\n",
        "\\t\\t\\t\\t if resolvents contain empty clause return true\\n\n",
        "\\t\\t\\t\\t new = new union resolvents\\n\n",
        "\\t\\t\\t if new $\\subset$ clauses return false \\n\n",
        "\\t\\t\\t clauses = clauses union new \\n\n",
        "\n",
        "We can apply more efficient inference algos to KBs in more restrictive forms: e.g. horn and definite clauses. \\\n",
        "Horn clauses are close under resolution: resolving horn clause yields horn clause. \\\n",
        "Every definite clase can turn into an implication, where premise = conjunction of positive literals (from negative \\\n",
        "literals in original clause) and conclusion = positive literal. E.g. -L $\\lor$ -B $\\lor$ A $\\equiv$ L $\\wedge$ B $\\implies$ A.\\n\n",
        "\n",
        "Inference with horn clauses: use forward and backward chaining. Can be done in linear time \\\n",
        "w.r.t size of the KB. Forward chaining is data-driven reasoning: add premises incrementally. \\\n",
        "Backward chaining is goal-directed reasoning: find implications in KB with conclusion = the query. \\\n",
        "Try to prove all the premises in one of those implications. \\n\n",
        "\n",
        "Forward chaining algo: \\n\n",
        "\\t def FC(KB, q):\\n\n",
        "\\t\\t count = table where count[c] = number of symbols in clause c's premise\\n\n",
        "\\t\\t inferred = table where inferred[c] is false initially for all\\n\n",
        "\\t\\t queue = a queue of symbols, initially true symbols in KB\\n\n",
        "\\t\\t while queue is not empty:\\n\n",
        "\\t\\t\\t p = queue.pop()\\n\n",
        "\\t\\t\\t if p = q return true \\n\n",
        "\\t\\t\\t if inferred[p] = false:\\n\n",
        "\\t\\t\\t\\t inferred[p] = true\\n\n",
        "\\t\\t\\t\\t for each clause c in KB where p is the premise of c:\\n\n",
        "\\t\\t\\t\\t\\t count[c] -= 1\\n\n",
        "\\t\\t\\t\\t\\t if count[c] = 0 then add c.concluson to queue\\n\n",
        "\\t\\t return false \\n\n",
        "\n",
        "\n",
        "\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Syntax\" : \"Specifies the well-formed sentences\", \n",
        "\"semantics\" : \"defines the truth of each sentence w.r.t a possible world/ model\",\n",
        "\"Models\" : \"Math abstracts with a fixed set of truth-values for each sentence\",\n",
        "\"Satisfaction\" : \"model m satisfies a if a is true in m\",\n",
        "\"Monotonicity\" : \"If $KB \\models a$ then $KB \\wedge B \\models a$. We can add to KB without \\\n",
        "invalidating anything \",\n",
        "\"horn clause\" : \"disjunction of litearls where at most one clause is positive, incl. no positives\",\n",
        "\"definite clasue\" : \"disjunction of literals where exactly one is positive\",\n",
        "\"theorem proving\" : \"applying rules of inference to sentences in knowledge base to prove sentence\\\n",
        " without models\", \n",
        " \"Validity\" : \"sentence is valid if it is true in all models, aka tautologies\",\n",
        " \"deduction theorem\" : \"a $\\models$ b iff sentence a $\\imples$ b is valid\", \n",
        " \"satisfiability\" : \"sentence is satifiable if it is true in some model\",\n",
        " \"And-elimination\" : \"we can derive any cojuncts from a conjunction\", \n",
        " \"factoring\" : \"removal of repeated literals in a clause\",\n",
        " \"goal clauses\" : \"clauses with no positive literals\",\n",
        " \"k-CNF sentence\" : \"a CNF sentence where each clause has at most k literals\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8df6342e-d0d8-4bc6-b3f1-d82f08c15ad8"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge based agent program: \n\n\t def KB-agent(percept): \n\n\t\t TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))\n\n\t\t action = ASK(KB, MAKE-ACTION-QUERY(t))\n\n\t\t TELL(KB, MAKE-ACTION-SENTENCE(action, t))\n\n\t\t t = t+1\n\n\t\t return action \n\n\nincludes a TELL action that informs the knowledge base of percepts, and a ASKS action that queries a rational action.MAKE-PERCEPT sentence builds a sentence about percept, MAKE-ACTION-QUERY builds a sentence to ask appropriate question at time t, MAKE-ACTION-SENTENCE asserts that action is executed. \n\n\nKnowledge level specifies what the agent knows and what its goals are, while implementation level implements it. Analysis of knowledge level is independent of implementation. \n\n\nDeclarative approach to system building proceed by telling agents what to do. Procedural approach encodes behaviors directly. Successful agents combine both. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world (with gold as goal instead of rescuing). Actions are going forward, turing left or turning right. Sense stench, breeze, glitter, bump, scream, represented as a list of current percepts.  \n\n## AIMA Chapter 7.3 Logic\n Modeling checking inference algorithm: examines whether M(KB) is subset of M(a) \n\n\nGrounding is the connection between the world and logical reasonning. Agent's sensor creates the connection by telling it what happens in the real world. Prodcues learning rules.  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n TT-entails algorithm: recursive enumeration of assignments to symbols. Sound since it implements entailment, and completes since it always terminates. \n\n\n\t def TT-Entails(KB, a):\n\n\t\t symbols = list of proposition symbols in KB and a\n\n\t\t return TT-CHECK-ALL(KB, A=a, symbols, {})\n\n\n\t def TT-CHECK-ALL(KB, a, symbols, model):\n\n\t\t if symbols.empty() then:\n\n\t\t\t if PL-TRUE(KB, model) then return PL-TRUE(A, model)\n\n\t\t\t else return true \n\n\t\t else \n\n\t\t\t p = symbols.first()\n\n\t\t\t rest = symbols.rest()\n\n\t\t\t return(TT-CHECK-ALL(KB, a, rest, model union {P = true}) and \n\n\t\t\t TT-CHECK-ALL(KB, a, rest, model union {P = false})) \n\n\nTime complexity is O(2^n) when there are n symbols in KB and a (since there are 2^n) possible models. Space complexity is just O(n) \n\n\nPropositional entailment is co-NP-complete: every known inference algo has worst-case complexity that is exponential. \n\n## AIMA 7.5 Propositional Theorem Proving\n Proof that resolution is complete, or the ground resolution theorem: if a set of clauses is unsatifiable, then resolution closure contains the empty clause \n\n\nResoution closure RC(S) = set of all clauses that can be derived by applying resoluton to clauses in S. S must be finite, so Resolution always terminates. \n\n\nWe prove by contrapositive: if RC(S) does not contain empty clause then S is satisfiable. We construct a model for S with truth values t1, t2 ...., assign false to ti if and only if a clause contains -Pi and all other literals are false. Otherwise assign true. \\ \nWe can show that the assignment is a model of S, by assuming (to the contrary) that at some stage i we first see a false clause. Then the clause would like like either (f or f or f or Pi) or (f or f or f or -Pi) and both of them have to be in RC(s). But if both are present, then the resolvent will be already falsfied at a prior stage, which yields a contradiction. \n\n\nWe can use AND-OR graph to illustrate forward chaining. We start from known facts then propagates thorugh the graph. Forward chaining is sound because of modus ponens. COmplete beacuse at the end, the inferred table will have true for all symbols inferred \n\n  \n\n## Module 7 Lecture Notes\n Knowledge-based agents: uses reasoning on internal representation of messages (which are non-atomic). Have knowledge base (KB) with a set of sentences written in a knowledge representation language. Two kinds of setences: (1) axioms and (2) derived sentences \n\nExample - Wampa world. 4 times 4 grid with 20% probability of pit. -1 point for each action, -10 for using fire. Perceives stench (near wampa), breeze (pit), bump (wall), scream (killing wampa). World is deterministic, discrete, static, single-agent, sequential partially observable.\n\n\nSet of all models of a = M(a). \n\n\nEntailment is the idea that a follows logically from b. $a \\models b$ iff $M(a) \\subset M(b).$i.e. a is more specific than b. \n\n\nInference is the process of using entailment to draw conclusions. KB single-turnstile_i a = a is derived from KB by i.\n\n\nPropositional logic uses single symbols to represent atomic sentences that can be true or false. Complex sentences = atomic sentences + Logical connectives. \n\n\nAn inference algorithm is sound if it only derives entailed sentences. Complete if it can derive all entailed sentences. \n\n\n$a \\equiv b$ iff they are true in the same set of models, and iff they entail each other. \n\n\nInference rules: conditions on top and conclusion belwo. Logical equivalence rules can all be rewritten as inference rules. \n\n\nWe can use search algorithms to find proofs. Initial state = KB. Actions are applications of inference rules, results are additional of sentences. Goal state = state where KB contains conclusion. \n\n\nLogical rules: \n\n\t Associativity of $\\lor$: ((a $\\lor$ b) $\\lor$ y ) $\\equiv$ (a $\\lor$ (B $\\lor$ Y))\n\n\t Associativity of $\\wedge$: ((a $\\wedge$ b) $\\wedge$ y ) $\\equiv$ (a $\\wedge$ (B $\\wedge$ Y))\n\n\t contraposition: a $\\implies$ b $\\equiv$ -b $\\implies$ -a \n\n\t implication elim: a $\\implies$ b $\\equiv$ -a $\\lor$ b \n\n\t distributivity of $\\lor$ over $\\wedge$: (a $\\lor$ (b $\\wedge$ y)) $\\equiv$ (a  $\\lor$ b) $\\wedge$ (a  $\\lor$ y)\n\n\t distributivity of $\\wedge$ over $\\lor$: (a $\\wedge$ (b $\\lor$ y)) $\\equiv$ (a  $\\wedge$ b) $\\lor$ (a  $\\wedge$ y)\n\n\nMonotonicity impllies soundness, set of entailed sentences can only increase. \n\n\nResoluton rule gives a complete inference algorithm when paired with any complete search algorithm. Idea: We can eliminate a literal in disjunctino and the negative of the same literal in conjunction. Unit resolution: If we have (l1 $\\lor$ l2, ..., lk) and -lk, we can eliminate lk and -lk. Only applies to clauses, i.e. disjunction of literals. \n\n\nEvery sentence can be reformulated as conjunction of clauses, thus applicable for resolution. Conjunctive normal form: start by eliminating implications, then move negative sign inwards. Application distributivity of $\\lor$ over $\\wedge$. \n\n\nProof by resolution: To show $KB \\models a$ we show that $KB \\wedge a$ is unsatisifiable. Convert $KB \\wedge a$ to CNF, applies resolution rule, continues until either (1) no new clause can be added (i.e. KB does not entail a), or (2) two (unit) clauses resolve to give empty clause (i.e. KB entails a). \n\n\nResolution algo: \n\n\t def resolution(KB, a) returns true or false: \n\n\t\t clauses = CNF clauses of KB $\\wedge$ -a \n\n\t\t new = set()\n\n\t\t while true do:\n\n\t\t\t for each pair of clauses:\n\n\t\t\t\t resolvents = PL-RESOLVE(pair)\n\n\t\t\t\t if resolvents contain empty clause return true\n\n\t\t\t\t new = new union resolvents\n\n\t\t\t if new $\\subset$ clauses return false \n\n\t\t\t clauses = clauses union new \n\n\nWe can apply more efficient inference algos to KBs in more restrictive forms: e.g. horn and definite clauses. Horn clauses are close under resolution: resolving horn clause yields horn clause. Every definite clase can turn into an implication, where premise = conjunction of positive literals (from negative literals in original clause) and conclusion = positive literal. E.g. -L $\\lor$ -B $\\lor$ A $\\equiv$ L $\\wedge$ B $\\implies$ A.\n\n\nInference with horn clauses: use forward and backward chaining. Can be done in linear time w.r.t size of the KB. Forward chaining is data-driven reasoning: add premises incrementally. Backward chaining is goal-directed reasoning: find implications in KB with conclusion = the query. Try to prove all the premises in one of those implications. \n\n\nForward chaining algo: \n\n\t def FC(KB, q):\n\n\t\t count = table where count[c] = number of symbols in clause c's premise\n\n\t\t inferred = table where inferred[c] is false initially for all\n\n\t\t queue = a queue of symbols, initially true symbols in KB\n\n\t\t while queue is not empty:\n\n\t\t\t p = queue.pop()\n\n\t\t\t if p = q return true \n\n\t\t\t if inferred[p] = false:\n\n\t\t\t\t inferred[p] = true\n\n\t\t\t\t for each clause c in KB where p is the premise of c:\n\n\t\t\t\t\t count[c] -= 1\n\n\t\t\t\t\t if count[c] = 0 then add c.concluson to queue\n\n\t\t return false \n\n\n\n\n  \n\n## Module 7 Definitions\n* **Syntax** - Specifies the well-formed sentences\n* **Semantics** - defines the truth of each sentence w.r.t a possible world/ model\n* **Models** - Math abstracts with a fixed set of truth-values for each sentence\n* **Satisfaction** - model m satisfies a if a is true in m\n* **Monotonicity** - If $KB \\models a$ then $KB \\wedge B \\models a$. We can add to KB without invalidating anything \n* **Horn clause** - disjunction of litearls where at most one clause is positive, incl. no positives\n* **Definite clasue** - disjunction of literals where exactly one is positive\n* **Theorem proving** - applying rules of inference to sentences in knowledge base to prove sentence without models\n* **Validity** - sentence is valid if it is true in all models, aka tautologies\n* **Deduction theorem** - a $\\models$ b iff sentence a $\\imples$ b is valid\n* **Satisfiability** - sentence is satifiable if it is true in some model\n* **And-elimination** - we can derive any cojuncts from a conjunction\n* **Factoring** - removal of repeated literals in a clause\n* **Goal clauses** - clauses with no positive literals\n* **K-cnf sentence** - a CNF sentence where each clause has at most k literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0826c67c-ad2a-481f-aa5c-3018d4de9ca9"
      },
      "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": 56,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n There are four major approaches to AI along two dimensions: thought vs behavior, and human vs rational. \n\n\n(1) Acting humanly usings Turing Test to verify AI. (e.g.Blade Runner - Voight-Kampff Test in lecture) \n\n\n(2) Thinking humanly uses cognitive modeling, applying knowledge gained from introspection, psychological experiments, and brain imaging (e.g. General Problem Solver by Newall/Simon, computer vision). \n\n\n(3) Thinking rationally, using logic and probability. \n\n\n(4) Acting rationally, or the rational agent approach. Advantages of this approach include (a) more general than logical apporach since inference is just one mechanism to achieve rationality, (b) easier to integrate with scientific development. (4) forms the [standard model] of AI. In AI there is a value alignment problem  - we want agents to be provably beneficial to us. \n\n## AIMA Chapter 27.1 The Limits of AI\n Searle: weak vs strong AI. Weak AI acts like it is intelligent, and Strong AI actually are conscious. \n\n\nDifferent objections to AI: \n\n1) Argument from informality. Humans use informal guidelines that cannot be captured by AI. Hubert Dreyfus's criticism of Good Old-Fashioned AI (GOFAI). Points out qualification problem: that it is difficult to capture all conditions of behaviors using necessary and sufficent logic rules. Also humans are situated since they have many perceptual inputs, compared to just logical sentences \n\n\n- Response: we can introduce probabilistic reasoning, or use deep learning to perform informal tasks. Embodied cognition approach emphasizes that robotics, visions, etc. can also provide inputs for AI to be situated. \n\n\n2) Argument from disability. Claims that machines cannot do certain things. E.g. Turing: machines cannot be kind, have sense of humor, make mistakes. \n\n\n- Response: meta-reasoning allows computers to check their own computations. \n\n\n3) mathematical objection: Godel's incompleteness thoerem. For any axiomatic framework F, we can construct a sentence G(F) s.t. G(F) is a sentence within F, but not provable, and if F is consistent, then G(F) is true. Penrose, Lucas use it to challenge AI. \n\n\n- Response: agents do not cease to be agents if they can't establish truth of a sentence. Secondly, Godel's theorem is about math rather than computers. Even humans cannot overcome Godel's incompleteness theorem. Thirdly, Godel's theorem only applies to systems powerful enough to do arithmetic. Covers Turing Machiines, but computers are not Turing machines as they are finite. It is also not true that computers cannot change their minds \n\n\nTuring test is used to measure AI. Eugene Goostman (2014) fooled 33% of amateur judges, but no well trained judges. \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Turing: we maintain the polite convention that everyone thinks, and we should also extend that to machines. Dijkstra: asking if machines can think is like asking if submarines can swim\n\n\nSearle: supports biological naturalism: mental states are high-level emergent features caused by low-level physical/ neural processes. \n\n\nResponse: humans are made of cells and they do not understand either. \n\n\nIntrinsic nature of experiences: qualia. Dividing ideas on consciousness: global workspace vs integrated information theory.  \n\n## AIMA 2.1 Agents and Environments\n Examples of agents include software, handheld calculators and vacuum cleaners. Agents' actions can depend on anything it has received up till present. Agent functions have two representations: tabulation for external representation and agent program for internal representation.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n We need  to know what rational, or [do the right thing] means. Consequentialism assesses behaviors by outcomes, using performance measures to capture desirability. \n\n\nIt is generally better to design performance measures according to our desired outcomes then how we want agents to behave. We assume that PMs can be specified correctly. \n\n\nRational agent uses percept sequence and internal knowledge to maximize performancemeasure. \n\nRationality is not omniscience or perfection: does not maximize actual performance. \n\n\nRational agents may do actions to modify future percepts, called information gathering. It also has to learn (i.e augments its internal knowledge). \n\n\nIf an agent does not entirely relyon prior knowledge (i.e. can learn), it is autonomous. Good to start with initial knowledge then gradually gain autonomny.  \n\n## AIMA 2.3 The Nature of Environments\n PEAS: Performance, environment, actuators, sensors. Example PEAS for automated taxi: actuators are the controls for brake, signal, horn,sensors are radar, GPS, etc. Software agents can also be as complex as physical ones. \n\n\nVarieties of task environments: \n\n\n(1) fully observable (sensor detects all aspects relevant to the choice of action, relevant being dependent on performance measure; no need of internal state in that case) vs partially observable (inaccurate sensor, missing data) vs unobservable (no sensor),\n\n\n(2) single vs multi-agent(can be competitive or cooperative, depending on how A's performance measure depends on B's ) Deterministic vs stochastic (state changes with quantifiable probability) vs non-deterministic (no quantification of prob) \n\n\n(3) Episodic (actions independent from each other) vs sequential (current decision can affect future) \n\n\n(4) static vs dynamic: can env change while agent is deliberating vs semi-dynamic: env does not change but agent's performance score does (e.g. chess with a clock) \n\n\n(5) discrete v continuous: whether the state,time, percepts, and actions are discrete or continuous. \n\n\n(6) known vs unknown: whether agent has knowledge of the laws of physics. \n\n\nMost difficult is partially observable, nondeterministic, multi agent, unknown, sequential dynamic, and continous. E.g. Taxi driving. Some examples: English tutor TE is partial, multi-agent, stochastic, sequential dynamic, discrete; part picking robot is partial, single agent, stochastic, episodic, dynamic, continuous. Experiments with environments are mostly carried out for many envs drawn from an environment class.\n\n## AIMA 2.4 The Structure of Agents\n Table approach is inefficient: if p is the length of percept sequence and T is lifetime then lookup table will have $\\sum_{t = 1}^{T} p ^ t$ entries.\n\n\nFour kinds of agent problems. \n\n(1) Simple reflex agent uses current percept without considerationof previous sequence, like vacuum agent. Uses condition- action rules, if then statements.Mostly uses in fully observable envs because of limited intelligence. Can fall into infinite loops in partially observable envs. May escape with randomized actions (randomized can be rational).\n\n\n(2) model based reflex agents (maintain internal states) requires two kinds of knowledge: (a) knowledge of how the world works, or transition model. (b) information about how the state of the world is reflected in precepts, i.e. sensor model. Uses the knowledge to guess the world's state at the moment. (update state using precept, uses actions rules to derive an action).\n\n\n(3) goal based agents: uses goalsto capture desirable outcomes (e.g. search and planning agents). Differs from (1) and (2) because agents knows why it does certain actions \n\n\n(4) utility based agents: uses utility as an internal representation of performance measure, has advantage in flexibility and learning. Better than (3) in two ways: (a) helps rank different goals, and (b) helps decide which goal to pursue under uncertainty. Not all utility based agents are model-based: model free agents can learn what action is best iwthout knowing how it changes the environment. \n \n\n## Module 1 Lecture Notes\n Descartes' dualism suggests mind body separation, seeing bodies as just complex machines. Descartes suggests that however machinescan never learn to use languages. Turing proposes an imitation game. Searle however,\nargues that machines are not thinking but just doing symbol manipulation as in Chinese Room (e.g. Eliza, early NLP chatbot). \n\n\nContrasts strong vs weak AI: strongAI has a mind and can understand, while weak AI only simulates thoughts and do nothave real understanding. Searle thinks that biological brains causes minds. Dennett's brain in a vat experiment in [Who Am I?] asks whether a brain in a vat is really different\\ \nfrom a machine processing symbols. Current AI endeavors focuses on solving subproblems andtopping leaderboards, but some wants to develop truly intelligent AI. \n\n\nAgent function f: P->A maps a sequence of percepts (list) to a set of actions. Agent program runs on an architecture to implement an agent function. Can do this in a table but length will be exponential in len(P). \n\n\nPerformance Measure, Environment, Actuators and Sensors specify a task environment. A designer'sgoal is to construct an agent function f that maximizes expected value of performance measure, then construct an agent program that implements the function on an architecutre, given a task environment. \n\n\nWe describe something as an agent when it can be said to have its own perfomance measure.\n\n\nFor initial part of course we assume fully observable, static, deterministic, and discrete \n\n\nReflex agent: makes action based on current precept vs problem solving agent: plans aheade.g. searching. It formulates goal, generates a search problem with states, actions, performanceand come up with a solution. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content that an agent's sensor receives\n* **Percept sequence** - complete history of everything the agent has perceived\n* **Rational agent** - an agent that acts to achieve the best outcome or best expected outcome (i.e. maximize performance measure\n* **Agent function** - maps any given percept sequence to an action\n* **Agent program** - implementation of agent function\n* **Standard model** - The idea of constructing agents to do the right thing\n* **Turing test** - computer test using human-written questions, requiring NLP, knowledge representation, automated reasoning, and ML\n* **Total turing test** - Enhanced Turing test requiring computer vision and roboticsinteraction with real world\n* **Performance measure** - an objective yardstick for evaluating performance, using evidencefrom percept sequence\n* **Task environment** - a problem specification to be solved by the agent, consists of PEAS\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Features of python: fast development (intuitive syntax, whitespace delimited, garbage collected), portable,  built-in types, many supporting libraries. \n\n\nREPL environment: Read-evaluate-print loop. e.g. Python3 in terminal. \n\n\nScript: Create file, run script, need to print explicitly \n\n\nUse newline to end line of code, use backslash to continue to next line. Line indentation indicates block scope. \n\n\nAll data are objects, deleted when unreachable.\n\n\nPrefixing with r creates rawstring, which do not need to escape special chars. \n\n\nString formating: e.g. print(\"%s ... %d\" % (\"abc\", 123))\n\n\nStrings are immutable in python\n\n\nUse \"is\" keyword to check if objects are same, and == to check if values are same \n\n\ny = x[:] gives a shallow copy of sequence: new object with exact same values \n\n\nTuples \n\n- Immutable, ordered sequence\n\n- can have mixed type items (including collections)\n\n\nStrings \n\n- Immutable \n\n- Unicode, Use 2 byte chars (or 8 bit in Python 2)\n\n\nLists \n\n- Mutable \n\n- Mixed types \n\n\nDictionaries \n\n- unordered \n\n- Keys must be immutable, use hashing \n\n- constant average time add, lookup, update \n\n- accessing dict with unknown key throws error \n\n\nSlicing always return a copy \n\n\nList methods: li.reverse(), li.remove(item) - gives error, li.count(item), li.index(item), li.insert(idx), li.append(item) \n\n\nli.sort() sorts in place, while sorted() returns a copy \n\n\nString methods: s.split(), s.captialize(), s.upper(), s.strip(), s.join(s2) \n\n\nDict methods: d.keys() returns list of keys, d.values() returns list of current values,  d.items() returns list of item tuples \n\n\nDefaultdict initializes nonexistent values, similar to Counter \n\n\nFunction def: \n\n\t def functionName(arguments): \n\n\t\t return something, somethingElse \n\n\nNo function overloading, two functions cannot have the same name\n\n\nDefault values for function should come last - else SyntaxError \n\n\nKeyword arguments allow calling functions with arguments out of order. It should be included after all other arguments. \n\n\n \\*args as argument allows variable number of arguments (in the form of tuple) to be passed as arguments. Use star operator * to unpack list into tuple.\n\n\n\\*\\*kwargs take variable number of dictionary entries as keyword arguments. Use double star * * to unpack dict into positional arguments. args and kwargs can be used together. \n\n\nDefault arguments in function refers to the same object across all calls, can use for memoization \n\n\nCreating class: \n\n\t class Example(superClass, superClass2):\n\n\t\t def __init__(self, attr):\n\n\t\t\t self.attr = attr\n\n\t\t def func(self): \n\n\t\t\t print(self.attr)\n\n\nRedefine methods in subclass: just use the same name. Calling methods in parent class: parent.method(self, arg, arg2...)\n\n\nMain method: if __name__ == '__main__':\n\n\nIterator creation: li.__iter__(), iter(li) returns iter object. Can call next(iter) or iter.__next__() or iter.next(). Need to catch StopIteration exception.\n\n\nFor loops uses iterators underneath. Iterator needs __next__ and iterable needs __iter__ \n\n\nWe can do \n\n\t for elem in Iter(input): \n\n\t\t print elem \n\n\nmore memory efficient than getting the whole list \n\n\nGenerators are iterators underneath. Including yield keywords makes a function returns a geneator. Each time the next() method of generator is called, the method runs until it finds a yield. \n\n\nGenerators use less code, auto-maintain local states, compute value one at a time, saves memory, provides one-pass aggregation of item, and very useful for infinite sequences \n\n\nUse importlib to reload code. importlib.reload(nameOfModule)\n\n\npip: package installer for Python. \n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - Object cannot be modified after creation\n* **Strong typing** - every object has fixed type, and interpreter enforce type restrictions (e.g. string + int)\n* **Static typing** - variables can only refer to objects of declared type, e.g. java; functions have type signatures\n* **Dynamic typing** - Variables can take on different types, functions do not have type signatures, catch type errors at runtime\n* **Dynamic scope** - functions sees and uses the most current value of variables\n* **First class objects** - Programming entities that can be created, destroyed, pass to functions return as a value, and be treated like other variables\n* **Extension** - One class using methods and attributes defined in another class\n* **Magic methods** - methods that allow user defined classes to act like built in types, e.g. __copy__, __cmp__\n* **Duck typing** - Assess suitability of object by checking whether corresponding method exists. Eliminates need of interface\n* **List comprehension** - [exp for x in list if cond(x)]\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-solving agent plans ahead, considers a sequence of actions. It does searching to come up with such a sequence. They use atomic representation (e.g. Markov decision, search agent), which have no internal  structure visible. In contrast, planning agents use factored  (variables, e.g. CSP, Logic) or structured (e.g. tree, e.g.) representations. \n\n\nFour phase problem solving: Formulating a goal, formulating a problem (comes up with state and action representation), search (generate a sequence of actions called a solution), and execution. In fully observable, deterministic,and known environment, solution is fixed and the system is called an open-loop system,since the agent can ignore the precepts. VS closed-loop approach where agent has to monitor percepts (e.g. indeterministic env)\n\n\nProblem definition requires (1) state space, (2) initial state, (3) goal states, (4) actions available (for every state the actions that are applicable in s, ACTIONS(s)), (5) transition model (RESULTS(s, a) -> s’),  and (6) action cost function (ACTION-COST(s, a, sp) -> cost). \n\n\nAbstraction is the process of removing details from a representation. Abstraction is valid if it can be elaborated into a working solution in a more detailed world; it is useful if the actions suggested through abstract \\ \nis easier than the original problem. \n\n## AIMA Chapter 3.2 Example Problems\n A standardised problem is used to illustrate problem solving methods. It has a concise exact description and is used as benchmark for  comparing algos. VS a real-world problem. \n\nGrid world puzzles (e.g. vacuum world have n * 2 ^n states (n as number of cells)). Actions can be specified as absolute, or egocentric (defined relative to agent’s viewpoint).\n\n\nSokoban puzzle is where an agent needs to push some boxes to locations. For a world with n non-obstacle cells and b boxes, there are $n * n! / (b!(n-b)!)$ states. \n\n\nSliding tile puzzles (e.g. 8-puzzle, Rush Hour Puzzle) is another type of standard problem.\n\n\nKnuth proposes another problem: using square root, floor, and factorial operations to transform number 4 into any number. State space is infinite.\n\n\nReal world problem example: rout-finding (reach a specific location), touring (visit a set of locations, e.g. TSP), VLSI layout (cell layout without overlapping, channel routing that finds a route for each wire), robot navigation (many-dimensional search space, one dimension for each joint angle), automatic assembly sequencing (e.g. protein design) \n\n## AIMA Chapter 3.3 Search Algorithms\n Search tree - representation of a state space with each node being a state and each edge being an action. Root represents initial state. Search tree is not the state space itself - multiple paths may get to any particular state, and each node in the tree can get back to the root by a unique path. \n\n\n\nBest-first search algorithm: choose node with minimum value of evaluation function. Also: Add initial node to frontier, pop node, if not goal then expand, add unvisited node (or visited node with lower cost) to frontier and reached lookup table. Continue until goal state found.\n\n\nBest first search uses priority queue; breadth first search uses FIFO queue; DFS uses LIFO queue/ stack.\n\n\nSometimes there can be repeated states. A cycle/ looping part involves coming back to the same state, which makes search tree infinite. It is a special case of redundant path - two paths with same goal and destination but different lengths.\n\n\nThree approaches to handle repeated states: 1) remember all reached states (preferred if many redundant paths), 2) do not worry about repeating (because of problem specification), 3) check for cycles but not redundant paths (follow up chains of parents to see if the current state has appeared earlier) \n\n\nGraph search checks for redundant paths and tree like search do not. Best first search is graph search.\n\n\nFour ways to measure alto’s performance, 1) completeness, 2) cost optimality, 3) time complexity, 4) space complexity. Completeness requires an algorithm to be systematic. If state space is infinite, a sound algorithm has to search forever.  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breath first search is used when all actions have the same costs. It is same as best-first search when f(n) returns the depth of the node. Advantages vs Best-first search: (1) FIFO faster than priority queue, (2) reached can be a set of state, not a state-to-node mapping (no need of distance info), (3) can do an early goal test - testing if a node is goal as soon as it is added to frontier, not when it is popped. \n\n\nDijkstra’s algorithm / uniform cost search is best-first-search with evaluation function = cost of path from root to current node. Worst case time and space complexity is $O(b^{1+floor(C* / \\epsilon)})$, where C* is cost of optimal solution, and epsilon is the lower bound on the cost of each action. It can be much greater than b^d, since it can explore large trees with low costs before high costs ones. When all action costs are equal, complexity is b^(d+1), similar to breadth-first search. It is complete and optimal. It will not get caught going down a single infinite path. \n\n\nDFS expands deepest node first. Same as BFS where evaluation function = negative of depth of node. Usually implemented as aa tree-like search. For tree-like finite state spaces it is efficient and complete. In acyclic spaces it may expand same state many times but will explore the entire space. However, it can get trapped in infinite loop in cyclic state spaces. In infinite stat spaces it is not systematic - can go along infinite path even without cycles. It is not optimal, since it will return first solution found. Runtime is O(bm) with m = maximum depth of tree. Used for CSP, satisfiability, and logic programming.\n\n\nA variant of DFS is backtracking serach, generating one successor at a time, which is done in place (modify current state) rather than constructing new state. Reduces memory req to O(m) actions. Also allows using an efficient DS to store states on current path with cycle checking in O(1) time. \n\n\nHybrid approach is to run BFS until all memory is consumed and run iterative deepening from all nodes in frontier. When search space is larger than memory, and depth of solution is unknown iterative deepening is preferred. \n\n\nBidirectional best first search reduces space and time complexity to O(b^(d/2)). We maintain two lookup tables and two frontiers, and expand in each direction. We join paths when one direction expands nodes already in another's path. Need a TERMINATED function to decide when to stop. If we do bidirectional uniform cost search and optimal path length is C*, then no node with cost C*/2 will be expanded. \n\n \n\n## Module 3 Lecture Notes\n Reflex agent ignores percept history; problem solving agents plan ahead using search. \n\n\nBFS pseudocode: \n\n\ndef BFS():\n\n  \t node = node with state = initial state, path cost = 0\n\n  \t if goal_test(node): return solution\n\n  \t fronter = FIFO queue with node\n\n  \t explored = empty set \n\n  \t while frontier:\n\n  \t\t node = frontier.pop() // shallowest node\n\n  \t\t explored.add(node.state)\n\n  \t\t for each action in node.state.actions():\n\n  \t\t\t child = child-node(problem, node, action)\n\n  \t\t\t if child.state not in explored or frontier:\n\n  \t\t\t\t if goal_test(child.state) return solution\n\n  \t\t\t\t frontier.insert(child)\n\n\nBFS is complete and optimal (when cost is constant). Total nodes generated = space and time complexity is $1 + b + b^2 + b^3 +… + b^d = O(b^d)$, b = branching factor and d = solution depth. Memory requirement is a bigger concern than time. Limits BFS to solving uninformed searches for large problems. \n\n\nDepth limited search is O(b^l) time and O(bl) space, l being the depth limit. Also tree like search. Can use the diameter of the stae space graph as depth (ie how many states). \n\n\nIterative deepening search has O(bd) memory requirement when there is solution,\nor O(bm) on finite spaces with no solution (m is max depth, d is depth of shallowest solution). Time complexity O(b^d) or O(b^m). Total number of nodes generated is db^1 + (d-1)b^2 + (d-2)b^3... + ... b^d \n\n\nComparing search methods:\n\n\nBFS: complete, $b^d$ time and space, optimal\n\nDFS: not complete, not optimal, $b^m$ time, $bm$ space\n\nDepth limited: Not complete, not optimal, $b^l$ time, bl space \n\nIterative deepening: complete, optimal, $b^d$ time, $bd$ space\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** -  a sequence of actions\n* **Node expansion** - consider all available actions for that state and generate a new node\n* **Solution** - a path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Completeness** - can find a solution if there is one, and repeat failure when there is none\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nEvery consistent heuristic is admissible but not vice versa. With consitent heuristic we will have optimal path the first time we reach a state. \n\n\n\nIf heuristic is inadmissible A * can still be optimal if 1) there is a path where it is admissible, or (2) heuristic does not overestimate more than C^2 - C * , with former being cost of second best and latter cost of optimal solution. \n\ng cost is always monotonic - only increase when we go along the path, so contour lines never cross. \n\n\nSurely expanded nodes have f(n) < C\\*. A\\* with consistent heuristic is optimally efficient since it exapnd all nodes that are surely expanded. \n\n\nDrawback is that number of expanded nodes can be exponential in length of solution. \n\n\nTo reduce number of nodes expanded we can do satisficing search, producing solutions thatmay not be optimal but are good enough. E.g. multipler SLD by a detour index Weighted A * search uses f(n) = g(n) + W * h(n) for some W > 1. \n\n\n\nWays to reduce memory req of A *: \n\n(1) stores frontier nodes only either on frontier or on reached set. \n\n\n(2) keep reference count of # times a state is visited to eliminate state \\ \nfrom reached when no longer needed. \n\n\n(3) beam search: keepiing only k nodes with best f scores incomplete and suboptimal. \n\n\n(4) alternative beam: keeps all node with f-score within a certain limit from optimal. \n\n\n(5) iterative A * search (IDA *) with cutoff value set to certain f-cost (g+h) works well when each path has integer f costs. \n\n\n(6) recursive best-first search, uses a f_limit variable to keep track of f-value of best alternative path from ancestor. If current node goes past the limit, goes back to that alternative, replacing f-value on each node with a backed-up value, the best f-value of its children. Helps decide whether it is useful to re-expand a subtree. More efficient than IDA *, optimal if h(n) is admissible, uses space linear in depth of deepest optimal solution. Time complexity depends on heuristic accuracy and how often path changes. \n\n\n(7) (simple) Memory-bounded A\\* (SMA\\*): expand best leaf until memory full, then drop (oldest) worst leaf node(highest f value), backs up the value of that node, and regen the subtree only if all other paths are found worse. Complete if there is any reachable solution with depth less than memsize. Optimal if solution is reachable. \n\n\n(8) bidirectional heuristic search: Two different h and g functions. lowerer bound of solution that goes to m, then n, then goal: $lb(m,n) = max(g_F(m)+g_B(n),f_F(m),f_B(n))$ For pair m,n with lb(m,n) less than optimal cost,  we must expand either m or n to look for potential solutions. Cannot be ensured to be optimally efficient, but can  be efficient. \n\n\n f2 evaluation function = max(2g(n), g(n)+h(n)). Combined with admissible h, makes bidrectional  search optimal and complete. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n We can use effective branching factor to measure usefulness of heuristic. $N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$, where N = number of nodes generated with heuristic, d = solution depth. Well designed heuristic should have value ~ 1. \n\n\nEffect of A * search can be captured by reducing effective depth of a search tree by a constant k_h. Total search cost bcomes $O(b^{d-k_h})$ instead of O(b^d). \n\n\nA heuristic that dominates another usually have lower branching factor and is thus better. \n\n\nWe can come up with heuristics by reasoning on relaxed problems, with fewer restrictions then the original, e.g. with shortcuts. Can auto generate relaxed problems by disjuncting and \\ \nclauses (e.g. absolver program, found heuristic for Rubrik's) \n\n\nWe can also use composite heuristic = max of all available and admissible heuristics Takes longer to compute but better than all alternatives.\n\n\nWe can come up with heuristics using subproblems (i.e. pattern databases). Store costs for subproblems, compute admissible heuristic by looking up subproblem in database , which is constructed by searching back from goal and recording cost of each new pattern. expense \n\n\nDisjoint pattern databases: divide up problem such that each move only affects one subproblem (e.g. in 8 puzzle, record number of moves involving 1-2-3-4, then sum up with 5-6-7-8.) \n\n\nAnother way to generate heuristics is to use landmarks. Choose a few landmark points, for each one compute and store optimal path from all other vertices to landmark (and opposite)then construct h(n) = min(C * (n, L) + C * (L, goal)). Efficient but not admissible. \\ \nIf we want admissible we can use instead h(n) = max(abs(C * (n, L) - C * (goal, L))), differential heuristic.\n\n\nCan save more time using shortcuts - artificial paths that pre-define optimal multi-action path. \n\n\nSelecting landmarks: use peripheral ones for differnetial heuristic, farthest ones, or frequently requested ones \n\n\nFinal way to generate heuristic is to use ML/RL to learn from experience. Works better when we have features of a state (e.g. number misplaced tiles). Combine features linearly to produce heuristic\n\n\n\n## Module 4 Lecture Notes\n Dimensions for evaluating search: (1) completeness, (2) optimality, (3) time complexity (num nodes generated), (4) space complexity (num nodes in memory). \n\n\nWe can use relaxed problems to generate heuristics. Cost of optimal solution to relaxed problem is admissible heuristic for original problem. \n\n\nGreedy best first search uses f(n) = h(n). It is complete in finite state spaces but not infinite ones. Worst case space & time complexity is O(|V|). With good heuristic function it can reach O(bm). \n\n\nGreedy Best first search code: \n\n\ndef greedy(): \n\n  \t frontier = PriorityQueue() \n\n  \t frontier.put(start, 0) \n\n  \t came_from = {} \n\n  \t came_from[start] = None \n\n  \t while not frontier.empty(): \n\n  \t\t current = frontier.get() \n\n  \t\t if current == goal: \n\n  \t\t\t break \n\n  \t\t for next in graph.neighbors(current): \n\n  \t\t\t if next not in came_from: \n\n  \t\t\t\t priority = heuristic(goal,next) \n\n  \t\t\t\t frontier.put(next, priority) \n\n  \t\t\t\t came_from[next] = current  \n\n\nA* waits until the goal node is expanded to terminate. \n\n\nA * search is complete. Whether it is optimal relates to whether it is admissible/optimistic. \n\n\nProof of A star: suppose optimal path has cost B * and algo returns path with cost B > B *. There must be some node on optimal path that is unexpanded. \n\n\n\nIf g * (n) = cost of optimal path since start state, h * (n) = cost of optimal path to nearest goal: \n\n\n\n$f(n) > C*$ or n would have been expanded \n\n\n\n$f(n) = g(n) + h(n)$ by definition \n\n\n\n$f(n) = g*(n) + h(n)$ since n is on optimal path \n\n\n\n$f(n) \\leq g*(n) + h*(n)$ since admissibility \n\n\n\n$f(n) \\leq C*$ by definition \n\n\nAlternative (word based proof):\n\n\nLet A be optimal goal node, B be suboptimal goal node, claim that A will exit frontier before B. \n\n\nIf B is on frontier, and some ancestor n of A is on the frontier, we try to claim that n will be expanded before B. \n\n\n1. $f(n) \\leq f(A)$ \n\n\t\t - $f(n) \\leq g(A) = f(A)$ \n\n2. $f(A) < f(B)$ \n\n\t\t - $g(A) < g(B) \\implies f(A) < f(B)$ since h = 0 at goal\n3. so, n expands before B \n\n\t\t - $f(n) \\leq f(A) < f(B)$\n4. Since all ancestors of A expand before B, A expand before B.\n\n\n\nUniform cost search can be seen as case where W = 0 and A* is W = 1. Greedy is W = infinity. \n\n## Module 4 Definitions\n* **Unbounded cost search** - accepts quick solutions at any cost \n* **Bounded cost search** - find solution with cost less than constant C\n* **Bounded suboptimal search** - find solution guaranteed to be within a constant factor W of the optimal cost (e.g. weighted A*)\n* **Speedy search** - example of unbounded search and greedy, uses h(n) = number of actions required to reach goal regardless of cost\n* **A star search** - best first search using f(n) = g(n) + h(n)\n* **Heuristic function** - estimates cost of cheapest path from state at node n to the goal state\n* **Consistent heuristic** - for every node n and every successor n' we have $h(n) \\leq c(n, a, n') + h(n')$.\n* **Manhattan distance/ city block distance** - sum of distances from goal positions\n* **Effective branching factor** - branching factor that a uniform tree of depth d has s.t. it has N + 1 nodes\n* **Heuristic domination** - h1 dominates h2 if h2(n) >= h1(n) for any n. Better to use heuristic with higher values\n* **Metalevel state space** - captures the internal state of a program searching in an object-levelstate space\n* **Metalevel learning algorithm** - learn from missteps to avoid exploring unpromising paths, minimzingtotal cost\n* **Front to end search** - bidirectional search with heuristics estimating distance to goal/ initial\n* **Front-to-front search** - bidrectional search with heuristics estimating distance to the other frontier\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Three stances toward multi-agent environments: (1) consider in aggregate as an economy, (2) consider agents as part of env that makes env non-deterministic, (3)  model agents with game-tree search. For each state we want to stop searching, we either  use evaluation function as heuristic or average outcomes of many simulations of game. \n\n For games move = action and position = state. Definition of game include: initial state, TO-MOVE(s), ACTIONS(s), RESULT(s,a), IS_TERMINAL(s), UTILITY(s, player). State space graph represent states and connections. We can superimpose search tree/ game tree. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n If game has binary outocome we can use AND-OR search. Solution = solution for a nondeterministic planning problem, guaranteeing reaching terminal state regardless of what other does. \n\n\nIf games with multiple outcome scores we use minimax search. If opponent plays sub-optimally we may not always want to play minimax, preferring risky move to certain sub-par move.\n\n\nMinimax algo: O(b^m) exponential complexity with m = max depth of tree and b = legal moves at each pointSpace complexity = O(bm) if all actions generated together or O(m) with backtracking. \n\n\nFor multi-player game, replace value of each node with vectors. Each players chooses vector with value higher for themselves. Alliances can emerge out of selfish behaviors. In positive sum vgames collaboration can also happen between 2.\n\n\nWe cannot eliminate exponent but can cut it in half. Alpha-beta pruning efffectiveness dependent on order of examination. Perfect alpha-beta pruning reduces runtime to  $O(b^{(m/2)})$. Effective branching factor becomes $\\sqrt(b)$. Random move ordering runtime  becomes $O(b^{(3m/4)})$. We cannot get perfrect ordering function, else we already have  info to play the game.\n\n\n Ways to improve move ordering/ search efficiency: (1) fnd killer moves using iterative deepending,  (2) uses transposition table to capture redundant states, \n\n\n Shannon's two strategies: Type A consider wide but shallow portion of tree, considers all  moves up to certain depth then estimate the lowest level; Type B follows promising lines, deep but  narrow search. Go problems are typically Type B, chess Type A. \n\n\n AB pseudo-code: \n\n\n \t function MAX_VALUE(game, state, alpha, beta) returns (utility, move) pair: \n\n \t if state is terminal: return utility, null \n\n \t v = negative inf \n\n \t for each a in actions(state) do: \n\n \t\t v2, a2 = MIN_VALUE(game, result(state, a), alpha, beta)\n\n \t\t if v2 > t then:\n\n \t\t\t v, move = v2, a\n\n \t\t\t alpha = max(alpha, v)\n\n \t\t if v >= beta then return v, move\n\n \t return v, move\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can apply evaluation function to nodes, and replace termination test with cutoff test. For non-terminal states, evaluation must be somewhere between utility of loss and utility of win (for the player) \n\n\nRequirements for eval function: 1) does not take too long, 2) strongly correlated with winning. E.g. use features of the state to delineate several categories/ equivalent classes of states, with same value for all features. Any category have some states leading to wins draws. and losses. Eval function estimates proportional of states with win, draw, losses and calculate expected value. \n\n\nAlternative to classes/categories: compute numerical contributions of each feature and combine. E.g. material value ]\nof chess pieces, transformed using a weighted linear function (with normalized weights). This assumes that contributions are independent. To remove assumption, we can use nonlinear combination of states. \n\n\nTo adapt alpha-beta algo, we need to keep track of depth/ use iterative deepening. Evaluation functions should be applied to quiescent positions: where no next move can wildly change evaluation. We can add quiescence search in cutoff test. \n\n\nAlso need to take into account horizon effect: when one can delay an opponent's move but not prevent it. To mitigate the effect we allow singular extensions, allowing beyond-depth moves that are clearly better than others. Usually will not add too much. \n\n\nForward pruning: prunes moves that do not look good. Type B: exchange risk for time. 1) E.g. beam search:  consider only best moves. 2) E.g. PROBCUT: use statistics from history to reduce chance of pruning best moves, pruning nodes that are probably outside the (alpha, beta) range. 3) E.g. late move reduction,  assume that moves are well ordered, and reduce the search depth of nodes that come late. \n\n\nNormal Minimax search for chess can look 5 plys, with alpha-beta, transposition table we have 14, and with better databases and computers we can go 30 ply. \n\n\nFor beginning and ending of games we can do table lookup instead of search. Computers can produce a policy, using retrograde minimax search: starting from endgames, go backwards to compute sure-win positions.\n  \n\n## AIMA Chapter 5.5 Stochastic Games\n Exampel of stochastic games: backgammon. Roll two dies, then move and capture. Calculate expected value of a position/ expectiminimax value. Evaluation functions for stochastic games haave stricter requirements: they must have values that are positive linear transformation of the probability of winning. \n\n\nExpectiminimax takes $O(b^m n^m)$ time, where n is the number of rolls/ chance events at each node. Pruning options are more limited: if we have bounds on the utility value of all outcomes then we can use it to yield a bound for the average/ expected utility for pruning. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(RESULT(a) = s') = \\sum_s P(s) P(s' | s, a)$ \n\n\n$Expected Utility = \\sum_s' P(RESULT(a) = s') U(s')$ \n\n\nMEU principle formalizes \"doing the right thing\" but does not operationalize: still need to estimate probability of states thruogh learning, and compute P(RESULT(a)=s') using a causal model.  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints/axioms on rational preference relations: (1) orderability either two lotteries are indifferent or agent prefers one over other, (2) transitivity , (3) continuity: if B is between A and C in preference, there is some probability p s.t. agent will be indifferent between B for sure and A / C with probability (4) substitutability: If indifferent between A and B, then indifferent between two lotteries with only difference being A vs B, (5) Monotonicity: If A $\\succ$ B then agent prefers lottery with higher probability for A, (6) decomposability: Compound lotteries can be reduced to simpler ones\n\n\nvon Neumann & Morgenstern: Existence of Utility function. If agent's preference obeys axiom, then there is a function s.t. U(A) > U(B) iff A $\\succ$ B and U(A) = U(B) if $A \\sim B$. \n\n## AIMA Chapter 16.3 Utility Functions\n Utility of money is not directly proportional to monetary value.Value of first million is very high, while marginal value decreases. s shaped curve. A billionnaire thus more likely to take a risky but beneficial move than a stable one \n\n\nGrayson study: utility of money almost exactly proportional to log of the amount. We typically have concave utility function for positive wealth (facing downwards),\n\n\nPeople in the slope-decreasing part of utility curve will assign higher utility to a guaranteed Expected Monetary Value than a lottery. Risk-avrese agents. Risk-seeking agents show up in the negative part of the wealth utility curve. If the changes in wealth are small, curve will be nearly linear, and agent will be risk-neutral \n\n\nMost rational action a = $argmax_a EU(a)$. Most of the time we can only estimate EU. Unbiased estimate: expected value of error is 0. Since we select action with highest EU estimate, we will have an optimistic bias/ optimizer's curse. Bias higher when we are choosing among more choices. If variance in utility estimate is high, what appears to be the best choice may not even be the best chioce: so make sure sample size is large enough for trials. We can avoid it by using a Bayesian model using a probability model of the error $P(EU_est | EU)$, updating EU based on our prior knowledge of it.\nHuman preferences are predictably irrataional: there may be no utility function consistent with our choices. Possible reasons: (1) certainty effect (reduce computational burden, distrust stated probsaccoutning for emotion) (2) Ellsberg paradox: people have ambiguity aversion, prefer known probability. (3) framing effect, (4) anchoring effect. \n\n## Module 5 Lecture Notes\n Hexpawn game (Martin Gardner): pawn moves diagonally to capture opponent or forward for one move. Illustrates game tree. Starts from level 0: MAX, then alternateEvaluation function assigns real number scores to each board position (node) without reference to path (i.e. based on static features). f(n) > 0 if MAX winning at n. Example: tic-tac-toeuses f(n) = 3 lengths open for MAX - MIN. \n\n\nEvaluation functions for chess: 1) Turing: each piece has value, sum of Max - sum min. 2) nowadays: weighted sum of positional features. \n\n\nMinimax rule: assuem that opponent always play best move. If opponent player does not play optimally it still works. \n\n\nAlpha beta pruning. Alpha = MAX's lower bound on its outcome. Beta: MIN's upper bound on its outcome. MAX will rule out anything worse than Alpha. So, when we are at max node, we stop evaluating branch if we get value >= Beta. Stop evaluate MIN branch if value <= Alpha. \n\n\nExpectimax search: we look at average-case outcomes rather than worst-case (minimax) E.g. random opponents, explicit random games, failed actions. Add chance nodes like MIN nodes: when we are at chance node we compute expected utility. May stop at some level and estimate expectimax value. Can't really prune as easily. \n\n\nPositive affine transformation (i.e. multiply by positive number then plus any number) \\ \ndoes not affect validity of utility function. When only preference ranking is needed, it is called a value function / ordinal utility function. \n\n\n## Module 5 Definitions\n* **Alpha** - the MAX nodes's current lower bound on MAX's outcome\n* **Beta** - the MIN node's current upper bound on MIN's outcome\n* **Transpositions in games** - different move sequences resulitng in the same position\n* **Minimax value** - utility of being in a state, assuming optimal decisions from both sidestill end of game\n* **Game tree** - search tree following all sequence of moves to a terminal state\n* **Backed-up value** - Optimal value of a node's children\n* **Random variable** - represents events with unknown outcome\n* **Probability distribution** - assignment of weights to outcomes\n* **Expected value of function of random variables** - average value weighted by probaility\n* **Objectivism/ frequentism** - Probabilities are averages over repeated experiments. Based on new eveidence, which change the reference class. Inherently random events.\n* **Subjectivism/ bayesianism** - Probabilities are degrees of belief about unobserved variables. Learning probabilities and using evidence to updating beliefs.\n* **Goal based agents** - Binary distinction between good and bad states\n* **Decision theoretic agent** - assign continuous range of values to states\n* **Utility function** - assigns a single value representing agent's preference to a state\n* **Principle of maximum expected utility (meu)** - Rational agent should choose action  that maximizes expected utility\n* **Justification of meu** - Agents who maximize an expected utility reflecting performance measure will achieve highest average performance score \n* **Lottery** - a mapping between a set of outcomes/states/lotteries and probabilities with probs summing up to 1\n* **Lottery notation** - $L = [p_1, S_1; p_2, S_2; ... ]$\n* **Preference notation** - indifference: $A \\sim B$, preference A over B: $A \\succ B$ \n* **Expected utility of lottery** - $U([p1, S1 ...]) = \\sum_i p_i U(S_i)$\n* **Prefernece elicitation** - Figure out human's utility function by presenting choices to huamans\n* **Normalized utility** - Utility scaling using 1 as best possible prize and 0 as worst\n* **Standard lottery** - compare s vs L=[$p * best; (1-p) * worst$], utility of S will be p if indifferent\n* **Value of statistical life** - $10 million, used by government agents to evaluate regulations\n* **Micromort** - One in a million chance of death = driving car for 230 miles\n* **Qaly** - Quality adjusted life year, accouting for disability etc.\n* **Monotonic preference** - Prefer more to less\n* **Certainty equivalent** - value that one will accept instead of a lottery\n* **Insurance premium** - EMV of lottery - certainty equivalent\n* **Order statistic** - distributino of any particular ranked element of a sample\n* **Optimizer's curse** - tendency for expected utility of best choice to be too high\n* **Policy** - mapping from possible states to the best move in the state\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n For search algorithms the state is atomic/ black box without internal structure. Need domain specific information of transitions between states. CSP uses factored representation: variables with values, solved when vars are assigned consistent values. CSPs use structure of states to design general heuristics for solutions. \n\n\nEach constraint in CSP is a pair <scope, relationship> where relationship can be binary,unary, etc. Partial assignment vs complete assignment. \n\n\nCSP solving is generally NP-complete. \n\n\nExamples of CSPs: map coloring, job scheduling (with precedence constraints, disjunctive constraints (no overlaps)), cryptarithmetic puzzles, linear programming (continuous domain, constraints are linear equalities and inequalities).\n\n\nInfinite domains require implict constraints (e.g. T1 value bigger than T2) rather than explict relationship between value tuples. If we have linear constraints on integer variabless there are special algorithms. But if constraints are nonlinear, problem is undecidable.\n\n\nConstraints can be represented in hypergraph: with n-ary constraints as n-ary nodes. \n\n\nEvery constraint with finite domain can be reduced into a set of binary constraints , so we can convert any CSP into binary constraint questions. We can also use dual graph transformation: one variable for each constraint, and one binary constraint for each constraint that share variables. Domain of the variables will be the set of tuples that satisfy the constraint. \n\n\nWhy global constraint is better than binary: (1) less error-prone, (2) we can design special-purpose inference algo for global constraints.  \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation \n\nIf a graph with k nodes is strongly k consistent, then we can choose a value for 1st, choose one for second, and so on without worrying about inconsistency. Only have to search d values in domain and check consistency (n^2 time). Runtime is O(n^2 d).\n\n\nHowever, to establish n-consistency we need exponential time and space in n.\n\n\nAlgorithm for global constraints: remove domains with just one value, then propagate until no single value domain. \n\n\nSometimes there are resource constraints or atmost constraints. We can do bounds propagation, using upper and lower bounds to represent domains. Check for bound-consistency: for every variable X, for both the lower and upper bound value of X, there is some value for Y that satisfy the constraint between X and Y. \n\n\nSudoku solvers: AC-3 for easier puzzles, PC-2 for slightly harder ones. More tricks e.g.naked triples: find three cells in a unit that share same subset of 3 numbers. Eliminate those numbers from other cells. \n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking search\n\nWhen inference is insufficient we alternate search with inference. Backtracking search uses DFS, has only one representation of the state, and modifies the representation instead of creating a new one. \n\n\nHeuristics: \n\n1) Minimum remaining values (MRV) \n\n2) degree heuristic (select vars involved in largest num of constraints \n\n3) least constraining value \n\n\nForward check: when X is assigned, check arc consistency with all neighbors \n\n\nMAC (Maintaining arc consistency): AC-3 constraint propgation, with checks on whether any domains become empty. Strictly more powerful than forward checking. \n\n\nChronological backtracking: basic backtracking, revisiting most recent decision point.\n\n\nBetter alternative (backjumping) is to backtrack to a variable that rules out one of the values of the empty var. Set of assignments in conflict with a value of variable is called a conflict set. Bacjump to most recent assignment in conflict set. \n\n\nForward checking can supply the conflict set. Every branch eliminated by backjumping is also elimed by forward checking. So the two are redundant. \n\n\nStrongly conflict set tracking (conflict directed backjumping) : track the set of variables that cause the empty var, and any subsequent vars to have no consistent solution. In this case, we establish conflict set with a prior node absorbing \\ \nthe conflict set of a (failed) child node. \n\n\nAfter backjumping to most recent node in conflict set we updating that node's conflict set : conflict_set(X_i) = conflict_set(X_i) union conflict_set(X_j) - {X_i} if X_j backjumps\nto Xi.\n\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local saerch approach: start with complete assignment, randomly choose a conflicted variable, then change it to something with minimum number of conflicts \n\n\nMin conflict heuristic local search has runtime independent of problem size for n-queens Local search works well for problems where solutions are densely distributed throughout state space. \n\n\nPlateau saerch: allow side-way moves to another state with the same score, can help local saerch get out of plateaus (space with few solutions). Tabu search: keeping list of recently visited states and forbidding return, or simulated annealing, can help escape from plateaus \n\n\nConstraint weighting focuses ssaerch on important constraints. We try to change variable/value such that lowest total weight will result. Then adjust weights by incrementing weight of violated constraints. Two benefits: (1) adding topography to platueas, and (2) adds learning. \n\n\nLocal search also can easily adapt to situations where the problem conditions change, e.g.schedule changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can improve efficiency by identifying independent subproblems. \n\n\nConnected components on constraint graph indicates independent subproblems. When we decompose problems into $n/c$ subproblems, each takes $d^c$ work to solve, so total work is $O(d^c n/c)$, linear in n vs exponential O(d^n). \n\n\nSlightly weaker than independent subproblems are tree-like CSPs, where any two vars are only connected by a path. Tree like CSPs can be solved in time linear to number of variables n, using directional arc consistency. A CSP is DAC iff every X_i is arc consistent with X_j for j > i.\n\n\nSolution to tree-like CSP:\n\n1) pick a var to be root, produce a topological sort\n\n2) Make the graph directed arc-consistent in O(nd^2) times (check n edges, for each edge compare d domain values for two vars) \n\n3) Go down list of variables and choose any value. Value cascade down and will be consistent \n\n\nCutset conditioning:\n\n1. Choose a cycle cutset S such that after removing S, the graph becomes a tree\n\n2. For each assignment to S that satisfy constraints in S:\n\n\t remove inconsistent values from remaining vars\n\n\t if remaining CSP has solution, return \n\n\nTotal run time is $O(d^c * (n-c)d^2)$, c = size of cycle cutset. IF the graph is almost, a tree, then will save a lot of time. However, finding the smallest cycle cutset is NP-hard, although there are approx algos. \n\n\nTree decomposition: \n\nTransform graph into a tree where each node is a set of (potentially overlapping) variables \n\nThree requirements for tree decomposition: \n\n1. Every variable appears at least once in one of the tree nodes \n\n2. If two variables are in same constraint, they must appear with that constraint in at least one tree node \n\n3. If a varable appears in two tree nodes, it must appear in all node in between those two nodes\n\n\nWith the tree graph, we can solve in O(nd^2) time, but d will be larger (domain is set of tuples of values). So if the nodes have small variables, solving will be efficient. \n\n\nTree width = [size of largest node - 1] determines efficiency of tree decomposition. Tree width of a CSP graph is the minimum width all all tree decompositions. Finding the decomposition with minimum tree width is NP-hard. \n\n\nWith tree width w and the corresponding decomposition, we can solve problem in $O(nd^{w+1})$ time i.e. polynomial time when tree width is bounded. \n\n\nWhenever we have cycle-cuteset of size c, there is also a tree width of size w < c+ 1, so tree decomposition is better time wise. But cycle cuteset requires just linear memory, while tree decomposition requires exponential memory in w. \n\nValue symmetry: If we have d colors for assignment, then for every consistent solution, there is d! solutions that we can get by just permuting colors We can include a symmetry-breaking constraint to reduce search space by d! . But in general it is NP-hard to eliminate all symmetry. \n\n\n## Module 6 Lecture Notes\n Two kinds of search: planning (find path) and identification (assign values to variables). In CSP we represent constraints with a declarative language and devise general purpose search algorithms to solve them. \n\n\nCSP components: (1) finite set of variables, (2) non-empty domain of values for each varaible (3) finite set of constrants. A CSP state is an assignment of value to some/all variables.\n\n\nBenefits of CSP: (1) easy to represent many problems, (2) know where to focus search, (3) can effectively prune off branches that violate constraints.\n\n\nUse a constraint graph to represent CSPs. Variables can be discrete (with finite or infinite domains (e.g. integers)) or continuous (time). Constraints can be unary, binary, higher-order, or preference-based (soft) constraints. \n\n\nCSP can be represented as a search problem, with constant path cost at each step, and value assignment as moves. Solutions have constant depth (num of variables). Rrepresented as such, the search tree has $n! d^n$ leaves (first-level branching factor nd, second-level (n-1)d, etc.), d being domain size and n being no. variables. However, since assignment is commutative, the effective leaves since is $d^n$. We do not have to consider all nodes at one step, just one, so branching factor = d. We can do a tree search rather than a graph search. \n\n\nBasic DFS approach to CSP is backtracking. We can improve its efficiency by using heuristics: (1) most constrained variable (fewest legal values in domain) / minimum remaining values (MRV), (2) most constraining variable tie-breaker (impose most constraints) on remaining variebls, (3) least constraining value assignment, (4) forward checking (keeping track of legal values for unassigned vars, terminate when there are none) \nForward check only propagates from assigned vars to unassigned ones. Constraint propagation uses inference to enforce local consistency, eliminating values that violate local consistency. \n\n\nIn checking arc consistency we change undirected edges to directed arcs (one pair between each pair of variables). Checking each arc takes $O(d^2)$ time. If x loses a value, we check neighbors of X. \n\n\nExample of arc consistency: Waltz Algorithm. USes to interpret 3D drawings. Intersections as variables, constraints between adjacent intersections. Waltz/ Mackworth Algorithm: (1) assign every node with all possible values, (2) Repeat until values do not change, (3) Enforce arc consistency. \n\n\nImprovements over Waltz-Mackworth: (1) only check those variables where its neighbors have lost a value. (2) No need to check Y if X loses a value because of Y, (3) if we remove X, it can only make Z inconsistent with X, so just check (z, x) is arc-consistent. \n\n\nImproved algo - AC-3:\n\n\t def AC-3(csp):\n\n\t\t while queue is not empty do:\n\n\t\t\t (X_i, X_j) = queue.pop()\n\n\t\t\t if REMOVE-INCONSISTENT(X_i, X_j):\n\n\t\t\t\t for each X_k in Neighbors(X_i) - {X_j}:\n\n\t\t\t\t\t queue.add(X_k, X_i)\n\n\n\t def REMOVE_INCONSISTENT(X_i, X_j):\n\n\t\t removed = false\n\n\t\t for each x in DOMAIN[X_i]:\n\n\t\t\t if no value in DOMAIN[X_j] makes (x, y) satify constraints\n\n\t\t\t\t delete x from DOMAIN[X_i]\n\n\t\t\t\t removed = true\n\n\t\t return removed \n\n\nTotal number of arcs: $2n(n-1)$, $O(n^2)$ \n\nChecking each arc is $O(d^2)$ \n\nEach arc can be inserted d times \n\nWorst case runtime: $O(n^2d^3)$ \n\n\nIf constraint graph is planar (edges do not intersect), number of arcs will be linear in N, so time complexity is $O(nd^3)$ \n\n  \n\n## Module 6 Definitions\n* **Complete assignment** - all variables assigned\n* **Consistent assignment** - does not violate constraint\n* **Backtracking search** - DFS for CSPs with single value assignments\n* **Xi arc consistency with xj** - For every value in domain_i, there is some value in domain_j that satifies binary constraint between Xi and Xj\n* **Global constraint** - a constraint that can involve an arbitrary number of variables (but not necessarily all), e.g. Alldiff\n* **Node consistency** - var is node consistent if all values in domain satisfy unary constraints\n* **Path consistency** - Two vars are PC with K if every consistent assignment to IJ is consistent with a value in K \n* **K consistency** - If there is consistent assignment to k-1 vars there is a consistentval for the kth var\n* **Strong k consistency** - k-consistent, k-1 consistent, and so on\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge based agent program: \n\n\t def KB-agent(percept): \n\n\t\t TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))\n\n\t\t action = ASK(KB, MAKE-ACTION-QUERY(t))\n\n\t\t TELL(KB, MAKE-ACTION-SENTENCE(action, t))\n\n\t\t t = t+1\n\n\t\t return action \n\n\nincludes a TELL action that informs the knowledge base of percepts, and a ASKS action that queries a rational action.MAKE-PERCEPT sentence builds a sentence about percept, MAKE-ACTION-QUERY builds a sentence to ask appropriate question at time t, MAKE-ACTION-SENTENCE asserts that action is executed. \n\n\nKnowledge level specifies what the agent knows and what its goals are, while implementation level implements it. Analysis of knowledge level is independent of implementation. \n\n\nDeclarative approach to system building proceed by telling agents what to do. Procedural approach encodes behaviors directly. Successful agents combine both. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world (with gold as goal instead of rescuing). Actions are going forward, turing left or turning right. Sense stench, breeze, glitter, bump, scream, represented as a list of current percepts.  \n\n## AIMA Chapter 7.3 Logic\n Modeling checking inference algorithm: examines whether M(KB) is subset of M(a) \n\n\nGrounding is the connection between the world and logical reasonning. Agent's sensor creates the connection by telling it what happens in the real world. Prodcues learning rules.  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n TT-entails algorithm: recursive enumeration of assignments to symbols. Sound since it implements entailment, and completes since it always terminates. \n\n\n\t def TT-Entails(KB, a):\n\n\t\t symbols = list of proposition symbols in KB and a\n\n\t\t return TT-CHECK-ALL(KB, A=a, symbols, {})\n\n\n\t def TT-CHECK-ALL(KB, a, symbols, model):\n\n\t\t if symbols.empty() then:\n\n\t\t\t if PL-TRUE(KB, model) then return PL-TRUE(A, model)\n\n\t\t\t else return true \n\n\t\t else \n\n\t\t\t p = symbols.first()\n\n\t\t\t rest = symbols.rest()\n\n\t\t\t return(TT-CHECK-ALL(KB, a, rest, model union {P = true}) and \n\n\t\t\t TT-CHECK-ALL(KB, a, rest, model union {P = false})) \n\n\nTime complexity is O(2^n) when there are n symbols in KB and a (since there are 2^n) possible models. Space complexity is just O(n) \n\n\nPropositional entailment is co-NP-complete: every known inference algo has worst-case complexity that is exponential. \n\n## AIMA 7.5 Propositional Theorem Proving\n Proof that resolution is complete, or the ground resolution theorem: if a set of clauses is unsatifiable, then resolution closure contains the empty clause \n\n\nResoution closure RC(S) = set of all clauses that can be derived by applying resoluton to clauses in S. S must be finite, so Resolution always terminates. \n\n\nWe prove by contrapositive: if RC(S) does not contain empty clause then S is satisfiable. We construct a model for S with truth values t1, t2 ...., assign false to ti if and only if a clause contains -Pi and all other literals are false. Otherwise assign true. \\ \nWe can show that the assignment is a model of S, by assuming (to the contrary) that at some stage i we first see a false clause. Then the clause would like like either (f or f or f or Pi) or (f or f or f or -Pi) and both of them have to be in RC(s). But if both are present, then the resolvent will be already falsfied at a prior stage, which yields a contradiction. \n\n\nWe can use AND-OR graph to illustrate forward chaining. We start from known facts then propagates thorugh the graph. Forward chaining is sound because of modus ponens. COmplete beacuse at the end, the inferred table will have true for all symbols inferred \n\n  \n\n## Module 7 Lecture Notes\n Knowledge-based agents: uses reasoning on internal representation of messages (which are non-atomic). Have knowledge base (KB) with a set of sentences written in a knowledge representation language. Two kinds of setences: (1) axioms and (2) derived sentences \n\nExample - Wampa world. 4 times 4 grid with 20% probability of pit. -1 point for each action, -10 for using fire. Perceives stench (near wampa), breeze (pit), bump (wall), scream (killing wampa). World is deterministic, discrete, static, single-agent, sequential partially observable.\n\n\nSet of all models of a = M(a). \n\n\nEntailment is the idea that a follows logically from b. $a \\models b$ iff $M(a) \\subset M(b).$i.e. a is more specific than b. \n\n\nInference is the process of using entailment to draw conclusions. KB single-turnstile_i a = a is derived from KB by i.\n\n\nPropositional logic uses single symbols to represent atomic sentences that can be true or false. Complex sentences = atomic sentences + Logical connectives. \n\n\nAn inference algorithm is sound if it only derives entailed sentences. Complete if it can derive all entailed sentences. \n\n\n$a \\equiv b$ iff they are true in the same set of models, and iff they entail each other. \n\n\nInference rules: conditions on top and conclusion belwo. Logical equivalence rules can all be rewritten as inference rules. \n\n\nWe can use search algorithms to find proofs. Initial state = KB. Actions are applications of inference rules, results are additional of sentences. Goal state = state where KB contains conclusion. \n\n\nLogical rules: \n\n\t Associativity of $\\lor$: ((a $\\lor$ b) $\\lor$ y ) $\\equiv$ (a $\\lor$ (B $\\lor$ Y))\n\n\t Associativity of $\\wedge$: ((a $\\wedge$ b) $\\wedge$ y ) $\\equiv$ (a $\\wedge$ (B $\\wedge$ Y))\n\n\t contraposition: a $\\implies$ b $\\equiv$ -b $\\implies$ -a \n\n\t implication elim: a $\\implies$ b $\\equiv$ -a $\\lor$ b \n\n\t distributivity of $\\lor$ over $\\wedge$: (a $\\lor$ (b $\\wedge$ y)) $\\equiv$ (a  $\\lor$ b) $\\wedge$ (a  $\\lor$ y)\n\n\t distributivity of $\\wedge$ over $\\lor$: (a $\\wedge$ (b $\\lor$ y)) $\\equiv$ (a  $\\wedge$ b) $\\lor$ (a  $\\wedge$ y)\n\n\nMonotonicity impllies soundness, set of entailed sentences can only increase. \n\n\nResoluton rule gives a complete inference algorithm when paired with any complete search algorithm. Idea: We can eliminate a literal in disjunctino and the negative of the same literal in conjunction. Unit resolution: If we have (l1 $\\lor$ l2, ..., lk) and -lk, we can eliminate lk and -lk. Only applies to clauses, i.e. disjunction of literals. \n\n\nEvery sentence can be reformulated as conjunction of clauses, thus applicable for resolution. Conjunctive normal form: start by eliminating implications, then move negative sign inwards. Application distributivity of $\\lor$ over $\\wedge$. \n\n\nProof by resolution: To show $KB \\models a$ we show that $KB \\wedge a$ is unsatisifiable. Convert $KB \\wedge a$ to CNF, applies resolution rule, continues until either (1) no new clause can be added (i.e. KB does not entail a), or (2) two (unit) clauses resolve to give empty clause (i.e. KB entails a). \n\n\nResolution algo: \n\n\t def resolution(KB, a) returns true or false: \n\n\t\t clauses = CNF clauses of KB $\\wedge$ -a \n\n\t\t new = set()\n\n\t\t while true do:\n\n\t\t\t for each pair of clauses:\n\n\t\t\t\t resolvents = PL-RESOLVE(pair)\n\n\t\t\t\t if resolvents contain empty clause return true\n\n\t\t\t\t new = new union resolvents\n\n\t\t\t if new $\\subset$ clauses return false \n\n\t\t\t clauses = clauses union new \n\n\nWe can apply more efficient inference algos to KBs in more restrictive forms: e.g. horn and definite clauses. Horn clauses are close under resolution: resolving horn clause yields horn clause. Every definite clase can turn into an implication, where premise = conjunction of positive literals (from negative literals in original clause) and conclusion = positive literal. E.g. -L $\\lor$ -B $\\lor$ A $\\equiv$ L $\\wedge$ B $\\implies$ A.\n\n\nInference with horn clauses: use forward and backward chaining. Can be done in linear time w.r.t size of the KB. Forward chaining is data-driven reasoning: add premises incrementally. Backward chaining is goal-directed reasoning: find implications in KB with conclusion = the query. Try to prove all the premises in one of those implications. \n\n\nForward chaining algo: \n\n\t def FC(KB, q):\n\n\t\t count = table where count[c] = number of symbols in clause c's premise\n\n\t\t inferred = table where inferred[c] is false initially for all\n\n\t\t queue = a queue of symbols, initially true symbols in KB\n\n\t\t while queue is not empty:\n\n\t\t\t p = queue.pop()\n\n\t\t\t if p = q return true \n\n\t\t\t if inferred[p] = false:\n\n\t\t\t\t inferred[p] = true\n\n\t\t\t\t for each clause c in KB where p is the premise of c:\n\n\t\t\t\t\t count[c] -= 1\n\n\t\t\t\t\t if count[c] = 0 then add c.concluson to queue\n\n\t\t return false \n\n\n\n\n  \n\n## Module 7 Definitions\n* **Syntax** - Specifies the well-formed sentences\n* **Semantics** - defines the truth of each sentence w.r.t a possible world/ model\n* **Models** - Math abstracts with a fixed set of truth-values for each sentence\n* **Satisfaction** - model m satisfies a if a is true in m\n* **Monotonicity** - If $KB \\models a$ then $KB \\wedge B \\models a$. We can add to KB without invalidating anything \n* **Horn clause** - disjunction of litearls where at most one clause is positive, incl. no positives\n* **Definite clasue** - disjunction of literals where exactly one is positive\n* **Theorem proving** - applying rules of inference to sentences in knowledge base to prove sentence without models\n* **Validity** - sentence is valid if it is true in all models, aka tautologies\n* **Deduction theorem** - a $\\models$ b iff sentence a $\\imples$ b is valid\n* **Satisfiability** - sentence is satifiable if it is true in some model\n* **And-elimination** - we can derive any cojuncts from a conjunction\n* **Factoring** - removal of repeated literals in a clause\n* **Goal clauses** - clauses with no positive literals\n* **K-cnf sentence** - a CNF sentence where each clause has at most k literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3zZOQDQcUjwE"
      },
      "source": [
        ""
      ],
      "execution_count": 56,
      "outputs": []
    }
  ]
}