{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Hollis Cooper - CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "GZZXyrV-xuAp",
        "9xRbdqDox2zD",
        "46MQLR-Gx8dZ",
        "WHREsHSSyA-h",
        "F3FPMzG9yUls",
        "qVSQhTVSyYYO"
      ]
    },
    "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": "3593a04d-73c3-49c5-a86b-c3a2472c89d5"
      },
      "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": 1,
      "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": "19595af8-c3e4-4a0a-bd7b-9a6375a86b2d"
      },
      "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": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7e1fa332-8574-4c9f-f2c8-285f50aa6b32"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" The dimensions of AI include:\n",
        "- human vs rational\n",
        "- thought vs behavior\n",
        "\n",
        "**Human intelligence** involves observations about behavior and about thought. A **Turing test** tests whether a human interrogator \\\n",
        "can determine if the written answers to his/her written questions are answered by a human or a computer. A total Turing test does this in physical space. In order to \\\n",
        "successfully pass a Turing test, a computer would need natural language processing, knowledge representation, automated reasoning, machine learning, and for a total \\\n",
        "Turing test, would also need computer vision, speech recognition, and robotics (for motion). **Cognitive modeling** tries to construct theories of mind, since if \\\n",
        "we have that, we can express it as a computer program.\n",
        "\n",
        "**Rationalist approach** to AI uses the study of \"laws of thought\" aka the field of logic. Logic uses knowledge about the world (and probability to fill in the gaps of \\\n",
        "uncertain information). To get intelligent behavior, we need to add rational action to this, which is the **rational agent** approach. Rational agent approach is more general \\\n",
        "than \"laws of thought\" approach and is easier to use for scientific development.\n",
        "\n",
        "AI is focused on studying/constructing agents that do the 'right' thing, which is the objective provided to the agent by us. This paradigm is called the **standard model**. \\\n",
        "Sometimes, because of computational load, perfect rationality is not possible, so we use limited rationality instead. Problems with the standard model are:\n",
        "- We might not be able to fully specify the objective\n",
        "- There might be a value alignment problem\n",
        "- We cannot anticipate all the ways a rational agent might misbehave if its objective is fixed\n",
        "\n",
        "We want machines to pursue our objectives, which means the machine might be uncertain about the objective. These agents should ultimately be positively beneficial to humans.\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agents perceive their environment through sensors and act upon their environment using actuators. Content that agent's sensors perceive is called a percept, and the \\\n",
        "collection of all percepts over time for an agent is called the percept sequence. \n",
        "- Agents base their actions on the percept sequence to date. \n",
        "- Agents cannot use future percepts when making a decision.\n",
        "The **agent function**, which maps percept sequences to actions (and is more of an abstract mathematical description), is implemented internally by the **agent program**, which its concrete \\ \n",
        "implementation running within a physical system.\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" Rational behavior is \\'doing the right thing\\'. We evaluate the behavior of an agent by looking at the consequences of that behavior (**consequentialism**). The agent's sequence of actions (based on its percept sequence) \\\n",
        "causes the environment to go through a sequence of states, which we evaluate using a **performance measure**.\n",
        "\n",
        "Good performance measures can be hard to come up with. Best results are usually achieved by designing the performance measure around the desired outcome rather than the agent's behavior. Sometimes, \\\n",
        "it is better if the agent have some uncertainty over the performance measure and learn about it over time.\n",
        "\n",
        "**Rationality** depends on 4 things: \n",
        "- performance measure to determine success\n",
        "- agent's previous knowledge of the environment\n",
        "- agent's possible actions\n",
        "- agent's current percept sequence\n",
        "\n",
        "If an agent is omniscient, it would know the actual outcomes of its actions and would act accordingly - but this is usually not possible in reality because we don't always know the future. \\\n",
        "This is why rationality maximizes expected performance, not actual performance. Agents may perform information gathering to potentially modify future precepts and rational agents \\\n",
        "learn as they go from what they perceive.\n",
        "\n",
        "Rational agents also are autonomous, meaning they can learn to compensate for incomplete or incorrect prior knowledge (of the designer). They should learn as much as possible.\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" **Task environments** are the problems solved by rational agent solutions. Their nature directly influences the design of the agent program, and they should be specified as completely as possible. \\\n",
        "We can define them with PEAS:\n",
        "- performance measure\n",
        "- environment (more restricted environments usually mean easier designs)\n",
        "- actuators needed\n",
        "- sensors needed\n",
        "\n",
        "Dimensions of task environments include:\n",
        "- **Fully observable vs partially observable**. \n",
        "Fully-observable – agent’s sensors can detect the complete state of the environment at each point in time (esp detect all aspects that are relevant to the choice of action where relevance depends on the performance measure). In FO environments, agent doesn’t need to maintain internal state to keep track of the world \\\\\n",
        "Partially-observable – environment is only partially observable because of problems with sensors, or part of the state missing from sensor data\n",
        "- **Single agent vs multiagent**. \n",
        "Multiagent – when agent B’s behavior is maximizing a performance measure whose value depends on agent A’s behavior. Multiagent environments can be competitive (ex. chess) or cooperative (ex. auto-driving car), or a mix of both.\n",
        "- **Deterministic vs Nondeterministic**. Deterministic – next state of env is completely determined by current state and action executed by agent(s); nondeterministic otherwise. Stochastic environments explicitly deal with quantifiable probabilities, while nondeterministic just list probabilities (without quantifying them)\n",
        "- **Episodic vs sequential**. Episodic task environment divides agent’s experience into atomic episodes (each episode: agent receives precept; agent then performs single action) (ex. spotting defective parts). Simpler of the two environments. Sequential task environment – current decision affects future decisions (ex. chess). May require agent to think ahead.\n",
        "- **Static vs dynamic**. Dynamic environments can change while agent is deliberating. Continually ask agent what to do and if agent hasn’t decided, counts as doing nothing. Static environments do not require the agent to consider the passage of time or to keep looking at the world while it’s deciding. If environment doesn’t change but agent’s performance score does, environment is called semidynamic.\n",
        "-\t**Discrete vs continuous**. Applies to state of the environment, way time is handled, and to percepts/actions of the agent. Ex. chess is discrete, driving is continuous\n",
        "-\t**Known vs unknown**. Refers to the agent’s or designer’s state of knowledge about the rules of the environment. Known environment: outcomes (or outcome probabilities) are given. Unknown environment: agent must learn how environment works to make good decisions. Known environments can be partially observable (ex. card games), and unknown environments can be fully observable (ex. video game)\n",
        "\n",
        "The hardest case to work with is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" Agent program runs on computing device with actuators and sensors called the agent architecture. Its goal is to produce most rational behavior from the smallest program possible \\\\\n",
        "(to save memory from a large lookup table). \n",
        "\n",
        "Agent = agent architecture + agent program\n",
        "\n",
        "1: **Simple Reflex Agents**\n",
        "-\tAgent selects actions based on current precept, ignoring rest of precept history\n",
        "-\tReflex behaviors can occur in complex environments (condition-action rules: if/then)\n",
        "-\tUsually requires fully observable environment; partially observable env can result in infinite loops. Randomization of actions can help avoid\n",
        "\n",
        "2: **Model-based Reflex Agents**\n",
        "-\tHandle partial observability by tracking unobserved part of the world – agent maintains internal state based on percept history and reflects some of the unobserved aspects. Internal state is best guess from agent\n",
        "-\tUpdating state info requires info about how world changes over time (effects of agent actions + how world works independently of agent = **transition model** of the world) and info about how state of world is reflected in agent percepts = **sensor model**. Limited by agent sensors\n",
        "-\tTransition model + sensor model = model-based agent\n",
        "\n",
        "3: **Goal-based Agents**\n",
        "-\tAlso needs goal info to describe desirable situations\n",
        "-\tSearch and planning are subfields that find sequences to achieve goals\n",
        "-\tMore flexible because goal can simply be replaced\n",
        "\n",
        "4: **Utility-based Agents**\n",
        "-\tUtility is performance measure that indicates how “happy” a specific state will make an agent\n",
        "-\tUtility function = internalization of performance measure\n",
        "-\tIf internal utility function and external performance measure are in agreement, agent that maximizes its utility will be rational\n",
        "-\tUtility function can make rational decisions when goals are inadequate or conflicting. Maximizes expected utility of the action outcomes\n",
        "-\tNot all are model-based (there are model-free agents)\n",
        "\n",
        "**Learning agents** can be any type of agent. Can operate in initially unknown environments.\n",
        "Components:\n",
        "- Learning element: makes improvements to perf element based on critic feedback\n",
        "-\tPerformance element: selects external actions by taking in percepts\n",
        "-\tCritic: Uses fixed performance standard that can distinguish incoming precept as reward or penalty that provides direct feedback on agent behavior quality\n",
        "- Problem generator: suggests actions that lead to new and informative experiences\n",
        "\n",
        "Representations of the state of the world:\n",
        "-\tAtomic: each state is indivisible “black box”\n",
        "-\tFactored: split into fixed set of variables/attributes, each of which can have a value. Two factored states can share some attributes and not others\n",
        "-\tStructured: things in the state have relationships to one another\n",
        "\n",
        "Additional representations:\n",
        "-\tLocalist: 1-to-1 arbitrary mapping between concepts and memory locations\n",
        "-\tDistributed: rep of concept spread over many memory locations & each location is part of the rep of mult diff concepts. More robust against noise and info loss\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"Turing test\" : \"computer passes if human questioner can't tell if written responses to written questions come from a human or a machine\",\n",
        "\"Total Turing test\" : \"Turing test conducted in physical space\",\n",
        "\"Agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"Rational agent\": \"agent perceives/acts in pursuit of achieving the best expected outcome\",\n",
        "\"Value alignment problem\": \"problem of getting agreement between our true objective and the objective put into the machine\",\n",
        "\"Weak AI\": \"the idea that machines could act as if they were actually intelligent\",\n",
        "\"Strong AI\": \"asserting that machines are actually thinking - not just appearing to be thinking\",\n",
        "\"Percepts\": \"the content perceived by the agent's sensors\",\n",
        "\"Percept sequence\" : \"a complete history of everything the agent has ever perceived\",\n",
        "\"Performance measure\" : \"used to measure the desirability of a particular state of the environment\",\n",
        "\"Agent function\" : \"maps the behavior of an agent to a specific precept sequence\",\n",
        "\"Agent program\" : \"the actual implementation of the agent program in a concrete environment\",\n",
        "\"Task environment\" : \"can be described with PEAS: performance, environment, actuators, sensors\",\n",
        "\"Utility\" : \"performance measure that indicates how “happy” a specific state will make an agent\",\n",
        "\"Utility function\" : \"internalization of utility-based performance measure\"\n",
        "\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_4))\n"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 407\n",
            "The length in characters is 2991\n"
          ]
        }
      ]
    },
    {
      "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": "3bcd4540-b535-4163-a7ae-671e09057740"
      },
      "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",
        "      len_sum = len(summary)\n",
        "      len_char_sum = len(summary.split(' '))\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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n The dimensions of AI include:\n- human vs rational\n- thought vs behavior\n\n**Human intelligence** involves observations about behavior and about thought. A **Turing test** tests whether a human interrogator can determine if the written answers to his/her written questions are answered by a human or a computer. A total Turing test does this in physical space. In order to successfully pass a Turing test, a computer would need natural language processing, knowledge representation, automated reasoning, machine learning, and for a total Turing test, would also need computer vision, speech recognition, and robotics (for motion). **Cognitive modeling** tries to construct theories of mind, since if we have that, we can express it as a computer program.\n\n**Rationalist approach** to AI uses the study of \"laws of thought\" aka the field of logic. Logic uses knowledge about the world (and probability to fill in the gaps of uncertain information). To get intelligent behavior, we need to add rational action to this, which is the **rational agent** approach. Rational agent approach is more general than \"laws of thought\" approach and is easier to use for scientific development.\n\nAI is focused on studying/constructing agents that do the 'right' thing, which is the objective provided to the agent by us. This paradigm is called the **standard model**. Sometimes, because of computational load, perfect rationality is not possible, so we use limited rationality instead. Problems with the standard model are:\n- We might not be able to fully specify the objective\n- There might be a value alignment problem\n- We cannot anticipate all the ways a rational agent might misbehave if its objective is fixed\n\nWe want machines to pursue our objectives, which means the machine might be uncertain about the objective. These agents should ultimately be positively beneficial to humans.\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Agents perceive their environment through sensors and act upon their environment using actuators. Content that agent's sensors perceive is called a percept, and the collection of all percepts over time for an agent is called the percept sequence. \n- Agents base their actions on the percept sequence to date. \n- Agents cannot use future percepts when making a decision.\nThe **agent function**, which maps percept sequences to actions (and is more of an abstract mathematical description), is implemented internally by the **agent program**, which its concrete \\ \nimplementation running within a physical system.\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational behavior is 'doing the right thing'. We evaluate the behavior of an agent by looking at the consequences of that behavior (**consequentialism**). The agent's sequence of actions (based on its percept sequence) causes the environment to go through a sequence of states, which we evaluate using a **performance measure**.\n\nGood performance measures can be hard to come up with. Best results are usually achieved by designing the performance measure around the desired outcome rather than the agent's behavior. Sometimes, it is better if the agent have some uncertainty over the performance measure and learn about it over time.\n\n**Rationality** depends on 4 things: \n- performance measure to determine success\n- agent's previous knowledge of the environment\n- agent's possible actions\n- agent's current percept sequence\n\nIf an agent is omniscient, it would know the actual outcomes of its actions and would act accordingly - but this is usually not possible in reality because we don't always know the future. This is why rationality maximizes expected performance, not actual performance. Agents may perform information gathering to potentially modify future precepts and rational agents learn as they go from what they perceive.\n\nRational agents also are autonomous, meaning they can learn to compensate for incomplete or incorrect prior knowledge (of the designer). They should learn as much as possible.\n \n\n## AIMA 2.3 The Nature of Environments\n **Task environments** are the problems solved by rational agent solutions. Their nature directly influences the design of the agent program, and they should be specified as completely as possible. We can define them with PEAS:\n- performance measure\n- environment (more restricted environments usually mean easier designs)\n- actuators needed\n- sensors needed\n\nDimensions of task environments include:\n- **Fully observable vs partially observable**. \nFully-observable – agent’s sensors can detect the complete state of the environment at each point in time (esp detect all aspects that are relevant to the choice of action where relevance depends on the performance measure). In FO environments, agent doesn’t need to maintain internal state to keep track of the world \\\nPartially-observable – environment is only partially observable because of problems with sensors, or part of the state missing from sensor data\n- **Single agent vs multiagent**. \nMultiagent – when agent B’s behavior is maximizing a performance measure whose value depends on agent A’s behavior. Multiagent environments can be competitive (ex. chess) or cooperative (ex. auto-driving car), or a mix of both.\n- **Deterministic vs Nondeterministic**. Deterministic – next state of env is completely determined by current state and action executed by agent(s); nondeterministic otherwise. Stochastic environments explicitly deal with quantifiable probabilities, while nondeterministic just list probabilities (without quantifying them)\n- **Episodic vs sequential**. Episodic task environment divides agent’s experience into atomic episodes (each episode: agent receives precept; agent then performs single action) (ex. spotting defective parts). Simpler of the two environments. Sequential task environment – current decision affects future decisions (ex. chess). May require agent to think ahead.\n- **Static vs dynamic**. Dynamic environments can change while agent is deliberating. Continually ask agent what to do and if agent hasn’t decided, counts as doing nothing. Static environments do not require the agent to consider the passage of time or to keep looking at the world while it’s deciding. If environment doesn’t change but agent’s performance score does, environment is called semidynamic.\n-\t**Discrete vs continuous**. Applies to state of the environment, way time is handled, and to percepts/actions of the agent. Ex. chess is discrete, driving is continuous\n-\t**Known vs unknown**. Refers to the agent’s or designer’s state of knowledge about the rules of the environment. Known environment: outcomes (or outcome probabilities) are given. Unknown environment: agent must learn how environment works to make good decisions. Known environments can be partially observable (ex. card games), and unknown environments can be fully observable (ex. video game)\n\nThe hardest case to work with is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n Agent program runs on computing device with actuators and sensors called the agent architecture. Its goal is to produce most rational behavior from the smallest program possible \\(to save memory from a large lookup table). \n\nAgent = agent architecture + agent program\n\n1: **Simple Reflex Agents**\n-\tAgent selects actions based on current precept, ignoring rest of precept history\n-\tReflex behaviors can occur in complex environments (condition-action rules: if/then)\n-\tUsually requires fully observable environment; partially observable env can result in infinite loops. Randomization of actions can help avoid\n\n2: **Model-based Reflex Agents**\n-\tHandle partial observability by tracking unobserved part of the world – agent maintains internal state based on percept history and reflects some of the unobserved aspects. Internal state is best guess from agent\n-\tUpdating state info requires info about how world changes over time (effects of agent actions + how world works independently of agent = **transition model** of the world) and info about how state of world is reflected in agent percepts = **sensor model**. Limited by agent sensors\n-\tTransition model + sensor model = model-based agent\n\n3: **Goal-based Agents**\n-\tAlso needs goal info to describe desirable situations\n-\tSearch and planning are subfields that find sequences to achieve goals\n-\tMore flexible because goal can simply be replaced\n\n4: **Utility-based Agents**\n-\tUtility is performance measure that indicates how “happy” a specific state will make an agent\n-\tUtility function = internalization of performance measure\n-\tIf internal utility function and external performance measure are in agreement, agent that maximizes its utility will be rational\n-\tUtility function can make rational decisions when goals are inadequate or conflicting. Maximizes expected utility of the action outcomes\n-\tNot all are model-based (there are model-free agents)\n\n**Learning agents** can be any type of agent. Can operate in initially unknown environments.\nComponents:\n- Learning element: makes improvements to perf element based on critic feedback\n-\tPerformance element: selects external actions by taking in percepts\n-\tCritic: Uses fixed performance standard that can distinguish incoming precept as reward or penalty that provides direct feedback on agent behavior quality\n- Problem generator: suggests actions that lead to new and informative experiences\n\nRepresentations of the state of the world:\n-\tAtomic: each state is indivisible “black box”\n-\tFactored: split into fixed set of variables/attributes, each of which can have a value. Two factored states can share some attributes and not others\n-\tStructured: things in the state have relationships to one another\n\nAdditional representations:\n-\tLocalist: 1-to-1 arbitrary mapping between concepts and memory locations\n-\tDistributed: rep of concept spread over many memory locations & each location is part of the rep of mult diff concepts. More robust against noise and info loss\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Turing test** - computer passes if human questioner can't tell if written responses to written questions come from a human or a machine\n* **Total turing test** - Turing test conducted in physical space\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent perceives/acts in pursuit of achieving the best expected outcome\n* **Value alignment problem** - problem of getting agreement between our true objective and the objective put into the machine\n* **Weak ai** - the idea that machines could act as if they were actually intelligent\n* **Strong ai** - asserting that machines are actually thinking - not just appearing to be thinking\n* **Percepts** - the content perceived by the agent's sensors\n* **Percept sequence** - a complete history of everything the agent has ever perceived\n* **Performance measure** - used to measure the desirability of a particular state of the environment\n* **Agent function** - maps the behavior of an agent to a specific precept sequence\n* **Agent program** - the actual implementation of the agent program in a concrete environment\n* **Task environment** - can be described with PEAS: performance, environment, actuators, sensors\n* **Utility** - performance measure that indicates how “happy” a specific state will make an agent\n* **Utility function** - internalization of utility-based performance measure\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 = \"\"\" Python is a strongly typed language - can't combine incompatible types. You can check type with type(object) or isinstance(object, type). \\\n",
        "Python is dynamically typed, though, so the types of variables are assigned when the variable  is assigned (or reassigned). Functions have no type signatures. This \\\n",
        "means type errors are caught at runtime.\n",
        "\n",
        "****\n",
        "\n",
        "**Mutability**\n",
        "- Strings are immutable. They are created once. Concatenating strings creates a new string object. Checking if 2 strings are equal (==) checks if they point to objects with same value. \\\n",
        "\"is\" checks whether they point to the same object.\n",
        "```\n",
        "x = 'foo '\n",
        "y = x         # so y == x would resolve as true\n",
        "x = x.strip() # creates new object\n",
        "print(x)      # 'foo'\n",
        "print(y)      # 'foo '\n",
        "```\n",
        "\n",
        "- Lists are mutable.\n",
        "```\n",
        "x=[1,2,3,4]\n",
        "y = x\n",
        "x.append(5)  # does not create new object\n",
        "print(y)     # [1,2,3,4,5]\n",
        "print(x)     # [1,2,3,4,5]\n",
        "y = x[:]     # creates shallow copy of x = new object of same value\n",
        "```\n",
        "****\n",
        "\n",
        "**Sequences**\n",
        "\n",
        "Sequence elements are indexed using positive numbers (from the left) or negative numbers (from the right)\n",
        "\n",
        "- **Tuples**\n",
        "  - immutable\n",
        "  - items can be mixed types, including collection types\n",
        "  - declared with ( )\n",
        "\n",
        "- **Strings**\n",
        "  - immutable\n",
        "  - regular strings are unicode with 2-byte char\n",
        "  - declared with single or double quotes\n",
        "  - Can be concatentated using the (overloaded) + sign\n",
        "  - % can be used for special string formatting\n",
        "  ```\n",
        "  print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n",
        "  ```\n",
        "\n",
        "- **Lists**\n",
        "  - mutable \n",
        "  - ordered mixed type items\n",
        "  - declared with [ ]\n",
        "\n",
        "**Slicing** allows you to return a copy of a subsequence:\n",
        "- list-name[first-index(inclusive) : end-index(exclusive)]\n",
        "- can use neg indexing as well \n",
        "- can use implicit indexing by not including first or last index\n",
        "- can select every nth item by adding 3rd argument\n",
        "```\n",
        "t=(23, 'w', 4, (3,4), 'asdf')\n",
        "t[1:4]      # ('w', 4, (3,4))\n",
        "t[1:-1]     # ('w', 4, (3,4))\n",
        "t[1:-1:2]   # every nth item ('w', (3,4))\n",
        "t[:2]       # copy from beginning (23, 'w')\n",
        "t[2:]       # copy to end (4, (3,4), 'asdf')\n",
        "```\n",
        "\n",
        "**List Operations**\n",
        "- list-name.append(element) adds to end of list\n",
        "- list-name.insert(index, element) inserts at that index\n",
        "- list-name.index(element) returns index of first occurrance of that element\n",
        "- list-name.count(element) returns number of occurrances\n",
        "- list-name.remove(element) removes first occurrance\n",
        "- list-name.reverse() reverses list in place\n",
        "- list-name.sort() sorts the list in place\n",
        "- list-name.sort(function) sorts with user-definied comparison\n",
        "- sorted(list-name) returns copy of list that's sorted\n",
        "\n",
        "**String Operations**\n",
        "- string.split(char) returns list of string tokens split by char \n",
        "- \"char\".join(list) pass in list of tokens to join with char operator\n",
        "- string.capitalize()\n",
        "- string.upper()\n",
        "- string.strip(char)\n",
        "***\n",
        "**Dictionaries**\n",
        "- unordered\n",
        "- work by hash table, keys must be immutable\n",
        "- constant avg time to add, lookup, update\n",
        "```\n",
        "d = {'user': 'Jim', 'pw': 1234}\n",
        "d['user']   # lookup by key - 'Jim'\n",
        "d['Jim']    # will return KeyError\n",
        "d['pw'] = 'asdf'  # will replace value for this key\n",
        "```\n",
        "- d.keys() returns list of current keys\n",
        "- d.values() returns list of current values\n",
        "- d.items() returns list of item tuples\n",
        "- defaultdict(type) is type of dict that can automatically initialize non-existent dictionary values. Values set to type specified. Doesn't throw KeyError if a key isn't in the dict - it will just create it.\n",
        "- Counter() dict subclass that counts hashable objects where elements stored as keys and their counts as values. Count of missing element is 0.\n",
        "\n",
        "***\n",
        "**Functions**\n",
        "```\n",
        "def function(args):           # can also define default values for args, which makes them optional when function is called\n",
        "                              # Must put non-default args first, or else get SyntaxError\n",
        "                              # Same with keyword args ex. def func(a,b,c) -> func(c=2,b=1,a=0) or fun(2,a=0,b=1) but not fun(b=1,a=0,2)\n",
        "  (Docstring encased in triple quotes)\n",
        "  ...\n",
        "  return value1, value2       # can return multiple values - will automatically be a tuple\n",
        "```\n",
        "\n",
        "Because Python doesn't specify type for a function's arguments, you can't overload the function like Java (using same function name more than once with diff args). \\\n",
        "You can overload operators using special methods when you initialize the class.\n",
        "- *args keyword lets you accept variable number of non-keyword args to function\n",
        "- **kwargs lets you accept variable number of keyword args to function\n",
        "\n",
        "```\n",
        "def print_all(*args):   # args is tuple of args\n",
        "  print(args)\n",
        "\n",
        "print_all('a','b','c')  # ('a','b','c')\n",
        "lst = ['a','b','c']\n",
        "print_all(*lst)         # ('a','b','c') - iterates through list using star notation\n",
        "\n",
        "def print_keywords(**kwargs):\n",
        "  print(kwargs)\n",
        "\n",
        "print_keywords(first='Jim', last='Smith')   # returns dict {'first': 'Jim', 'last': 'Smith'}\n",
        "my_dict = {'first': 'Jim', 'last': 'Smith'}\n",
        "print_keywords(**my_dict)                   # can pass in dict {'first': 'Jim', 'last': 'Smith'}\n",
        "```\n",
        "\n",
        "Python uses dynamic scope - uses most current value of variables\n",
        "\n",
        "Can use recursion and memoization to achieve dynamic programming:\n",
        "\n",
        ">```\n",
        "calculated = {}   # for memoization\n",
        "def fib(n):\n",
        "  if n == 0: # base case 1\n",
        "    return 0\n",
        "  if n == 1: # base case 2\n",
        "    return 1\n",
        "  elif n in calculated:\n",
        "    return calculated[n]\n",
        "  else: # recursive step\n",
        "    calculated[n] = fib(n-1) + fib(n-2)\n",
        "    return calculated[n]\n",
        "```\n",
        "\n",
        "Functions are first-class objects which can be dynamically created, destroyed, passed to function, returned as value = same rights as a variable. Higher order \\\n",
        "functions take a function as input.\n",
        "\n",
        ">```\n",
        "def compose(f,g,x):\n",
        "  return f(g(x))\n",
        "compose(str,sum,[1,2,3])    # '6'\n",
        "```\n",
        "\n",
        "\n",
        "***\n",
        "**Classes**\n",
        "- to create a class, just use 'class NameofClass:'\n",
        "- can have attributes - variables that apply to all instances\n",
        "- require ```def __init__(self, args):``` to initialize\n",
        "- all functions within class require 'self' as argument\n",
        "- other magic/dunder methods include ```__str__``` which is the constructor function, ```__len__``` which defines how len(obj) works, ```__cmp__``` which defines ==, etc.\n",
        "\n",
        "**Subclasses**\n",
        "- extension of class that allows us to use methods and attributes defined in parent class\n",
        "- to define, put parent class name as argument in first line - ex. class SubClass(ParentClass):\n",
        "- multiple inheritence is supported\n",
        "- must explicitly call the init function of parent class within its init function\n",
        "```\n",
        "class SubClass(ParentClass):\n",
        "  def __init__(self, args):\n",
        "    ParentClass.__init__(self, args)\n",
        "```\n",
        "- you can also override parent class methods by using the same method name in subclass with a new definition. Must explicitly call parent class to execute parent class version of method:\n",
        "parentClass.method(self, args) this is the only time you'll call self as an argument outside of the class definition (only when calling method of an ancestor - don't have to do it for subclass).\n",
        "- Python does not have built in main method - uses ``` if __name__ == '__main__':``` to define main method\n",
        "- Duck typing determines the presence of methods for an object - ex. we can call len() on any class that implements ```__len__``` . We get an AttributeError if we try and call a method that isn't implemented.\n",
        "***\n",
        "**Loops and Iterators**\n",
        "- enumerate generates a tuple where first item is index, second item is item\n",
        "- list comprehensions create a new list - format is [ expression for name in list if filter ]\n",
        "- dictionary and set comprehensions create new dicts and sets and use format { k:v for k,v in list1} and { x for x in list2} respectively\n",
        "\n",
        "**Generators** are iterators created with magic ```__next__``` method using the 'yield' keyword\n",
        "- less code than using iterator\n",
        "- maintains local state\n",
        "- values computed one at a time\n",
        "- saves memory because entire sequence isn't stored\n",
        "- one pass to sum or count items\n",
        "- bad if you need to inspect individual values\n",
        "\n",
        "***\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"immutable\" : \"cannot be modified once created\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "132602a6-3ab1-4e1a-d8da-52f23fc720bc"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Python is a strongly typed language - can't combine incompatible types. You can check type with type(object) or isinstance(object, type). Python is dynamically typed, though, so the types of variables are assigned when the variable  is assigned (or reassigned). Functions have no type signatures. This means type errors are caught at runtime.\n\n****\n\n**Mutability**\n- Strings are immutable. They are created once. Concatenating strings creates a new string object. Checking if 2 strings are equal (==) checks if they point to objects with same value. \"is\" checks whether they point to the same object.\n```\nx = 'foo '\ny = x         # so y == x would resolve as true\nx = x.strip() # creates new object\nprint(x)      # 'foo'\nprint(y)      # 'foo '\n```\n\n- Lists are mutable.\n```\nx=[1,2,3,4]\ny = x\nx.append(5)  # does not create new object\nprint(y)     # [1,2,3,4,5]\nprint(x)     # [1,2,3,4,5]\ny = x[:]     # creates shallow copy of x = new object of same value\n```\n****\n\n**Sequences**\n\nSequence elements are indexed using positive numbers (from the left) or negative numbers (from the right)\n\n- **Tuples**\n  - immutable\n  - items can be mixed types, including collection types\n  - declared with ( )\n\n- **Strings**\n  - immutable\n  - regular strings are unicode with 2-byte char\n  - declared with single or double quotes\n  - Can be concatentated using the (overloaded) + sign\n  - % can be used for special string formatting\n  ```\n  print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n  ```\n\n- **Lists**\n  - mutable \n  - ordered mixed type items\n  - declared with [ ]\n\n**Slicing** allows you to return a copy of a subsequence:\n- list-name[first-index(inclusive) : end-index(exclusive)]\n- can use neg indexing as well \n- can use implicit indexing by not including first or last index\n- can select every nth item by adding 3rd argument\n```\nt=(23, 'w', 4, (3,4), 'asdf')\nt[1:4]      # ('w', 4, (3,4))\nt[1:-1]     # ('w', 4, (3,4))\nt[1:-1:2]   # every nth item ('w', (3,4))\nt[:2]       # copy from beginning (23, 'w')\nt[2:]       # copy to end (4, (3,4), 'asdf')\n```\n\n**List Operations**\n- list-name.append(element) adds to end of list\n- list-name.insert(index, element) inserts at that index\n- list-name.index(element) returns index of first occurrance of that element\n- list-name.count(element) returns number of occurrances\n- list-name.remove(element) removes first occurrance\n- list-name.reverse() reverses list in place\n- list-name.sort() sorts the list in place\n- list-name.sort(function) sorts with user-definied comparison\n- sorted(list-name) returns copy of list that's sorted\n\n**String Operations**\n- string.split(char) returns list of string tokens split by char \n- \"char\".join(list) pass in list of tokens to join with char operator\n- string.capitalize()\n- string.upper()\n- string.strip(char)\n***\n**Dictionaries**\n- unordered\n- work by hash table, keys must be immutable\n- constant avg time to add, lookup, update\n```\nd = {'user': 'Jim', 'pw': 1234}\nd['user']   # lookup by key - 'Jim'\nd['Jim']    # will return KeyError\nd['pw'] = 'asdf'  # will replace value for this key\n```\n- d.keys() returns list of current keys\n- d.values() returns list of current values\n- d.items() returns list of item tuples\n- defaultdict(type) is type of dict that can automatically initialize non-existent dictionary values. Values set to type specified. Doesn't throw KeyError if a key isn't in the dict - it will just create it.\n- Counter() dict subclass that counts hashable objects where elements stored as keys and their counts as values. Count of missing element is 0.\n\n***\n**Functions**\n```\ndef function(args):           # can also define default values for args, which makes them optional when function is called\n                              # Must put non-default args first, or else get SyntaxError\n                              # Same with keyword args ex. def func(a,b,c) -> func(c=2,b=1,a=0) or fun(2,a=0,b=1) but not fun(b=1,a=0,2)\n  (Docstring encased in triple quotes)\n  ...\n  return value1, value2       # can return multiple values - will automatically be a tuple\n```\n\nBecause Python doesn't specify type for a function's arguments, you can't overload the function like Java (using same function name more than once with diff args). You can overload operators using special methods when you initialize the class.\n- *args keyword lets you accept variable number of non-keyword args to function\n- **kwargs lets you accept variable number of keyword args to function\n\n```\ndef print_all(*args):   # args is tuple of args\n  print(args)\n\nprint_all('a','b','c')  # ('a','b','c')\nlst = ['a','b','c']\nprint_all(*lst)         # ('a','b','c') - iterates through list using star notation\n\ndef print_keywords(**kwargs):\n  print(kwargs)\n\nprint_keywords(first='Jim', last='Smith')   # returns dict {'first': 'Jim', 'last': 'Smith'}\nmy_dict = {'first': 'Jim', 'last': 'Smith'}\nprint_keywords(**my_dict)                   # can pass in dict {'first': 'Jim', 'last': 'Smith'}\n```\n\nPython uses dynamic scope - uses most current value of variables\n\nCan use recursion and memoization to achieve dynamic programming:\n\n>```\ncalculated = {}   # for memoization\ndef fib(n):\n  if n == 0: # base case 1\n    return 0\n  if n == 1: # base case 2\n    return 1\n  elif n in calculated:\n    return calculated[n]\n  else: # recursive step\n    calculated[n] = fib(n-1) + fib(n-2)\n    return calculated[n]\n```\n\nFunctions are first-class objects which can be dynamically created, destroyed, passed to function, returned as value = same rights as a variable. Higher order functions take a function as input.\n\n>```\ndef compose(f,g,x):\n  return f(g(x))\ncompose(str,sum,[1,2,3])    # '6'\n```\n\n\n***\n**Classes**\n- to create a class, just use 'class NameofClass:'\n- can have attributes - variables that apply to all instances\n- require ```def __init__(self, args):``` to initialize\n- all functions within class require 'self' as argument\n- other magic/dunder methods include ```__str__``` which is the constructor function, ```__len__``` which defines how len(obj) works, ```__cmp__``` which defines ==, etc.\n\n**Subclasses**\n- extension of class that allows us to use methods and attributes defined in parent class\n- to define, put parent class name as argument in first line - ex. class SubClass(ParentClass):\n- multiple inheritence is supported\n- must explicitly call the init function of parent class within its init function\n```\nclass SubClass(ParentClass):\n  def __init__(self, args):\n    ParentClass.__init__(self, args)\n```\n- you can also override parent class methods by using the same method name in subclass with a new definition. Must explicitly call parent class to execute parent class version of method:\nparentClass.method(self, args) this is the only time you'll call self as an argument outside of the class definition (only when calling method of an ancestor - don't have to do it for subclass).\n- Python does not have built in main method - uses ``` if __name__ == '__main__':``` to define main method\n- Duck typing determines the presence of methods for an object - ex. we can call len() on any class that implements ```__len__``` . We get an AttributeError if we try and call a method that isn't implemented.\n***\n**Loops and Iterators**\n- enumerate generates a tuple where first item is index, second item is item\n- list comprehensions create a new list - format is [ expression for name in list if filter ]\n- dictionary and set comprehensions create new dicts and sets and use format { k:v for k,v in list1} and { x for x in list2} respectively\n\n**Generators** are iterators created with magic ```__next__``` method using the 'yield' keyword\n- less code than using iterator\n- maintains local state\n- values computed one at a time\n- saves memory because entire sequence isn't stored\n- one pass to sum or count items\n- bad if you need to inspect individual values\n\n***\n \n\n## Module 2 Definitions\n* **Immutable** - cannot be modified once created\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "56aa04bb-9476-4fa6-a0f0-faaad8d730fe"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Problem solving agents can plan ahead to find the sequence of actions that will lead to the goal using search. They use atomic representations of the world to do so.\n",
        "\n",
        "Problem solving process:\n",
        "- Goal formulation\n",
        "- Problem formulation: description of actions and states needed to reach goal\n",
        "- Search: agent simulates sequences of actions until it finds one that reaches the goal. It will either discover the solution or discover that there is no solution.\n",
        "- Execution: agent will execute the actions in the solution\n",
        "\n",
        "If environment is fully observable, deterministic, and known, the solution is a fixed sequence of actions where the agent can ignore precepts while executing the actions. This is an open-loop system. If model \\\n",
        "is incomplete, incorrect, or nondeterministic, the agent should use a closed-loop approach.\n",
        "\n",
        "Formal definition of Search Problem includes:\n",
        "- State space: the set of possible states that the environment can be in (possibly infinite)\n",
        "- Initial state: starting state within state space (may be defined or arbitrary)\n",
        "- Goal state(s)\n",
        "- Available actions: the finite set of actions available to the agent that can be executed within a certain state. Each action is **applicable** in this state.\n",
        "- Transition model: describes what each action does. Returns the state that happens from doing an action to a particular state.\n",
        "- Action cost function: numeric cost of applying an action to transition from one state to the resulting state. Should reflect the performance measure.\n",
        "- Path: sequence of actions\n",
        "- Solution: path from initial state to goal state (includes sum of individual action costs)\n",
        "- Optimal solution: solution with lowest path cost\n",
        "\n",
        "Good problem formulation has the right level of detail vs abstraction. The abstraction is valid if it can be elaborated into a solution in the more detailed world. \\\n",
        "Abstraction is useful if carrying out each action in the solution is easier than the original problem (because of lack of detail). We should therefore remove as much detail \\\n",
        "as possible while keeping validity and the ease of carrying out the actions.\n",
        " \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" Sample standardized problems include:\n",
        "\n",
        "- Grid world problem: \n",
        "2D rectangular array of square cells where agents can move from cell to cell (with constraints such as walls, etc)\n",
        "States: says which objects are in which cells (can be infinite state spaces for some math problems)\n",
        "Initial state: any\n",
        "Actions: absolute or egocentric actions or movement\n",
        "Transition model: map actions to change states\n",
        "Goal state(s)\n",
        "Action cost (usually uniform cost)\n",
        "\n",
        "Real world problem examples include:\n",
        "-\tRoute-finding problem\n",
        "States: Location, time (cost may depend on these, so must track history)\n",
        "Initial state: user\\’s initial location\n",
        "Actions: movement from location to location, with changes in time and cost\n",
        "Goal state: user\\’s destination (can have more restrictions than this)\n",
        "Action cost: money, time, distance, etc.\n",
        "-\tTouring problem – set of locations must be visited\n",
        "-\tTraveling Salesperson Problem – touring problem that visits every location on map with a cost less than C or the lowest cost possible\n",
        "-\tVLSI Problem – determine cell layout and channel routing of chips\n",
        "-\tRobot navigation – generalized route finding problem\n",
        "-\tAssembly problems such as automatic assembly sequencing and protein design \n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" Search algorithm takes search problem as input and returns a solution or that there is no solution.\n",
        "\n",
        "Search tree can use this to model problem where each node in tree corresponds to a state in the state space and edges correspond to actions. Root of tree is initial state. Each node has a unique path back to root. \\ \n",
        "When we expand nodes, we consider available actions for state and use result function to see where those actions lead, generating a child (successor) node for each resulting state.\n",
        "\n",
        "**Best-first search**: choose a node with a min value of an evaluation function. Each iteration, we choose another frontier node with min f(n) value. If it is a goal state, we return, else expand the node and \\\n",
        "create the child nodes. Each child node is added to frontier if it is unreached or else readded if it is now reached with a lower path cost. Algorithm returns failure or node that is part of path to goal.\n",
        "\n",
        "**Node** in tree represented as data structure with four components:\n",
        "- state: the state that the node represents\n",
        "- parent: the node that generated this node\n",
        "- action: action applied to parent node to generate this node\n",
        "- path cost: total cost of path from initial state to this node\n",
        "\n",
        "We can follow the parent pointers to recover states and actions backwards. From the goal node, this will give us the solution.\n",
        "\n",
        "**Frontier** uses a queue data structure with four operations:\n",
        "- is empty: return true if no nodes in frontier\n",
        "- pop: removes top node and returns it\n",
        "- top: returns top node without removing it\n",
        "- add: inserts node into the queue\n",
        "\n",
        "Three types of queues are used in search algorithms:\n",
        "- **priority queue**: pops node with min cost according to f(n). Used in best-first search\n",
        "- **FIFO queue**. Used in breadth-first search\n",
        "- **LIFO queue** aka **stack**. Used in depth-first search\n",
        "\n",
        "Cycles can cause search trees to become infinite, so we need to be able to recognize and remove redundant paths (as long as table of reached states fits in memory), unless we are working with a problem where cycles and redundant paths are rare or impossible. \\\n",
        "In these problems, not checking reached states or redundant paths means we save memory space. If a search algorithm checks for redundant paths, it is a graph search (ex. BFS). If it does not check, it is tree-like. \\\n",
        "Tree-like searches use less memory but run slower since they might check redundant paths. We can check for cycles but not redundant paths overall as a compromise.\n",
        "\n",
        "Search algorithms are complete if they are systematic in the way they explore the state space (finite or infinite). Time and space complexity are evaluated with respect to the problem difficulty. Can be measured in terms of the **depth** \\\n",
        "of the number of actions in the optimal solution, the max number of actions in any path, and the **branching factor** of each node.\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed search algorithms don't know how close a state is to the goal. They can only solve the smallest instances of exponential-complexity search problems.\n",
        "\n",
        "**Breadth-first**: when all actions have same cost\n",
        "- complete (systematic) even on infinite search spaces\n",
        "- f(n) is depth of node\n",
        "- check shallowest nodes first\n",
        "- reached is set of states rather than nodes because we always find best paths first\n",
        "- early goal test when node generated instead of popped from queue (late goal test like best-first search)\n",
        "- always finds shortest path\n",
        "- space and time: $O(b^d)$\n",
        "- memory a bigger problem than time\n",
        "\n",
        "**Djikstra's Algorithm** / **Uniform Cost**: when actions have different costs by considering all paths systematically in order of increasing cost\n",
        "- algorithm is Best First Search where f(n) is path cost\n",
        "- tests for goal when expanding (lowest cost) node from the frontier\n",
        "- space and time: $O(b^{1+\\lfloor C* / e \\rfloor })$ where C* is the cost of optimal solution and e is the lower bound of each action cost\n",
        "- if all action costs the same, UCS is similar to BFS: $O(b^{d+1})$\n",
        "- complete, cost-optimal\n",
        "\n",
        "**Depth-first** expands deepest node first\n",
        "- not cost optimal: returns first solution, not always cheapest\n",
        "- efficient, complete in finite tree-like spaces\n",
        "- less efficient in acyclic state spaces (still complete)\n",
        "- not systematic or complete in infinite state spaces (even without cycles)\n",
        "- use DFS in tree-like search because it has lower memory needs (small frontier, no tracking reached states) - only $O(bm)$ where b=branching factor and m=max depth\n",
        "- used for constraint satisfaction, propositional satisfiability, logic programming\n",
        "\n",
        "**Backtracking**: variant of DFS, even less memory\n",
        "- generate one successor at a time\n",
        "- partially-expanded nodes track which to generate next\n",
        "- successors generated by modifying current state rather than saving as brand new state\n",
        "- space: $O(m)$\n",
        "- can use efficient data structure for states on current path to check for cycles: $O(1)$ time\n",
        "- must be able to undo each action\n",
        "- used for problems with large state descriptions\n",
        "\n",
        "**Depth-limited** explore to depth limit $l$\n",
        "- time: $O(b^l)$\n",
        "- space: $O(bl)$\n",
        "- more efficient if we know what $l$ should be (diameter)\n",
        "\n",
        "**Iterative deepening** tries all values of $l$ until solution/failure found\n",
        "- space: $O(bd)$ (solution); $O(bm)$ (finite state no solution)\n",
        "- use for problems where all actions have same cost (like BFS)\n",
        "- complete on finite, acyclic state spaces\n",
        "- complete on any finite space if we check for cycles\n",
        "- time: $O(b^d)$ (solution); $O(b^m)$ (no solution)\n",
        "- final nodes generated once; upper nodes generated each time run (but fewer nodes at top)\n",
        "\n",
        "**Bidirectional** searches from initial state and back from goal state\n",
        "- two frontiers, two tables of reached states\n",
        "- solution when frontiers collide\n",
        "- expands min f(n) value node on either frontier\n",
        "- if f(n) is path cost it is bidirectional UCS and first solution will be best\n",
        "- diff f(n) don't guarantee first solution is optimal\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Comparing graph search and tree search:\n",
        "```\n",
        "function TREE-SEARCH(problem) returns solution or failure\n",
        "      initialize the frontier with initial problem state\n",
        "      loop do:\n",
        "          if frontier is empty, return failure\n",
        "          otherwise:\n",
        "              pop leaf node from frontier\n",
        "              if it is the goal state, return solution\n",
        "              else expand the node and add successors to frontier\n",
        "\n",
        "function GRAPH-SEARCH(problem) returns solution or failure\n",
        "      initialize frontier with initial problem state\n",
        "      initialize explored set as empty (** this is different)\n",
        "      loop do\n",
        "          if frontier is empty, return failure\n",
        "          otherwise:\n",
        "              pop leaf from frontier\n",
        "              if it is the goal state, return solution\n",
        "              add node to explored set (** this is different)\n",
        "              expand the node and add successors to frontier\n",
        "                only if not already in frontier or explored set (handles repeated states)\n",
        "\n",
        "```\n",
        "Repeated states can make a problem exponential, even if it was previously linear. Graph search helps by checking for repeated states. Exponential complexity uninformed search cannot be solved unless they are very small because \\\n",
        "memory problems becomes an issue (more than time complexity).\n",
        "\n",
        "Uninformed search is aka \"blind search\" because the agent can only use information from the problem definition. The agent is unable to evaluate non-goal nodes as to being better than others.\n",
        "\n",
        "```\n",
        "function BREADTH-FIRST-SEARCH (problem) returns solution or failure\n",
        "    node (node with state = initial state of problem. path cost = 0)\n",
        "    perform goal test on state, return solution if true\n",
        "    frontier (FIFO containing initial node)\n",
        "    explored (empty set)\n",
        "    loop do:\n",
        "        if frontier empty, return failure\n",
        "        pop (shallowest) node from frontier (this determines search strategy)\n",
        "        (if this were Uniform Cost Search, there would be a goal test here)\n",
        "        add node to explored\n",
        "        for each legal action possible do:\n",
        "              if successor state not in explored or frontier then\n",
        "                  if goal test of this state = true, return solution\n",
        "                  otherwise add child node to the frontier (note: after testing for goal)\n",
        "```\n",
        "\n",
        "DFS essentially the same but uses LIFO queue. DFS is best if space is limited, solutions can have long paths and wrong paths are caught quickly, search can be fine-tuned quickly. \\\n",
        "BFS is better if there could be infinite paths, solutions could have short paths, and unpromising paths can be quickly abandoned.\n",
        "\n",
        "Best of both could be:\n",
        "- Depth-limited search (depth limit $l$ - eliminates possible infinite paths). If $l=d$, it is optimal, otherwise $l<d$ it is incomplete, $l>d$ it is not optimal. Space is $O(bl)$ which is good.\n",
        "- Iterative deepening search (DLS with increasing $l$) - this is complete and optimal (if step cost is 1), space complexity is good ($O(bd)$ - better than BFS) but space complexity is asymptotic ($O(b^d)$)\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",
        "\"open-loop system\" : \"loop between agent and environment broken by ignoring precepts\",\n",
        "\"closed-loop approach\" : \"branching strategy that recommends different actions based on precepts\",\n",
        "\"model\" : \"abstract mathematical description\",\n",
        "\"abstraction\" : \"process of removing detail from a representation\",\n",
        "\"standardized problem\" : \"illustrates or exercises various problem solving methods such that it is suitable as a benchmark\",\n",
        "\"real world problem\" : \"has ideosyncratic solutions that people actually use\",\n",
        "\"frontier\" : \"set of unexpanded nodes in search tree that separates the reached from the unreached regions\",\n",
        "\"completeness\" : \"quality of algorithm guaranteed to correctly find solution or report lack of one\",\n",
        "\"cost optimality\": \"quality of algorithm that correctly finds a solution with lowest path cost\",\n",
        "\"time complexity\" : \"length of time (or number of states) required to find a solution\",\n",
        "\"space complexity\" : \"amount of memory needed to perform search\",\n",
        "\"diameter\" : \"describes max number of steps needed to reach any state within state space\",\n",
        "\"best first search\" : \"uses evaluation function to select nodes to expand\",\n",
        "\"breadth first search\" : \"complete and optimal algorithm that expands shallowest nodes first and has exponential space complexity\",\n",
        "\"uniform cost search\" : \"optimal algorithm that expands node with lowest path cost\",\n",
        "\"depth first search\" : \"algorithm that expands deepest unexplored node first. Not complete or optimal. Has linear space complexity.\",\n",
        "\"depth limited search\" : \"depth first search with a limit on explored depth\",\n",
        "\"iterative deepening search\" : \"depth limited search with increasing limits on depth. Has linear space complexity, same time complexity as BFS. Complete and optimal.\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_4))"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 447\n",
            "The length in characters is 2999\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "c346581c-467b-4e0f-9032-83d2c19e1b01"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem solving agents can plan ahead to find the sequence of actions that will lead to the goal using search. They use atomic representations of the world to do so.\n\nProblem solving process:\n- Goal formulation\n- Problem formulation: description of actions and states needed to reach goal\n- Search: agent simulates sequences of actions until it finds one that reaches the goal. It will either discover the solution or discover that there is no solution.\n- Execution: agent will execute the actions in the solution\n\nIf environment is fully observable, deterministic, and known, the solution is a fixed sequence of actions where the agent can ignore precepts while executing the actions. This is an open-loop system. If model is incomplete, incorrect, or nondeterministic, the agent should use a closed-loop approach.\n\nFormal definition of Search Problem includes:\n- State space: the set of possible states that the environment can be in (possibly infinite)\n- Initial state: starting state within state space (may be defined or arbitrary)\n- Goal state(s)\n- Available actions: the finite set of actions available to the agent that can be executed within a certain state. Each action is **applicable** in this state.\n- Transition model: describes what each action does. Returns the state that happens from doing an action to a particular state.\n- Action cost function: numeric cost of applying an action to transition from one state to the resulting state. Should reflect the performance measure.\n- Path: sequence of actions\n- Solution: path from initial state to goal state (includes sum of individual action costs)\n- Optimal solution: solution with lowest path cost\n\nGood problem formulation has the right level of detail vs abstraction. The abstraction is valid if it can be elaborated into a solution in the more detailed world. Abstraction is useful if carrying out each action in the solution is easier than the original problem (because of lack of detail). We should therefore remove as much detail as possible while keeping validity and the ease of carrying out the actions.\n \n\n## AIMA Chapter 3.2 Example Problems\n Sample standardized problems include:\n\n- Grid world problem: \n2D rectangular array of square cells where agents can move from cell to cell (with constraints such as walls, etc)\nStates: says which objects are in which cells (can be infinite state spaces for some math problems)\nInitial state: any\nActions: absolute or egocentric actions or movement\nTransition model: map actions to change states\nGoal state(s)\nAction cost (usually uniform cost)\n\nReal world problem examples include:\n-\tRoute-finding problem\nStates: Location, time (cost may depend on these, so must track history)\nInitial state: user\\’s initial location\nActions: movement from location to location, with changes in time and cost\nGoal state: user\\’s destination (can have more restrictions than this)\nAction cost: money, time, distance, etc.\n-\tTouring problem – set of locations must be visited\n-\tTraveling Salesperson Problem – touring problem that visits every location on map with a cost less than C or the lowest cost possible\n-\tVLSI Problem – determine cell layout and channel routing of chips\n-\tRobot navigation – generalized route finding problem\n-\tAssembly problems such as automatic assembly sequencing and protein design \n\n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithm takes search problem as input and returns a solution or that there is no solution.\n\nSearch tree can use this to model problem where each node in tree corresponds to a state in the state space and edges correspond to actions. Root of tree is initial state. Each node has a unique path back to root. \\ \nWhen we expand nodes, we consider available actions for state and use result function to see where those actions lead, generating a child (successor) node for each resulting state.\n\n**Best-first search**: choose a node with a min value of an evaluation function. Each iteration, we choose another frontier node with min f(n) value. If it is a goal state, we return, else expand the node and create the child nodes. Each child node is added to frontier if it is unreached or else readded if it is now reached with a lower path cost. Algorithm returns failure or node that is part of path to goal.\n\n**Node** in tree represented as data structure with four components:\n- state: the state that the node represents\n- parent: the node that generated this node\n- action: action applied to parent node to generate this node\n- path cost: total cost of path from initial state to this node\n\nWe can follow the parent pointers to recover states and actions backwards. From the goal node, this will give us the solution.\n\n**Frontier** uses a queue data structure with four operations:\n- is empty: return true if no nodes in frontier\n- pop: removes top node and returns it\n- top: returns top node without removing it\n- add: inserts node into the queue\n\nThree types of queues are used in search algorithms:\n- **priority queue**: pops node with min cost according to f(n). Used in best-first search\n- **FIFO queue**. Used in breadth-first search\n- **LIFO queue** aka **stack**. Used in depth-first search\n\nCycles can cause search trees to become infinite, so we need to be able to recognize and remove redundant paths (as long as table of reached states fits in memory), unless we are working with a problem where cycles and redundant paths are rare or impossible. In these problems, not checking reached states or redundant paths means we save memory space. If a search algorithm checks for redundant paths, it is a graph search (ex. BFS). If it does not check, it is tree-like. Tree-like searches use less memory but run slower since they might check redundant paths. We can check for cycles but not redundant paths overall as a compromise.\n\nSearch algorithms are complete if they are systematic in the way they explore the state space (finite or infinite). Time and space complexity are evaluated with respect to the problem difficulty. Can be measured in terms of the **depth** of the number of actions in the optimal solution, the max number of actions in any path, and the **branching factor** of each node.\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search algorithms don't know how close a state is to the goal. They can only solve the smallest instances of exponential-complexity search problems.\n\n**Breadth-first**: when all actions have same cost\n- complete (systematic) even on infinite search spaces\n- f(n) is depth of node\n- check shallowest nodes first\n- reached is set of states rather than nodes because we always find best paths first\n- early goal test when node generated instead of popped from queue (late goal test like best-first search)\n- always finds shortest path\n- space and time: $O(b^d)$\n- memory a bigger problem than time\n\n**Djikstra's Algorithm** / **Uniform Cost**: when actions have different costs by considering all paths systematically in order of increasing cost\n- algorithm is Best First Search where f(n) is path cost\n- tests for goal when expanding (lowest cost) node from the frontier\n- space and time: $O(b^{1+\\lfloor C* / e \rfloor })$ where C* is the cost of optimal solution and e is the lower bound of each action cost\n- if all action costs the same, UCS is similar to BFS: $O(b^{d+1})$\n- complete, cost-optimal\n\n**Depth-first** expands deepest node first\n- not cost optimal: returns first solution, not always cheapest\n- efficient, complete in finite tree-like spaces\n- less efficient in acyclic state spaces (still complete)\n- not systematic or complete in infinite state spaces (even without cycles)\n- use DFS in tree-like search because it has lower memory needs (small frontier, no tracking reached states) - only $O(bm)$ where b=branching factor and m=max depth\n- used for constraint satisfaction, propositional satisfiability, logic programming\n\n**Backtracking**: variant of DFS, even less memory\n- generate one successor at a time\n- partially-expanded nodes track which to generate next\n- successors generated by modifying current state rather than saving as brand new state\n- space: $O(m)$\n- can use efficient data structure for states on current path to check for cycles: $O(1)$ time\n- must be able to undo each action\n- used for problems with large state descriptions\n\n**Depth-limited** explore to depth limit $l$\n- time: $O(b^l)$\n- space: $O(bl)$\n- more efficient if we know what $l$ should be (diameter)\n\n**Iterative deepening** tries all values of $l$ until solution/failure found\n- space: $O(bd)$ (solution); $O(bm)$ (finite state no solution)\n- use for problems where all actions have same cost (like BFS)\n- complete on finite, acyclic state spaces\n- complete on any finite space if we check for cycles\n- time: $O(b^d)$ (solution); $O(b^m)$ (no solution)\n- final nodes generated once; upper nodes generated each time run (but fewer nodes at top)\n\n**Bidirectional** searches from initial state and back from goal state\n- two frontiers, two tables of reached states\n- solution when frontiers collide\n- expands min f(n) value node on either frontier\n- if f(n) is path cost it is bidirectional UCS and first solution will be best\n- diff f(n) don't guarantee first solution is optimal\n \n \n\n## Module 3 Lecture Notes\n Comparing graph search and tree search:\n```\nfunction TREE-SEARCH(problem) returns solution or failure\n      initialize the frontier with initial problem state\n      loop do:\n          if frontier is empty, return failure\n          otherwise:\n              pop leaf node from frontier\n              if it is the goal state, return solution\n              else expand the node and add successors to frontier\n\nfunction GRAPH-SEARCH(problem) returns solution or failure\n      initialize frontier with initial problem state\n      initialize explored set as empty (** this is different)\n      loop do\n          if frontier is empty, return failure\n          otherwise:\n              pop leaf from frontier\n              if it is the goal state, return solution\n              add node to explored set (** this is different)\n              expand the node and add successors to frontier\n                only if not already in frontier or explored set (handles repeated states)\n\n```\nRepeated states can make a problem exponential, even if it was previously linear. Graph search helps by checking for repeated states. Exponential complexity uninformed search cannot be solved unless they are very small because memory problems becomes an issue (more than time complexity).\n\nUninformed search is aka \"blind search\" because the agent can only use information from the problem definition. The agent is unable to evaluate non-goal nodes as to being better than others.\n\n```\nfunction BREADTH-FIRST-SEARCH (problem) returns solution or failure\n    node (node with state = initial state of problem. path cost = 0)\n    perform goal test on state, return solution if true\n    frontier (FIFO containing initial node)\n    explored (empty set)\n    loop do:\n        if frontier empty, return failure\n        pop (shallowest) node from frontier (this determines search strategy)\n        (if this were Uniform Cost Search, there would be a goal test here)\n        add node to explored\n        for each legal action possible do:\n              if successor state not in explored or frontier then\n                  if goal test of this state = true, return solution\n                  otherwise add child node to the frontier (note: after testing for goal)\n```\n\nDFS essentially the same but uses LIFO queue. DFS is best if space is limited, solutions can have long paths and wrong paths are caught quickly, search can be fine-tuned quickly. BFS is better if there could be infinite paths, solutions could have short paths, and unpromising paths can be quickly abandoned.\n\nBest of both could be:\n- Depth-limited search (depth limit $l$ - eliminates possible infinite paths). If $l=d$, it is optimal, otherwise $l<d$ it is incomplete, $l>d$ it is not optimal. Space is $O(bl)$ which is good.\n- Iterative deepening search (DLS with increasing $l$) - this is complete and optimal (if step cost is 1), space complexity is good ($O(bd)$ - better than BFS) but space complexity is asymptotic ($O(b^d)$)\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop system** - loop between agent and environment broken by ignoring precepts\n* **Closed-loop approach** - branching strategy that recommends different actions based on precepts\n* **Model** - abstract mathematical description\n* **Abstraction** - process of removing detail from a representation\n* **Standardized problem** - illustrates or exercises various problem solving methods such that it is suitable as a benchmark\n* **Real world problem** - has ideosyncratic solutions that people actually use\n* **Frontier** - set of unexpanded nodes in search tree that separates the reached from the unreached regions\n* **Completeness** - quality of algorithm guaranteed to correctly find solution or report lack of one\n* **Cost optimality** - quality of algorithm that correctly finds a solution with lowest path cost\n* **Time complexity** - length of time (or number of states) required to find a solution\n* **Space complexity** - amount of memory needed to perform search\n* **Diameter** - describes max number of steps needed to reach any state within state space\n* **Best first search** - uses evaluation function to select nodes to expand\n* **Breadth first search** - complete and optimal algorithm that expands shallowest nodes first and has exponential space complexity\n* **Uniform cost search** - optimal algorithm that expands node with lowest path cost\n* **Depth first search** - algorithm that expands deepest unexplored node first. Not complete or optimal. Has linear space complexity.\n* **Depth limited search** - depth first search with a limit on explored depth\n* **Iterative deepening search** - depth limited search with increasing limits on depth. Has linear space complexity, same time complexity as BFS. Complete and optimal.\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "60420719-7a6a-4bb0-9d3f-45a35902f9cc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed search can be more efficient than uninformed search. Heuristic function used to give hints about goal location.\n",
        "\n",
        "$h(n)$: estimated cost of cheapest path from current node $n$ to goal\n",
        "\n",
        "**Greedy Best First**\n",
        "- expands node with lowest $h(n)$ value (i.e. node seemingly closest to goal)\n",
        "- $f(n) = h(n)$\n",
        "- complete in finite search spaces (but not in infinite)\n",
        "- time and space: $O(|V|)$, can be reduced to $O(bm)$ with good heuristic\n",
        "\n",
        "**A Star**\n",
        "- best first that uses $f(n) = g(n) + h(n)$, where $g(n)$ is actual path cost to current node $n$ and $h(n)$ is estimated path cost from $n$ to goal\n",
        "- complete\n",
        "- expands node in frontier with lowest $f(n)$ value\n",
        "- cost-optimality depends on admissable and consistent heuristic\n",
        "- consistent heuristic means we will always reach a state via an optimal path first, we never have to re-add states to the frontier\n",
        "- if heuristic is inadmissible, cost-optimality is not guaranteed\n",
        "- efficient by pruning nodes not part of optimal solution\n",
        "\n",
        "Consistent heuristic: $h(n) \\leq c(n,a,n\\') + (h(n'))$. Always admissible, but not vice-versa. \n",
        "\n",
        "If $C*$ represents optimal solution path cost:\n",
        "- A* surely expands all nodes from initial state where every node's $f(n) < C*$\n",
        "- A* might expand nodes where $f(n) = C*$ (on the global contour)\n",
        "- A* expands no nodes where $f(n) > C*$\n",
        "\n",
        "Problem for A* is it expands a lot of nodes so reducing nodes may mean accepting suboptimal, satisficing solutions (ex. using inadmissable/overestimating heuristic that may be more accurate)\n",
        "\n",
        "**Weighted A* Search**\n",
        "- heuristic weighted more: $f(n) = g(n) + W * h(n)$ for some $W > 1$ (ex detour index)\n",
        "- solution cost somewhere between C* and $W * $C* (closer to optimal in practice)\n",
        "\n",
        "Other suboptimal search:\n",
        "- **bounded suboptimal**: solution within constant factor W of optimal cost (ex. weighted A*)\n",
        "- **bounded cost**: solution cost less than some constant C\n",
        "- **unbounded cost**: any cost solution is ok if found quickly (ex speedy search)\n",
        "\n",
        "Memory requirements determined by size of frontier and size of reached states.\n",
        "\n",
        "Memory-conserving search:\n",
        "- **beam search**\n",
        "- **iterative deepening A** doesn't keep all reached states in memory, but extra cost of visiting states multiple times. \n",
        "Used for programs that don't fit in memory\n",
        "Cutoff is $f$-cost ($g+h$) at each iteration\n",
        "Next cutoff value is lowest $f$ cost node just beyond previous cut-off\n",
        "- **Recursive best first search** BFS but with linear space. Tracks alt paths available from ancestors of current node - may backtrack and replace nodes with backed up values. \n",
        "More efficient than IDA*\n",
        "Optimal if $h(n)$ admissable\n",
        "\n",
        "IDA* and RBFS use too little memory and may explore same states multiple times\n",
        "\n",
        "**Memory bounded A** and **Simplified MA** use all available memory. SMA expands newest best leaf and deletes oldest worst leaf. Complete if reachable solution.\n",
        "\n",
        "**Bidirectional heuristic search** must consider surely expanded pairs of nodes. Sometimes more efficient with avg heuristic.\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "Judging quality of heuristic:\n",
        "- effective branching factor b* = branching factor a tree of uniform depth $d$ would have to contain $N+1$ nodes, where $N$ is the total number of nodes generated and solution depth $d$\n",
        "- well-designed heuristics have a b* close to 1\n",
        "\n",
        "Domination:\n",
        "- If h2 dominates h1: $h2(n) \\geq h1(n)$ and using h2 will never expand more nodes than using h1. h1 will always expand all nodes that h2 does, plus possibly others. Usually better to use \\\n",
        "heuristic with higher values as long as it is consistent and is not slow computationally.\n",
        "\n",
        "Using a relaxed version of a problem is one way to find a heuristic. Relaxed problem adds edges to state space graph, and optimal solution in the original problem is still a \\\n",
        "solution in the relaxed problem. Relaxed problem may allow us to find shortcuts that are better, so the cost of these optimal solutions becomes an admissible heuristic for the original problem. \\\n",
        "The heuristics are also consistent because they still obey the triangle ineequality.\n",
        "\n",
        "We can use composite heuristics when we have trouble distinguishing between the quality of several heuristics: different ones are used on different nodes (although this can be slower computationally).\n",
        "$h(n) =$ max {$h1(n),…, hk(n)$}\n",
        "\n",
        "We can generate heuristics from the solution of a subproblem within the problem.\n",
        "\n",
        "For route-finding search, we can choose landmark points (pivots/anchors) and precompute the optimal path between every vertex in the graph and the landmark. Can then compute inadmissable (overestimates cost to goal if optimal path doesn't go through landmark) \\\n",
        "heuristic from current node landmark to goal. We can also add shortcuts (artifical graph edges) that describe optimal multi-action paths.\n",
        "\n",
        "We can make the landmark search admissable by turning it into a differential heuristic. Also landmarks should be spread out so they are not super close to each other.\n",
        "\n",
        "Agents can learn to search better. For example, an agent can use a metalevel search space to learn to avoid non-helpful states. The overall goal is to minimize the total cost of problem solving, even \\\n",
        "if there have to be tradeoffs between computational cost and path cost.\n",
        "\n",
        "Machine learning can also be achieved with experience, although heuristics generated this way may not be admissible. We can include features of the state that help predict the heuristic value to improve this.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform Cost Search is an extension of BFS where we expand the node with the lowest path cost. The frontier is a priority queue ordered by the lowest path cost to get to that node ($g(n)$). \\\n",
        "Different from BFS because it tests if a node is a goal state when it's popped from the queue, not when it's added to the frontier. If a better path to that node is found, it will update the node on the frontier (so \\\n",
        "that's why goal check is after it comes out of the queue - so you know you have the lowest-cost version). We can thus prioritize which paths to explore. Uniform Cost Search is also called Dijkstra's Algorithm. It is complete and optimal.\n",
        "\n",
        "Best-first search improves on this by using an evaluation function to select the node to pop off the queue. The evaluation function $f(n)$ includes an estimate of the distance between this node and the goal. So, Best-first search is UCS where $f(n)$ replaces $g(n)$. \\\n",
        "Heuristic function $h(n)$ estimates the distance between a state $n$ and the goal. Heuristics are helpful, but not always exact or correct.\n",
        "\n",
        "Greedy best-first search expands node that is estimated to be closest to the goal, ignoring $g(n)$, which is the cost to get to $n$. So $f(n) = h(n)$. It is not optimal (not guaranteed to find lowest-cost) or complete (can get stuck in loops).\n",
        "```\n",
        "function GREEDY-BEST-FIRST(problem, heuristic) returns solution or failure\n",
        "    frontier (priority queue)\n",
        "    initial node put into frontier\n",
        "    came_from (empty set)\n",
        "    while frontier is not empty:\n",
        "        pop node from queue\n",
        "        goal-test node - if goal, return solution\n",
        "        else for each neighbor not in came_from:\n",
        "              set node priority to h(n)\n",
        "              put node in frontier\n",
        "              put node in came_from\n",
        "\n",
        "```\n",
        "A* Search is another form of best-first search that avoids exploring expensive paths and focus instead on most promising. It's evaluation function is: $f(n) = g(n) + h(n)$, where $g(n)$ is the actual cost to reach current node, \\\n",
        "$h(n)$ is the estimated cost to get from the current node to the goal, so $f(n)$ is the total cost of the path from the initial state through the current node to the goal. Its frontier is also a monotonically increasing priority queue. \\\n",
        "- Optimal with an admissible heuristic\n",
        "- basically UCS (distance from start to current) + Greedy best-first (distance from current to goal)\n",
        "\n",
        "Admissible heuristic never overestimates the cost to reach the goal (optimistic). Inadmissible heuristics tend to push the good plans too far down the queue.\n",
        "\n",
        "Relaxed problem is one with fewer restrictions than the original. The cost of an optimal solution for a relaxed problem is an admissible heuristic for the original problem. Ex. True map travel distance vs Manhattan distance\n",
        "\n",
        "Dominance means one heuristic is better than (dominates) another. If $h_2(n) \\geq h_1(n)$ for all $n$ and both are admissible:\n",
        "- $h_2$ dominates $h_1$\n",
        "- $h_2$ has a higher cost but is still optimistic\n",
        "- $h_2$ is  optimistic and **more accurate** than $h_1$ and is better for search\n",
        "\n",
        "Best heuristic = the truth ( h*(n) ): called the Oracle heuristic, is unachievable, dominates all other heuristics\n",
        "Worst heuristic = 0 (aka we're here): dominated by all other heuristics, basically uniform cost search\n",
        "So an admissible heuristic is 0 <= h(n) <= h*(n)\n",
        "\n",
        "A* is used in path/route planning (maps), video games, robot motion planning, resource planning\n",
        "\n",
        "```\n",
        "function A-STAR-SEARCH(problem, heuristic) returns solution or failure\n",
        "    frontier (priority queue)\n",
        "    put starting node in the frontier\n",
        "    came_from (empty dict)\n",
        "    cost_so_far (empty_dict)\n",
        "    came_from[start] = 0\n",
        "    cost_so_far[start] = 0\n",
        "\n",
        "    while frontier is not empty:\n",
        "        pop node from queue\n",
        "        goal-check node, if goal then return solution\n",
        "\n",
        "        else for each neighbor of current node:\n",
        "            set new_cost = cost_so_far[current] + graph.cost[current, next]\n",
        "            if next not in cost_so_far or new_cost is less than cost_so_far[next]:\n",
        "                set cost_so_far[next] to new_cost\n",
        "                set node priority to new_cost + heuristic(goal, next)\n",
        "                add node to frontier\n",
        "                came_from[next] = current node\n",
        "```\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"uses heauristics: hints specific to the domain about the location of goals\",\n",
        "\"heuristic function\" : \"gives estimated cost of cheapest path from current node $n$ to goal state\",\n",
        "\"admissible heuristic\" : \"optimistic heuristic that always underestimates cost to reach goal\",\n",
        "\"consistency\" : \"When going from one node to another, estimated step cost never exceeds actual step cost. Based on triangle inequality\",\n",
        "\"triangle inequality\" : \"one side of a triangle cannot be longer than sum of other sides\",\n",
        "\"monotonic\" : \"never decreases\",\n",
        "\"optimally efficient\" : \"means any algorithm with same heuristic will expand same surely expanded nodes as A*\",\n",
        "\"greedy best-first search\" : \"expands nodes with minimal heuristic cost. Not optimal but is usually efficient.\",\n",
        "\"A* search\" : \"expands nodes with minimal actual + estimated costs. Complete and optimal with admissible heuristic but has space complexity problems\",\n",
        "\"bidirectional A* search\" : \"A* search that measures from start and goal. Can be more efficient than A*\",\n",
        "\"front-to-end\" : \"heuristic that measures distance to goal or distance to start\",\n",
        "\"front-to-front\" : \"heuristic that measures distance to other frontier\",\n",
        "\"backed-up value\" : \"best $f$-value of child nodes\",\n",
        "\"reference count\" : \"number of times state has been reached\",\n",
        "\"IDA*\": \"iterative deepening version of A* that addresses its space complexity problems\",\n",
        "\"RBFS\" : \"optimal variation of best first search that uses limited memory\",\n",
        "\"SMA*\" : \"optimal variation of A*  that uses limited memory and can solve problems when A* runs out of memory\",\n",
        "\"speedy search\" : \"greedy best first with $h(n)$ equal to the estimated number of actions to reach goal\",\n",
        "\"beam search\" : \"memory-conserving incomplete and suboptimal search that limits size of frontier and runs faster than complete searches\",\n",
        "\"weighted A* search\" : \"uses weighted heuristic to focus on goal, expanding fewer nodes. Tradeoff is optimality.\",\n",
        "\"domination\" : \"when one heuristic always outperforms and is more efficient than another\",\n",
        "\"relaxed problem\" : \"version of a problem with fewer restrictions. Creates a supergraph of original problem.\",\n",
        "\"pattern database\" : \"stores all solution costs for subproblem instances\",\n",
        "\"disjoint pattern databases\" : \"use added costs of disjoint solutions to get lower bound on cost of solving entire problem\",\n",
        "\"metalevel state space\" : \"contains each state of the internal state of a program searching a regular state space\",\n",
        "\"metalevel learning\" : \"algorithm that uses metalevel state space to learn to avoid unpromising search trees\"\n",
        "}\n",
        "\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_6.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_6))\n"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 376\n",
            "The length in characters is 2378\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "7c28c0eb-94ad-4d27-dd6f-5ed0476c49f8"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed search can be more efficient than uninformed search. Heuristic function used to give hints about goal location.\n\n$h(n)$: estimated cost of cheapest path from current node $n$ to goal\n\n**Greedy Best First**\n- expands node with lowest $h(n)$ value (i.e. node seemingly closest to goal)\n- $f(n) = h(n)$\n- complete in finite search spaces (but not in infinite)\n- time and space: $O(|V|)$, can be reduced to $O(bm)$ with good heuristic\n\n**A Star**\n- best first that uses $f(n) = g(n) + h(n)$, where $g(n)$ is actual path cost to current node $n$ and $h(n)$ is estimated path cost from $n$ to goal\n- complete\n- expands node in frontier with lowest $f(n)$ value\n- cost-optimality depends on admissable and consistent heuristic\n- consistent heuristic means we will always reach a state via an optimal path first, we never have to re-add states to the frontier\n- if heuristic is inadmissible, cost-optimality is not guaranteed\n- efficient by pruning nodes not part of optimal solution\n\nConsistent heuristic: $h(n) \\leq c(n,a,n') + (h(n'))$. Always admissible, but not vice-versa. \n\nIf $C*$ represents optimal solution path cost:\n- A* surely expands all nodes from initial state where every node's $f(n) < C*$\n- A* might expand nodes where $f(n) = C*$ (on the global contour)\n- A* expands no nodes where $f(n) > C*$\n\nProblem for A* is it expands a lot of nodes so reducing nodes may mean accepting suboptimal, satisficing solutions (ex. using inadmissable/overestimating heuristic that may be more accurate)\n\n**Weighted A* Search**\n- heuristic weighted more: $f(n) = g(n) + W * h(n)$ for some $W > 1$ (ex detour index)\n- solution cost somewhere between C* and $W * $C* (closer to optimal in practice)\n\nOther suboptimal search:\n- **bounded suboptimal**: solution within constant factor W of optimal cost (ex. weighted A*)\n- **bounded cost**: solution cost less than some constant C\n- **unbounded cost**: any cost solution is ok if found quickly (ex speedy search)\n\nMemory requirements determined by size of frontier and size of reached states.\n\nMemory-conserving search:\n- **beam search**\n- **iterative deepening A** doesn't keep all reached states in memory, but extra cost of visiting states multiple times. \nUsed for programs that don't fit in memory\nCutoff is $f$-cost ($g+h$) at each iteration\nNext cutoff value is lowest $f$ cost node just beyond previous cut-off\n- **Recursive best first search** BFS but with linear space. Tracks alt paths available from ancestors of current node - may backtrack and replace nodes with backed up values. \nMore efficient than IDA*\nOptimal if $h(n)$ admissable\n\nIDA* and RBFS use too little memory and may explore same states multiple times\n\n**Memory bounded A** and **Simplified MA** use all available memory. SMA expands newest best leaf and deletes oldest worst leaf. Complete if reachable solution.\n\n**Bidirectional heuristic search** must consider surely expanded pairs of nodes. Sometimes more efficient with avg heuristic.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nJudging quality of heuristic:\n- effective branching factor b* = branching factor a tree of uniform depth $d$ would have to contain $N+1$ nodes, where $N$ is the total number of nodes generated and solution depth $d$\n- well-designed heuristics have a b* close to 1\n\nDomination:\n- If h2 dominates h1: $h2(n) \\geq h1(n)$ and using h2 will never expand more nodes than using h1. h1 will always expand all nodes that h2 does, plus possibly others. Usually better to use heuristic with higher values as long as it is consistent and is not slow computationally.\n\nUsing a relaxed version of a problem is one way to find a heuristic. Relaxed problem adds edges to state space graph, and optimal solution in the original problem is still a solution in the relaxed problem. Relaxed problem may allow us to find shortcuts that are better, so the cost of these optimal solutions becomes an admissible heuristic for the original problem. The heuristics are also consistent because they still obey the triangle ineequality.\n\nWe can use composite heuristics when we have trouble distinguishing between the quality of several heuristics: different ones are used on different nodes (although this can be slower computationally).\n$h(n) =$ max {$h1(n),…, hk(n)$}\n\nWe can generate heuristics from the solution of a subproblem within the problem.\n\nFor route-finding search, we can choose landmark points (pivots/anchors) and precompute the optimal path between every vertex in the graph and the landmark. Can then compute inadmissable (overestimates cost to goal if optimal path doesn't go through landmark) heuristic from current node landmark to goal. We can also add shortcuts (artifical graph edges) that describe optimal multi-action paths.\n\nWe can make the landmark search admissable by turning it into a differential heuristic. Also landmarks should be spread out so they are not super close to each other.\n\nAgents can learn to search better. For example, an agent can use a metalevel search space to learn to avoid non-helpful states. The overall goal is to minimize the total cost of problem solving, even if there have to be tradeoffs between computational cost and path cost.\n\nMachine learning can also be achieved with experience, although heuristics generated this way may not be admissible. We can include features of the state that help predict the heuristic value to improve this.\n \n\n## Module 4 Lecture Notes\n Uniform Cost Search is an extension of BFS where we expand the node with the lowest path cost. The frontier is a priority queue ordered by the lowest path cost to get to that node ($g(n)$). Different from BFS because it tests if a node is a goal state when it's popped from the queue, not when it's added to the frontier. If a better path to that node is found, it will update the node on the frontier (so that's why goal check is after it comes out of the queue - so you know you have the lowest-cost version). We can thus prioritize which paths to explore. Uniform Cost Search is also called Dijkstra's Algorithm. It is complete and optimal.\n\nBest-first search improves on this by using an evaluation function to select the node to pop off the queue. The evaluation function $f(n)$ includes an estimate of the distance between this node and the goal. So, Best-first search is UCS where $f(n)$ replaces $g(n)$. Heuristic function $h(n)$ estimates the distance between a state $n$ and the goal. Heuristics are helpful, but not always exact or correct.\n\nGreedy best-first search expands node that is estimated to be closest to the goal, ignoring $g(n)$, which is the cost to get to $n$. So $f(n) = h(n)$. It is not optimal (not guaranteed to find lowest-cost) or complete (can get stuck in loops).\n```\nfunction GREEDY-BEST-FIRST(problem, heuristic) returns solution or failure\n    frontier (priority queue)\n    initial node put into frontier\n    came_from (empty set)\n    while frontier is not empty:\n        pop node from queue\n        goal-test node - if goal, return solution\n        else for each neighbor not in came_from:\n              set node priority to h(n)\n              put node in frontier\n              put node in came_from\n\n```\nA* Search is another form of best-first search that avoids exploring expensive paths and focus instead on most promising. It's evaluation function is: $f(n) = g(n) + h(n)$, where $g(n)$ is the actual cost to reach current node, $h(n)$ is the estimated cost to get from the current node to the goal, so $f(n)$ is the total cost of the path from the initial state through the current node to the goal. Its frontier is also a monotonically increasing priority queue. - Optimal with an admissible heuristic\n- basically UCS (distance from start to current) + Greedy best-first (distance from current to goal)\n\nAdmissible heuristic never overestimates the cost to reach the goal (optimistic). Inadmissible heuristics tend to push the good plans too far down the queue.\n\nRelaxed problem is one with fewer restrictions than the original. The cost of an optimal solution for a relaxed problem is an admissible heuristic for the original problem. Ex. True map travel distance vs Manhattan distance\n\nDominance means one heuristic is better than (dominates) another. If $h_2(n) \\geq h_1(n)$ for all $n$ and both are admissible:\n- $h_2$ dominates $h_1$\n- $h_2$ has a higher cost but is still optimistic\n- $h_2$ is  optimistic and **more accurate** than $h_1$ and is better for search\n\nBest heuristic = the truth ( h*(n) ): called the Oracle heuristic, is unachievable, dominates all other heuristics\nWorst heuristic = 0 (aka we're here): dominated by all other heuristics, basically uniform cost search\nSo an admissible heuristic is 0 <= h(n) <= h*(n)\n\nA* is used in path/route planning (maps), video games, robot motion planning, resource planning\n\n```\nfunction A-STAR-SEARCH(problem, heuristic) returns solution or failure\n    frontier (priority queue)\n    put starting node in the frontier\n    came_from (empty dict)\n    cost_so_far (empty_dict)\n    came_from[start] = 0\n    cost_so_far[start] = 0\n\n    while frontier is not empty:\n        pop node from queue\n        goal-check node, if goal then return solution\n\n        else for each neighbor of current node:\n            set new_cost = cost_so_far[current] + graph.cost[current, next]\n            if next not in cost_so_far or new_cost is less than cost_so_far[next]:\n                set cost_so_far[next] to new_cost\n                set node priority to new_cost + heuristic(goal, next)\n                add node to frontier\n                came_from[next] = current node\n```\n\n \n\n## Module 4 Definitions\n* **Informed search** - uses heauristics: hints specific to the domain about the location of goals\n* **Heuristic function** - gives estimated cost of cheapest path from current node $n$ to goal state\n* **Admissible heuristic** - optimistic heuristic that always underestimates cost to reach goal\n* **Consistency** - When going from one node to another, estimated step cost never exceeds actual step cost. Based on triangle inequality\n* **Triangle inequality** - one side of a triangle cannot be longer than sum of other sides\n* **Monotonic** - never decreases\n* **Optimally efficient** - means any algorithm with same heuristic will expand same surely expanded nodes as A*\n* **Greedy best-first search** - expands nodes with minimal heuristic cost. Not optimal but is usually efficient.\n* **A* search** - expands nodes with minimal actual + estimated costs. Complete and optimal with admissible heuristic but has space complexity problems\n* **Bidirectional a* search** - A* search that measures from start and goal. Can be more efficient than A*\n* **Front-to-end** - heuristic that measures distance to goal or distance to start\n* **Front-to-front** - heuristic that measures distance to other frontier\n* **Backed-up value** - best $f$-value of child nodes\n* **Reference count** - number of times state has been reached\n* **Ida*** - iterative deepening version of A* that addresses its space complexity problems\n* **Rbfs** - optimal variation of best first search that uses limited memory\n* **Sma*** - optimal variation of A*  that uses limited memory and can solve problems when A* runs out of memory\n* **Speedy search** - greedy best first with $h(n)$ equal to the estimated number of actions to reach goal\n* **Beam search** - memory-conserving incomplete and suboptimal search that limits size of frontier and runs faster than complete searches\n* **Weighted a* search** - uses weighted heuristic to focus on goal, expanding fewer nodes. Tradeoff is optimality.\n* **Domination** - when one heuristic always outperforms and is more efficient than another\n* **Relaxed problem** - version of a problem with fewer restrictions. Creates a supergraph of original problem.\n* **Pattern database** - stores all solution costs for subproblem instances\n* **Disjoint pattern databases** - use added costs of disjoint solutions to get lower bound on cost of solving entire problem\n* **Metalevel state space** - contains each state of the internal state of a program searching a regular state space\n* **Metalevel learning** - algorithm that uses metalevel state space to learn to avoid unpromising search trees\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 = \"\"\" In adversarial environments, other agents are actively trying to defeat us. We can model these agents using adversarial tree game-tree search approaches. We can use the Minimax algorithm to solve these problems.\n",
        "\n",
        "Formal definition of a game:\n",
        "- Initial state of the game\n",
        "- The player whose turn it is to move in a particular state\n",
        "- The set of legal moves (actions) within a particular state\n",
        "- The transition model (result) of the state that results from making a particular move in a previous state\n",
        "- Terminal test that checks if game is over; if yes, current state is terminal state\n",
        "- Utility function that assigns final numeric value (payoff) to the player when the game ends\n",
        "\n",
        "State space graph is definied by the actions function and the result function. There may be multiple ways/paths to reach a state in the game. We can use a search tree to determine the next best move in the graph. \\\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" For adversarial search, we need a conditional plan. In games with multiple outcome scores, we should use minimax search to do this.\n",
        "\n",
        "**Minimax Search**\n",
        "- determine minimax value of each state in the tree\n",
        "- in non-terminal state, MAX wants to move to a state of max value (when it is MAX's turn) and MIN wants to move to state that is min value for MAX\n",
        "- if MIN does not play optimally, MAX will do at least as well as if it were going against an optimal player\n",
        "- algorithm computes all states and returns one with the highest minmax value\n",
        "- completes depth-frist exploration of entire game tree\n",
        "- time: $O(b^m)$ where $b$ is legal moves and $m$ is max depth of tree\n",
        "- space: $O(bm)$ if algo generates all actions at once, or $O(m)$ if actions are generated one at a time\n",
        "\n",
        "Minimax is not useful for complex games because of its exponential complexity.\n",
        "\n",
        "For multiplayer games, utility will be returned from each player's viewpoint in terminal states. Backed-up value of a node n is utility of child state with \\\n",
        "highest value for the player making a choice at n. Note that multiplayer games might include alliances between players.\n",
        "\n",
        "We can reduce the number of game states explored by pruning parts of the tree that will not affect the outcome. **Alpha-Beta pruning** can be used on \\\n",
        "trees of any depth, and both leaves and subtrees can be pruned. The two extra parameters are **alpha** (highest-value choice found so far on path for MAX - \"at least\") and **beta** (lowest-value choice \\\n",
        "found so far on path for MIN - \"at most\"). \n",
        "\n",
        "Effectiveness depends on the order in which states are examined - most efficient to examine likely best child nodes. \n",
        "- Done perfectly: $O(b^{m/2} )$ nodes examined, branching factor of $\\sqrt b$ instead of $b$\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" We can reduce computation time by cutting off the search at a predetermined point (cutoff test) and using a heuristic to evaluate the now terminal states. Heuristic will give estimate of \\\n",
        "expected utility of a state to a player. Estimate can be calculated by combining the expected utility of the individual features of the state (weighted linear function). Can also use non-linear elements \\\n",
        "that happen because certain combinations of elements might have a different value than they do as independent elements.\n",
        "\n",
        "We can run an iterative deepening version of alpha-beta search, where we increase the cut-off depth on each iteration. Other ways of reducing computation time include forward pruning (ex beam search) or \\\n",
        "probabilistic cut algorithm (forward-pruning version of alpha-beta search using stats/probability from prior experience to avoid pruning best move) or late move reduction (assumes later moves are less \\\n",
        "likely to be good, so we reduce the amount of time we search these moves)\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" **Stochastic games** cannot use normal game tree because of the element of chance. Their game tree includes chance nodes in addition to the MIN and MAX nodes. Positions no longer have definite minimax values - they have expected values instead. \\\n",
        "The expected value is the average of all possible outcomes (sum of all outcomes weighted by probability of that outcome). Stochastic games use the **expetiminimax** value (similar to minimax value), where we determine the expected value for chance nodes. \\\n",
        "The best evaluation function will be the one that returns values that are a positive linear transformation of the probability of winning.\n",
        "- Expectiminimax time: $O(b^mn^m)$, where $n$ is number of distinct rolls\n",
        "- Extra cost means it is not very helpful to look very far ahead for stochastic games, because levels of chance remove element of \\'likely\\' moves\n",
        "- We can use pruning on game tree chance nodes by considering bounds on the possible values of the utility function\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "**MEU (maximum expected utility) principle** is the formal abstract way of stating that intelligent agents should act rationally, although it does not state how this should be done. It helps define the problem.\n",
        "\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" Rational preference relation has the following constraints (axioms of utility theory - if an agent violates one, it will behave irrationally):\n",
        "- **Orderability** - Given any two lotteries, an agent has to decide if one is more preferable than the other, or if they are equal (A>B, B>A, A~B)\n",
        "- **Transitivity** - Given any three lotteries, if an agent prefers A to B and B to C, then the agent prefers A to C \n",
        "- **Continuity** - If some lottery B is between A and C then there is some probability $p$ that will make the agent indifferent between getting B, getting A (with $p$), and getting C (with $1-p$)\n",
        "- **Substitutability** - If agent is indifferent to A and B, then agent is indifferent to more complex identical lotteries where B is substituted for A\n",
        "- **Monotonicity** - If two lotteries have outcomes A and B and agent prefers A to B, then agent prefers lottery with higher probability for A as the outcome\n",
        "- **Decomposability** - Compound lotteries can be simplified using laws of probability\n",
        "\n",
        "We can derive the following from these axioms:\n",
        "- **existence of utility function** - if agent follows axioms, then there is a function $U$ such that $U(A) > U(B)$ iff agent prefers A to B, and $U(A) = U(B)$ iff agent is indifferent\n",
        "- **expected utility of a lottery** - utility of a lottery is the sum of the probability of each outcome multiplied by the utility of that outcome\n",
        "\n",
        "When probabilities and utilities of states are determined, utility of compound lottery is determined. Note that utility functions are not guaranteed to be unique.\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" Scales for utilities are helpful in order to compare them for a specific problem. We can establish a scale by fixing the worst and best outcomes as measurement points. \\\n",
        "When human judgement is involved, there are a range of other aspects that influence how human agent's act.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Simplest game environment is multiagent, static (no change while agent deliberates), discrete (finite precepts and actions), fully observable, strategic\n",
        "\n",
        "Our games: 2 players, alternate moves, zero-sum, clear set of legal moves, well-definied outcomes (win/lose/draw)\n",
        "Properties of complex games: stochastic (not deterministic), not fully observable, continuous (not discrete), no pause between actions, no turns, also cooperative games\n",
        "\n",
        "If we configure games as search:\n",
        "- initial state\n",
        "- successor function (pair of (move,state) that specify legal moves)\n",
        "- terminal state test\n",
        "- utility function (numerical values given to terminal states)\n",
        "- MAX determines next move through search tree\n",
        "\n",
        "Game trees:\n",
        "- nodes are board states\n",
        "- edges are legal moves\n",
        "- root node is first state in which a decision must be made\n",
        "- evaluation function that assigns numbers to board positions without needing to know path to get there (evaluates board position based on static features of board $f(n)>0$ if MAX is winning, $f(n)=0$ if tied, $f(n)<0$ if MIN is winning in position n)\n",
        "\n",
        "Minimax: assumes MAX's best moves are based on MIN also making the best move for itself. Computed recursively. The minimax value is the best achievable utility against a rational opponent.\n",
        "\n",
        "```\n",
        "def value(state)\n",
        "  if state is terminal, return state's utility\n",
        "  if it is MAX's turn, return max-value(state)\n",
        "  if it is MIN's turn, return min-value(state)\n",
        "\n",
        "def max-value(state)\n",
        "  initialize v = -inf\n",
        "  for each successor of state:\n",
        "      v = max(v, value(successor))\n",
        "  return v\n",
        "\n",
        "def min-value(state)\n",
        "  initialize v = +inf\n",
        "  for each successor of state:\n",
        "      v = min(v, value(successor))\n",
        "  return v\n",
        "  \n",
        "```\n",
        "\n",
        "Alpha-beta pruning = minimax that tracks 2 additional values: alpha ('at least' = MAX's lower bound on MAX's outcome) and beta ('at most' = MIN's upper bound on MIN's outcome). We stop evaluating a branch whenever a value >= beta is backed up for a MAX node \\\n",
        "(because MIN will never select it) or whenever a value <= alpha is backed up for MIN node (because MAX will never select it)\n",
        "\n",
        "```\n",
        "def value(state)\n",
        "  alpha = -inf\n",
        "  beta = +inf\n",
        "  if state is terminal, return state's utility\n",
        "  if it is MAX's turn, return max-value(state, alpha, beta)\n",
        "  if it is MIN's turn, return min-value(state, alpha, beta)\n",
        "\n",
        "def max-value(state)\n",
        "  initialize v = -inf\n",
        "  for each successor of state:\n",
        "      v = max(v, value(successor))\n",
        "      alpha = max(alpha, v)\n",
        "  return v\n",
        "\n",
        "def min-value(state)\n",
        "  initialize v = +inf\n",
        "  for each successor of state:\n",
        "      v = min(v, value(successor))\n",
        "      beta = min(beta, v)\n",
        "  return v\n",
        "\n",
        "```\n",
        "\n",
        "Expectimax is used for games with uncertain outcomes (contain chance nodes). It computers average score under optimal play: MAX nodes, Chance nodes (instead of MIN) , calculate expected utility of the chance node (weighted expectation of all children)\n",
        "\n",
        "```\n",
        "def value(state)\n",
        "  if state is terminal, return state's utility\n",
        "  if it is MAX's turn, return max-value(state)\n",
        "  if it is EXP's turn, return exp-value(state)\n",
        "\n",
        "def max-value(state)\n",
        "  initialize v = -inf\n",
        "  for each successor of state:\n",
        "      v = max(v, value(successor))\n",
        "  return v\n",
        "\n",
        "def exp-value(state)\n",
        "  initialize v = 0\n",
        "  for each successor of state:\n",
        "      p = probability(successor)\n",
        "        v += p*\n",
        "      value(successor)\n",
        "return v\n",
        "```\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"competitive environments\" : \"environment where two or more agents operate with conflicting goals\",\n",
        "\"adversarial search\" : \"search problem in multi-agent competitive environments\",\n",
        "\"perfect information\" : \"means fully observable\",\n",
        "\"zero-sum game\" : \"game in which there is no win-win: if one player wins, the other loses\",\n",
        "\"position\": \"in the context of a game, it is the state\",\n",
        "\"state space graph\" : \"graph where vertices are states and edges are moves\",\n",
        "\"game tree\" : \"search tree that tracks all sequences of moves to a terminal state. Can be infinite.\",\n",
        "\"ply\" : \"one move by one player\",\n",
        "\"minimax value\" : \"utility/max of being in a particular state, assuming optimal play from both players to the end of the game\",\n",
        "\"minimax decision\" : \"optimal choice for MAX in order to get to state with highest minimax value\",\n",
        "\"transpositions\" : \"move sequence permutations that end up at same position\",\n",
        "\"transposition table\" : \"used to track heuristic values of positions/states\",\n",
        "\"Type A strategy\" : \"strategy that looks at all moves up to a certain tree depth (wide but shallow)\",\n",
        "\"Type B strategy\" : \"strategy that looks only at promising moves and follows them as far as it can\",\n",
        "\"horizon effect\" : \"agent faces unavoidable (but delayable) negative opponent move\",\n",
        "\"singular extension\" : \"in cutoff alpha-beta search, allows \\'clearly better\\' moves that would normally be cut off\",\n",
        "\"forward pruning\" : \"prune moves that look like they will be bad, with the risk they might be good\",\n",
        "\"Stochastic game\" : \"game that contains random/chance elements\",\n",
        "\"expected utility\" : \"average utility value of all outcomes weighted by probability of each of those outcomes occurrs\",\n",
        "\"maximum expected utility (MEU)\" : \"principle that states a rational agent will choose the action that maximizes utility\",\n",
        "\"value function or ordinal utility function\" : \"in deterministic environments, an agent just needs a ranking on states\",\n",
        "\"Normalized utilities\" : \"scale between 0-1 (worst and best outcome), adjust $p$ until agent indifferent to $S$ vs standard lottery\",\n",
        "\"certainty equivalent\" : \"amount an agent will accept in place of a lottery\",\n",
        "\"risk-neutral\" : \"agent with a linear curve in relation to small changes in wealth vs current wealth\",\n",
        "\"optimizer’s curse\" : \"when estimated expected utility of the best choice is higher than it should be\",\n",
        "\"normative theory\" : \"describes how rational agent is supposed to act\",\n",
        "\"descriptive theory\" : \"describes how rational agent acutally acts\",\n",
        "\"certainty effect\" : \"people tend to prefer things that are \\'sure\\' things\",\n",
        "\"ambiguity aversion\" : \"people avoid unknown probabilities\",\n",
        "\"framing effect\" : \"the way a decision problem is worded can influence the agent's choices\",\n",
        "\"anchoring effect\" : \"uses relative utility judgments to influence an agent's choice\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "827cd62e-99da-4fd9-fbc9-91c2d656dcd6"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n In adversarial environments, other agents are actively trying to defeat us. We can model these agents using adversarial tree game-tree search approaches. We can use the Minimax algorithm to solve these problems.\n\nFormal definition of a game:\n- Initial state of the game\n- The player whose turn it is to move in a particular state\n- The set of legal moves (actions) within a particular state\n- The transition model (result) of the state that results from making a particular move in a previous state\n- Terminal test that checks if game is over; if yes, current state is terminal state\n- Utility function that assigns final numeric value (payoff) to the player when the game ends\n\nState space graph is definied by the actions function and the result function. There may be multiple ways/paths to reach a state in the game. We can use a search tree to determine the next best move in the graph.  \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n For adversarial search, we need a conditional plan. In games with multiple outcome scores, we should use minimax search to do this.\n\n**Minimax Search**\n- determine minimax value of each state in the tree\n- in non-terminal state, MAX wants to move to a state of max value (when it is MAX's turn) and MIN wants to move to state that is min value for MAX\n- if MIN does not play optimally, MAX will do at least as well as if it were going against an optimal player\n- algorithm computes all states and returns one with the highest minmax value\n- completes depth-frist exploration of entire game tree\n- time: $O(b^m)$ where $b$ is legal moves and $m$ is max depth of tree\n- space: $O(bm)$ if algo generates all actions at once, or $O(m)$ if actions are generated one at a time\n\nMinimax is not useful for complex games because of its exponential complexity.\n\nFor multiplayer games, utility will be returned from each player's viewpoint in terminal states. Backed-up value of a node n is utility of child state with highest value for the player making a choice at n. Note that multiplayer games might include alliances between players.\n\nWe can reduce the number of game states explored by pruning parts of the tree that will not affect the outcome. **Alpha-Beta pruning** can be used on trees of any depth, and both leaves and subtrees can be pruned. The two extra parameters are **alpha** (highest-value choice found so far on path for MAX - \"at least\") and **beta** (lowest-value choice found so far on path for MIN - \"at most\"). \n\nEffectiveness depends on the order in which states are examined - most efficient to examine likely best child nodes. \n- Done perfectly: $O(b^{m/2} )$ nodes examined, branching factor of $\\sqrt b$ instead of $b$\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can reduce computation time by cutting off the search at a predetermined point (cutoff test) and using a heuristic to evaluate the now terminal states. Heuristic will give estimate of expected utility of a state to a player. Estimate can be calculated by combining the expected utility of the individual features of the state (weighted linear function). Can also use non-linear elements that happen because certain combinations of elements might have a different value than they do as independent elements.\n\nWe can run an iterative deepening version of alpha-beta search, where we increase the cut-off depth on each iteration. Other ways of reducing computation time include forward pruning (ex beam search) or probabilistic cut algorithm (forward-pruning version of alpha-beta search using stats/probability from prior experience to avoid pruning best move) or late move reduction (assumes later moves are less likely to be good, so we reduce the amount of time we search these moves)\n \n\n## AIMA Chapter 5.5 Stochastic Games\n **Stochastic games** cannot use normal game tree because of the element of chance. Their game tree includes chance nodes in addition to the MIN and MAX nodes. Positions no longer have definite minimax values - they have expected values instead. The expected value is the average of all possible outcomes (sum of all outcomes weighted by probability of that outcome). Stochastic games use the **expetiminimax** value (similar to minimax value), where we determine the expected value for chance nodes. The best evaluation function will be the one that returns values that are a positive linear transformation of the probability of winning.\n- Expectiminimax time: $O(b^mn^m)$, where $n$ is number of distinct rolls\n- Extra cost means it is not very helpful to look very far ahead for stochastic games, because levels of chance remove element of 'likely' moves\n- We can use pruning on game tree chance nodes by considering bounds on the possible values of the utility function\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n**MEU (maximum expected utility) principle** is the formal abstract way of stating that intelligent agents should act rationally, although it does not state how this should be done. It helps define the problem.\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Rational preference relation has the following constraints (axioms of utility theory - if an agent violates one, it will behave irrationally):\n- **Orderability** - Given any two lotteries, an agent has to decide if one is more preferable than the other, or if they are equal (A>B, B>A, A~B)\n- **Transitivity** - Given any three lotteries, if an agent prefers A to B and B to C, then the agent prefers A to C \n- **Continuity** - If some lottery B is between A and C then there is some probability $p$ that will make the agent indifferent between getting B, getting A (with $p$), and getting C (with $1-p$)\n- **Substitutability** - If agent is indifferent to A and B, then agent is indifferent to more complex identical lotteries where B is substituted for A\n- **Monotonicity** - If two lotteries have outcomes A and B and agent prefers A to B, then agent prefers lottery with higher probability for A as the outcome\n- **Decomposability** - Compound lotteries can be simplified using laws of probability\n\nWe can derive the following from these axioms:\n- **existence of utility function** - if agent follows axioms, then there is a function $U$ such that $U(A) > U(B)$ iff agent prefers A to B, and $U(A) = U(B)$ iff agent is indifferent\n- **expected utility of a lottery** - utility of a lottery is the sum of the probability of each outcome multiplied by the utility of that outcome\n\nWhen probabilities and utilities of states are determined, utility of compound lottery is determined. Note that utility functions are not guaranteed to be unique.\n \n\n## AIMA Chapter 16.3 Utility Functions\n Scales for utilities are helpful in order to compare them for a specific problem. We can establish a scale by fixing the worst and best outcomes as measurement points. When human judgement is involved, there are a range of other aspects that influence how human agent's act.\n \n\n## Module 5 Lecture Notes\n Simplest game environment is multiagent, static (no change while agent deliberates), discrete (finite precepts and actions), fully observable, strategic\n\nOur games: 2 players, alternate moves, zero-sum, clear set of legal moves, well-definied outcomes (win/lose/draw)\nProperties of complex games: stochastic (not deterministic), not fully observable, continuous (not discrete), no pause between actions, no turns, also cooperative games\n\nIf we configure games as search:\n- initial state\n- successor function (pair of (move,state) that specify legal moves)\n- terminal state test\n- utility function (numerical values given to terminal states)\n- MAX determines next move through search tree\n\nGame trees:\n- nodes are board states\n- edges are legal moves\n- root node is first state in which a decision must be made\n- evaluation function that assigns numbers to board positions without needing to know path to get there (evaluates board position based on static features of board $f(n)>0$ if MAX is winning, $f(n)=0$ if tied, $f(n)<0$ if MIN is winning in position n)\n\nMinimax: assumes MAX's best moves are based on MIN also making the best move for itself. Computed recursively. The minimax value is the best achievable utility against a rational opponent.\n\n```\ndef value(state)\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state)\n  if it is MIN's turn, return min-value(state)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n  return v\n\ndef min-value(state)\n  initialize v = +inf\n  for each successor of state:\n      v = min(v, value(successor))\n  return v\n  \n```\n\nAlpha-beta pruning = minimax that tracks 2 additional values: alpha ('at least' = MAX's lower bound on MAX's outcome) and beta ('at most' = MIN's upper bound on MIN's outcome). We stop evaluating a branch whenever a value >= beta is backed up for a MAX node (because MIN will never select it) or whenever a value <= alpha is backed up for MIN node (because MAX will never select it)\n\n```\ndef value(state)\n  alpha = -inf\n  beta = +inf\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state, alpha, beta)\n  if it is MIN's turn, return min-value(state, alpha, beta)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n      alpha = max(alpha, v)\n  return v\n\ndef min-value(state)\n  initialize v = +inf\n  for each successor of state:\n      v = min(v, value(successor))\n      beta = min(beta, v)\n  return v\n\n```\n\nExpectimax is used for games with uncertain outcomes (contain chance nodes). It computers average score under optimal play: MAX nodes, Chance nodes (instead of MIN) , calculate expected utility of the chance node (weighted expectation of all children)\n\n```\ndef value(state)\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state)\n  if it is EXP's turn, return exp-value(state)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n  return v\n\ndef exp-value(state)\n  initialize v = 0\n  for each successor of state:\n      p = probability(successor)\n        v += p*\n      value(successor)\nreturn v\n```\n\n\n \n\n## Module 5 Definitions\n* **Competitive environments** - environment where two or more agents operate with conflicting goals\n* **Adversarial search** - search problem in multi-agent competitive environments\n* **Perfect information** - means fully observable\n* **Zero-sum game** - game in which there is no win-win: if one player wins, the other loses\n* **Position** - in the context of a game, it is the state\n* **State space graph** - graph where vertices are states and edges are moves\n* **Game tree** - search tree that tracks all sequences of moves to a terminal state. Can be infinite.\n* **Ply** - one move by one player\n* **Minimax value** - utility/max of being in a particular state, assuming optimal play from both players to the end of the game\n* **Minimax decision** - optimal choice for MAX in order to get to state with highest minimax value\n* **Transpositions** - move sequence permutations that end up at same position\n* **Transposition table** - used to track heuristic values of positions/states\n* **Type a strategy** - strategy that looks at all moves up to a certain tree depth (wide but shallow)\n* **Type b strategy** - strategy that looks only at promising moves and follows them as far as it can\n* **Horizon effect** - agent faces unavoidable (but delayable) negative opponent move\n* **Singular extension** - in cutoff alpha-beta search, allows 'clearly better' moves that would normally be cut off\n* **Forward pruning** - prune moves that look like they will be bad, with the risk they might be good\n* **Stochastic game** - game that contains random/chance elements\n* **Expected utility** - average utility value of all outcomes weighted by probability of each of those outcomes occurrs\n* **Maximum expected utility (meu)** - principle that states a rational agent will choose the action that maximizes utility\n* **Value function or ordinal utility function** - in deterministic environments, an agent just needs a ranking on states\n* **Normalized utilities** - scale between 0-1 (worst and best outcome), adjust $p$ until agent indifferent to $S$ vs standard lottery\n* **Certainty equivalent** - amount an agent will accept in place of a lottery\n* **Risk-neutral** - agent with a linear curve in relation to small changes in wealth vs current wealth\n* **Optimizer’s curse** - when estimated expected utility of the best choice is higher than it should be\n* **Normative theory** - describes how rational agent is supposed to act\n* **Descriptive theory** - describes how rational agent acutally acts\n* **Certainty effect** - people tend to prefer things that are 'sure' things\n* **Ambiguity aversion** - people avoid unknown probabilities\n* **Framing effect** - the way a decision problem is worded can influence the agent's choices\n* **Anchoring effect** - uses relative utility judgments to influence an agent's choice\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b8f55741-9c5b-48eb-cb92-0c400c94db48"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" To examine **constraint satisfaction problems** we need to break atomic representation of a state into a **factored representation** that has a set of variables, each assigned its own value. CSP algorithms \\\n",
        "use general heuristics to solve CSP problems. We can eliminate sections of the search space simply by removing states that violate constraints (something atomic solvers cannot do). This means if a problem can be formulated \\\n",
        "as a CSP, it can often be solved much mroe quickly than an atomic problem. CSPs are NP-complete.\n",
        "\n",
        "Examples CSPs: map coloring, job scheduling, assembling, N-queens\n",
        "\n",
        "CSP components:\n",
        "- set of variables $\\{X_1, ..., X_n\\}$\n",
        "- set of domains, one for each variable $\\{D_1, ..., D_n\\}$\n",
        "- set of constraints that specific allowable value combinations\n",
        "\n",
        "Each constraint is composed of a pair of scope (tuple of variables) and relation that defines those variable's values. A relation can be an explicit set of values or a function that can compute valid values.\n",
        "\n",
        "CSPs can be depicted as constraint graphs, where the nodes of the graph represent the variables in the problem, and the edges represent the constraints. Simple CSPs have discrete (can be infinite), finite domains. \\\n",
        "Real-world CSPs often have continuous domains (ex linear programming problems, where constraints are linear equalities/inequalities).\n",
        "\n",
        "Types of constraints:\n",
        "- **unary** - restricts value of one variable\n",
        "- **binary** - relates values of two variables (binary CSP only has unary and binary constraints and can be represented as a constraint graph)\n",
        "- \"\"higher order**\n",
        "- **global** - restricts an arbitrary number of variables (not necessarily all)\n",
        "\n",
        "CSPs can also have preference constraints to determine preferred solutions. These can be encapsulated as costs on variable assignments. CSP then becomes constrained optimization problem.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" CSPs can make progress by creating successors through new variable assignments or perform inference through constraint propagation, using local consistency, which \\\n",
        "removes inconsistent values from the graph.\n",
        "\n",
        "Types of local consistency:\n",
        "- **node consistency**: node-consistent variables have values that satisfy the variable's unary constraints (remove inconsistent values or convert to binary at the start of the solving process). If all nodes are consistent, then graph is node-consistent\n",
        "- **arc consistency**: arc-consistent variables have values that satisfy the variable's binary constraints. Graph is arc-consistent if all variables are with every other variable.\n",
        "\n",
        "AC is enforced with algorithm AC-3:\n",
        "- maintain queue of arcs\n",
        "- pop one arc off of queue and make arc-consistent\n",
        "- if domain is changed (smaller), we add to queue all arcs that are neighbors of this arc\n",
        "- if domain is empty, immediately return failure\n",
        "- can either solve completely or prove no solution\n",
        "- time to check one arc: $O(d^2)$\n",
        "- time to check all arcs: $O(cd^3)$ where $d$ is domain size and $c$ is number of binary constraints\n",
        "\n",
        "Arc-consistent CSP faster to search because of smaller domains.\n",
        "\n",
        "Path consistency considers 3 variables: $X_i - X_m - X_j$\n",
        "\n",
        "K-consistency means for any set of $k-1$ variables in the CSP with a consistent assignment, a consistent value can be assigned to the $k^{th}$ variable:\n",
        "- unary: 1-consistency\n",
        "- arc: 2-consistency\n",
        "- path: 3-consistency\n",
        "For a strongly k-consistent graph, time: $O(n^2d)$ where $n$ is number of nodes. However, it will require space exponential to $n$ and will take time exponential in $n$.\n",
        "\n",
        "**Alldiff** constraint algorithm: remove variables with singleton domains and then remove those values from the remaining variable domains. Continue until either an empty domain is created or more variables than domain values left.\n",
        "\n",
        "**Resource (Atmost) constraint** - can check the sum of the min values of all the domains or check whether the max values of domains are consistent with min values of other domains.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" **backtracking search** chooses an unassigned variable, and tries all the values of that variable's domain, using a recursive call to try and find a solution. When one value fails, it moves on to the next one. Keeps only one \\\n",
        "representation of a state and changes it rather than creating new states. Can be improved with domain-independent heuristics:\n",
        "- choose **minimum-remaining-values (MRV)** heuristic, which picks the variable with fewest \\'legal\\' values. Designed to find branches of the search tree that \\'fail fast\\' so that those branches can be pruned. \n",
        "Performs better than random or static ordering. (variable is fail-first)\n",
        "- use **degree heuristic** which tries to reduce branching by choosing the vairable that has the largest number of constraints on other (unassigned) variables. Can be used as a tie-breaker or when there is no clear choice for the MRV heuristic\n",
        "(ex all domains are the same size)\n",
        "- use **least constraining value** heuristic, which chooses a value based on it constraining the fewest choices in neighboring variables. Tries to keep maximum flexibility for subsequent assignments. (value is fail-last)\n",
        "\n",
        "Note that value ordering does not matter if we are trying to find all solutions instead of just one.\n",
        "\n",
        "**forward checking** is using inference to check neighboring variables to eliminate non-legal values once a variable has a value chosen (establishes arc consistency for a variable with whatever other variables are connected to it). \\\n",
        "Doesn't detect all inconsistencies because it doesn't go forward enough.\n",
        "\n",
        "Usually efficient to combine forward checking with MRV heuristic.\n",
        "\n",
        "**Maintaining arc consistency (MAC)** detects inconsistencies through inference by recursively propgating constraints as variable values are assigned. Goes farther than forward checking.\n",
        "\n",
        "Don't need to do both backjumping and forward checking in the same search - forward checking (or using MAC algorithm) will prune the same branches that backjumping prunes.\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search algorithms work well for solving CSPs, using complete-state formulation where all variables are assigned a value in every state, and search changes one variable at a time. We can \\\n",
        "use the **min conflicts** heuristic after randomly choosing a conflicted variable to choose a value with the fewest conflicts with other variables. Min conflicts works well for both easy and hard problems (ex n-Queens and scheduling\\\n",
        " the Hubble Telescope). We can also use constraint weighting to focus just on the most important constraints.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" We can look at the structure of the problem itself to help find an effective approach. We can identify **independent subproblems** by finding connected components within the constraint graph. We can also see if the CSP is tree-shaped \\\n",
        "where we know it can be solved in linear time relative to the number of variables. We can use directional arc consistency to determine this (and avoid backtracking by using a topological sort, \\\n",
        "which takes $O(n)$ steps to make directed arc-consistent (total time is $O(nd^2)$).\n",
        "\n",
        "We can then use other methods to try and reduce constraint graphs into trees.\n",
        "- **cutset conditioning** assigns values to some variables so that the remaining ones form a tree. We have to test each possible value for those variables in order to choose one that results in the tree structure having a solution.\n",
        "- \"\"tree decomposition** of constraint graph: transform original graph into a tree where each node of the tree is a set of variables such that every variable in the original problem appears in at least one tree node,\n",
        "if two variables are connected by a constraint, the variables plus their constraint must appear in at least one tree node, and if a variable appears in two tree nodes, it has to appear in every node on the path between those two nodes.\n",
        "\n",
        "With a tree-structured graph, we can use the Tree-CSP-Solver algorithm (time: $O(nd^2)$, where $n$ is nodes and $d$ is size of largest domain) - this is efficient as long as $d$ remains small. When performing a tree decomposition \\\n",
        "the goal is to keep subproblems as small as possible. The tree width of the tree decomposition is one less than the size of the largest node, tree width of entire graph is min width of all tree decompositions. If a graph has tree width $w$, \\\n",
        "it can be solved in $O(nd^{w+1})$ time, so CSPs that have constraint graphs of bounded tree width are solvable in polynomial time.\n",
        "\n",
        "For cutset conditioning vs tree decomposition, time favors tree decomposition, but cutset uses linear memory (tree memory is exponential in $w$)\n",
        "\n",
        "When looking at the values of variables, we realize that permutations of values mean there are $d!$ solutions made by permuting $d$ possible values. To break value symmetry, we can use a symmetry-breaking constraint, such as imposing \\\n",
        "some sort of arbitrary order of values. In gerneral, it is NP-hard to eliminate all symmetry, but breaking some symmetry is usually effective.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSPs are identification problems: the goal is important, not the path. We can use general purpose search algorithms that don't have to be tailored for the state or heuristic. Only problem has to be specified in a formal \\\n",
        "declarative language. Consists of variables, possible values, and constraints. A consistent assignment of values to variables doesn't violate any constraints. Assignment is complete when every variable has a value assigned. A solution to CSP is both complete and consistent. \n",
        "\n",
        "Types of CSPs: map coloring, scheduling, sudoku\n",
        "\n",
        "Benefit to modeling problem as CSP is that we can use general algorithms to solve, CSP can auto-prune branches that violate constraints, CSP already knows which variables violate the constraints. Turn problem into constraint graph \\\n",
        "where variables are the nodes and constraints are the arcs between the nodes.\n",
        "\n",
        "CSPs can have finite or infinite domains, can also have continuous variables.\n",
        "\n",
        "We can also create a search tree for CSP, where the initial state is the empty assignment, a successor function assigns a value to any unassigned variable (where there is no conflict), the goal test is the successful assignment of values to variables \\\n",
        "and a constant cost for the path. Solution for $n$ variables is always at depth $n$, so DFS can be used.\n",
        "\n",
        "Backtracking search (basic uninformed algorithm for CSP): DFS with single variable assignments. Chooses values one variable at a time and backtracks if it hits a variable with no legal values left. However, we can use general heuristics \\\n",
        "to make algorithm faster: \n",
        "- most constrained variable should be assigned next (minimum remaining values (MRV) heuristic - aka fast fail)\n",
        "- in case of tie: most constraining variable should be assigned\n",
        "- variable values should be tried from least constraining value first so it rules out the fewest remaining values in other variables (how to assign the values, once we've chosen the variable)\n",
        "- forward-check to detect failure (keep track of remaining legal values for unassigned variables). forward checking only works on neighbors; it doesn't detect all issues\n",
        "\n",
        "Can combine search with inference: search assigns values and then inference propagates the constraints to the possible values of the rest of the variables\n",
        "\n",
        "Checking arc consistency with $d$ values takes $O(d^2)$ time worst case.\n",
        "\n",
        "```\n",
        "function AC-3(csp) returns CSP possibly with reduced domains\n",
        "  input: binary csp with variables {X1, ..., $Xn}\n",
        "  queue of arcs (initially arcs in csp) - keeps track of the arcs we need to process\n",
        "  while queue is not empty do:\n",
        "      pop (Xi, Xj) from the queue\n",
        "      if we can REMOVE-INCONSISTENT-VALUES(Xi, Xj) then - if a node had values removed, adds back arcs to neighbors\n",
        "          for each Xk in Xi's NEIGHBORS - {Xj} do\n",
        "            add (Xk, Xi) to queue\n",
        "\n",
        "function REMOVE-INCONSISTENT-VALUES(Xi, Xj) returns true iff we remove a value\n",
        "  removed = false\n",
        "  for each X in DOMAIN[Xi] do\n",
        "      if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n",
        "      then delete x from DOMAIN[Xi] and set removed = true\n",
        "  return removed\n",
        "\n",
        "```\n",
        "Worst case time complexity is if all nodes are connected to every other node: $O(n^2d^3)$\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint satisfaction problem\" : \"problem that has consstraints on its variables and is solved when all constraints are satisfied\",\n",
        "\"consistent assignment\" : \"assignment of value to variable that doesn't violate a constraint\",\n",
        "\"complete assignment\" : \"when every variable has been assigned a value\",\n",
        "\"partial assignment\" : \"when some variables have not been assigned\",\n",
        "\"partial solution\" : \"partial assignment that is consistent\",\n",
        "\"precidence constraint\" : \"when one task must come before another\",\n",
        "\"disjunctive constraint\" : \"when two tasks cannot overlap one another\",\n",
        "\"constraint hypergraph\" : \"graph that has nodes and hypernodes that represent n-ary constraints\",\n",
        "\"dual graph\" : \"one variable for each constraint in original graph and one binary constraint for each pair of constraints that share variables\",\n",
        "\"constraint propagation\" : \"use constraints to reduce possible values for a variable, which then affects other variables. Can be done as preprocessing step.\",\n",
        "\"Path consistency\" : \"uses implicit constraints inferred from looking at triplets of variables to tighten binary constraints\",\n",
        "\"strongly k-consistent\" : \"CSP that is k-consistent, k-1 consistent, etc., down to 1-consistent\",\n",
        "\"bounds propagation\" : \"consistency checker that uses upper and lower bounds\",\n",
        "\"bounds-consistent\": \"CSP that satisfies bounds propogation constraints\",\n",
        "\"commutativity\" : \"property of CSPs that says order of application of actions doesn't matter\",\n",
        "\"chronological backtracking\" : \"when the most recent decision is revisited and tried with a different value\",\n",
        "\"conflict set\" : \"set of values that are in conflict with another variable's value assignment\",\n",
        "\"backjumping method\" : \"backtrack to most recent assignment that is within a variable's conflict set\",\n",
        "\"conflict-directed backjumping\" : \"algorithm that backjumps with conflict sets consisting of variables and subsequent variables that cause problems\",\n",
        "\"Constraint learning\" : \"finding the minimum subset of variables in the conflict set that are actually causing the problem\"\n",
        "\n",
        "}\n",
        "\n",
        "\n",
        "print(\"The length in words is\", len(chapter6_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter6_2))\n"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 301\n",
            "The length in characters is 2040\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "58340242-dd9d-4281-fd80-c23c2f756587"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n To examine **constraint satisfaction problems** we need to break atomic representation of a state into a **factored representation** that has a set of variables, each assigned its own value. CSP algorithms use general heuristics to solve CSP problems. We can eliminate sections of the search space simply by removing states that violate constraints (something atomic solvers cannot do). This means if a problem can be formulated as a CSP, it can often be solved much mroe quickly than an atomic problem. CSPs are NP-complete.\n\nExamples CSPs: map coloring, job scheduling, assembling, N-queens\n\nCSP components:\n- set of variables $\\{X_1, ..., X_n\\}$\n- set of domains, one for each variable $\\{D_1, ..., D_n\\}$\n- set of constraints that specific allowable value combinations\n\nEach constraint is composed of a pair of scope (tuple of variables) and relation that defines those variable's values. A relation can be an explicit set of values or a function that can compute valid values.\n\nCSPs can be depicted as constraint graphs, where the nodes of the graph represent the variables in the problem, and the edges represent the constraints. Simple CSPs have discrete (can be infinite), finite domains. Real-world CSPs often have continuous domains (ex linear programming problems, where constraints are linear equalities/inequalities).\n\nTypes of constraints:\n- **unary** - restricts value of one variable\n- **binary** - relates values of two variables (binary CSP only has unary and binary constraints and can be represented as a constraint graph)\n- \"\"higher order**\n- **global** - restricts an arbitrary number of variables (not necessarily all)\n\nCSPs can also have preference constraints to determine preferred solutions. These can be encapsulated as costs on variable assignments. CSP then becomes constrained optimization problem.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n CSPs can make progress by creating successors through new variable assignments or perform inference through constraint propagation, using local consistency, which removes inconsistent values from the graph.\n\nTypes of local consistency:\n- **node consistency**: node-consistent variables have values that satisfy the variable's unary constraints (remove inconsistent values or convert to binary at the start of the solving process). If all nodes are consistent, then graph is node-consistent\n- **arc consistency**: arc-consistent variables have values that satisfy the variable's binary constraints. Graph is arc-consistent if all variables are with every other variable.\n\nAC is enforced with algorithm AC-3:\n- maintain queue of arcs\n- pop one arc off of queue and make arc-consistent\n- if domain is changed (smaller), we add to queue all arcs that are neighbors of this arc\n- if domain is empty, immediately return failure\n- can either solve completely or prove no solution\n- time to check one arc: $O(d^2)$\n- time to check all arcs: $O(cd^3)$ where $d$ is domain size and $c$ is number of binary constraints\n\nArc-consistent CSP faster to search because of smaller domains.\n\nPath consistency considers 3 variables: $X_i - X_m - X_j$\n\nK-consistency means for any set of $k-1$ variables in the CSP with a consistent assignment, a consistent value can be assigned to the $k^{th}$ variable:\n- unary: 1-consistency\n- arc: 2-consistency\n- path: 3-consistency\nFor a strongly k-consistent graph, time: $O(n^2d)$ where $n$ is number of nodes. However, it will require space exponential to $n$ and will take time exponential in $n$.\n\n**Alldiff** constraint algorithm: remove variables with singleton domains and then remove those values from the remaining variable domains. Continue until either an empty domain is created or more variables than domain values left.\n\n**Resource (Atmost) constraint** - can check the sum of the min values of all the domains or check whether the max values of domains are consistent with min values of other domains.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n **backtracking search** chooses an unassigned variable, and tries all the values of that variable's domain, using a recursive call to try and find a solution. When one value fails, it moves on to the next one. Keeps only one representation of a state and changes it rather than creating new states. Can be improved with domain-independent heuristics:\n- choose **minimum-remaining-values (MRV)** heuristic, which picks the variable with fewest 'legal' values. Designed to find branches of the search tree that 'fail fast' so that those branches can be pruned. \nPerforms better than random or static ordering. (variable is fail-first)\n- use **degree heuristic** which tries to reduce branching by choosing the vairable that has the largest number of constraints on other (unassigned) variables. Can be used as a tie-breaker or when there is no clear choice for the MRV heuristic\n(ex all domains are the same size)\n- use **least constraining value** heuristic, which chooses a value based on it constraining the fewest choices in neighboring variables. Tries to keep maximum flexibility for subsequent assignments. (value is fail-last)\n\nNote that value ordering does not matter if we are trying to find all solutions instead of just one.\n\n**forward checking** is using inference to check neighboring variables to eliminate non-legal values once a variable has a value chosen (establishes arc consistency for a variable with whatever other variables are connected to it). Doesn't detect all inconsistencies because it doesn't go forward enough.\n\nUsually efficient to combine forward checking with MRV heuristic.\n\n**Maintaining arc consistency (MAC)** detects inconsistencies through inference by recursively propgating constraints as variable values are assigned. Goes farther than forward checking.\n\nDon't need to do both backjumping and forward checking in the same search - forward checking (or using MAC algorithm) will prune the same branches that backjumping prunes.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms work well for solving CSPs, using complete-state formulation where all variables are assigned a value in every state, and search changes one variable at a time. We can use the **min conflicts** heuristic after randomly choosing a conflicted variable to choose a value with the fewest conflicts with other variables. Min conflicts works well for both easy and hard problems (ex n-Queens and scheduling the Hubble Telescope). We can also use constraint weighting to focus just on the most important constraints.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can look at the structure of the problem itself to help find an effective approach. We can identify **independent subproblems** by finding connected components within the constraint graph. We can also see if the CSP is tree-shaped where we know it can be solved in linear time relative to the number of variables. We can use directional arc consistency to determine this (and avoid backtracking by using a topological sort, which takes $O(n)$ steps to make directed arc-consistent (total time is $O(nd^2)$).\n\nWe can then use other methods to try and reduce constraint graphs into trees.\n- **cutset conditioning** assigns values to some variables so that the remaining ones form a tree. We have to test each possible value for those variables in order to choose one that results in the tree structure having a solution.\n- \"\"tree decomposition** of constraint graph: transform original graph into a tree where each node of the tree is a set of variables such that every variable in the original problem appears in at least one tree node,\nif two variables are connected by a constraint, the variables plus their constraint must appear in at least one tree node, and if a variable appears in two tree nodes, it has to appear in every node on the path between those two nodes.\n\nWith a tree-structured graph, we can use the Tree-CSP-Solver algorithm (time: $O(nd^2)$, where $n$ is nodes and $d$ is size of largest domain) - this is efficient as long as $d$ remains small. When performing a tree decomposition the goal is to keep subproblems as small as possible. The tree width of the tree decomposition is one less than the size of the largest node, tree width of entire graph is min width of all tree decompositions. If a graph has tree width $w$, it can be solved in $O(nd^{w+1})$ time, so CSPs that have constraint graphs of bounded tree width are solvable in polynomial time.\n\nFor cutset conditioning vs tree decomposition, time favors tree decomposition, but cutset uses linear memory (tree memory is exponential in $w$)\n\nWhen looking at the values of variables, we realize that permutations of values mean there are $d!$ solutions made by permuting $d$ possible values. To break value symmetry, we can use a symmetry-breaking constraint, such as imposing some sort of arbitrary order of values. In gerneral, it is NP-hard to eliminate all symmetry, but breaking some symmetry is usually effective.\n\n \n\n## Module 6 Lecture Notes\n CSPs are identification problems: the goal is important, not the path. We can use general purpose search algorithms that don't have to be tailored for the state or heuristic. Only problem has to be specified in a formal declarative language. Consists of variables, possible values, and constraints. A consistent assignment of values to variables doesn't violate any constraints. Assignment is complete when every variable has a value assigned. A solution to CSP is both complete and consistent. \n\nTypes of CSPs: map coloring, scheduling, sudoku\n\nBenefit to modeling problem as CSP is that we can use general algorithms to solve, CSP can auto-prune branches that violate constraints, CSP already knows which variables violate the constraints. Turn problem into constraint graph where variables are the nodes and constraints are the arcs between the nodes.\n\nCSPs can have finite or infinite domains, can also have continuous variables.\n\nWe can also create a search tree for CSP, where the initial state is the empty assignment, a successor function assigns a value to any unassigned variable (where there is no conflict), the goal test is the successful assignment of values to variables and a constant cost for the path. Solution for $n$ variables is always at depth $n$, so DFS can be used.\n\nBacktracking search (basic uninformed algorithm for CSP): DFS with single variable assignments. Chooses values one variable at a time and backtracks if it hits a variable with no legal values left. However, we can use general heuristics to make algorithm faster: \n- most constrained variable should be assigned next (minimum remaining values (MRV) heuristic - aka fast fail)\n- in case of tie: most constraining variable should be assigned\n- variable values should be tried from least constraining value first so it rules out the fewest remaining values in other variables (how to assign the values, once we've chosen the variable)\n- forward-check to detect failure (keep track of remaining legal values for unassigned variables). forward checking only works on neighbors; it doesn't detect all issues\n\nCan combine search with inference: search assigns values and then inference propagates the constraints to the possible values of the rest of the variables\n\nChecking arc consistency with $d$ values takes $O(d^2)$ time worst case.\n\n```\nfunction AC-3(csp) returns CSP possibly with reduced domains\n  input: binary csp with variables {X1, ..., $Xn}\n  queue of arcs (initially arcs in csp) - keeps track of the arcs we need to process\n  while queue is not empty do:\n      pop (Xi, Xj) from the queue\n      if we can REMOVE-INCONSISTENT-VALUES(Xi, Xj) then - if a node had values removed, adds back arcs to neighbors\n          for each Xk in Xi's NEIGHBORS - {Xj} do\n            add (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) returns true iff we remove a value\n  removed = false\n  for each X in DOMAIN[Xi] do\n      if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n      then delete x from DOMAIN[Xi] and set removed = true\n  return removed\n\n```\nWorst case time complexity is if all nodes are connected to every other node: $O(n^2d^3)$\n\n \n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - problem that has consstraints on its variables and is solved when all constraints are satisfied\n* **Consistent assignment** - assignment of value to variable that doesn't violate a constraint\n* **Complete assignment** - when every variable has been assigned a value\n* **Partial assignment** - when some variables have not been assigned\n* **Partial solution** - partial assignment that is consistent\n* **Precidence constraint** - when one task must come before another\n* **Disjunctive constraint** - when two tasks cannot overlap one another\n* **Constraint hypergraph** - graph that has nodes and hypernodes that represent n-ary constraints\n* **Dual graph** - one variable for each constraint in original graph and one binary constraint for each pair of constraints that share variables\n* **Constraint propagation** - use constraints to reduce possible values for a variable, which then affects other variables. Can be done as preprocessing step.\n* **Path consistency** - uses implicit constraints inferred from looking at triplets of variables to tighten binary constraints\n* **Strongly k-consistent** - CSP that is k-consistent, k-1 consistent, etc., down to 1-consistent\n* **Bounds propagation** - consistency checker that uses upper and lower bounds\n* **Bounds-consistent** - CSP that satisfies bounds propogation constraints\n* **Commutativity** - property of CSPs that says order of application of actions doesn't matter\n* **Chronological backtracking** - when the most recent decision is revisited and tried with a different value\n* **Conflict set** - set of values that are in conflict with another variable's value assignment\n* **Backjumping method** - backtrack to most recent assignment that is within a variable's conflict set\n* **Conflict-directed backjumping** - algorithm that backjumps with conflict sets consisting of variables and subsequent variables that cause problems\n* **Constraint learning** - finding the minimum subset of variables in the conflict set that are actually causing the problem\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "Problem-solving agents only have limited knowledge of their environment, what they know is mostly based around the legal actions they can take for a particular problem. They also are limited by atomic represenations.\n",
        "\n",
        "**Knowledge-based agents** can use logic to combine information for use as needed (now or possibly in the future). They can:\n",
        "- accept new tasks with well-defined goals\n",
        "- achieve competence by learning new things about the environment\n",
        "- adapt to changes in the environment by updating what they had previously known\n",
        "\n",
        "The **knowledge base** is the main component of a KB agent. Adding and querying the KB is done with \\'ask\\'s and \\'tell\\'s. The KB may start with **background knowledge** initially, before the agent adds to or modifies it.\n",
        "\n",
        " When the knowledge agent is called, it:\n",
        " - tells the knowledge base its percepts (make-percept-sentence)\n",
        " - asks the KB what actions it should perform (make-action-query)\n",
        " - tells the KB what it chose to do, and returns that action (make-action-sentence)\n",
        "\n",
        " Knowledge agent can determine actions at the knowledge level as opposed to the implementation level. It can also be created by telling it sentences one by one until it knows how to act in its environment (the **declarative** \\\n",
        " approach to system building). Successful agents often use a combination of declarative and procedural approaches in their design.\n",
        "\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" Wumpus world example shows us that conclusions can be guaranteed if the information that generated them is correct. \"\"\"\n",
        "chapter7_3 = \"\"\" Entailment means that if a entails b, then b is true in every model in which a is true. a is stronger than b because it rules out more possibilities (the set of a's models is a subset of the set of b's models)\n",
        "\n",
        "A **sound** inference algorithm (truth preserving) derives only entailed (true) sentences. If it were unsound, it would be able to make things up.\n",
        "\n",
        "A **complete** inference algorithm can derive any sentence that is entailed.\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" **propositional logic** is composed of:\n",
        "- syntax: allowable sentences are atomic that use a single proposition symbol (usually uppercase letter with another letter or subscript, ex. $W_{1,3}$). This symbol stands for a true or false proposition. True always \\\n",
        "means true, and False always means false. We can construct complex sentences from these simple sentences with parenthesis and logical connectives. The connectives are: not (positive or negative literal), and (conjunction), or (disjunction) \\\n",
        "implies (premise/antecedent -> conclusion/consequent. also known as if-then statement), biconditional (if and only if). Not operator has highest precedence.\n",
        "- semantics: how the truth value of a sentence is determined, given a particular model. We can use truth tables to do this.\n",
        "\n",
        "Entailment algorithm is sound (directly implements entailment) and complete (works for any KB and a and it always terminates because the state space is finite). There are $2^n$ models, where $n$ is the number of atomic symbols. Time \\\n",
        "complexity: $O(2^n)$; Space complexity: $O(n)$ because it works depth-first. Every known algorithm for propositional logic has worst-case exponential complexity (based on size of input).\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "Logical equivalence is used to compare sentences (vs biconditional, which is used for elements withn a sentence).\n",
        "\n",
        "To determine if a sentence is satisfiable, we must examine all models until we find one in which the sentence is true. This is an NP-complete problem. This can also be expressed as \\'a $ \\models $ b iff the sentence (a  $\\land \\lnot$ b) is unsatisfiable\\'. \\\n",
        "This is actually a proof by contradiction.\n",
        "\n",
        "**Modus Ponens** is an inference rule used to derive a proof: $ (a \\implies b, a)/b $ which means if the numerator sentances are present, the denominator sentence can be derived.\n",
        "\n",
        "**And-Elimination** is an inference rule that says any of the conjuncts can be inferred from a conjunction: $(a \\land b) / a$\n",
        "\n",
        "**resolution** is an inference rule that can be combined with a complete search algorithm to produce a complete inference algorithm. **unit resolution** uses complementary literals (one is negation of other) to use a literal and a clause to \\\n",
        "create a new clause (by removing the complementary literal). Full resolution rule takes two clauses, and creates a new clause with all contents from the original two clauses, minus the complementary literals. The resolution rule is sound and complete.\n",
        "\n",
        "Since every sentence of propositional logic is logically equivalent to a conjunction of clauses, we can express sentences in **conjunctive normal form**. The steps for CNF involve eliminating biconditionals, then eliminating implications, then moving 'not' \\\n",
        "inwards to individual literals (ex. De Morgan), then apply distributivity law of $\\lor$ over $\\land$ wherever possible.\n",
        "\n",
        "Both goal and definite clauses are Horn clauses. Definite clauses can be rewritten as implication where the premise is a conjunction of positive literals and the conclusion is a single positive literal.\n",
        "\n",
        "Ex. $ \\lnot L_{1,1} \\lor \\lnot Breeze \\lor B_{1,1}$ can be written as $ (L_{1,1} \\land Breeze) \\implies B_{1,1}$\n",
        "\n",
        "Inference with Horn clauses use forward-chaining or backward-chaining algorithms. Forward chaining uses modus ponens to make every inference and so is sound. FC is also complete because it will derive every entailed atomic sentence. FC is also \\\n",
        "a kind a data-driven reasoning. Backward chaining looks for implications in the KB whose conclusion is the query. BC is a type of goal-directed reasoning.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "```\n",
        "function PL-RESOLUTION(KB, alpha) returns true or false\n",
        "  inputs: KB, a sentence in propositional logic \n",
        "        alpha, the query, a sentence in propositional logic\n",
        "\n",
        "  clauses (set of clauses in CNF representation of (KB AND not alpha))\n",
        "  new (empty {} that keeps track of new clauses)\n",
        "  while true do:\n",
        "    for each pair of clauses Ci, Cj in clauses do:\n",
        "      resolvents = PL-RESOLVE(Ci, Cj) (returns the set of all possible \n",
        "      clauses obtained by resolving the two inputs - want to see if there \n",
        "      are two things that are the opposite of one another)\n",
        "\n",
        "      if resolvents contains empty clause, return true (means we found p \n",
        "      and not p, so we can return true because alpha is entailed by KB)\n",
        "\n",
        "      else new = new U resolvents (add resolvents to new set)\n",
        "    if new is just a subset of clauses then return false (haven't arrived at anything new not already in KB)\n",
        "    otherwise clauses = clauses U new (update clauses with everything we've found)\n",
        "```\n",
        "Resolution algorithm is complete. If our KB has a more restrictive form, we can use more efficient inference algorithms instead:\n",
        "- Definite clause (disjunction of literals where exactly one is positive)\n",
        "- Horn clause (disjunction of literals where at most one is positive; includes definite clauses and clauses with no positive literals). Horn clauses are closed under resolution: if you apply resolution to a horn clause, it returns a horn clause.\n",
        "\n",
        "If KB only has definite clauses, can rewrite them as implication whose premise is a conjuntion of positive literals whose conclusion is a positive literal. Inference can be done through forward- and backward-chaining. \\\n",
        "Deciding entailment with Horn clauses can be done in linear time (with respect to size of KB) (this is why we would want to have a KB full of definite clauses)\n",
        "\n",
        "Forward-chaining algorithm:\n",
        "```\n",
        "fucntion PL-FC-ENTAILS(KB,q) returns true or false (does KB entail q?)\n",
        "  inputs: KB, a set of propositional definite clauses\n",
        "          q, the query, a propsition symbol\n",
        "  count (table where count[c] is initially the number of symbols in in clause c's premise)\n",
        "  inferred (table where inferred[s] is initially false for all symbols) \n",
        "  (tells us if particular symbol has been inferred or not)\n",
        "  queue (queue of symbols, initially known to be true in KB)\n",
        "\n",
        "  while queue is not empty do:\n",
        "    pop p from queue\n",
        "    if p=q, return true\n",
        "    if inferred[p] = false then\n",
        "      set inferred[p] to true\n",
        "      for each clause c in KB where p is in c.PREMISE do:\n",
        "        decrement count[c] (because we've proven part of the clause c)\n",
        "        if count[c] = 0 then add c.CONCLUSION to queue (we've proven the whole clause c \n",
        "        and seen all parts of the premise)\n",
        "  return false\n",
        "```\n",
        "Forward chaining is data-driven reasoning becaues it can start with known data and add premises as percepts come in, and then use the FC algorithm to derive new conclusions. It can do this without a specific query, too.\n",
        "\n",
        "Backward chaining works in reverse from the query, searching the KB for implications whose conclusion is the query. If we can prove the premises for any clause that match the query, then the query is true. (this is goal-directed reasoning)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning instead of internal knowledge to decide what to do\",\n",
        "\"knowledge base\" : \"set of sentences written in a knowledge representation language that asserts something about the world\",\n",
        "\"axiom\" : \"sentence given without being derived from other sentences\",\n",
        "\"inference\" : \"deriving a new sentence from an old sentence without making up information\",\n",
        "\"knowledge level\" : \"can make logical decisions based on knowledge\",\n",
        "\"declarative\" : \"knowledge on how to act is obtained by an agent from TELL operation rather than direct encoding of behavior\",\n",
        "\"syntax\" : \"determines if a sentence is well-formed accoring to the representation language\",\n",
        "\"semantics\" : \"the meaning of a sentence that defines if it is true\",\n",
        "\"model\" : \"mathematical abstraction of a world in which each sentence is either true or false\",\n",
        "\"m satisfies a\" : \"sentence a is true in model m\",\n",
        "\"m is a model of a\" : \"sentence a is true in model m\",\n",
        "\"logical entailment\" : \"when one sentence follows logically from another sentence\",\n",
        "\"logical inference\" : \"using entailment to derive conclusions\",\n",
        "\"model checking\" : \"listing all possible models to check whether a is true in models where KB is true. Works in finite spaces\",\n",
        "\"grounding\" : \"means there is a connection between the logical reasoning and the agent's actual environment\",\n",
        "\"theorem proving\" : \"use rules of inference to create proof of a sentence, using only KB sentences\",\n",
        "\"logical equivalence\" : \"two sentences are logically equivalent if they are true in the same set of models\",\n",
        "\"validity\" : \"property of sentence that is true in all models\",\n",
        "\"deduction theorem\" : \"$a \\models b$ iff sentence $a\\implies b$ is valid\",\n",
        "\"satisfiability\" : \"attibute of sentences that are true in some model\",\n",
        "\"monotonicity\" : \"property of logical systems because set of entailed sentences will only increase as information is added\",\n",
        "\"clause\" : \"disjunction (or) of literals\",\n",
        "\"factoring\" : \"removal of multiple copies of the same literal so the result only contains one copy\",\n",
        "\"ground resolution theorem\" : \"completeness theorem for resolution in propositional logic: if set of clauses is unsatisfiable, the resolution closure is the empty clause\",\n",
        "\"definite clause\" : \"restricted form sentence that is a disjunction of literals where exactly one is positive\",\n",
        "\"Horn clause\" : \"restricted form sentence that is a disjunction of literals where at most one is positive\",\n",
        "\"goal clauses\" : \"restricted form sentence that is a disjunction of literals where none are positive\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6d61046a-8ca1-4782-d03a-ae35cfb48394"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nProblem-solving agents only have limited knowledge of their environment, what they know is mostly based around the legal actions they can take for a particular problem. They also are limited by atomic represenations.\n\n**Knowledge-based agents** can use logic to combine information for use as needed (now or possibly in the future). They can:\n- accept new tasks with well-defined goals\n- achieve competence by learning new things about the environment\n- adapt to changes in the environment by updating what they had previously known\n\nThe **knowledge base** is the main component of a KB agent. Adding and querying the KB is done with 'ask's and 'tell's. The KB may start with **background knowledge** initially, before the agent adds to or modifies it.\n\n When the knowledge agent is called, it:\n - tells the knowledge base its percepts (make-percept-sentence)\n - asks the KB what actions it should perform (make-action-query)\n - tells the KB what it chose to do, and returns that action (make-action-sentence)\n\n Knowledge agent can determine actions at the knowledge level as opposed to the implementation level. It can also be created by telling it sentences one by one until it knows how to act in its environment (the **declarative**  approach to system building). Successful agents often use a combination of declarative and procedural approaches in their design.\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world example shows us that conclusions can be guaranteed if the information that generated them is correct. \n\n## AIMA Chapter 7.3 Logic\n Entailment means that if a entails b, then b is true in every model in which a is true. a is stronger than b because it rules out more possibilities (the set of a's models is a subset of the set of b's models)\n\nA **sound** inference algorithm (truth preserving) derives only entailed (true) sentences. If it were unsound, it would be able to make things up.\n\nA **complete** inference algorithm can derive any sentence that is entailed.\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n **propositional logic** is composed of:\n- syntax: allowable sentences are atomic that use a single proposition symbol (usually uppercase letter with another letter or subscript, ex. $W_{1,3}$). This symbol stands for a true or false proposition. True always means true, and False always means false. We can construct complex sentences from these simple sentences with parenthesis and logical connectives. The connectives are: not (positive or negative literal), and (conjunction), or (disjunction) implies (premise/antecedent -> conclusion/consequent. also known as if-then statement), biconditional (if and only if). Not operator has highest precedence.\n- semantics: how the truth value of a sentence is determined, given a particular model. We can use truth tables to do this.\n\nEntailment algorithm is sound (directly implements entailment) and complete (works for any KB and a and it always terminates because the state space is finite). There are $2^n$ models, where $n$ is the number of atomic symbols. Time complexity: $O(2^n)$; Space complexity: $O(n)$ because it works depth-first. Every known algorithm for propositional logic has worst-case exponential complexity (based on size of input).\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nLogical equivalence is used to compare sentences (vs biconditional, which is used for elements withn a sentence).\n\nTo determine if a sentence is satisfiable, we must examine all models until we find one in which the sentence is true. This is an NP-complete problem. This can also be expressed as 'a $ \\models $ b iff the sentence (a  $\\land \\lnot$ b) is unsatisfiable'. This is actually a proof by contradiction.\n\n**Modus Ponens** is an inference rule used to derive a proof: $ (a \\implies b, a)/b $ which means if the numerator sentances are present, the denominator sentence can be derived.\n\n**And-Elimination** is an inference rule that says any of the conjuncts can be inferred from a conjunction: $(a \\land b) / a$\n\n**resolution** is an inference rule that can be combined with a complete search algorithm to produce a complete inference algorithm. **unit resolution** uses complementary literals (one is negation of other) to use a literal and a clause to create a new clause (by removing the complementary literal). Full resolution rule takes two clauses, and creates a new clause with all contents from the original two clauses, minus the complementary literals. The resolution rule is sound and complete.\n\nSince every sentence of propositional logic is logically equivalent to a conjunction of clauses, we can express sentences in **conjunctive normal form**. The steps for CNF involve eliminating biconditionals, then eliminating implications, then moving 'not' inwards to individual literals (ex. De Morgan), then apply distributivity law of $\\lor$ over $\\land$ wherever possible.\n\nBoth goal and definite clauses are Horn clauses. Definite clauses can be rewritten as implication where the premise is a conjunction of positive literals and the conclusion is a single positive literal.\n\nEx. $ \\lnot L_{1,1} \\lor \\lnot Breeze \\lor B_{1,1}$ can be written as $ (L_{1,1} \\land Breeze) \\implies B_{1,1}$\n\nInference with Horn clauses use forward-chaining or backward-chaining algorithms. Forward chaining uses modus ponens to make every inference and so is sound. FC is also complete because it will derive every entailed atomic sentence. FC is also a kind a data-driven reasoning. Backward chaining looks for implications in the KB whose conclusion is the query. BC is a type of goal-directed reasoning.\n\n \n\n## Module 7 Lecture Notes\n \n```\nfunction PL-RESOLUTION(KB, alpha) returns true or false\n  inputs: KB, a sentence in propositional logic \n        alpha, the query, a sentence in propositional logic\n\n  clauses (set of clauses in CNF representation of (KB AND not alpha))\n  new (empty {} that keeps track of new clauses)\n  while true do:\n    for each pair of clauses Ci, Cj in clauses do:\n      resolvents = PL-RESOLVE(Ci, Cj) (returns the set of all possible \n      clauses obtained by resolving the two inputs - want to see if there \n      are two things that are the opposite of one another)\n\n      if resolvents contains empty clause, return true (means we found p \n      and not p, so we can return true because alpha is entailed by KB)\n\n      else new = new U resolvents (add resolvents to new set)\n    if new is just a subset of clauses then return false (haven't arrived at anything new not already in KB)\n    otherwise clauses = clauses U new (update clauses with everything we've found)\n```\nResolution algorithm is complete. If our KB has a more restrictive form, we can use more efficient inference algorithms instead:\n- Definite clause (disjunction of literals where exactly one is positive)\n- Horn clause (disjunction of literals where at most one is positive; includes definite clauses and clauses with no positive literals). Horn clauses are closed under resolution: if you apply resolution to a horn clause, it returns a horn clause.\n\nIf KB only has definite clauses, can rewrite them as implication whose premise is a conjuntion of positive literals whose conclusion is a positive literal. Inference can be done through forward- and backward-chaining. Deciding entailment with Horn clauses can be done in linear time (with respect to size of KB) (this is why we would want to have a KB full of definite clauses)\n\nForward-chaining algorithm:\n```\nfucntion PL-FC-ENTAILS(KB,q) returns true or false (does KB entail q?)\n  inputs: KB, a set of propositional definite clauses\n          q, the query, a propsition symbol\n  count (table where count[c] is initially the number of symbols in in clause c's premise)\n  inferred (table where inferred[s] is initially false for all symbols) \n  (tells us if particular symbol has been inferred or not)\n  queue (queue of symbols, initially known to be true in KB)\n\n  while queue is not empty do:\n    pop p from queue\n    if p=q, return true\n    if inferred[p] = false then\n      set inferred[p] to true\n      for each clause c in KB where p is in c.PREMISE do:\n        decrement count[c] (because we've proven part of the clause c)\n        if count[c] = 0 then add c.CONCLUSION to queue (we've proven the whole clause c \n        and seen all parts of the premise)\n  return false\n```\nForward chaining is data-driven reasoning becaues it can start with known data and add premises as percepts come in, and then use the FC algorithm to derive new conclusions. It can do this without a specific query, too.\n\nBackward chaining works in reverse from the query, searching the KB for implications whose conclusion is the query. If we can prove the premises for any clause that match the query, then the query is true. (this is goal-directed reasoning)\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning instead of internal knowledge to decide what to do\n* **Knowledge base** - set of sentences written in a knowledge representation language that asserts something about the world\n* **Axiom** - sentence given without being derived from other sentences\n* **Inference** - deriving a new sentence from an old sentence without making up information\n* **Knowledge level** - can make logical decisions based on knowledge\n* **Declarative** - knowledge on how to act is obtained by an agent from TELL operation rather than direct encoding of behavior\n* **Syntax** - determines if a sentence is well-formed accoring to the representation language\n* **Semantics** - the meaning of a sentence that defines if it is true\n* **Model** - mathematical abstraction of a world in which each sentence is either true or false\n* **M satisfies a** - sentence a is true in model m\n* **M is a model of a** - sentence a is true in model m\n* **Logical entailment** - when one sentence follows logically from another sentence\n* **Logical inference** - using entailment to derive conclusions\n* **Model checking** - listing all possible models to check whether a is true in models where KB is true. Works in finite spaces\n* **Grounding** - means there is a connection between the logical reasoning and the agent's actual environment\n* **Theorem proving** - use rules of inference to create proof of a sentence, using only KB sentences\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - property of sentence that is true in all models\n* **Deduction theorem** - $a \\models b$ iff sentence $a\\implies b$ is valid\n* **Satisfiability** - attibute of sentences that are true in some model\n* **Monotonicity** - property of logical systems because set of entailed sentences will only increase as information is added\n* **Clause** - disjunction (or) of literals\n* **Factoring** - removal of multiple copies of the same literal so the result only contains one copy\n* **Ground resolution theorem** - completeness theorem for resolution in propositional logic: if set of clauses is unsatisfiable, the resolution closure is the empty clause\n* **Definite clause** - restricted form sentence that is a disjunction of literals where exactly one is positive\n* **Horn clause** - restricted form sentence that is a disjunction of literals where at most one is positive\n* **Goal clauses** - restricted form sentence that is a disjunction of literals where none are positive\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",
        "cellView": "form",
        "outputId": "f4da8fed-d385-4871-f9dc-36d17d266b88"
      },
      "source": [
        "#@title\n",
        "# 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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n The dimensions of AI include:\n- human vs rational\n- thought vs behavior\n\n**Human intelligence** involves observations about behavior and about thought. A **Turing test** tests whether a human interrogator can determine if the written answers to his/her written questions are answered by a human or a computer. A total Turing test does this in physical space. In order to successfully pass a Turing test, a computer would need natural language processing, knowledge representation, automated reasoning, machine learning, and for a total Turing test, would also need computer vision, speech recognition, and robotics (for motion). **Cognitive modeling** tries to construct theories of mind, since if we have that, we can express it as a computer program.\n\n**Rationalist approach** to AI uses the study of \"laws of thought\" aka the field of logic. Logic uses knowledge about the world (and probability to fill in the gaps of uncertain information). To get intelligent behavior, we need to add rational action to this, which is the **rational agent** approach. Rational agent approach is more general than \"laws of thought\" approach and is easier to use for scientific development.\n\nAI is focused on studying/constructing agents that do the 'right' thing, which is the objective provided to the agent by us. This paradigm is called the **standard model**. Sometimes, because of computational load, perfect rationality is not possible, so we use limited rationality instead. Problems with the standard model are:\n- We might not be able to fully specify the objective\n- There might be a value alignment problem\n- We cannot anticipate all the ways a rational agent might misbehave if its objective is fixed\n\nWe want machines to pursue our objectives, which means the machine might be uncertain about the objective. These agents should ultimately be positively beneficial to humans.\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Agents perceive their environment through sensors and act upon their environment using actuators. Content that agent's sensors perceive is called a percept, and the collection of all percepts over time for an agent is called the percept sequence. \n- Agents base their actions on the percept sequence to date. \n- Agents cannot use future percepts when making a decision.\nThe **agent function**, which maps percept sequences to actions (and is more of an abstract mathematical description), is implemented internally by the **agent program**, which its concrete \\ \nimplementation running within a physical system.\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational behavior is 'doing the right thing'. We evaluate the behavior of an agent by looking at the consequences of that behavior (**consequentialism**). The agent's sequence of actions (based on its percept sequence) causes the environment to go through a sequence of states, which we evaluate using a **performance measure**.\n\nGood performance measures can be hard to come up with. Best results are usually achieved by designing the performance measure around the desired outcome rather than the agent's behavior. Sometimes, it is better if the agent have some uncertainty over the performance measure and learn about it over time.\n\n**Rationality** depends on 4 things: \n- performance measure to determine success\n- agent's previous knowledge of the environment\n- agent's possible actions\n- agent's current percept sequence\n\nIf an agent is omniscient, it would know the actual outcomes of its actions and would act accordingly - but this is usually not possible in reality because we don't always know the future. This is why rationality maximizes expected performance, not actual performance. Agents may perform information gathering to potentially modify future precepts and rational agents learn as they go from what they perceive.\n\nRational agents also are autonomous, meaning they can learn to compensate for incomplete or incorrect prior knowledge (of the designer). They should learn as much as possible.\n \n\n## AIMA 2.3 The Nature of Environments\n **Task environments** are the problems solved by rational agent solutions. Their nature directly influences the design of the agent program, and they should be specified as completely as possible. We can define them with PEAS:\n- performance measure\n- environment (more restricted environments usually mean easier designs)\n- actuators needed\n- sensors needed\n\nDimensions of task environments include:\n- **Fully observable vs partially observable**. \nFully-observable – agent’s sensors can detect the complete state of the environment at each point in time (esp detect all aspects that are relevant to the choice of action where relevance depends on the performance measure). In FO environments, agent doesn’t need to maintain internal state to keep track of the world \\\nPartially-observable – environment is only partially observable because of problems with sensors, or part of the state missing from sensor data\n- **Single agent vs multiagent**. \nMultiagent – when agent B’s behavior is maximizing a performance measure whose value depends on agent A’s behavior. Multiagent environments can be competitive (ex. chess) or cooperative (ex. auto-driving car), or a mix of both.\n- **Deterministic vs Nondeterministic**. Deterministic – next state of env is completely determined by current state and action executed by agent(s); nondeterministic otherwise. Stochastic environments explicitly deal with quantifiable probabilities, while nondeterministic just list probabilities (without quantifying them)\n- **Episodic vs sequential**. Episodic task environment divides agent’s experience into atomic episodes (each episode: agent receives precept; agent then performs single action) (ex. spotting defective parts). Simpler of the two environments. Sequential task environment – current decision affects future decisions (ex. chess). May require agent to think ahead.\n- **Static vs dynamic**. Dynamic environments can change while agent is deliberating. Continually ask agent what to do and if agent hasn’t decided, counts as doing nothing. Static environments do not require the agent to consider the passage of time or to keep looking at the world while it’s deciding. If environment doesn’t change but agent’s performance score does, environment is called semidynamic.\n-\t**Discrete vs continuous**. Applies to state of the environment, way time is handled, and to percepts/actions of the agent. Ex. chess is discrete, driving is continuous\n-\t**Known vs unknown**. Refers to the agent’s or designer’s state of knowledge about the rules of the environment. Known environment: outcomes (or outcome probabilities) are given. Unknown environment: agent must learn how environment works to make good decisions. Known environments can be partially observable (ex. card games), and unknown environments can be fully observable (ex. video game)\n\nThe hardest case to work with is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n Agent program runs on computing device with actuators and sensors called the agent architecture. Its goal is to produce most rational behavior from the smallest program possible \\(to save memory from a large lookup table). \n\nAgent = agent architecture + agent program\n\n1: **Simple Reflex Agents**\n-\tAgent selects actions based on current precept, ignoring rest of precept history\n-\tReflex behaviors can occur in complex environments (condition-action rules: if/then)\n-\tUsually requires fully observable environment; partially observable env can result in infinite loops. Randomization of actions can help avoid\n\n2: **Model-based Reflex Agents**\n-\tHandle partial observability by tracking unobserved part of the world – agent maintains internal state based on percept history and reflects some of the unobserved aspects. Internal state is best guess from agent\n-\tUpdating state info requires info about how world changes over time (effects of agent actions + how world works independently of agent = **transition model** of the world) and info about how state of world is reflected in agent percepts = **sensor model**. Limited by agent sensors\n-\tTransition model + sensor model = model-based agent\n\n3: **Goal-based Agents**\n-\tAlso needs goal info to describe desirable situations\n-\tSearch and planning are subfields that find sequences to achieve goals\n-\tMore flexible because goal can simply be replaced\n\n4: **Utility-based Agents**\n-\tUtility is performance measure that indicates how “happy” a specific state will make an agent\n-\tUtility function = internalization of performance measure\n-\tIf internal utility function and external performance measure are in agreement, agent that maximizes its utility will be rational\n-\tUtility function can make rational decisions when goals are inadequate or conflicting. Maximizes expected utility of the action outcomes\n-\tNot all are model-based (there are model-free agents)\n\n**Learning agents** can be any type of agent. Can operate in initially unknown environments.\nComponents:\n- Learning element: makes improvements to perf element based on critic feedback\n-\tPerformance element: selects external actions by taking in percepts\n-\tCritic: Uses fixed performance standard that can distinguish incoming precept as reward or penalty that provides direct feedback on agent behavior quality\n- Problem generator: suggests actions that lead to new and informative experiences\n\nRepresentations of the state of the world:\n-\tAtomic: each state is indivisible “black box”\n-\tFactored: split into fixed set of variables/attributes, each of which can have a value. Two factored states can share some attributes and not others\n-\tStructured: things in the state have relationships to one another\n\nAdditional representations:\n-\tLocalist: 1-to-1 arbitrary mapping between concepts and memory locations\n-\tDistributed: rep of concept spread over many memory locations & each location is part of the rep of mult diff concepts. More robust against noise and info loss\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Turing test** - computer passes if human questioner can't tell if written responses to written questions come from a human or a machine\n* **Total turing test** - Turing test conducted in physical space\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent perceives/acts in pursuit of achieving the best expected outcome\n* **Value alignment problem** - problem of getting agreement between our true objective and the objective put into the machine\n* **Weak ai** - the idea that machines could act as if they were actually intelligent\n* **Strong ai** - asserting that machines are actually thinking - not just appearing to be thinking\n* **Percepts** - the content perceived by the agent's sensors\n* **Percept sequence** - a complete history of everything the agent has ever perceived\n* **Performance measure** - used to measure the desirability of a particular state of the environment\n* **Agent function** - maps the behavior of an agent to a specific precept sequence\n* **Agent program** - the actual implementation of the agent program in a concrete environment\n* **Task environment** - can be described with PEAS: performance, environment, actuators, sensors\n* **Utility** - performance measure that indicates how “happy” a specific state will make an agent\n* **Utility function** - internalization of utility-based performance measure\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Python is a strongly typed language - can't combine incompatible types. You can check type with type(object) or isinstance(object, type). Python is dynamically typed, though, so the types of variables are assigned when the variable  is assigned (or reassigned). Functions have no type signatures. This means type errors are caught at runtime.\n\n****\n\n**Mutability**\n- Strings are immutable. They are created once. Concatenating strings creates a new string object. Checking if 2 strings are equal (==) checks if they point to objects with same value. \"is\" checks whether they point to the same object.\n```\nx = 'foo '\ny = x         # so y == x would resolve as true\nx = x.strip() # creates new object\nprint(x)      # 'foo'\nprint(y)      # 'foo '\n```\n\n- Lists are mutable.\n```\nx=[1,2,3,4]\ny = x\nx.append(5)  # does not create new object\nprint(y)     # [1,2,3,4,5]\nprint(x)     # [1,2,3,4,5]\ny = x[:]     # creates shallow copy of x = new object of same value\n```\n****\n\n**Sequences**\n\nSequence elements are indexed using positive numbers (from the left) or negative numbers (from the right)\n\n- **Tuples**\n  - immutable\n  - items can be mixed types, including collection types\n  - declared with ( )\n\n- **Strings**\n  - immutable\n  - regular strings are unicode with 2-byte char\n  - declared with single or double quotes\n  - Can be concatentated using the (overloaded) + sign\n  - % can be used for special string formatting\n  ```\n  print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n  ```\n\n- **Lists**\n  - mutable \n  - ordered mixed type items\n  - declared with [ ]\n\n**Slicing** allows you to return a copy of a subsequence:\n- list-name[first-index(inclusive) : end-index(exclusive)]\n- can use neg indexing as well \n- can use implicit indexing by not including first or last index\n- can select every nth item by adding 3rd argument\n```\nt=(23, 'w', 4, (3,4), 'asdf')\nt[1:4]      # ('w', 4, (3,4))\nt[1:-1]     # ('w', 4, (3,4))\nt[1:-1:2]   # every nth item ('w', (3,4))\nt[:2]       # copy from beginning (23, 'w')\nt[2:]       # copy to end (4, (3,4), 'asdf')\n```\n\n**List Operations**\n- list-name.append(element) adds to end of list\n- list-name.insert(index, element) inserts at that index\n- list-name.index(element) returns index of first occurrance of that element\n- list-name.count(element) returns number of occurrances\n- list-name.remove(element) removes first occurrance\n- list-name.reverse() reverses list in place\n- list-name.sort() sorts the list in place\n- list-name.sort(function) sorts with user-definied comparison\n- sorted(list-name) returns copy of list that's sorted\n\n**String Operations**\n- string.split(char) returns list of string tokens split by char \n- \"char\".join(list) pass in list of tokens to join with char operator\n- string.capitalize()\n- string.upper()\n- string.strip(char)\n***\n**Dictionaries**\n- unordered\n- work by hash table, keys must be immutable\n- constant avg time to add, lookup, update\n```\nd = {'user': 'Jim', 'pw': 1234}\nd['user']   # lookup by key - 'Jim'\nd['Jim']    # will return KeyError\nd['pw'] = 'asdf'  # will replace value for this key\n```\n- d.keys() returns list of current keys\n- d.values() returns list of current values\n- d.items() returns list of item tuples\n- defaultdict(type) is type of dict that can automatically initialize non-existent dictionary values. Values set to type specified. Doesn't throw KeyError if a key isn't in the dict - it will just create it.\n- Counter() dict subclass that counts hashable objects where elements stored as keys and their counts as values. Count of missing element is 0.\n\n***\n**Functions**\n```\ndef function(args):           # can also define default values for args, which makes them optional when function is called\n                              # Must put non-default args first, or else get SyntaxError\n                              # Same with keyword args ex. def func(a,b,c) -> func(c=2,b=1,a=0) or fun(2,a=0,b=1) but not fun(b=1,a=0,2)\n  (Docstring encased in triple quotes)\n  ...\n  return value1, value2       # can return multiple values - will automatically be a tuple\n```\n\nBecause Python doesn't specify type for a function's arguments, you can't overload the function like Java (using same function name more than once with diff args). You can overload operators using special methods when you initialize the class.\n- *args keyword lets you accept variable number of non-keyword args to function\n- **kwargs lets you accept variable number of keyword args to function\n\n```\ndef print_all(*args):   # args is tuple of args\n  print(args)\n\nprint_all('a','b','c')  # ('a','b','c')\nlst = ['a','b','c']\nprint_all(*lst)         # ('a','b','c') - iterates through list using star notation\n\ndef print_keywords(**kwargs):\n  print(kwargs)\n\nprint_keywords(first='Jim', last='Smith')   # returns dict {'first': 'Jim', 'last': 'Smith'}\nmy_dict = {'first': 'Jim', 'last': 'Smith'}\nprint_keywords(**my_dict)                   # can pass in dict {'first': 'Jim', 'last': 'Smith'}\n```\n\nPython uses dynamic scope - uses most current value of variables\n\nCan use recursion and memoization to achieve dynamic programming:\n\n>```\ncalculated = {}   # for memoization\ndef fib(n):\n  if n == 0: # base case 1\n    return 0\n  if n == 1: # base case 2\n    return 1\n  elif n in calculated:\n    return calculated[n]\n  else: # recursive step\n    calculated[n] = fib(n-1) + fib(n-2)\n    return calculated[n]\n```\n\nFunctions are first-class objects which can be dynamically created, destroyed, passed to function, returned as value = same rights as a variable. Higher order functions take a function as input.\n\n>```\ndef compose(f,g,x):\n  return f(g(x))\ncompose(str,sum,[1,2,3])    # '6'\n```\n\n\n***\n**Classes**\n- to create a class, just use 'class NameofClass:'\n- can have attributes - variables that apply to all instances\n- require ```def __init__(self, args):``` to initialize\n- all functions within class require 'self' as argument\n- other magic/dunder methods include ```__str__``` which is the constructor function, ```__len__``` which defines how len(obj) works, ```__cmp__``` which defines ==, etc.\n\n**Subclasses**\n- extension of class that allows us to use methods and attributes defined in parent class\n- to define, put parent class name as argument in first line - ex. class SubClass(ParentClass):\n- multiple inheritence is supported\n- must explicitly call the init function of parent class within its init function\n```\nclass SubClass(ParentClass):\n  def __init__(self, args):\n    ParentClass.__init__(self, args)\n```\n- you can also override parent class methods by using the same method name in subclass with a new definition. Must explicitly call parent class to execute parent class version of method:\nparentClass.method(self, args) this is the only time you'll call self as an argument outside of the class definition (only when calling method of an ancestor - don't have to do it for subclass).\n- Python does not have built in main method - uses ``` if __name__ == '__main__':``` to define main method\n- Duck typing determines the presence of methods for an object - ex. we can call len() on any class that implements ```__len__``` . We get an AttributeError if we try and call a method that isn't implemented.\n***\n**Loops and Iterators**\n- enumerate generates a tuple where first item is index, second item is item\n- list comprehensions create a new list - format is [ expression for name in list if filter ]\n- dictionary and set comprehensions create new dicts and sets and use format { k:v for k,v in list1} and { x for x in list2} respectively\n\n**Generators** are iterators created with magic ```__next__``` method using the 'yield' keyword\n- less code than using iterator\n- maintains local state\n- values computed one at a time\n- saves memory because entire sequence isn't stored\n- one pass to sum or count items\n- bad if you need to inspect individual values\n\n***\n \n\n## Module 2 Definitions\n* **Immutable** - cannot be modified once created\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem solving agents can plan ahead to find the sequence of actions that will lead to the goal using search. They use atomic representations of the world to do so.\n\nProblem solving process:\n- Goal formulation\n- Problem formulation: description of actions and states needed to reach goal\n- Search: agent simulates sequences of actions until it finds one that reaches the goal. It will either discover the solution or discover that there is no solution.\n- Execution: agent will execute the actions in the solution\n\nIf environment is fully observable, deterministic, and known, the solution is a fixed sequence of actions where the agent can ignore precepts while executing the actions. This is an open-loop system. If model is incomplete, incorrect, or nondeterministic, the agent should use a closed-loop approach.\n\nFormal definition of Search Problem includes:\n- State space: the set of possible states that the environment can be in (possibly infinite)\n- Initial state: starting state within state space (may be defined or arbitrary)\n- Goal state(s)\n- Available actions: the finite set of actions available to the agent that can be executed within a certain state. Each action is **applicable** in this state.\n- Transition model: describes what each action does. Returns the state that happens from doing an action to a particular state.\n- Action cost function: numeric cost of applying an action to transition from one state to the resulting state. Should reflect the performance measure.\n- Path: sequence of actions\n- Solution: path from initial state to goal state (includes sum of individual action costs)\n- Optimal solution: solution with lowest path cost\n\nGood problem formulation has the right level of detail vs abstraction. The abstraction is valid if it can be elaborated into a solution in the more detailed world. Abstraction is useful if carrying out each action in the solution is easier than the original problem (because of lack of detail). We should therefore remove as much detail as possible while keeping validity and the ease of carrying out the actions.\n \n\n## AIMA Chapter 3.2 Example Problems\n Sample standardized problems include:\n\n- Grid world problem: \n2D rectangular array of square cells where agents can move from cell to cell (with constraints such as walls, etc)\nStates: says which objects are in which cells (can be infinite state spaces for some math problems)\nInitial state: any\nActions: absolute or egocentric actions or movement\nTransition model: map actions to change states\nGoal state(s)\nAction cost (usually uniform cost)\n\nReal world problem examples include:\n-\tRoute-finding problem\nStates: Location, time (cost may depend on these, so must track history)\nInitial state: user\\’s initial location\nActions: movement from location to location, with changes in time and cost\nGoal state: user\\’s destination (can have more restrictions than this)\nAction cost: money, time, distance, etc.\n-\tTouring problem – set of locations must be visited\n-\tTraveling Salesperson Problem – touring problem that visits every location on map with a cost less than C or the lowest cost possible\n-\tVLSI Problem – determine cell layout and channel routing of chips\n-\tRobot navigation – generalized route finding problem\n-\tAssembly problems such as automatic assembly sequencing and protein design \n\n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithm takes search problem as input and returns a solution or that there is no solution.\n\nSearch tree can use this to model problem where each node in tree corresponds to a state in the state space and edges correspond to actions. Root of tree is initial state. Each node has a unique path back to root. \\ \nWhen we expand nodes, we consider available actions for state and use result function to see where those actions lead, generating a child (successor) node for each resulting state.\n\n**Best-first search**: choose a node with a min value of an evaluation function. Each iteration, we choose another frontier node with min f(n) value. If it is a goal state, we return, else expand the node and create the child nodes. Each child node is added to frontier if it is unreached or else readded if it is now reached with a lower path cost. Algorithm returns failure or node that is part of path to goal.\n\n**Node** in tree represented as data structure with four components:\n- state: the state that the node represents\n- parent: the node that generated this node\n- action: action applied to parent node to generate this node\n- path cost: total cost of path from initial state to this node\n\nWe can follow the parent pointers to recover states and actions backwards. From the goal node, this will give us the solution.\n\n**Frontier** uses a queue data structure with four operations:\n- is empty: return true if no nodes in frontier\n- pop: removes top node and returns it\n- top: returns top node without removing it\n- add: inserts node into the queue\n\nThree types of queues are used in search algorithms:\n- **priority queue**: pops node with min cost according to f(n). Used in best-first search\n- **FIFO queue**. Used in breadth-first search\n- **LIFO queue** aka **stack**. Used in depth-first search\n\nCycles can cause search trees to become infinite, so we need to be able to recognize and remove redundant paths (as long as table of reached states fits in memory), unless we are working with a problem where cycles and redundant paths are rare or impossible. In these problems, not checking reached states or redundant paths means we save memory space. If a search algorithm checks for redundant paths, it is a graph search (ex. BFS). If it does not check, it is tree-like. Tree-like searches use less memory but run slower since they might check redundant paths. We can check for cycles but not redundant paths overall as a compromise.\n\nSearch algorithms are complete if they are systematic in the way they explore the state space (finite or infinite). Time and space complexity are evaluated with respect to the problem difficulty. Can be measured in terms of the **depth** of the number of actions in the optimal solution, the max number of actions in any path, and the **branching factor** of each node.\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search algorithms don't know how close a state is to the goal. They can only solve the smallest instances of exponential-complexity search problems.\n\n**Breadth-first**: when all actions have same cost\n- complete (systematic) even on infinite search spaces\n- f(n) is depth of node\n- check shallowest nodes first\n- reached is set of states rather than nodes because we always find best paths first\n- early goal test when node generated instead of popped from queue (late goal test like best-first search)\n- always finds shortest path\n- space and time: $O(b^d)$\n- memory a bigger problem than time\n\n**Djikstra's Algorithm** / **Uniform Cost**: when actions have different costs by considering all paths systematically in order of increasing cost\n- algorithm is Best First Search where f(n) is path cost\n- tests for goal when expanding (lowest cost) node from the frontier\n- space and time: $O(b^{1+\\lfloor C* / e \rfloor })$ where C* is the cost of optimal solution and e is the lower bound of each action cost\n- if all action costs the same, UCS is similar to BFS: $O(b^{d+1})$\n- complete, cost-optimal\n\n**Depth-first** expands deepest node first\n- not cost optimal: returns first solution, not always cheapest\n- efficient, complete in finite tree-like spaces\n- less efficient in acyclic state spaces (still complete)\n- not systematic or complete in infinite state spaces (even without cycles)\n- use DFS in tree-like search because it has lower memory needs (small frontier, no tracking reached states) - only $O(bm)$ where b=branching factor and m=max depth\n- used for constraint satisfaction, propositional satisfiability, logic programming\n\n**Backtracking**: variant of DFS, even less memory\n- generate one successor at a time\n- partially-expanded nodes track which to generate next\n- successors generated by modifying current state rather than saving as brand new state\n- space: $O(m)$\n- can use efficient data structure for states on current path to check for cycles: $O(1)$ time\n- must be able to undo each action\n- used for problems with large state descriptions\n\n**Depth-limited** explore to depth limit $l$\n- time: $O(b^l)$\n- space: $O(bl)$\n- more efficient if we know what $l$ should be (diameter)\n\n**Iterative deepening** tries all values of $l$ until solution/failure found\n- space: $O(bd)$ (solution); $O(bm)$ (finite state no solution)\n- use for problems where all actions have same cost (like BFS)\n- complete on finite, acyclic state spaces\n- complete on any finite space if we check for cycles\n- time: $O(b^d)$ (solution); $O(b^m)$ (no solution)\n- final nodes generated once; upper nodes generated each time run (but fewer nodes at top)\n\n**Bidirectional** searches from initial state and back from goal state\n- two frontiers, two tables of reached states\n- solution when frontiers collide\n- expands min f(n) value node on either frontier\n- if f(n) is path cost it is bidirectional UCS and first solution will be best\n- diff f(n) don't guarantee first solution is optimal\n \n \n\n## Module 3 Lecture Notes\n Comparing graph search and tree search:\n```\nfunction TREE-SEARCH(problem) returns solution or failure\n      initialize the frontier with initial problem state\n      loop do:\n          if frontier is empty, return failure\n          otherwise:\n              pop leaf node from frontier\n              if it is the goal state, return solution\n              else expand the node and add successors to frontier\n\nfunction GRAPH-SEARCH(problem) returns solution or failure\n      initialize frontier with initial problem state\n      initialize explored set as empty (** this is different)\n      loop do\n          if frontier is empty, return failure\n          otherwise:\n              pop leaf from frontier\n              if it is the goal state, return solution\n              add node to explored set (** this is different)\n              expand the node and add successors to frontier\n                only if not already in frontier or explored set (handles repeated states)\n\n```\nRepeated states can make a problem exponential, even if it was previously linear. Graph search helps by checking for repeated states. Exponential complexity uninformed search cannot be solved unless they are very small because memory problems becomes an issue (more than time complexity).\n\nUninformed search is aka \"blind search\" because the agent can only use information from the problem definition. The agent is unable to evaluate non-goal nodes as to being better than others.\n\n```\nfunction BREADTH-FIRST-SEARCH (problem) returns solution or failure\n    node (node with state = initial state of problem. path cost = 0)\n    perform goal test on state, return solution if true\n    frontier (FIFO containing initial node)\n    explored (empty set)\n    loop do:\n        if frontier empty, return failure\n        pop (shallowest) node from frontier (this determines search strategy)\n        (if this were Uniform Cost Search, there would be a goal test here)\n        add node to explored\n        for each legal action possible do:\n              if successor state not in explored or frontier then\n                  if goal test of this state = true, return solution\n                  otherwise add child node to the frontier (note: after testing for goal)\n```\n\nDFS essentially the same but uses LIFO queue. DFS is best if space is limited, solutions can have long paths and wrong paths are caught quickly, search can be fine-tuned quickly. BFS is better if there could be infinite paths, solutions could have short paths, and unpromising paths can be quickly abandoned.\n\nBest of both could be:\n- Depth-limited search (depth limit $l$ - eliminates possible infinite paths). If $l=d$, it is optimal, otherwise $l<d$ it is incomplete, $l>d$ it is not optimal. Space is $O(bl)$ which is good.\n- Iterative deepening search (DLS with increasing $l$) - this is complete and optimal (if step cost is 1), space complexity is good ($O(bd)$ - better than BFS) but space complexity is asymptotic ($O(b^d)$)\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop system** - loop between agent and environment broken by ignoring precepts\n* **Closed-loop approach** - branching strategy that recommends different actions based on precepts\n* **Model** - abstract mathematical description\n* **Abstraction** - process of removing detail from a representation\n* **Standardized problem** - illustrates or exercises various problem solving methods such that it is suitable as a benchmark\n* **Real world problem** - has ideosyncratic solutions that people actually use\n* **Frontier** - set of unexpanded nodes in search tree that separates the reached from the unreached regions\n* **Completeness** - quality of algorithm guaranteed to correctly find solution or report lack of one\n* **Cost optimality** - quality of algorithm that correctly finds a solution with lowest path cost\n* **Time complexity** - length of time (or number of states) required to find a solution\n* **Space complexity** - amount of memory needed to perform search\n* **Diameter** - describes max number of steps needed to reach any state within state space\n* **Best first search** - uses evaluation function to select nodes to expand\n* **Breadth first search** - complete and optimal algorithm that expands shallowest nodes first and has exponential space complexity\n* **Uniform cost search** - optimal algorithm that expands node with lowest path cost\n* **Depth first search** - algorithm that expands deepest unexplored node first. Not complete or optimal. Has linear space complexity.\n* **Depth limited search** - depth first search with a limit on explored depth\n* **Iterative deepening search** - depth limited search with increasing limits on depth. Has linear space complexity, same time complexity as BFS. Complete and optimal.\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed search can be more efficient than uninformed search. Heuristic function used to give hints about goal location.\n\n$h(n)$: estimated cost of cheapest path from current node $n$ to goal\n\n**Greedy Best First**\n- expands node with lowest $h(n)$ value (i.e. node seemingly closest to goal)\n- $f(n) = h(n)$\n- complete in finite search spaces (but not in infinite)\n- time and space: $O(|V|)$, can be reduced to $O(bm)$ with good heuristic\n\n**A Star**\n- best first that uses $f(n) = g(n) + h(n)$, where $g(n)$ is actual path cost to current node $n$ and $h(n)$ is estimated path cost from $n$ to goal\n- complete\n- expands node in frontier with lowest $f(n)$ value\n- cost-optimality depends on admissable and consistent heuristic\n- consistent heuristic means we will always reach a state via an optimal path first, we never have to re-add states to the frontier\n- if heuristic is inadmissible, cost-optimality is not guaranteed\n- efficient by pruning nodes not part of optimal solution\n\nConsistent heuristic: $h(n) \\leq c(n,a,n') + (h(n'))$. Always admissible, but not vice-versa. \n\nIf $C*$ represents optimal solution path cost:\n- A* surely expands all nodes from initial state where every node's $f(n) < C*$\n- A* might expand nodes where $f(n) = C*$ (on the global contour)\n- A* expands no nodes where $f(n) > C*$\n\nProblem for A* is it expands a lot of nodes so reducing nodes may mean accepting suboptimal, satisficing solutions (ex. using inadmissable/overestimating heuristic that may be more accurate)\n\n**Weighted A* Search**\n- heuristic weighted more: $f(n) = g(n) + W * h(n)$ for some $W > 1$ (ex detour index)\n- solution cost somewhere between C* and $W * $C* (closer to optimal in practice)\n\nOther suboptimal search:\n- **bounded suboptimal**: solution within constant factor W of optimal cost (ex. weighted A*)\n- **bounded cost**: solution cost less than some constant C\n- **unbounded cost**: any cost solution is ok if found quickly (ex speedy search)\n\nMemory requirements determined by size of frontier and size of reached states.\n\nMemory-conserving search:\n- **beam search**\n- **iterative deepening A** doesn't keep all reached states in memory, but extra cost of visiting states multiple times. \nUsed for programs that don't fit in memory\nCutoff is $f$-cost ($g+h$) at each iteration\nNext cutoff value is lowest $f$ cost node just beyond previous cut-off\n- **Recursive best first search** BFS but with linear space. Tracks alt paths available from ancestors of current node - may backtrack and replace nodes with backed up values. \nMore efficient than IDA*\nOptimal if $h(n)$ admissable\n\nIDA* and RBFS use too little memory and may explore same states multiple times\n\n**Memory bounded A** and **Simplified MA** use all available memory. SMA expands newest best leaf and deletes oldest worst leaf. Complete if reachable solution.\n\n**Bidirectional heuristic search** must consider surely expanded pairs of nodes. Sometimes more efficient with avg heuristic.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nJudging quality of heuristic:\n- effective branching factor b* = branching factor a tree of uniform depth $d$ would have to contain $N+1$ nodes, where $N$ is the total number of nodes generated and solution depth $d$\n- well-designed heuristics have a b* close to 1\n\nDomination:\n- If h2 dominates h1: $h2(n) \\geq h1(n)$ and using h2 will never expand more nodes than using h1. h1 will always expand all nodes that h2 does, plus possibly others. Usually better to use heuristic with higher values as long as it is consistent and is not slow computationally.\n\nUsing a relaxed version of a problem is one way to find a heuristic. Relaxed problem adds edges to state space graph, and optimal solution in the original problem is still a solution in the relaxed problem. Relaxed problem may allow us to find shortcuts that are better, so the cost of these optimal solutions becomes an admissible heuristic for the original problem. The heuristics are also consistent because they still obey the triangle ineequality.\n\nWe can use composite heuristics when we have trouble distinguishing between the quality of several heuristics: different ones are used on different nodes (although this can be slower computationally).\n$h(n) =$ max {$h1(n),…, hk(n)$}\n\nWe can generate heuristics from the solution of a subproblem within the problem.\n\nFor route-finding search, we can choose landmark points (pivots/anchors) and precompute the optimal path between every vertex in the graph and the landmark. Can then compute inadmissable (overestimates cost to goal if optimal path doesn't go through landmark) heuristic from current node landmark to goal. We can also add shortcuts (artifical graph edges) that describe optimal multi-action paths.\n\nWe can make the landmark search admissable by turning it into a differential heuristic. Also landmarks should be spread out so they are not super close to each other.\n\nAgents can learn to search better. For example, an agent can use a metalevel search space to learn to avoid non-helpful states. The overall goal is to minimize the total cost of problem solving, even if there have to be tradeoffs between computational cost and path cost.\n\nMachine learning can also be achieved with experience, although heuristics generated this way may not be admissible. We can include features of the state that help predict the heuristic value to improve this.\n \n\n## Module 4 Lecture Notes\n Uniform Cost Search is an extension of BFS where we expand the node with the lowest path cost. The frontier is a priority queue ordered by the lowest path cost to get to that node ($g(n)$). Different from BFS because it tests if a node is a goal state when it's popped from the queue, not when it's added to the frontier. If a better path to that node is found, it will update the node on the frontier (so that's why goal check is after it comes out of the queue - so you know you have the lowest-cost version). We can thus prioritize which paths to explore. Uniform Cost Search is also called Dijkstra's Algorithm. It is complete and optimal.\n\nBest-first search improves on this by using an evaluation function to select the node to pop off the queue. The evaluation function $f(n)$ includes an estimate of the distance between this node and the goal. So, Best-first search is UCS where $f(n)$ replaces $g(n)$. Heuristic function $h(n)$ estimates the distance between a state $n$ and the goal. Heuristics are helpful, but not always exact or correct.\n\nGreedy best-first search expands node that is estimated to be closest to the goal, ignoring $g(n)$, which is the cost to get to $n$. So $f(n) = h(n)$. It is not optimal (not guaranteed to find lowest-cost) or complete (can get stuck in loops).\n```\nfunction GREEDY-BEST-FIRST(problem, heuristic) returns solution or failure\n    frontier (priority queue)\n    initial node put into frontier\n    came_from (empty set)\n    while frontier is not empty:\n        pop node from queue\n        goal-test node - if goal, return solution\n        else for each neighbor not in came_from:\n              set node priority to h(n)\n              put node in frontier\n              put node in came_from\n\n```\nA* Search is another form of best-first search that avoids exploring expensive paths and focus instead on most promising. It's evaluation function is: $f(n) = g(n) + h(n)$, where $g(n)$ is the actual cost to reach current node, $h(n)$ is the estimated cost to get from the current node to the goal, so $f(n)$ is the total cost of the path from the initial state through the current node to the goal. Its frontier is also a monotonically increasing priority queue. - Optimal with an admissible heuristic\n- basically UCS (distance from start to current) + Greedy best-first (distance from current to goal)\n\nAdmissible heuristic never overestimates the cost to reach the goal (optimistic). Inadmissible heuristics tend to push the good plans too far down the queue.\n\nRelaxed problem is one with fewer restrictions than the original. The cost of an optimal solution for a relaxed problem is an admissible heuristic for the original problem. Ex. True map travel distance vs Manhattan distance\n\nDominance means one heuristic is better than (dominates) another. If $h_2(n) \\geq h_1(n)$ for all $n$ and both are admissible:\n- $h_2$ dominates $h_1$\n- $h_2$ has a higher cost but is still optimistic\n- $h_2$ is  optimistic and **more accurate** than $h_1$ and is better for search\n\nBest heuristic = the truth ( h*(n) ): called the Oracle heuristic, is unachievable, dominates all other heuristics\nWorst heuristic = 0 (aka we're here): dominated by all other heuristics, basically uniform cost search\nSo an admissible heuristic is 0 <= h(n) <= h*(n)\n\nA* is used in path/route planning (maps), video games, robot motion planning, resource planning\n\n```\nfunction A-STAR-SEARCH(problem, heuristic) returns solution or failure\n    frontier (priority queue)\n    put starting node in the frontier\n    came_from (empty dict)\n    cost_so_far (empty_dict)\n    came_from[start] = 0\n    cost_so_far[start] = 0\n\n    while frontier is not empty:\n        pop node from queue\n        goal-check node, if goal then return solution\n\n        else for each neighbor of current node:\n            set new_cost = cost_so_far[current] + graph.cost[current, next]\n            if next not in cost_so_far or new_cost is less than cost_so_far[next]:\n                set cost_so_far[next] to new_cost\n                set node priority to new_cost + heuristic(goal, next)\n                add node to frontier\n                came_from[next] = current node\n```\n\n \n\n## Module 4 Definitions\n* **Informed search** - uses heauristics: hints specific to the domain about the location of goals\n* **Heuristic function** - gives estimated cost of cheapest path from current node $n$ to goal state\n* **Admissible heuristic** - optimistic heuristic that always underestimates cost to reach goal\n* **Consistency** - When going from one node to another, estimated step cost never exceeds actual step cost. Based on triangle inequality\n* **Triangle inequality** - one side of a triangle cannot be longer than sum of other sides\n* **Monotonic** - never decreases\n* **Optimally efficient** - means any algorithm with same heuristic will expand same surely expanded nodes as A*\n* **Greedy best-first search** - expands nodes with minimal heuristic cost. Not optimal but is usually efficient.\n* **A* search** - expands nodes with minimal actual + estimated costs. Complete and optimal with admissible heuristic but has space complexity problems\n* **Bidirectional a* search** - A* search that measures from start and goal. Can be more efficient than A*\n* **Front-to-end** - heuristic that measures distance to goal or distance to start\n* **Front-to-front** - heuristic that measures distance to other frontier\n* **Backed-up value** - best $f$-value of child nodes\n* **Reference count** - number of times state has been reached\n* **Ida*** - iterative deepening version of A* that addresses its space complexity problems\n* **Rbfs** - optimal variation of best first search that uses limited memory\n* **Sma*** - optimal variation of A*  that uses limited memory and can solve problems when A* runs out of memory\n* **Speedy search** - greedy best first with $h(n)$ equal to the estimated number of actions to reach goal\n* **Beam search** - memory-conserving incomplete and suboptimal search that limits size of frontier and runs faster than complete searches\n* **Weighted a* search** - uses weighted heuristic to focus on goal, expanding fewer nodes. Tradeoff is optimality.\n* **Domination** - when one heuristic always outperforms and is more efficient than another\n* **Relaxed problem** - version of a problem with fewer restrictions. Creates a supergraph of original problem.\n* **Pattern database** - stores all solution costs for subproblem instances\n* **Disjoint pattern databases** - use added costs of disjoint solutions to get lower bound on cost of solving entire problem\n* **Metalevel state space** - contains each state of the internal state of a program searching a regular state space\n* **Metalevel learning** - algorithm that uses metalevel state space to learn to avoid unpromising search trees\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n In adversarial environments, other agents are actively trying to defeat us. We can model these agents using adversarial tree game-tree search approaches. We can use the Minimax algorithm to solve these problems.\n\nFormal definition of a game:\n- Initial state of the game\n- The player whose turn it is to move in a particular state\n- The set of legal moves (actions) within a particular state\n- The transition model (result) of the state that results from making a particular move in a previous state\n- Terminal test that checks if game is over; if yes, current state is terminal state\n- Utility function that assigns final numeric value (payoff) to the player when the game ends\n\nState space graph is definied by the actions function and the result function. There may be multiple ways/paths to reach a state in the game. We can use a search tree to determine the next best move in the graph.  \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n For adversarial search, we need a conditional plan. In games with multiple outcome scores, we should use minimax search to do this.\n\n**Minimax Search**\n- determine minimax value of each state in the tree\n- in non-terminal state, MAX wants to move to a state of max value (when it is MAX's turn) and MIN wants to move to state that is min value for MAX\n- if MIN does not play optimally, MAX will do at least as well as if it were going against an optimal player\n- algorithm computes all states and returns one with the highest minmax value\n- completes depth-frist exploration of entire game tree\n- time: $O(b^m)$ where $b$ is legal moves and $m$ is max depth of tree\n- space: $O(bm)$ if algo generates all actions at once, or $O(m)$ if actions are generated one at a time\n\nMinimax is not useful for complex games because of its exponential complexity.\n\nFor multiplayer games, utility will be returned from each player's viewpoint in terminal states. Backed-up value of a node n is utility of child state with highest value for the player making a choice at n. Note that multiplayer games might include alliances between players.\n\nWe can reduce the number of game states explored by pruning parts of the tree that will not affect the outcome. **Alpha-Beta pruning** can be used on trees of any depth, and both leaves and subtrees can be pruned. The two extra parameters are **alpha** (highest-value choice found so far on path for MAX - \"at least\") and **beta** (lowest-value choice found so far on path for MIN - \"at most\"). \n\nEffectiveness depends on the order in which states are examined - most efficient to examine likely best child nodes. \n- Done perfectly: $O(b^{m/2} )$ nodes examined, branching factor of $\\sqrt b$ instead of $b$\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can reduce computation time by cutting off the search at a predetermined point (cutoff test) and using a heuristic to evaluate the now terminal states. Heuristic will give estimate of expected utility of a state to a player. Estimate can be calculated by combining the expected utility of the individual features of the state (weighted linear function). Can also use non-linear elements that happen because certain combinations of elements might have a different value than they do as independent elements.\n\nWe can run an iterative deepening version of alpha-beta search, where we increase the cut-off depth on each iteration. Other ways of reducing computation time include forward pruning (ex beam search) or probabilistic cut algorithm (forward-pruning version of alpha-beta search using stats/probability from prior experience to avoid pruning best move) or late move reduction (assumes later moves are less likely to be good, so we reduce the amount of time we search these moves)\n \n\n## AIMA Chapter 5.5 Stochastic Games\n **Stochastic games** cannot use normal game tree because of the element of chance. Their game tree includes chance nodes in addition to the MIN and MAX nodes. Positions no longer have definite minimax values - they have expected values instead. The expected value is the average of all possible outcomes (sum of all outcomes weighted by probability of that outcome). Stochastic games use the **expetiminimax** value (similar to minimax value), where we determine the expected value for chance nodes. The best evaluation function will be the one that returns values that are a positive linear transformation of the probability of winning.\n- Expectiminimax time: $O(b^mn^m)$, where $n$ is number of distinct rolls\n- Extra cost means it is not very helpful to look very far ahead for stochastic games, because levels of chance remove element of 'likely' moves\n- We can use pruning on game tree chance nodes by considering bounds on the possible values of the utility function\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n**MEU (maximum expected utility) principle** is the formal abstract way of stating that intelligent agents should act rationally, although it does not state how this should be done. It helps define the problem.\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Rational preference relation has the following constraints (axioms of utility theory - if an agent violates one, it will behave irrationally):\n- **Orderability** - Given any two lotteries, an agent has to decide if one is more preferable than the other, or if they are equal (A>B, B>A, A~B)\n- **Transitivity** - Given any three lotteries, if an agent prefers A to B and B to C, then the agent prefers A to C \n- **Continuity** - If some lottery B is between A and C then there is some probability $p$ that will make the agent indifferent between getting B, getting A (with $p$), and getting C (with $1-p$)\n- **Substitutability** - If agent is indifferent to A and B, then agent is indifferent to more complex identical lotteries where B is substituted for A\n- **Monotonicity** - If two lotteries have outcomes A and B and agent prefers A to B, then agent prefers lottery with higher probability for A as the outcome\n- **Decomposability** - Compound lotteries can be simplified using laws of probability\n\nWe can derive the following from these axioms:\n- **existence of utility function** - if agent follows axioms, then there is a function $U$ such that $U(A) > U(B)$ iff agent prefers A to B, and $U(A) = U(B)$ iff agent is indifferent\n- **expected utility of a lottery** - utility of a lottery is the sum of the probability of each outcome multiplied by the utility of that outcome\n\nWhen probabilities and utilities of states are determined, utility of compound lottery is determined. Note that utility functions are not guaranteed to be unique.\n \n\n## AIMA Chapter 16.3 Utility Functions\n Scales for utilities are helpful in order to compare them for a specific problem. We can establish a scale by fixing the worst and best outcomes as measurement points. When human judgement is involved, there are a range of other aspects that influence how human agent's act.\n \n\n## Module 5 Lecture Notes\n Simplest game environment is multiagent, static (no change while agent deliberates), discrete (finite precepts and actions), fully observable, strategic\n\nOur games: 2 players, alternate moves, zero-sum, clear set of legal moves, well-definied outcomes (win/lose/draw)\nProperties of complex games: stochastic (not deterministic), not fully observable, continuous (not discrete), no pause between actions, no turns, also cooperative games\n\nIf we configure games as search:\n- initial state\n- successor function (pair of (move,state) that specify legal moves)\n- terminal state test\n- utility function (numerical values given to terminal states)\n- MAX determines next move through search tree\n\nGame trees:\n- nodes are board states\n- edges are legal moves\n- root node is first state in which a decision must be made\n- evaluation function that assigns numbers to board positions without needing to know path to get there (evaluates board position based on static features of board $f(n)>0$ if MAX is winning, $f(n)=0$ if tied, $f(n)<0$ if MIN is winning in position n)\n\nMinimax: assumes MAX's best moves are based on MIN also making the best move for itself. Computed recursively. The minimax value is the best achievable utility against a rational opponent.\n\n```\ndef value(state)\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state)\n  if it is MIN's turn, return min-value(state)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n  return v\n\ndef min-value(state)\n  initialize v = +inf\n  for each successor of state:\n      v = min(v, value(successor))\n  return v\n  \n```\n\nAlpha-beta pruning = minimax that tracks 2 additional values: alpha ('at least' = MAX's lower bound on MAX's outcome) and beta ('at most' = MIN's upper bound on MIN's outcome). We stop evaluating a branch whenever a value >= beta is backed up for a MAX node (because MIN will never select it) or whenever a value <= alpha is backed up for MIN node (because MAX will never select it)\n\n```\ndef value(state)\n  alpha = -inf\n  beta = +inf\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state, alpha, beta)\n  if it is MIN's turn, return min-value(state, alpha, beta)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n      alpha = max(alpha, v)\n  return v\n\ndef min-value(state)\n  initialize v = +inf\n  for each successor of state:\n      v = min(v, value(successor))\n      beta = min(beta, v)\n  return v\n\n```\n\nExpectimax is used for games with uncertain outcomes (contain chance nodes). It computers average score under optimal play: MAX nodes, Chance nodes (instead of MIN) , calculate expected utility of the chance node (weighted expectation of all children)\n\n```\ndef value(state)\n  if state is terminal, return state's utility\n  if it is MAX's turn, return max-value(state)\n  if it is EXP's turn, return exp-value(state)\n\ndef max-value(state)\n  initialize v = -inf\n  for each successor of state:\n      v = max(v, value(successor))\n  return v\n\ndef exp-value(state)\n  initialize v = 0\n  for each successor of state:\n      p = probability(successor)\n        v += p*\n      value(successor)\nreturn v\n```\n\n\n \n\n## Module 5 Definitions\n* **Competitive environments** - environment where two or more agents operate with conflicting goals\n* **Adversarial search** - search problem in multi-agent competitive environments\n* **Perfect information** - means fully observable\n* **Zero-sum game** - game in which there is no win-win: if one player wins, the other loses\n* **Position** - in the context of a game, it is the state\n* **State space graph** - graph where vertices are states and edges are moves\n* **Game tree** - search tree that tracks all sequences of moves to a terminal state. Can be infinite.\n* **Ply** - one move by one player\n* **Minimax value** - utility/max of being in a particular state, assuming optimal play from both players to the end of the game\n* **Minimax decision** - optimal choice for MAX in order to get to state with highest minimax value\n* **Transpositions** - move sequence permutations that end up at same position\n* **Transposition table** - used to track heuristic values of positions/states\n* **Type a strategy** - strategy that looks at all moves up to a certain tree depth (wide but shallow)\n* **Type b strategy** - strategy that looks only at promising moves and follows them as far as it can\n* **Horizon effect** - agent faces unavoidable (but delayable) negative opponent move\n* **Singular extension** - in cutoff alpha-beta search, allows 'clearly better' moves that would normally be cut off\n* **Forward pruning** - prune moves that look like they will be bad, with the risk they might be good\n* **Stochastic game** - game that contains random/chance elements\n* **Expected utility** - average utility value of all outcomes weighted by probability of each of those outcomes occurrs\n* **Maximum expected utility (meu)** - principle that states a rational agent will choose the action that maximizes utility\n* **Value function or ordinal utility function** - in deterministic environments, an agent just needs a ranking on states\n* **Normalized utilities** - scale between 0-1 (worst and best outcome), adjust $p$ until agent indifferent to $S$ vs standard lottery\n* **Certainty equivalent** - amount an agent will accept in place of a lottery\n* **Risk-neutral** - agent with a linear curve in relation to small changes in wealth vs current wealth\n* **Optimizer’s curse** - when estimated expected utility of the best choice is higher than it should be\n* **Normative theory** - describes how rational agent is supposed to act\n* **Descriptive theory** - describes how rational agent acutally acts\n* **Certainty effect** - people tend to prefer things that are 'sure' things\n* **Ambiguity aversion** - people avoid unknown probabilities\n* **Framing effect** - the way a decision problem is worded can influence the agent's choices\n* **Anchoring effect** - uses relative utility judgments to influence an agent's choice\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n To examine **constraint satisfaction problems** we need to break atomic representation of a state into a **factored representation** that has a set of variables, each assigned its own value. CSP algorithms use general heuristics to solve CSP problems. We can eliminate sections of the search space simply by removing states that violate constraints (something atomic solvers cannot do). This means if a problem can be formulated as a CSP, it can often be solved much mroe quickly than an atomic problem. CSPs are NP-complete.\n\nExamples CSPs: map coloring, job scheduling, assembling, N-queens\n\nCSP components:\n- set of variables $\\{X_1, ..., X_n\\}$\n- set of domains, one for each variable $\\{D_1, ..., D_n\\}$\n- set of constraints that specific allowable value combinations\n\nEach constraint is composed of a pair of scope (tuple of variables) and relation that defines those variable's values. A relation can be an explicit set of values or a function that can compute valid values.\n\nCSPs can be depicted as constraint graphs, where the nodes of the graph represent the variables in the problem, and the edges represent the constraints. Simple CSPs have discrete (can be infinite), finite domains. Real-world CSPs often have continuous domains (ex linear programming problems, where constraints are linear equalities/inequalities).\n\nTypes of constraints:\n- **unary** - restricts value of one variable\n- **binary** - relates values of two variables (binary CSP only has unary and binary constraints and can be represented as a constraint graph)\n- \"\"higher order**\n- **global** - restricts an arbitrary number of variables (not necessarily all)\n\nCSPs can also have preference constraints to determine preferred solutions. These can be encapsulated as costs on variable assignments. CSP then becomes constrained optimization problem.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n CSPs can make progress by creating successors through new variable assignments or perform inference through constraint propagation, using local consistency, which removes inconsistent values from the graph.\n\nTypes of local consistency:\n- **node consistency**: node-consistent variables have values that satisfy the variable's unary constraints (remove inconsistent values or convert to binary at the start of the solving process). If all nodes are consistent, then graph is node-consistent\n- **arc consistency**: arc-consistent variables have values that satisfy the variable's binary constraints. Graph is arc-consistent if all variables are with every other variable.\n\nAC is enforced with algorithm AC-3:\n- maintain queue of arcs\n- pop one arc off of queue and make arc-consistent\n- if domain is changed (smaller), we add to queue all arcs that are neighbors of this arc\n- if domain is empty, immediately return failure\n- can either solve completely or prove no solution\n- time to check one arc: $O(d^2)$\n- time to check all arcs: $O(cd^3)$ where $d$ is domain size and $c$ is number of binary constraints\n\nArc-consistent CSP faster to search because of smaller domains.\n\nPath consistency considers 3 variables: $X_i - X_m - X_j$\n\nK-consistency means for any set of $k-1$ variables in the CSP with a consistent assignment, a consistent value can be assigned to the $k^{th}$ variable:\n- unary: 1-consistency\n- arc: 2-consistency\n- path: 3-consistency\nFor a strongly k-consistent graph, time: $O(n^2d)$ where $n$ is number of nodes. However, it will require space exponential to $n$ and will take time exponential in $n$.\n\n**Alldiff** constraint algorithm: remove variables with singleton domains and then remove those values from the remaining variable domains. Continue until either an empty domain is created or more variables than domain values left.\n\n**Resource (Atmost) constraint** - can check the sum of the min values of all the domains or check whether the max values of domains are consistent with min values of other domains.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n **backtracking search** chooses an unassigned variable, and tries all the values of that variable's domain, using a recursive call to try and find a solution. When one value fails, it moves on to the next one. Keeps only one representation of a state and changes it rather than creating new states. Can be improved with domain-independent heuristics:\n- choose **minimum-remaining-values (MRV)** heuristic, which picks the variable with fewest 'legal' values. Designed to find branches of the search tree that 'fail fast' so that those branches can be pruned. \nPerforms better than random or static ordering. (variable is fail-first)\n- use **degree heuristic** which tries to reduce branching by choosing the vairable that has the largest number of constraints on other (unassigned) variables. Can be used as a tie-breaker or when there is no clear choice for the MRV heuristic\n(ex all domains are the same size)\n- use **least constraining value** heuristic, which chooses a value based on it constraining the fewest choices in neighboring variables. Tries to keep maximum flexibility for subsequent assignments. (value is fail-last)\n\nNote that value ordering does not matter if we are trying to find all solutions instead of just one.\n\n**forward checking** is using inference to check neighboring variables to eliminate non-legal values once a variable has a value chosen (establishes arc consistency for a variable with whatever other variables are connected to it). Doesn't detect all inconsistencies because it doesn't go forward enough.\n\nUsually efficient to combine forward checking with MRV heuristic.\n\n**Maintaining arc consistency (MAC)** detects inconsistencies through inference by recursively propgating constraints as variable values are assigned. Goes farther than forward checking.\n\nDon't need to do both backjumping and forward checking in the same search - forward checking (or using MAC algorithm) will prune the same branches that backjumping prunes.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms work well for solving CSPs, using complete-state formulation where all variables are assigned a value in every state, and search changes one variable at a time. We can use the **min conflicts** heuristic after randomly choosing a conflicted variable to choose a value with the fewest conflicts with other variables. Min conflicts works well for both easy and hard problems (ex n-Queens and scheduling the Hubble Telescope). We can also use constraint weighting to focus just on the most important constraints.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can look at the structure of the problem itself to help find an effective approach. We can identify **independent subproblems** by finding connected components within the constraint graph. We can also see if the CSP is tree-shaped where we know it can be solved in linear time relative to the number of variables. We can use directional arc consistency to determine this (and avoid backtracking by using a topological sort, which takes $O(n)$ steps to make directed arc-consistent (total time is $O(nd^2)$).\n\nWe can then use other methods to try and reduce constraint graphs into trees.\n- **cutset conditioning** assigns values to some variables so that the remaining ones form a tree. We have to test each possible value for those variables in order to choose one that results in the tree structure having a solution.\n- \"\"tree decomposition** of constraint graph: transform original graph into a tree where each node of the tree is a set of variables such that every variable in the original problem appears in at least one tree node,\nif two variables are connected by a constraint, the variables plus their constraint must appear in at least one tree node, and if a variable appears in two tree nodes, it has to appear in every node on the path between those two nodes.\n\nWith a tree-structured graph, we can use the Tree-CSP-Solver algorithm (time: $O(nd^2)$, where $n$ is nodes and $d$ is size of largest domain) - this is efficient as long as $d$ remains small. When performing a tree decomposition the goal is to keep subproblems as small as possible. The tree width of the tree decomposition is one less than the size of the largest node, tree width of entire graph is min width of all tree decompositions. If a graph has tree width $w$, it can be solved in $O(nd^{w+1})$ time, so CSPs that have constraint graphs of bounded tree width are solvable in polynomial time.\n\nFor cutset conditioning vs tree decomposition, time favors tree decomposition, but cutset uses linear memory (tree memory is exponential in $w$)\n\nWhen looking at the values of variables, we realize that permutations of values mean there are $d!$ solutions made by permuting $d$ possible values. To break value symmetry, we can use a symmetry-breaking constraint, such as imposing some sort of arbitrary order of values. In gerneral, it is NP-hard to eliminate all symmetry, but breaking some symmetry is usually effective.\n\n \n\n## Module 6 Lecture Notes\n CSPs are identification problems: the goal is important, not the path. We can use general purpose search algorithms that don't have to be tailored for the state or heuristic. Only problem has to be specified in a formal declarative language. Consists of variables, possible values, and constraints. A consistent assignment of values to variables doesn't violate any constraints. Assignment is complete when every variable has a value assigned. A solution to CSP is both complete and consistent. \n\nTypes of CSPs: map coloring, scheduling, sudoku\n\nBenefit to modeling problem as CSP is that we can use general algorithms to solve, CSP can auto-prune branches that violate constraints, CSP already knows which variables violate the constraints. Turn problem into constraint graph where variables are the nodes and constraints are the arcs between the nodes.\n\nCSPs can have finite or infinite domains, can also have continuous variables.\n\nWe can also create a search tree for CSP, where the initial state is the empty assignment, a successor function assigns a value to any unassigned variable (where there is no conflict), the goal test is the successful assignment of values to variables and a constant cost for the path. Solution for $n$ variables is always at depth $n$, so DFS can be used.\n\nBacktracking search (basic uninformed algorithm for CSP): DFS with single variable assignments. Chooses values one variable at a time and backtracks if it hits a variable with no legal values left. However, we can use general heuristics to make algorithm faster: \n- most constrained variable should be assigned next (minimum remaining values (MRV) heuristic - aka fast fail)\n- in case of tie: most constraining variable should be assigned\n- variable values should be tried from least constraining value first so it rules out the fewest remaining values in other variables (how to assign the values, once we've chosen the variable)\n- forward-check to detect failure (keep track of remaining legal values for unassigned variables). forward checking only works on neighbors; it doesn't detect all issues\n\nCan combine search with inference: search assigns values and then inference propagates the constraints to the possible values of the rest of the variables\n\nChecking arc consistency with $d$ values takes $O(d^2)$ time worst case.\n\n```\nfunction AC-3(csp) returns CSP possibly with reduced domains\n  input: binary csp with variables {X1, ..., $Xn}\n  queue of arcs (initially arcs in csp) - keeps track of the arcs we need to process\n  while queue is not empty do:\n      pop (Xi, Xj) from the queue\n      if we can REMOVE-INCONSISTENT-VALUES(Xi, Xj) then - if a node had values removed, adds back arcs to neighbors\n          for each Xk in Xi's NEIGHBORS - {Xj} do\n            add (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) returns true iff we remove a value\n  removed = false\n  for each X in DOMAIN[Xi] do\n      if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n      then delete x from DOMAIN[Xi] and set removed = true\n  return removed\n\n```\nWorst case time complexity is if all nodes are connected to every other node: $O(n^2d^3)$\n\n \n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - problem that has consstraints on its variables and is solved when all constraints are satisfied\n* **Consistent assignment** - assignment of value to variable that doesn't violate a constraint\n* **Complete assignment** - when every variable has been assigned a value\n* **Partial assignment** - when some variables have not been assigned\n* **Partial solution** - partial assignment that is consistent\n* **Precidence constraint** - when one task must come before another\n* **Disjunctive constraint** - when two tasks cannot overlap one another\n* **Constraint hypergraph** - graph that has nodes and hypernodes that represent n-ary constraints\n* **Dual graph** - one variable for each constraint in original graph and one binary constraint for each pair of constraints that share variables\n* **Constraint propagation** - use constraints to reduce possible values for a variable, which then affects other variables. Can be done as preprocessing step.\n* **Path consistency** - uses implicit constraints inferred from looking at triplets of variables to tighten binary constraints\n* **Strongly k-consistent** - CSP that is k-consistent, k-1 consistent, etc., down to 1-consistent\n* **Bounds propagation** - consistency checker that uses upper and lower bounds\n* **Bounds-consistent** - CSP that satisfies bounds propogation constraints\n* **Commutativity** - property of CSPs that says order of application of actions doesn't matter\n* **Chronological backtracking** - when the most recent decision is revisited and tried with a different value\n* **Conflict set** - set of values that are in conflict with another variable's value assignment\n* **Backjumping method** - backtrack to most recent assignment that is within a variable's conflict set\n* **Conflict-directed backjumping** - algorithm that backjumps with conflict sets consisting of variables and subsequent variables that cause problems\n* **Constraint learning** - finding the minimum subset of variables in the conflict set that are actually causing the problem\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nProblem-solving agents only have limited knowledge of their environment, what they know is mostly based around the legal actions they can take for a particular problem. They also are limited by atomic represenations.\n\n**Knowledge-based agents** can use logic to combine information for use as needed (now or possibly in the future). They can:\n- accept new tasks with well-defined goals\n- achieve competence by learning new things about the environment\n- adapt to changes in the environment by updating what they had previously known\n\nThe **knowledge base** is the main component of a KB agent. Adding and querying the KB is done with 'ask's and 'tell's. The KB may start with **background knowledge** initially, before the agent adds to or modifies it.\n\n When the knowledge agent is called, it:\n - tells the knowledge base its percepts (make-percept-sentence)\n - asks the KB what actions it should perform (make-action-query)\n - tells the KB what it chose to do, and returns that action (make-action-sentence)\n\n Knowledge agent can determine actions at the knowledge level as opposed to the implementation level. It can also be created by telling it sentences one by one until it knows how to act in its environment (the **declarative**  approach to system building). Successful agents often use a combination of declarative and procedural approaches in their design.\n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world example shows us that conclusions can be guaranteed if the information that generated them is correct. \n\n## AIMA Chapter 7.3 Logic\n Entailment means that if a entails b, then b is true in every model in which a is true. a is stronger than b because it rules out more possibilities (the set of a's models is a subset of the set of b's models)\n\nA **sound** inference algorithm (truth preserving) derives only entailed (true) sentences. If it were unsound, it would be able to make things up.\n\nA **complete** inference algorithm can derive any sentence that is entailed.\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n **propositional logic** is composed of:\n- syntax: allowable sentences are atomic that use a single proposition symbol (usually uppercase letter with another letter or subscript, ex. $W_{1,3}$). This symbol stands for a true or false proposition. True always means true, and False always means false. We can construct complex sentences from these simple sentences with parenthesis and logical connectives. The connectives are: not (positive or negative literal), and (conjunction), or (disjunction) implies (premise/antecedent -> conclusion/consequent. also known as if-then statement), biconditional (if and only if). Not operator has highest precedence.\n- semantics: how the truth value of a sentence is determined, given a particular model. We can use truth tables to do this.\n\nEntailment algorithm is sound (directly implements entailment) and complete (works for any KB and a and it always terminates because the state space is finite). There are $2^n$ models, where $n$ is the number of atomic symbols. Time complexity: $O(2^n)$; Space complexity: $O(n)$ because it works depth-first. Every known algorithm for propositional logic has worst-case exponential complexity (based on size of input).\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nLogical equivalence is used to compare sentences (vs biconditional, which is used for elements withn a sentence).\n\nTo determine if a sentence is satisfiable, we must examine all models until we find one in which the sentence is true. This is an NP-complete problem. This can also be expressed as 'a $ \\models $ b iff the sentence (a  $\\land \\lnot$ b) is unsatisfiable'. This is actually a proof by contradiction.\n\n**Modus Ponens** is an inference rule used to derive a proof: $ (a \\implies b, a)/b $ which means if the numerator sentances are present, the denominator sentence can be derived.\n\n**And-Elimination** is an inference rule that says any of the conjuncts can be inferred from a conjunction: $(a \\land b) / a$\n\n**resolution** is an inference rule that can be combined with a complete search algorithm to produce a complete inference algorithm. **unit resolution** uses complementary literals (one is negation of other) to use a literal and a clause to create a new clause (by removing the complementary literal). Full resolution rule takes two clauses, and creates a new clause with all contents from the original two clauses, minus the complementary literals. The resolution rule is sound and complete.\n\nSince every sentence of propositional logic is logically equivalent to a conjunction of clauses, we can express sentences in **conjunctive normal form**. The steps for CNF involve eliminating biconditionals, then eliminating implications, then moving 'not' inwards to individual literals (ex. De Morgan), then apply distributivity law of $\\lor$ over $\\land$ wherever possible.\n\nBoth goal and definite clauses are Horn clauses. Definite clauses can be rewritten as implication where the premise is a conjunction of positive literals and the conclusion is a single positive literal.\n\nEx. $ \\lnot L_{1,1} \\lor \\lnot Breeze \\lor B_{1,1}$ can be written as $ (L_{1,1} \\land Breeze) \\implies B_{1,1}$\n\nInference with Horn clauses use forward-chaining or backward-chaining algorithms. Forward chaining uses modus ponens to make every inference and so is sound. FC is also complete because it will derive every entailed atomic sentence. FC is also a kind a data-driven reasoning. Backward chaining looks for implications in the KB whose conclusion is the query. BC is a type of goal-directed reasoning.\n\n \n\n## Module 7 Lecture Notes\n \n```\nfunction PL-RESOLUTION(KB, alpha) returns true or false\n  inputs: KB, a sentence in propositional logic \n        alpha, the query, a sentence in propositional logic\n\n  clauses (set of clauses in CNF representation of (KB AND not alpha))\n  new (empty {} that keeps track of new clauses)\n  while true do:\n    for each pair of clauses Ci, Cj in clauses do:\n      resolvents = PL-RESOLVE(Ci, Cj) (returns the set of all possible \n      clauses obtained by resolving the two inputs - want to see if there \n      are two things that are the opposite of one another)\n\n      if resolvents contains empty clause, return true (means we found p \n      and not p, so we can return true because alpha is entailed by KB)\n\n      else new = new U resolvents (add resolvents to new set)\n    if new is just a subset of clauses then return false (haven't arrived at anything new not already in KB)\n    otherwise clauses = clauses U new (update clauses with everything we've found)\n```\nResolution algorithm is complete. If our KB has a more restrictive form, we can use more efficient inference algorithms instead:\n- Definite clause (disjunction of literals where exactly one is positive)\n- Horn clause (disjunction of literals where at most one is positive; includes definite clauses and clauses with no positive literals). Horn clauses are closed under resolution: if you apply resolution to a horn clause, it returns a horn clause.\n\nIf KB only has definite clauses, can rewrite them as implication whose premise is a conjuntion of positive literals whose conclusion is a positive literal. Inference can be done through forward- and backward-chaining. Deciding entailment with Horn clauses can be done in linear time (with respect to size of KB) (this is why we would want to have a KB full of definite clauses)\n\nForward-chaining algorithm:\n```\nfucntion PL-FC-ENTAILS(KB,q) returns true or false (does KB entail q?)\n  inputs: KB, a set of propositional definite clauses\n          q, the query, a propsition symbol\n  count (table where count[c] is initially the number of symbols in in clause c's premise)\n  inferred (table where inferred[s] is initially false for all symbols) \n  (tells us if particular symbol has been inferred or not)\n  queue (queue of symbols, initially known to be true in KB)\n\n  while queue is not empty do:\n    pop p from queue\n    if p=q, return true\n    if inferred[p] = false then\n      set inferred[p] to true\n      for each clause c in KB where p is in c.PREMISE do:\n        decrement count[c] (because we've proven part of the clause c)\n        if count[c] = 0 then add c.CONCLUSION to queue (we've proven the whole clause c \n        and seen all parts of the premise)\n  return false\n```\nForward chaining is data-driven reasoning becaues it can start with known data and add premises as percepts come in, and then use the FC algorithm to derive new conclusions. It can do this without a specific query, too.\n\nBackward chaining works in reverse from the query, searching the KB for implications whose conclusion is the query. If we can prove the premises for any clause that match the query, then the query is true. (this is goal-directed reasoning)\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning instead of internal knowledge to decide what to do\n* **Knowledge base** - set of sentences written in a knowledge representation language that asserts something about the world\n* **Axiom** - sentence given without being derived from other sentences\n* **Inference** - deriving a new sentence from an old sentence without making up information\n* **Knowledge level** - can make logical decisions based on knowledge\n* **Declarative** - knowledge on how to act is obtained by an agent from TELL operation rather than direct encoding of behavior\n* **Syntax** - determines if a sentence is well-formed accoring to the representation language\n* **Semantics** - the meaning of a sentence that defines if it is true\n* **Model** - mathematical abstraction of a world in which each sentence is either true or false\n* **M satisfies a** - sentence a is true in model m\n* **M is a model of a** - sentence a is true in model m\n* **Logical entailment** - when one sentence follows logically from another sentence\n* **Logical inference** - using entailment to derive conclusions\n* **Model checking** - listing all possible models to check whether a is true in models where KB is true. Works in finite spaces\n* **Grounding** - means there is a connection between the logical reasoning and the agent's actual environment\n* **Theorem proving** - use rules of inference to create proof of a sentence, using only KB sentences\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - property of sentence that is true in all models\n* **Deduction theorem** - $a \\models b$ iff sentence $a\\implies b$ is valid\n* **Satisfiability** - attibute of sentences that are true in some model\n* **Monotonicity** - property of logical systems because set of entailed sentences will only increase as information is added\n* **Clause** - disjunction (or) of literals\n* **Factoring** - removal of multiple copies of the same literal so the result only contains one copy\n* **Ground resolution theorem** - completeness theorem for resolution in propositional logic: if set of clauses is unsatisfiable, the resolution closure is the empty clause\n* **Definite clause** - restricted form sentence that is a disjunction of literals where exactly one is positive\n* **Horn clause** - restricted form sentence that is a disjunction of literals where at most one is positive\n* **Goal clauses** - restricted form sentence that is a disjunction of literals where none are positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}