{
  "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",
      "execution_count": 70,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "66c14313-124f-43bb-c860-5df2bc7a4872"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 71,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "e8ee7f16-67a0-4556-c801-db5c2c7b1ad9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 72,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 73,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "- **turing test** - human asks a series of questions to determine if subject is a human or computer.\n",
        "\n",
        "\"laws of thought\" approach: *logic* as an irrefutable reasoning process.\n",
        "\n",
        "\"rational agent\" approach\n",
        "\n",
        "- **agent** - a subject that acts. **rational agent** - acts to achieve the best (expected) outcome.\n",
        "    - advantages over other approaches: (1) greater generality in approaches to achieve rationality. (2) mathematically defined, easy to measure & define.\n",
        "\n",
        "**value alignment problem** - objectives of machine should be aligned with the human.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "- (John Searle) **weak AI -** machines *act* like they are intelligent. **strong AI** - machines *are* consciously thinking.\n",
        "- Godel's incompleteness theorem\n",
        "    \n",
        "    $G(F)$ is a sentence of $F$, but cannot be proved within $F$\n",
        "    \n",
        "    If $F$ is consistent, then $G(F)$ is true.\n",
        "    \n",
        "- Roger Penrose: *I cannot consistently assert that this sentence is true.*\n",
        "    - if true ⇒ contradiction ⇒ therefore must be true\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "- an **agent** perceives the **environment** through sensors and acts through **actuators**\n",
        "- **percept** - what an agent is perceiving. **percept sequence** - history of everything the agent has perceived.\n",
        "- **agent function** - maps a percept sequence to an action, describes an agent's behavior. abstract mathematical description.\n",
        "- **agent program** - concrete implementation of the agent function (agent program ≠ agent function)\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "- **rational agent** is an agent that does *the right thing*, as defined by **consequentialism**: evaluating behavior by its consequences.\n",
        "- a **performance measure** evaluates any given sequence of environment states.\n",
        "    - better to design measures based on what one wants to be achieved, not how the agent should behave\n",
        "\n",
        "rationality depends on:\n",
        "\n",
        "1. performance measure, defines success\n",
        "2. agent's prior knowledge of environment\n",
        "3. performable actions\n",
        "4. agent's percept sequence\n",
        "- **rational agent defn** - for each possible percept sequence, a rational agent should choose the action which maximizes the performance measure, given the percept sequence and prior knowledge of the agent.\n",
        "- **omniscience** - when the agent knows the *actual* outcome of its actions. impossible in reality. rationality ≠ perfection, but instead maximizes *expected* performance.\n",
        "- **autonomy** - how much an agent relies on prior knowledge from the designer vs own percepts and learning. it's an evolutionary process :)\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- **task environments** - \"problems\"\n",
        "    - **PEAS** (Performance, Environment, Actuators, Sensors)\n",
        "    - e.g. taxi driver - P: safe, fast, legal; E: roads, police, pedestrians; A: steering, acelerator, brake; S: cameras, radar, speedometer\n",
        "\n",
        "**fully observable v. partially observable**\n",
        "\n",
        "- fully observable - sensors have access to complete relevant (in terms of performance measure) environment state at every point.\n",
        "- partially observable - noisy / inaccurate sensors (e.g. self-driving cars)\n",
        "\n",
        "**single-agent v. multiagent**\n",
        "\n",
        "- multi-agent - another agent's behavior is maximizing a performance value which depends on A's behavior (e.g. chess)\n",
        "    - chess is a *competitive* multiagent environment\n",
        "    - taxi-driving is a partially *cooperative* multiagent environment\n",
        "- single-agent - one agent (e.g. crossword puzzle)\n",
        "\n",
        "**deterministic v. nondeterministic**\n",
        "\n",
        "- deterministic - next state is determined by current state and action\n",
        "- non-deterministic - uncertainty, most real situations (also known as stochastic if w/ probabilities)\n",
        "\n",
        "**episodic v. sequential**\n",
        "\n",
        "- episodic - experience divided into atomic episodes where agent receives a percept and does an action. actions don't depend on previous actions.\n",
        "- sequential - current decision affects future decisions (e.g. chess, driving)\n",
        "\n",
        "**static v. dynamic**\n",
        "\n",
        "- dynamic - environment changes while agent is deciding action\n",
        "- semidynamic - environment might not change but agent's score does (e.g. chess with a clock)\n",
        "\n",
        "**discrete v. continuous:** taxi-driving is continuous. chess is discrete.\n",
        "\n",
        "**known v. unknown**\n",
        "\n",
        "- not strictly an environment property. more an agent property.\n",
        "- known - given outcomes for all actions. can have *known* partially observable games, like solitaire.\n",
        "\n",
        "*hardest case = partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown* (e.g. self-driving)\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- *agent = architecture + program.* AI designs an agent program which implements the agent function.\n",
        "- agent programs take current percept from sensors as input and return an action to actuators.\n",
        "    - a simple lookup table is exponential in size.\n",
        "\n",
        "**simple reflex agents**\n",
        "\n",
        "- selects actions based on *current* percept. ignores rest of percept history.\n",
        "- condition-action rule - percept sensor input establishes a condition which triggers some action.\n",
        "- can create infinite loops (e.g. on clean, the roomba turns left forever :/, can prevent this with randomization)\n",
        "\n",
        "**model-based reflex agents**\n",
        "\n",
        "- to handle partial observability: agent maintains some kind of internal state to represent unobserved aspects (e.g. keeping track of where other cars are if they can't be seen)\n",
        "    - requires info on how the world changes over time (effects of agent's actions and changes irrespective of agent)\n",
        "- \"how the world work\" ⇒ **transition model**\n",
        "- **sensor model** - how world's state is reflected by percepts (e.g. what does a car braking in front look like in the camera?)\n",
        "- transition model + sensor model → model-based agent\n",
        "\n",
        "**goal-based agents**\n",
        "\n",
        "- decisions depend on the goal.\n",
        "- simple when goal satisfaction results from a single actions. search and planning required for long sequences of actions.\n",
        "- involves future considerations...less efficient but more flexible.\n",
        "\n",
        "**utility-based agents**\n",
        "\n",
        "- goals are a binary distinction - success or failures. a better performance measure compares *utility.*\n",
        "- **utility function** - internalization of performance measure.\n",
        "    - determining appropriate tradeoffs when there are conflicting goals (e.g. speed v. safety)\n",
        "    - several goals with uncertainty - utility can weigh the likelihood against importance\n",
        "- rational utility-based agent chooses the action which maximizes the **expected utility** of the action outcomes\n",
        "\n",
        "**learning agents**\n",
        "\n",
        "- allows agents to be in unknown environments and gain competency\n",
        "- learning element is responsible for making improvements (feedback from *critic*). performance element selects external actions (percepts, actions).\n",
        "- **problem generator** - suggests improving actions. encourages agent to explore a lil.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "### ai & philosophy\n",
        "\n",
        "- **descartes**: *cogito ergo sum* (i think therefore i am)\n",
        "    - *dualism* - mind is incorporeal or spiritual, separate from body\n",
        "- **alan turing**: the imitation game, is it possible for a machine to imitate a human so plausibly that a human can't tell it is a machine?\n",
        "- **john searle**: the chinese room\n",
        "    - turing problem can be solved through simple symbol manipulation, not an indicator of true intelligence but just syntax rules\n",
        "    - appearance of conversation ≠ intelligence\n",
        "    - strong vs. weak AI: weak AI gives appearance of intelligence. must be something foundational about biological brains which allow for strong AI.\n",
        "- ELIZA: early NLP therapist.\n",
        "- **daniel dennett:** brain in a vat\n",
        "    - need to diffuse a bomb without radiation - DoD removes brain from body and sends it in a vat. \"Where am I?\" is the brain me or the body?\n",
        "    - replaced all the neurons and information flow of the brain, is it conscious?\n",
        "\n",
        "### rational agents\n",
        "\n",
        "**acting rationally**\n",
        "\n",
        "**agent:** anything that *perceives* its environment through *sensors* and can *act* on its environment through *actuators*\n",
        "\n",
        "- *percept -* agent's perceptual inputs at any given instance\n",
        "- specified by an *agent function* $f: P \\rightarrow a$, maps a sequence of percept vectors $P$ to an action $a$ from a set $A$\n",
        "- *agent program* is the concrete implementation to produce the function\n",
        "    - e.g. a giant table that maps every possible sequence of percepts to an action\n",
        "        - but this is exponential in length. need more sophisticated algs\n",
        "- agent = architecture + program\n",
        "- e.g. humans, robots, thermostats (perceives environment, adjusts boiler to inc temp), roombas\n",
        "\n",
        "**rational agent**: for each possible percept sequence $P$, a rational agent selects an action $a$ to maximize the expected value of its performance measure.\n",
        "\n",
        "- *consequentialism* - evaluate an agent's behavior by its consequences\n",
        "    - *Herbert Simon, A Behavioral Model of Rational Choice*\n",
        "- *performance measure* - objective criterion for success of an agent's behavior\n",
        "    - better to design performance measures according to **what you want to be achieved**, rather than how it should behave (+1 for each time the robot cleans a square vs. +1 for each clean square at time T, first might result in robot maximizing by cleaning one square over and over again)\n",
        "- computational limitations make *complete rationality* unachievable.\n",
        "\n",
        "### task environments\n",
        "\n",
        "**task environment -** problem specification for which the agent is a solution\n",
        "\n",
        "- PEAS specifies the task environment: Performance measure, Environment, Actuators, Sensors\n",
        "\n",
        "ex) automated taxi driver\n",
        "\n",
        "- performance measure: safe, fast, legal, comfortable, maximize profits\n",
        "- environment: roads, other traffic, pedestrians\n",
        "- actuators: steering, accelerator, brake, signal, horn\n",
        "- sensors: cameras, LIDAR, GPS, speedometer\n",
        "\n",
        "**fully observable:** task agent sensors can detect all relevant aspects (e.g. chess)\n",
        "\n",
        "**partially observable:** only have access to info perceived by sensors (e.g. self-driving car, pedestrians may be hidden, noisy/inaccurate sensors)\n",
        "\n",
        "**deterministic:** know with certainty the result of an action. resulting state is completely knowable based on current state.\n",
        "\n",
        "**nondeterministic:** outcome is uncertain. many possible resulting states. games of chance.\n",
        "\n",
        "- often also **stochastic** (probabilistic)\n",
        "\n",
        "**episodic**: choice of each action is not dependent on previous actions (e.g. robot picking out defective parts)\n",
        "\n",
        "**sequential:** action effects future sequence of actions (e.g. cars)\n",
        "\n",
        "**static:** state doesn't change until agent finishes deciding action (e.g. crossword)\n",
        "\n",
        "**dynamic:** environment is constantly changing (e.g. cars)\n",
        "\n",
        "- can be semi-dynamic if score changes (e.g. clock in chess)\n",
        "\n",
        "**discrete:** finite set of possible actions (board games)\n",
        "\n",
        "**continuous:** inifinite possible actions (oil temperature settings)\n",
        "\n",
        "**simple agent:** only one agent (crossword)\n",
        "\n",
        "**multi agent:** treat other agents as rational (chess)\n",
        "\n",
        "- when something's behavior can be best described as having its own performance measure, it should be its own agent\n",
        "\n",
        "hardest environment: continuous, partially observable, stochastic, multi-agent\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\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",
      "execution_count": 74,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "gYYeNcdM_maE",
        "outputId": "4385798f-7f8a-4c13-d3ea-ef427d1f8ef1"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "- **turing test** - human asks a series of questions to determine if subject is a human or computer.\n",
              "\n",
              "\"laws of thought\" approach: *logic* as an irrefutable reasoning process.\n",
              "\n",
              "\"rational agent\" approach\n",
              "\n",
              "- **agent** - a subject that acts. **rational agent** - acts to achieve the best (expected) outcome.\n",
              "    - advantages over other approaches: (1) greater generality in approaches to achieve rationality. (2) mathematically defined, easy to measure & define.\n",
              "\n",
              "**value alignment problem** - objectives of machine should be aligned with the human.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "- (John Searle) **weak AI -** machines *act* like they are intelligent. **strong AI** - machines *are* consciously thinking.\n",
              "- Godel's incompleteness theorem\n",
              "    \n",
              "    $G(F)$ is a sentence of $F$, but cannot be proved within $F$\n",
              "    \n",
              "    If $F$ is consistent, then $G(F)$ is true.\n",
              "    \n",
              "- Roger Penrose: *I cannot consistently assert that this sentence is true.*\n",
              "    - if true ⇒ contradiction ⇒ therefore must be true\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "- an **agent** perceives the **environment** through sensors and acts through **actuators**\n",
              "- **percept** - what an agent is perceiving. **percept sequence** - history of everything the agent has perceived.\n",
              "- **agent function** - maps a percept sequence to an action, describes an agent's behavior. abstract mathematical description.\n",
              "- **agent program** - concrete implementation of the agent function (agent program ≠ agent function)\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "- **rational agent** is an agent that does *the right thing*, as defined by **consequentialism**: evaluating behavior by its consequences.\n",
              "- a **performance measure** evaluates any given sequence of environment states.\n",
              "    - better to design measures based on what one wants to be achieved, not how the agent should behave\n",
              "\n",
              "rationality depends on:\n",
              "\n",
              "1. performance measure, defines success\n",
              "2. agent's prior knowledge of environment\n",
              "3. performable actions\n",
              "4. agent's percept sequence\n",
              "- **rational agent defn** - for each possible percept sequence, a rational agent should choose the action which maximizes the performance measure, given the percept sequence and prior knowledge of the agent.\n",
              "- **omniscience** - when the agent knows the *actual* outcome of its actions. impossible in reality. rationality ≠ perfection, but instead maximizes *expected* performance.\n",
              "- **autonomy** - how much an agent relies on prior knowledge from the designer vs own percepts and learning. it's an evolutionary process :)\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "- **task environments** - \"problems\"\n",
              "    - **PEAS** (Performance, Environment, Actuators, Sensors)\n",
              "    - e.g. taxi driver - P: safe, fast, legal; E: roads, police, pedestrians; A: steering, acelerator, brake; S: cameras, radar, speedometer\n",
              "\n",
              "**fully observable v. partially observable**\n",
              "\n",
              "- fully observable - sensors have access to complete relevant (in terms of performance measure) environment state at every point.\n",
              "- partially observable - noisy / inaccurate sensors (e.g. self-driving cars)\n",
              "\n",
              "**single-agent v. multiagent**\n",
              "\n",
              "- multi-agent - another agent's behavior is maximizing a performance value which depends on A's behavior (e.g. chess)\n",
              "    - chess is a *competitive* multiagent environment\n",
              "    - taxi-driving is a partially *cooperative* multiagent environment\n",
              "- single-agent - one agent (e.g. crossword puzzle)\n",
              "\n",
              "**deterministic v. nondeterministic**\n",
              "\n",
              "- deterministic - next state is determined by current state and action\n",
              "- non-deterministic - uncertainty, most real situations (also known as stochastic if w/ probabilities)\n",
              "\n",
              "**episodic v. sequential**\n",
              "\n",
              "- episodic - experience divided into atomic episodes where agent receives a percept and does an action. actions don't depend on previous actions.\n",
              "- sequential - current decision affects future decisions (e.g. chess, driving)\n",
              "\n",
              "**static v. dynamic**\n",
              "\n",
              "- dynamic - environment changes while agent is deciding action\n",
              "- semidynamic - environment might not change but agent's score does (e.g. chess with a clock)\n",
              "\n",
              "**discrete v. continuous:** taxi-driving is continuous. chess is discrete.\n",
              "\n",
              "**known v. unknown**\n",
              "\n",
              "- not strictly an environment property. more an agent property.\n",
              "- known - given outcomes for all actions. can have *known* partially observable games, like solitaire.\n",
              "\n",
              "*hardest case = partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown* (e.g. self-driving)\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "- *agent = architecture + program.* AI designs an agent program which implements the agent function.\n",
              "- agent programs take current percept from sensors as input and return an action to actuators.\n",
              "    - a simple lookup table is exponential in size.\n",
              "\n",
              "**simple reflex agents**\n",
              "\n",
              "- selects actions based on *current* percept. ignores rest of percept history.\n",
              "- condition-action rule - percept sensor input establishes a condition which triggers some action.\n",
              "- can create infinite loops (e.g. on clean, the roomba turns left forever :/, can prevent this with randomization)\n",
              "\n",
              "**model-based reflex agents**\n",
              "\n",
              "- to handle partial observability: agent maintains some kind of internal state to represent unobserved aspects (e.g. keeping track of where other cars are if they can't be seen)\n",
              "    - requires info on how the world changes over time (effects of agent's actions and changes irrespective of agent)\n",
              "- \"how the world work\" ⇒ **transition model**\n",
              "- **sensor model** - how world's state is reflected by percepts (e.g. what does a car braking in front look like in the camera?)\n",
              "- transition model + sensor model → model-based agent\n",
              "\n",
              "**goal-based agents**\n",
              "\n",
              "- decisions depend on the goal.\n",
              "- simple when goal satisfaction results from a single actions. search and planning required for long sequences of actions.\n",
              "- involves future considerations...less efficient but more flexible.\n",
              "\n",
              "**utility-based agents**\n",
              "\n",
              "- goals are a binary distinction - success or failures. a better performance measure compares *utility.*\n",
              "- **utility function** - internalization of performance measure.\n",
              "    - determining appropriate tradeoffs when there are conflicting goals (e.g. speed v. safety)\n",
              "    - several goals with uncertainty - utility can weigh the likelihood against importance\n",
              "- rational utility-based agent chooses the action which maximizes the **expected utility** of the action outcomes\n",
              "\n",
              "**learning agents**\n",
              "\n",
              "- allows agents to be in unknown environments and gain competency\n",
              "- learning element is responsible for making improvements (feedback from *critic*). performance element selects external actions (percepts, actions).\n",
              "- **problem generator** - suggests improving actions. encourages agent to explore a lil.\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "### ai & philosophy\n",
              "\n",
              "- **descartes**: *cogito ergo sum* (i think therefore i am)\n",
              "    - *dualism* - mind is incorporeal or spiritual, separate from body\n",
              "- **alan turing**: the imitation game, is it possible for a machine to imitate a human so plausibly that a human can't tell it is a machine?\n",
              "- **john searle**: the chinese room\n",
              "    - turing problem can be solved through simple symbol manipulation, not an indicator of true intelligence but just syntax rules\n",
              "    - appearance of conversation ≠ intelligence\n",
              "    - strong vs. weak AI: weak AI gives appearance of intelligence. must be something foundational about biological brains which allow for strong AI.\n",
              "- ELIZA: early NLP therapist.\n",
              "- **daniel dennett:** brain in a vat\n",
              "    - need to diffuse a bomb without radiation - DoD removes brain from body and sends it in a vat. \"Where am I?\" is the brain me or the body?\n",
              "    - replaced all the neurons and information flow of the brain, is it conscious?\n",
              "\n",
              "### rational agents\n",
              "\n",
              "**acting rationally**\n",
              "\n",
              "**agent:** anything that *perceives* its environment through *sensors* and can *act* on its environment through *actuators*\n",
              "\n",
              "- *percept -* agent's perceptual inputs at any given instance\n",
              "- specified by an *agent function* $f: P \rightarrow a$, maps a sequence of percept vectors $P$ to an action $a$ from a set $A$\n",
              "- *agent program* is the concrete implementation to produce the function\n",
              "    - e.g. a giant table that maps every possible sequence of percepts to an action\n",
              "        - but this is exponential in length. need more sophisticated algs\n",
              "- agent = architecture + program\n",
              "- e.g. humans, robots, thermostats (perceives environment, adjusts boiler to inc temp), roombas\n",
              "\n",
              "**rational agent**: for each possible percept sequence $P$, a rational agent selects an action $a$ to maximize the expected value of its performance measure.\n",
              "\n",
              "- *consequentialism* - evaluate an agent's behavior by its consequences\n",
              "    - *Herbert Simon, A Behavioral Model of Rational Choice*\n",
              "- *performance measure* - objective criterion for success of an agent's behavior\n",
              "    - better to design performance measures according to **what you want to be achieved**, rather than how it should behave (+1 for each time the robot cleans a square vs. +1 for each clean square at time T, first might result in robot maximizing by cleaning one square over and over again)\n",
              "- computational limitations make *complete rationality* unachievable.\n",
              "\n",
              "### task environments\n",
              "\n",
              "**task environment -** problem specification for which the agent is a solution\n",
              "\n",
              "- PEAS specifies the task environment: Performance measure, Environment, Actuators, Sensors\n",
              "\n",
              "ex) automated taxi driver\n",
              "\n",
              "- performance measure: safe, fast, legal, comfortable, maximize profits\n",
              "- environment: roads, other traffic, pedestrians\n",
              "- actuators: steering, accelerator, brake, signal, horn\n",
              "- sensors: cameras, LIDAR, GPS, speedometer\n",
              "\n",
              "**fully observable:** task agent sensors can detect all relevant aspects (e.g. chess)\n",
              "\n",
              "**partially observable:** only have access to info perceived by sensors (e.g. self-driving car, pedestrians may be hidden, noisy/inaccurate sensors)\n",
              "\n",
              "**deterministic:** know with certainty the result of an action. resulting state is completely knowable based on current state.\n",
              "\n",
              "**nondeterministic:** outcome is uncertain. many possible resulting states. games of chance.\n",
              "\n",
              "- often also **stochastic** (probabilistic)\n",
              "\n",
              "**episodic**: choice of each action is not dependent on previous actions (e.g. robot picking out defective parts)\n",
              "\n",
              "**sequential:** action effects future sequence of actions (e.g. cars)\n",
              "\n",
              "**static:** state doesn't change until agent finishes deciding action (e.g. crossword)\n",
              "\n",
              "**dynamic:** environment is constantly changing (e.g. cars)\n",
              "\n",
              "- can be semi-dynamic if score changes (e.g. clock in chess)\n",
              "\n",
              "**discrete:** finite set of possible actions (board games)\n",
              "\n",
              "**continuous:** inifinite possible actions (oil temperature settings)\n",
              "\n",
              "**simple agent:** only one agent (crossword)\n",
              "\n",
              "**multi agent:** treat other agents as rational (chess)\n",
              "\n",
              "- when something's behavior can be best described as having its own performance measure, it should be its own agent\n",
              "\n",
              "hardest environment: continuous, partially observable, stochastic, multi-agent\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 75,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "### Homework 1 Answers\n",
        "\n",
        "Python is dynamically typed, meaning declared variables are untyped but objects \n",
        "created at runtime have typings. Essentially, this allows for redefining variables \n",
        "to different types without error.\n",
        "\n",
        "```\n",
        "a = \"string\"\n",
        "a = 5\n",
        "```\n",
        "\n",
        "Python is strongly typed, meaning object types are defined and cannot be coerced\n",
        "into other types. Changing the type of an object requires explicit casting.\n",
        "For example, a = 5 + \"string\" will throw an error because the types of the two\n",
        "are not the same.\n",
        "\n",
        "Dictionary keys cannot be lists since they are mutable. If we use a list as a key,\n",
        "but modify the list object, then the key inside the dictionary has changed.\n",
        "\n",
        "The solution would be to use tuples instead. If all the points are 2-dimensional,\n",
        "changing [0,0] to (0,0) converts the key to a tuple. Tuples have a fixed length,\n",
        "and are immutable.\n",
        "\n",
        "concatenate2 is better. In concatenate1, using += creates a new string in each\n",
        "iteration, and copies the old string over in addition to the new string every time.\n",
        "In concatenate2, using .join() doesn't create intermediate strings and only copies \n",
        "each string once.\n",
        "\n",
        "- immutable: tuples, strings\n",
        "- mutable: sets, dictionaries, lists\n",
        "\n",
        "---\n",
        "```\n",
        "mathematicians_list = [\"Babbage\", \"Einstein\" \"Leibniz\"]\n",
        "mathematicians_list[:][0] = \"Godel\"\n",
        "```\n",
        "creates a copy of the list and replaces name but original list remains the same.\n",
        "\n",
        "Which of the following pieces of code will generate an error? Select all that apply.\n",
        "{\"a\": 3, \"b\": 2, [1,2]: 2} -- all keys of dictionary must be same type\n",
        "first_two = set(); first_two.add(\"one\"); first_two.remove(\"two\") -- cannot remove nonexistent element from set\n",
        "{\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4} -- cannot add dictionaries\n",
        "a = '123'; a[1] = '1' -- cannot index into string\n",
        "b = (1, 2, 3); b[1] = 1 -- cannot mutate a tuple\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 76,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 590
        },
        "id": "ydOK__lwWgdp",
        "outputId": "4900cd41-e31c-4ea0-8f7f-0800779cf8c1"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "### Homework 1 Answers\n",
              "\n",
              "Python is dynamically typed, meaning declared variables are untyped but objects \n",
              "created at runtime have typings. Essentially, this allows for redefining variables \n",
              "to different types without error.\n",
              "\n",
              "```\n",
              "a = \"string\"\n",
              "a = 5\n",
              "```\n",
              "\n",
              "Python is strongly typed, meaning object types are defined and cannot be coerced\n",
              "into other types. Changing the type of an object requires explicit casting.\n",
              "For example, a = 5 + \"string\" will throw an error because the types of the two\n",
              "are not the same.\n",
              "\n",
              "Dictionary keys cannot be lists since they are mutable. If we use a list as a key,\n",
              "but modify the list object, then the key inside the dictionary has changed.\n",
              "\n",
              "The solution would be to use tuples instead. If all the points are 2-dimensional,\n",
              "changing [0,0] to (0,0) converts the key to a tuple. Tuples have a fixed length,\n",
              "and are immutable.\n",
              "\n",
              "concatenate2 is better. In concatenate1, using += creates a new string in each\n",
              "iteration, and copies the old string over in addition to the new string every time.\n",
              "In concatenate2, using .join() doesn't create intermediate strings and only copies \n",
              "each string once.\n",
              "\n",
              "- immutable: tuples, strings\n",
              "- mutable: sets, dictionaries, lists\n",
              "\n",
              "---\n",
              "```\n",
              "mathematicians_list = [\"Babbage\", \"Einstein\" \"Leibniz\"]\n",
              "mathematicians_list[:][0] = \"Godel\"\n",
              "```\n",
              "creates a copy of the list and replaces name but original list remains the same.\n",
              "\n",
              "Which of the following pieces of code will generate an error? Select all that apply.\n",
              "{\"a\": 3, \"b\": 2, [1,2]: 2} -- all keys of dictionary must be same type\n",
              "first_two = set(); first_two.add(\"one\"); first_two.remove(\"two\") -- cannot remove nonexistent element from set\n",
              "{\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4} -- cannot add dictionaries\n",
              "a = '123'; a[1] = '1' -- cannot index into string\n",
              "b = (1, 2, 3); b[1] = 1 -- cannot mutate a tuple\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 77,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "- **problem-solving agent** - agent that plans ahead, considers an action sequence to get to the goal state. this process is **search**.\n",
        "- **informed** algorithms - agent knows how far it is from the goal.\n",
        "- **uninformed** - no estimate of distance to goal.\n",
        "- in a fully observable, deterministic, known environment, solution to any problem is a fixed sequence of actions.\n",
        "\n",
        "formal defn of a search problem:\n",
        "\n",
        "- state space\n",
        "- initial state\n",
        "- set of goal states\n",
        "- action space\n",
        "- transition model - describes what each action does\n",
        "- action cost function - numeric cost of applying an action in a state\n",
        "\n",
        "---\n",
        "\n",
        "- **optimal solution** - lowest path cost among all solutions\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "**standardized problem** - theorhetical, illustrates problem-solving methods and used as a benchmark\n",
        "\n",
        "- **grid world**: 2D array, agent moves left/right and diagonally. cells can contain objects which are picked up, pushed, etc...\n",
        "    - states: cells\n",
        "    - initial state\n",
        "    - actions: suck, move left, move right\n",
        "    - transition model: suck removes dirt from the cell, forward moves forward, backward, etc...\n",
        "    - goal state: all cells are clean\n",
        "    - action cost: each action costs 1\n",
        "- **sokoban puzzle**: push a number of boxes to storage locations, one box / cell\n",
        "- **sliding-tile puzzle**: variants include rush-hour puzzle, 8-puzzle (8 tiles in 9 cells)\n",
        "\n",
        "**real-world problem** - solutions are actually used.\n",
        "\n",
        "- **route-finding problem**: websites, GPS, airline travel-planning\n",
        "    - states: time and place, historical info (previous flight costs, etc...)\n",
        "    - init state: home airport\n",
        "    - actions: take any flight in any class seat, leaving after current time\n",
        "    - transition model: arrival state and time\n",
        "    - goal state: destination city\n",
        "    - action cost: monetary cost, wait time, flight time, etc...\n",
        "- **touring problems**: TSP (visit every city with cost < C)\n",
        "- **VLSI layout**: position millions of components and connections to minimize area, circuit delays, stray capacitance...\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "- **search alg** - search problem as input, solution or failure returned.\n",
        "    - **search tree** gets imposed over state-space graph. **nodes** are states in the state space, **edges** are actions. **root** = init state. each node has a unique path back to the root.\n",
        "- **frontier** separates the interior region (all states have been expanded) and exterior region (not yet reached). usually a queue.\n",
        "\n",
        "**best-first search**: expand the node with the minimum evaluation function, $f(n)$\n",
        "\n",
        "```python\n",
        "function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure\n",
        "\tnode = initial state, problem.INIT\n",
        "\tfrontier = priority queue, ordered by f, with node as an element\n",
        "\treached = lookup table, add node to this\n",
        "\twhile frontier is not empty do\n",
        "\t\tnode = pop(frontier)\n",
        "\t\tif node is goal state then return node\n",
        "\t\tfor every child in EXPAND(problem, node)\n",
        "\t\t\ts = child.STATE\n",
        "\t\t\tif s is not in reached or child.PATHCOST < reached[s].PATH_COST then\n",
        "\t\t\t\treached[s] = child\n",
        "\t\t\t\tadd child to frontier\n",
        "\treturn failure\n",
        "\n",
        "function EXPAND(problem, node) yields nodes\n",
        "\ts = node.STATE\n",
        "\tfor every action in problems.ACTIONS(s)\n",
        "\t\ts' = problem.RESULT(s, action)\n",
        "\t\tcost = node.PATH-COST + problem.ACTION-COST(s, action, s')\n",
        "\t\tyield NODE(STATE=s', PARENT=node, ACTION=acton, PATH-COST=cost)\n",
        "```\n",
        "\n",
        "- nodes have state, parent, action, path-cost\n",
        "- types of queues\n",
        "    - priority queue - pops node with minimum cost. used in best-first search.\n",
        "    - FIFO queue - first-in-first-out, breadth-first search\n",
        "    - LIFO queue - last-in-first-out, stack, depth-first search\n",
        "- a complete search tree is *infinite* since it allows repeated states and **redundant paths**\n",
        "- **graph search** checks for redundant paths. best-first search is a graph search alg since we check for *reached*\n",
        "\n",
        "**alg performance**\n",
        "\n",
        "- **complete** if it's guaranteed to find a soln when there is one and report failure if not.\n",
        "- **cost optimality**\n",
        "- **time complexity & space complexity**\n",
        "    - d (depth) - number of actions in an optimal soln\n",
        "    - m - max number of actions in any path\n",
        "    - b (branching factor) - number of successors of a node to consider\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "- uninformed - no information on how close a state is to the goal\n",
        "\n",
        "**breadth-first search**\n",
        "\n",
        "- useful when all actions with the same cost\n",
        "- complete even on infinite spaces\n",
        "- best-first search where evaluation function, f(n) is node's depth\n",
        "    - use FIFO queue instead of priority\n",
        "    - reached is a set of states\n",
        "    - early goal test - check whether a node is a solution when generated\n",
        "    - always finds soln with minimal number of actions.\n",
        "    - cost-optimal when all actions have the same cost, not otherwise. but complete for all problems.\n",
        "    - time and space complexity: $O(b^d)$\n",
        "        - space is a bigger problem than time.\n",
        "\n",
        "```python\n",
        "function UNIFORM-COST-SEARCH(problem) returns solution node or failure\n",
        "\treturn BEST-FIRST-SEARCH(problem, PATH-COST)\n",
        "```\n",
        "\n",
        "**iterative deepening search**\n",
        "\n",
        "- pick a good $l$ value by trying all values until a solution is found or depth-limited search returns *failure* (not cutoff)\n",
        "- modest mem reqs: $O(bd)$ when there's a solution, $O(bm)$ without solution\n",
        "- time complexity = $O(b^d)$ when there's a solution, $O(b^m)$ without soln\n",
        "- optimal when all actions have same cost, complete on finite acyclic states\n",
        "\n",
        "```python\n",
        "function ITERATIVE-DEEPENING-SEARCH(problem) returns soln node or failure\n",
        "\tfor depth = 0 to infinity\n",
        "\t\tresult = DEPTH-LIMITED-SEARCH(problem, depth)\n",
        "\t\tif result != cutoff then return result\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "### search problems\n",
        "\n",
        "- **reflex agent:** selects an action based only on the current precept, igonres the rest of the percept history\n",
        "- **problem-solving agent**: considers a sequence of actions to form a path to a goal state. sequence = solution.\n",
        "- example sliding-tile puzzle (8-puzzle)\n",
        "- map navigation\n",
        "\n",
        "### search problem formulation\n",
        "\n",
        "**formal problem definition,** representation\n",
        "\n",
        "1. states: a set $S$ \n",
        "2. initial state: $s_i \\in S$\n",
        "3. actions: a set $A$, $\\forall s$, actions that we can take from any state\n",
        "4. transition model: for all actions, $result(s, a) → s_r$, $s_r$ is called a successor of $s$\n",
        "5. path cost: must be additive (e.g. sum of distances, number of actions, etc...)\n",
        "    1. $c(x, a_xy)$ is the step cost, assumed to be ≥ 0\n",
        "6. goal test: $goal(s)$ is true or false\n",
        "- **ex) vacuum world**\n",
        "    1. states: 2-square grid world. each cell can be dirty or not.\n",
        "        1. 2 cells * 2 positions * 2 possibilities (dirt or not) = 8 states\n",
        "        2. $n$ cells, $n 2^n$ states\n",
        "    2. one state is designated as the initial state\n",
        "    3. actions: suck, move left, right\n",
        "    4. transition: suck = removes dirt, move = move in that direction, unless we hit a wall.\n",
        "    5. action cost: uniform cost, each action costs 1.\n",
        "    6. goal state: everything is clean.\n",
        "\n",
        "**solutions and optimal solutions:**\n",
        "\n",
        "- a solution is a sequence of actions from the initial state to a goal state\n",
        "- **optimal solution**: no solution has a lower path cost\n",
        "- **ex) 8-puzzle**\n",
        "    1. states: list of 9 locations\n",
        "    2. initial state: single array or list\n",
        "    3. actions: set of possible moves {left, right, up, down}\n",
        "    4. transition model\n",
        "    5. goal test: iterate through and in ascending order\n",
        "    6. path cost: number of actions to reach goal, each action = 1\n",
        "\n",
        "*state space:* set of all states reachable from the initial state by any sequence of actions\n",
        "\n",
        "*path*: sequence of actions leading from one state, $s_j$ to another state $s_k$\n",
        "\n",
        "*frontier:* states available for expanding\n",
        "\n",
        "*solution:* path from the initial state $s_i$ to a state $s_f$ that satisfies the goal test\n",
        "\n",
        "### basic search algs\n",
        "\n",
        "- initialize frontier → choose a node on the frontier to expand → add resulting states to frontier (while frontier is not empty)\n",
        "- repeatedly visiting the same state is a problem → turns a linear problem into an exponential problem\n",
        "- algorithm is **complete** **if the algorithm is guaranteed to find a solution if there is one, and to correctly report failure when there is not\n",
        "\n",
        "### uninformed (blind) search strategies\n",
        "\n",
        "- A search method is **uninformed** if it only has access to the problem definition\n",
        "\n",
        "definitions for evaluation\n",
        "\n",
        "- completeness - always find the solution?\n",
        "- optimality - finds a least cost solution?\n",
        "- time complexity\n",
        "- space complexity\n",
        "\n",
        "time/space complexity variables: \n",
        "\n",
        "- $b$, a maximum branching factor of search tree\n",
        "- $d$, depth of shallowest goal node\n",
        "- $m$, max length of any potential path\n",
        "\n",
        "### bfs/dfs\n",
        "\n",
        "- bfs: expand shallowest unexpanded node, FIFO frontier queue\n",
        "    - complete\n",
        "    - time complexity: $O(b^d)$\n",
        "    - space complexity: $O(b^d)$\n",
        "    - optimal: yes if one step = one cost\n",
        "    - use if possible infinite paths, some solns have short paths\n",
        "- dfs: expand deepest node, LIFO\n",
        "    - incomplete - fails in loops\n",
        "    - time complexity: $O(b^m)$\n",
        "    - space complexity: $O(b*m)$\n",
        "    - optimal: yes if one step = one cost\n",
        "    - use if space-restricted, wrong paths are terminated quickly, search can be fine-tuned quickly\n",
        "\n",
        "### depth limited search and iterative deepening search\n",
        "\n",
        "depth limited search\n",
        "\n",
        "- DFS with depth limit $l$\n",
        "- no infinite-path problem\n",
        "- optimal if $l = d$, otherwise if $l < d$ then incomplete, if $l > d$ then not optimal\n",
        "\n",
        "iterative deepening search\n",
        "\n",
        "- general strategy to find best depth limit $l$\n",
        "    - key idea: use depth-limited search as subroutine and increase $l$\n",
        "- complete & optimal (if step cost = 1)\n",
        "- time complexity: $O(b^d)$\n",
        "- space complexity: $O(bd)$\n",
        "\n",
        "### review questions\n",
        "\n",
        "- uninformed complete algs: BFS, uniform-cost search, iterative deepening, bidirectional\n",
        "- uninformed optimal algs: same as above.\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",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 78,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "c2f785a8-9cc3-4439-ca7a-6caf40807979"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "- **problem-solving agent** - agent that plans ahead, considers an action sequence to get to the goal state. this process is **search**.\n",
              "- **informed** algorithms - agent knows how far it is from the goal.\n",
              "- **uninformed** - no estimate of distance to goal.\n",
              "- in a fully observable, deterministic, known environment, solution to any problem is a fixed sequence of actions.\n",
              "\n",
              "formal defn of a search problem:\n",
              "\n",
              "- state space\n",
              "- initial state\n",
              "- set of goal states\n",
              "- action space\n",
              "- transition model - describes what each action does\n",
              "- action cost function - numeric cost of applying an action in a state\n",
              "\n",
              "---\n",
              "\n",
              "- **optimal solution** - lowest path cost among all solutions\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "**standardized problem** - theorhetical, illustrates problem-solving methods and used as a benchmark\n",
              "\n",
              "- **grid world**: 2D array, agent moves left/right and diagonally. cells can contain objects which are picked up, pushed, etc...\n",
              "    - states: cells\n",
              "    - initial state\n",
              "    - actions: suck, move left, move right\n",
              "    - transition model: suck removes dirt from the cell, forward moves forward, backward, etc...\n",
              "    - goal state: all cells are clean\n",
              "    - action cost: each action costs 1\n",
              "- **sokoban puzzle**: push a number of boxes to storage locations, one box / cell\n",
              "- **sliding-tile puzzle**: variants include rush-hour puzzle, 8-puzzle (8 tiles in 9 cells)\n",
              "\n",
              "**real-world problem** - solutions are actually used.\n",
              "\n",
              "- **route-finding problem**: websites, GPS, airline travel-planning\n",
              "    - states: time and place, historical info (previous flight costs, etc...)\n",
              "    - init state: home airport\n",
              "    - actions: take any flight in any class seat, leaving after current time\n",
              "    - transition model: arrival state and time\n",
              "    - goal state: destination city\n",
              "    - action cost: monetary cost, wait time, flight time, etc...\n",
              "- **touring problems**: TSP (visit every city with cost < C)\n",
              "- **VLSI layout**: position millions of components and connections to minimize area, circuit delays, stray capacitance...\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "- **search alg** - search problem as input, solution or failure returned.\n",
              "    - **search tree** gets imposed over state-space graph. **nodes** are states in the state space, **edges** are actions. **root** = init state. each node has a unique path back to the root.\n",
              "- **frontier** separates the interior region (all states have been expanded) and exterior region (not yet reached). usually a queue.\n",
              "\n",
              "**best-first search**: expand the node with the minimum evaluation function, $f(n)$\n",
              "\n",
              "```python\n",
              "function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure\n",
              "\tnode = initial state, problem.INIT\n",
              "\tfrontier = priority queue, ordered by f, with node as an element\n",
              "\treached = lookup table, add node to this\n",
              "\twhile frontier is not empty do\n",
              "\t\tnode = pop(frontier)\n",
              "\t\tif node is goal state then return node\n",
              "\t\tfor every child in EXPAND(problem, node)\n",
              "\t\t\ts = child.STATE\n",
              "\t\t\tif s is not in reached or child.PATHCOST < reached[s].PATH_COST then\n",
              "\t\t\t\treached[s] = child\n",
              "\t\t\t\tadd child to frontier\n",
              "\treturn failure\n",
              "\n",
              "function EXPAND(problem, node) yields nodes\n",
              "\ts = node.STATE\n",
              "\tfor every action in problems.ACTIONS(s)\n",
              "\t\ts' = problem.RESULT(s, action)\n",
              "\t\tcost = node.PATH-COST + problem.ACTION-COST(s, action, s')\n",
              "\t\tyield NODE(STATE=s', PARENT=node, ACTION=acton, PATH-COST=cost)\n",
              "```\n",
              "\n",
              "- nodes have state, parent, action, path-cost\n",
              "- types of queues\n",
              "    - priority queue - pops node with minimum cost. used in best-first search.\n",
              "    - FIFO queue - first-in-first-out, breadth-first search\n",
              "    - LIFO queue - last-in-first-out, stack, depth-first search\n",
              "- a complete search tree is *infinite* since it allows repeated states and **redundant paths**\n",
              "- **graph search** checks for redundant paths. best-first search is a graph search alg since we check for *reached*\n",
              "\n",
              "**alg performance**\n",
              "\n",
              "- **complete** if it's guaranteed to find a soln when there is one and report failure if not.\n",
              "- **cost optimality**\n",
              "- **time complexity & space complexity**\n",
              "    - d (depth) - number of actions in an optimal soln\n",
              "    - m - max number of actions in any path\n",
              "    - b (branching factor) - number of successors of a node to consider\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "- uninformed - no information on how close a state is to the goal\n",
              "\n",
              "**breadth-first search**\n",
              "\n",
              "- useful when all actions with the same cost\n",
              "- complete even on infinite spaces\n",
              "- best-first search where evaluation function, f(n) is node's depth\n",
              "    - use FIFO queue instead of priority\n",
              "    - reached is a set of states\n",
              "    - early goal test - check whether a node is a solution when generated\n",
              "    - always finds soln with minimal number of actions.\n",
              "    - cost-optimal when all actions have the same cost, not otherwise. but complete for all problems.\n",
              "    - time and space complexity: $O(b^d)$\n",
              "        - space is a bigger problem than time.\n",
              "\n",
              "```python\n",
              "function UNIFORM-COST-SEARCH(problem) returns solution node or failure\n",
              "\treturn BEST-FIRST-SEARCH(problem, PATH-COST)\n",
              "```\n",
              "\n",
              "**iterative deepening search**\n",
              "\n",
              "- pick a good $l$ value by trying all values until a solution is found or depth-limited search returns *failure* (not cutoff)\n",
              "- modest mem reqs: $O(bd)$ when there's a solution, $O(bm)$ without solution\n",
              "- time complexity = $O(b^d)$ when there's a solution, $O(b^m)$ without soln\n",
              "- optimal when all actions have same cost, complete on finite acyclic states\n",
              "\n",
              "```python\n",
              "function ITERATIVE-DEEPENING-SEARCH(problem) returns soln node or failure\n",
              "\tfor depth = 0 to infinity\n",
              "\t\tresult = DEPTH-LIMITED-SEARCH(problem, depth)\n",
              "\t\tif result != cutoff then return result\n",
              "```\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "### search problems\n",
              "\n",
              "- **reflex agent:** selects an action based only on the current precept, igonres the rest of the percept history\n",
              "- **problem-solving agent**: considers a sequence of actions to form a path to a goal state. sequence = solution.\n",
              "- example sliding-tile puzzle (8-puzzle)\n",
              "- map navigation\n",
              "\n",
              "### search problem formulation\n",
              "\n",
              "**formal problem definition,** representation\n",
              "\n",
              "1. states: a set $S$ \n",
              "2. initial state: $s_i \\in S$\n",
              "3. actions: a set $A$, $\forall s$, actions that we can take from any state\n",
              "4. transition model: for all actions, $result(s, a) → s_r$, $s_r$ is called a successor of $s$\n",
              "5. path cost: must be additive (e.g. sum of distances, number of actions, etc...)\n",
              "    1. $c(x, a_xy)$ is the step cost, assumed to be ≥ 0\n",
              "6. goal test: $goal(s)$ is true or false\n",
              "- **ex) vacuum world**\n",
              "    1. states: 2-square grid world. each cell can be dirty or not.\n",
              "        1. 2 cells * 2 positions * 2 possibilities (dirt or not) = 8 states\n",
              "        2. $n$ cells, $n 2^n$ states\n",
              "    2. one state is designated as the initial state\n",
              "    3. actions: suck, move left, right\n",
              "    4. transition: suck = removes dirt, move = move in that direction, unless we hit a wall.\n",
              "    5. action cost: uniform cost, each action costs 1.\n",
              "    6. goal state: everything is clean.\n",
              "\n",
              "**solutions and optimal solutions:**\n",
              "\n",
              "- a solution is a sequence of actions from the initial state to a goal state\n",
              "- **optimal solution**: no solution has a lower path cost\n",
              "- **ex) 8-puzzle**\n",
              "    1. states: list of 9 locations\n",
              "    2. initial state: single array or list\n",
              "    3. actions: set of possible moves {left, right, up, down}\n",
              "    4. transition model\n",
              "    5. goal test: iterate through and in ascending order\n",
              "    6. path cost: number of actions to reach goal, each action = 1\n",
              "\n",
              "*state space:* set of all states reachable from the initial state by any sequence of actions\n",
              "\n",
              "*path*: sequence of actions leading from one state, $s_j$ to another state $s_k$\n",
              "\n",
              "*frontier:* states available for expanding\n",
              "\n",
              "*solution:* path from the initial state $s_i$ to a state $s_f$ that satisfies the goal test\n",
              "\n",
              "### basic search algs\n",
              "\n",
              "- initialize frontier → choose a node on the frontier to expand → add resulting states to frontier (while frontier is not empty)\n",
              "- repeatedly visiting the same state is a problem → turns a linear problem into an exponential problem\n",
              "- algorithm is **complete** **if the algorithm is guaranteed to find a solution if there is one, and to correctly report failure when there is not\n",
              "\n",
              "### uninformed (blind) search strategies\n",
              "\n",
              "- A search method is **uninformed** if it only has access to the problem definition\n",
              "\n",
              "definitions for evaluation\n",
              "\n",
              "- completeness - always find the solution?\n",
              "- optimality - finds a least cost solution?\n",
              "- time complexity\n",
              "- space complexity\n",
              "\n",
              "time/space complexity variables: \n",
              "\n",
              "- $b$, a maximum branching factor of search tree\n",
              "- $d$, depth of shallowest goal node\n",
              "- $m$, max length of any potential path\n",
              "\n",
              "### bfs/dfs\n",
              "\n",
              "- bfs: expand shallowest unexpanded node, FIFO frontier queue\n",
              "    - complete\n",
              "    - time complexity: $O(b^d)$\n",
              "    - space complexity: $O(b^d)$\n",
              "    - optimal: yes if one step = one cost\n",
              "    - use if possible infinite paths, some solns have short paths\n",
              "- dfs: expand deepest node, LIFO\n",
              "    - incomplete - fails in loops\n",
              "    - time complexity: $O(b^m)$\n",
              "    - space complexity: $O(b*m)$\n",
              "    - optimal: yes if one step = one cost\n",
              "    - use if space-restricted, wrong paths are terminated quickly, search can be fine-tuned quickly\n",
              "\n",
              "### depth limited search and iterative deepening search\n",
              "\n",
              "depth limited search\n",
              "\n",
              "- DFS with depth limit $l$\n",
              "- no infinite-path problem\n",
              "- optimal if $l = d$, otherwise if $l < d$ then incomplete, if $l > d$ then not optimal\n",
              "\n",
              "iterative deepening search\n",
              "\n",
              "- general strategy to find best depth limit $l$\n",
              "    - key idea: use depth-limited search as subroutine and increase $l$\n",
              "- complete & optimal (if step cost = 1)\n",
              "- time complexity: $O(b^d)$\n",
              "- space complexity: $O(bd)$\n",
              "\n",
              "### review questions\n",
              "\n",
              "- uninformed complete algs: BFS, uniform-cost search, iterative deepening, bidirectional\n",
              "- uninformed optimal algs: same as above.\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 79,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "- informed search - domain-specific hints about goals\n",
        "- **heuristic function,** h(n) - estimated cost of the cheapest path from state at node to goal\n",
        "\n",
        "**greedy best-first search**\n",
        "\n",
        "- first expands node with lowest h(n) so f(n) = h(n)\n",
        "- e.g. route-finding problem in Romania uses **straight-line distance** heuristic\n",
        "- complete in finite spaces, not in infinite ones\n",
        "- time/space complexity = O(|V|), can be reduced to O(bm) with a good heuristic\n",
        "- not necessarily optimal solution\n",
        "\n",
        "**A* search**\n",
        "\n",
        "- best-first search with evaluation function\n",
        "    \n",
        "    $$f(n) = g(n) + h(n)$$\n",
        "    \n",
        "    - g(n) = path cost from initial state to node n\n",
        "    - h(n) = estimated cost of shortest path from n to goal state.\n",
        "    - f(n) = estimated cost of best path that continues from n to goal\n",
        "- complete\n",
        "- cost-optimal if heuristic is **admissible**: never overestimates cost to reach goal\n",
        "    - with an inadmissable heuristic: cost-optimal if (1) there is one cost-optimal path on which h(n) is admissable for all nodes on the path or (2) optimal soln has cost C* and second-best has cost C2 and h(n) overestimates some costs but never > C2 - C*\n",
        "- **consistency**: a heuristic h(n) is consistent if for every node and every successor n' of n, (form of triangle inequality)\n",
        "    \n",
        "    $$h(n) \\leq c(n, a, n') + h(n')$$\n",
        "    \n",
        "    - every consistent heuristic is admissable (but not other way around)\n",
        "    - first time we reach a state is optimal\n",
        "- **surely expanded nodes** - A* expands all nodes reachable from the initial state with f(n) < C*\n",
        "    - does not expand any nodes with f(n) > C*\n",
        "- optimally efficient - one algorithm may choose the optimal one first while another alg doesn't, but no difference in \"optimal efficiency\"\n",
        "- **prunes** search tree nodes that don't lead to the optimal solution\n",
        "- number of expanded nodes can be exponential in the length of the solution\n",
        "\n",
        "**satisficing search: inadmissable heuristics and weighted A***\n",
        "\n",
        "- explore less nodes but settle for **satisficing** solutions, \"good enough\"\n",
        "- weighted A* search weighs heuristic more heavily\n",
        "    \n",
        "    $$f(n) = g(n) + W*h(n), W>1$$\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "- **effective branching factor b*** - branching factor a uniform tree of depth d (solution depth) needs to contain N+1 nodes, where N is the total number of nodes generated\n",
        "    \n",
        "    $$N + 1 = 1 + b^* + (b^*)^2 + ... + (b^*)^d$$\n",
        "    \n",
        "    - e.g. A* finds a soln at depth 5 with 52 nodes ⇒ b* = 1.92\n",
        "    - well-designed heuristic has b* = 1. and a lower branching factor (but heuristic function values) is \"essentially\" always better.\n",
        "- if for any node n, h2(n) ≥ h1(n), then h2 **dominates** h1\n",
        "- **relaxed problem** - fewer restrictions on the actions. supergraph of the state space. *cost of an optimal soln to a relaxed problem is an admissable heuristic for the original problem*.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "### uniform cost search\n",
        "\n",
        "- search algorithm for *weighted paths*\n",
        "- motivation: map navigation problems\n",
        "    - path cost = $g(N) = depth(N)$\n",
        "- expand node with *lowest path cost*\n",
        "- frontier uses a priority queue, ordered by $g(n)$\n",
        "\n",
        "subtle but significant differences from BFS:\n",
        "\n",
        "- tests if a node is a goal state when it is selected for expansion, not when it's added to frontier\n",
        "- updates a node on the frontier if a better path to same state is found\n",
        "- could be multiple ways of getting to the node, *not guaranteed to have lowest path cost when enqueued*\n",
        "\n",
        "shape of search draws a map of equivalence classes.\n",
        "\n",
        "### heuristic functions\n",
        "\n",
        "- best-first search is based on an evaluation function $f(n)$\n",
        "- simple, useful heuristic. an approximation of travel that reduces problem space (e.g. straight-line distance)\n",
        "    - **must be an underestimate of true path cost**\n",
        "\n",
        "### greedy bfs\n",
        "\n",
        "best-first search: select node for expansion with minimal evaluation function $f(n)$. use priority queue.\n",
        "\n",
        "- completely ignores $g(n)$\n",
        "\n",
        "### a* search\n",
        "\n",
        "- key idea: avoid expanding paths that are already expensive, but expand most promising first.\n",
        "- $f(n) = g(n) + h(n)$\n",
        "    - $g(n)$ is actual cost to reach node\n",
        "    - $h(n)$ estimated cost to get from node to goal\n",
        "    - $f(n)$ estimated total cost of path through $n$ to goal\n",
        "- implementation: frontier queue as priority queue by increasing $f(n)$\n",
        "\n",
        "**admissible** heuristics: a heuristic $h(n)$ is admissible if it never overestimates the cost to reach the goal (*optimistic*)\n",
        "\n",
        "- slow down bad plans but never outweigh true costs. ensures true best plan will always be expanded.\n",
        "- $\\forall n, h(n) \\leq h*n, h(n) \\geq 0$\n",
        "\n",
        "if $h(n)$ is admissible, then a* search is optimal.\n",
        "\n",
        "**relaxed problems**\n",
        "\n",
        "- cost of an optimal solution to a relaxed problem is an admissable heuristic for the original problem\n",
        "\n",
        "measure if a heuristic is better than another (h1 *dominates* h2 if $h_2(n) \\geq h_1(n)$ for all $n$)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 80,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "39fd92a1-5b60-4d68-93a7-78ad0c89301c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "- informed search - domain-specific hints about goals\n",
              "- **heuristic function,** h(n) - estimated cost of the cheapest path from state at node to goal\n",
              "\n",
              "**greedy best-first search**\n",
              "\n",
              "- first expands node with lowest h(n) so f(n) = h(n)\n",
              "- e.g. route-finding problem in Romania uses **straight-line distance** heuristic\n",
              "- complete in finite spaces, not in infinite ones\n",
              "- time/space complexity = O(|V|), can be reduced to O(bm) with a good heuristic\n",
              "- not necessarily optimal solution\n",
              "\n",
              "**A* search**\n",
              "\n",
              "- best-first search with evaluation function\n",
              "    \n",
              "    $$f(n) = g(n) + h(n)$$\n",
              "    \n",
              "    - g(n) = path cost from initial state to node n\n",
              "    - h(n) = estimated cost of shortest path from n to goal state.\n",
              "    - f(n) = estimated cost of best path that continues from n to goal\n",
              "- complete\n",
              "- cost-optimal if heuristic is **admissible**: never overestimates cost to reach goal\n",
              "    - with an inadmissable heuristic: cost-optimal if (1) there is one cost-optimal path on which h(n) is admissable for all nodes on the path or (2) optimal soln has cost C* and second-best has cost C2 and h(n) overestimates some costs but never > C2 - C*\n",
              "- **consistency**: a heuristic h(n) is consistent if for every node and every successor n' of n, (form of triangle inequality)\n",
              "    \n",
              "    $$h(n) \\leq c(n, a, n') + h(n')$$\n",
              "    \n",
              "    - every consistent heuristic is admissable (but not other way around)\n",
              "    - first time we reach a state is optimal\n",
              "- **surely expanded nodes** - A* expands all nodes reachable from the initial state with f(n) < C*\n",
              "    - does not expand any nodes with f(n) > C*\n",
              "- optimally efficient - one algorithm may choose the optimal one first while another alg doesn't, but no difference in \"optimal efficiency\"\n",
              "- **prunes** search tree nodes that don't lead to the optimal solution\n",
              "- number of expanded nodes can be exponential in the length of the solution\n",
              "\n",
              "**satisficing search: inadmissable heuristics and weighted A***\n",
              "\n",
              "- explore less nodes but settle for **satisficing** solutions, \"good enough\"\n",
              "- weighted A* search weighs heuristic more heavily\n",
              "    \n",
              "    $$f(n) = g(n) + W*h(n), W>1$$\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "- **effective branching factor b*** - branching factor a uniform tree of depth d (solution depth) needs to contain N+1 nodes, where N is the total number of nodes generated\n",
              "    \n",
              "    $$N + 1 = 1 + b^* + (b^*)^2 + ... + (b^*)^d$$\n",
              "    \n",
              "    - e.g. A* finds a soln at depth 5 with 52 nodes ⇒ b* = 1.92\n",
              "    - well-designed heuristic has b* = 1. and a lower branching factor (but heuristic function values) is \"essentially\" always better.\n",
              "- if for any node n, h2(n) ≥ h1(n), then h2 **dominates** h1\n",
              "- **relaxed problem** - fewer restrictions on the actions. supergraph of the state space. *cost of an optimal soln to a relaxed problem is an admissable heuristic for the original problem*.\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "### uniform cost search\n",
              "\n",
              "- search algorithm for *weighted paths*\n",
              "- motivation: map navigation problems\n",
              "    - path cost = $g(N) = depth(N)$\n",
              "- expand node with *lowest path cost*\n",
              "- frontier uses a priority queue, ordered by $g(n)$\n",
              "\n",
              "subtle but significant differences from BFS:\n",
              "\n",
              "- tests if a node is a goal state when it is selected for expansion, not when it's added to frontier\n",
              "- updates a node on the frontier if a better path to same state is found\n",
              "- could be multiple ways of getting to the node, *not guaranteed to have lowest path cost when enqueued*\n",
              "\n",
              "shape of search draws a map of equivalence classes.\n",
              "\n",
              "### heuristic functions\n",
              "\n",
              "- best-first search is based on an evaluation function $f(n)$\n",
              "- simple, useful heuristic. an approximation of travel that reduces problem space (e.g. straight-line distance)\n",
              "    - **must be an underestimate of true path cost**\n",
              "\n",
              "### greedy bfs\n",
              "\n",
              "best-first search: select node for expansion with minimal evaluation function $f(n)$. use priority queue.\n",
              "\n",
              "- completely ignores $g(n)$\n",
              "\n",
              "### a* search\n",
              "\n",
              "- key idea: avoid expanding paths that are already expensive, but expand most promising first.\n",
              "- $f(n) = g(n) + h(n)$\n",
              "    - $g(n)$ is actual cost to reach node\n",
              "    - $h(n)$ estimated cost to get from node to goal\n",
              "    - $f(n)$ estimated total cost of path through $n$ to goal\n",
              "- implementation: frontier queue as priority queue by increasing $f(n)$\n",
              "\n",
              "**admissible** heuristics: a heuristic $h(n)$ is admissible if it never overestimates the cost to reach the goal (*optimistic*)\n",
              "\n",
              "- slow down bad plans but never outweigh true costs. ensures true best plan will always be expanded.\n",
              "- $\forall n, h(n) \\leq h*n, h(n) \\geq 0$\n",
              "\n",
              "if $h(n)$ is admissible, then a* search is optimal.\n",
              "\n",
              "**relaxed problems**\n",
              "\n",
              "- cost of an optimal solution to a relaxed problem is an admissable heuristic for the original problem\n",
              "\n",
              "measure if a heuristic is better than another (h1 *dominates* h2 if $h_2(n) \\geq h_1(n)$ for all $n$)\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 81,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "- **competitive environments** - ≥2 agents have conflicting goals ⇒ adversarila search\n",
        "1. economy - consider a large number of agents in aggregate\n",
        "2. adversarial agents are part of the environment, nondeterministic\n",
        "3. explicitly model adversarial agents ← this is what we do\n",
        "- **perfect information** - \"fully observable\"\n",
        "- **zero-sum** - one player's wins are another player's losses. no win-win.\n",
        "- MAX moves first (wants to maximize utility). MIN wants to minimize.\n",
        "\n",
        "game formal defn:\n",
        "\n",
        "- S0: initial state\n",
        "- TO-MOVE(s): player to move in state s\n",
        "- ACTIONS(s): set of legal moves\n",
        "- RESULT(s, a): transition model\n",
        "- IS-TERMINAL(s): true when game is over\n",
        "- UTILITY(s, p): final numeric value when game ends (e.g. chess win = 1, loss = 0, draw = 1/2)\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "**minimax search**\n",
        "\n",
        "- **minimax value** of each state gives optimal strategy, MINIMAX(s)\n",
        "    - MAX's utility, assuming both players play optimally to the end of the game\n",
        "    - terminal nodes' utility is just from the utility function\n",
        "- minimax search alg - find best move for MAX by attempting all actions, recursive alg which searches all the way to leaves and backs up the minimax values through the tree\n",
        "\n",
        "```python\n",
        "function MINIMAX-SEARCH(game, state) returns an action\n",
        "\tplayer = game.TO-MOVE(state)\n",
        "\tvalue, move = MAX-VALUE(game, state)\n",
        "\treturn move\n",
        "\n",
        "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        "\tif game is terminal then return game.UTILITY, null\n",
        "\tv = -infinity\n",
        "\tfor each action\n",
        "\t\tv2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n",
        "\t\tif v2 > v then\n",
        "\t\t\tv, move = v2, a\n",
        "\treturn v, move\n",
        "\n",
        "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        "\tif game is terminal then return game.UTILITY, null\n",
        "\tv = infinity\n",
        "\tfor each action\n",
        "\t\tv2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n",
        "\tif v2 < v then\n",
        "\t\tv, move = v2, a\n",
        "\treturn v, move\n",
        "```\n",
        "\n",
        "- complete depth-first exploration of game tree\n",
        "    - time complexity = O(b^m), b = legal moves at each point. m = max depth.\n",
        "    - space complexity = O(bm)\n",
        "\n",
        "**multiplayer games -** value gets replaced with *vector* of values. but you also have to deal with alliances\n",
        "\n",
        "**alpha-beta pruning**\n",
        "\n",
        "- prune sub-trees to save time and space\n",
        "- for a node n that player can move to, if player has a better choice at the same level or higher up, then player will never move to n ⇒ prune\n",
        "- $\\alpha$ = highest-value choice found so far for MAX (at least)\n",
        "- $\\beta$ = lowest-value choice found so far for MIN (at most)\n",
        "\n",
        "```python\n",
        "function ALPHA-BETA-SEARCH(game, state) returns an action\n",
        "\tplayer = game.TO-MOVE(state)\n",
        "\tvalue, move = MAX-VALUE(game, state, -inf, +inf)\n",
        "\treturn move\n",
        "\n",
        "function MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
        "\tif game is terminal, return utility, null\n",
        "\tv = -inf\n",
        "\tfor each action\n",
        "\t\tv2, a2 = MIN-VALUE(game, result, alpha, beta)\n",
        "\t\tif v2 > v then\n",
        "\t\t\tv, move = v2, a\n",
        "\t\t\talpha = MAX(alpha, v)\n",
        "\t\tif v >= beta then return v, move\n",
        "\treturn v, move\n",
        "\n",
        "function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
        "\tif game is terminal then return game.UTILITY\n",
        "\tv = +inf\n",
        "\tfor each action\n",
        "\t\tv2, a2 = MAX-VALUE(game, result, alpha, beta)\n",
        "\t\tif v2 < v then\n",
        "\t\t\tv, move = v2, a\n",
        "\t\t\tbeta = MIN(beta, v)\n",
        "\t\tif v <= a then return v, move\n",
        "\treturn v, move\n",
        "```\n",
        "\n",
        "- highly dependent on order — perfect ordering would result in $O(b^{m/2})$ nodes, √b instead of b branching factor\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "- cut off search early and apply a heuristic evaluation function to states\n",
        "\n",
        "**evaluation functions**\n",
        "\n",
        "- returns an estimate of the expected utility. for terminal states EVAL(s, p) = UTILITY(s, p). for non-terminal states, UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p)\n",
        "- calculate various features (e.g. chess: number of white pawns, queens, etc...)\n",
        "    - rules come from knowledge, culture of the game\n",
        "\n",
        "**cutting off search**\n",
        "\n",
        "- most straightforward = set a fixed depth limit. more robust = iterative deepening.\n",
        "- **quiscent** - positions where no pending move can change the evaluation\n",
        "    - for non-quiscent positions, continue searching\n",
        "- **horizon effect** - inevitable move by opponent is delayed past depth cutoff\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- stochastic games include a random element. must include **chance nodes** labeled with roll and probability and use expected value.\n",
        "- **expectiminimax value**\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "### game formulation\n",
        "\n",
        "games need to have an opponent\n",
        "\n",
        "- 5.11.1997 deep blue (ibm) beats garry kasparov in chess\n",
        "- AlphaGo beats grandmaster lee sedol (>> more configurations than chess)\n",
        "\n",
        "simplest game environment: multiagent, static (no change while an agent is deliberating), discrete (finite set of percepts and actinos), fully observable (complete state is visible to sensor), strategic (next state is determined by current state, action by agent, and action of opponent)\n",
        "\n",
        "key properties of our games:\n",
        "\n",
        "1. two players alternate moves\n",
        "2. zero-sum: one player's loss is another's gain\n",
        "3. clear set of legal moves\n",
        "4. well-defined outcomes (win, lose, draw)\n",
        "\n",
        "more complicated games: most card games, scrabble, real-time strategy games (starcraft), cooperative games\n",
        "\n",
        "formalizing game setup:\n",
        "\n",
        "1. two players: **max** and **min** (max moves first)\n",
        "2. **max** and **min** take turns until the game is over\n",
        "3. winner gets award, loser gets penalty\n",
        "\n",
        "game as search:\n",
        "\n",
        "- initial state (e.g. board configuration of chess)\n",
        "- successor function: list of (move, state) pairs specifying legal moves\n",
        "- terminal test: is the game finished?\n",
        "- utility function: gives numerical value of terminal states\n",
        "- **max** uses search tree to determine next move\n",
        "\n",
        "### game tree\n",
        "\n",
        "**hexapawn**\n",
        "\n",
        "- played on a 3x3 chessboard. 6 pawn pieces.\n",
        "- only standard pawn moves: (a) a pawn moves forward one square onto an empty square. (b) pawn \"captures\" an opponent pawn by moving diagonally forward one square if square contains opposing pawn. remove opposing pawn from board.\n",
        "- player $P_1$ wins against $P_2$ when: one of P1's pawns reaches the far side of the board, $P_2$ cannot move because no legal moves possible, $P_2$ has no pawns left\n",
        "\n",
        "represent game problem as a tree\n",
        "\n",
        "- nodes = board positions\n",
        "- edges = legal moves\n",
        "- root node = first position in which a decision must be made\n",
        "- adversarial search: best move for me, best move for them?\n",
        "\n",
        "max moves first (attempts to maximize max's outcome). max's opponent (min) attempts to minimize max's outcome.\n",
        "\n",
        "even levels represent max. odd levels represent min.\n",
        "\n",
        "$f$ assigns real-number scores to 'board positions'. terminal nodes represent the way the game could end.\n",
        "\n",
        "$f(n)$ evaluation function\n",
        "\n",
        "- based on *static features* of that board alone.\n",
        "- $f(n) > 0$ if MAX is winning in position $n$\n",
        "- $f(n) = 0$ if position $n$ is tied\n",
        "- $f(n) < 0$ if MIN is winning in position $n$\n",
        "- e.g. for tic tac toe, $f(n)$ = # of potential three-lines for X - # of potential three-lines for O\n",
        "\n",
        "### minimax rules\n",
        "\n",
        "idea: make the best move for MAX assuming that MIN always replies with the best move for MIN\n",
        "\n",
        "**easily computed by recursive process**\n",
        "\n",
        "- **backed-up** value of each node is tree determined by the values of its children\n",
        "- for MAX node: backed-up value is **maximum** of the values of its children\n",
        "- for MIN node: backed-up value is **minimum** of values of its children\n",
        "\n",
        "**minimax procedure**\n",
        "\n",
        "1. start with current position as MAX node\n",
        "2. expand game tree a fixed number of ply (may not always be able to reach end-state, truncated search)\n",
        "3. apply evaluation function to leaf positions\n",
        "4. calculate back-up values bottom-up\n",
        "5. pick move assigned to MAX at root\n",
        "6. wait for MIN to respond\n",
        "\n",
        "```python\n",
        "def max-value(state):\n",
        "\tif (state in terminal state): return state's utility\n",
        "\tv = -infinity\n",
        "\tfor successor of state:\n",
        "\t\tv = max(v, min-value(successor))\n",
        "\treturn v\n",
        "\n",
        "def min-value(state):\n",
        "\tif (state in terminal state): return state's utility\n",
        "\tv =-infinity\n",
        "\tfor successor of state:\n",
        "\t\tv = min(v, max-value(successor))\n",
        "\treturn v \n",
        "```\n",
        "\n",
        "### alpha-beta pruning\n",
        "\n",
        "stop evaluating a branch whenever:\n",
        "\n",
        "$\\alpha$: MAX's current lower bound on MAX's outcome\n",
        "\n",
        "- never allows a move worse than $\\alpha$\n",
        "\n",
        "$\\beta$: MIN's current upper bound on MIN's outcome\n",
        "\n",
        "- never allows a move better than $\\beta$\n",
        "\n",
        "### expectimax\n",
        "\n",
        "uncertain outcomes: rolling dice, shuffled card games, \n",
        "\n",
        "- model tree as before but max nodes and chance nodes. chances nodes say how likely branch is.\n",
        "\n",
        "expectimax: compute average score under optimal play.\n",
        "\n",
        "- calculate *expected utilities* (weighted average / expectation)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 82,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "778ca834-3cee-43d7-d560-7605dc6d91bf"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "- **competitive environments** - ≥2 agents have conflicting goals ⇒ adversarila search\n",
              "1. economy - consider a large number of agents in aggregate\n",
              "2. adversarial agents are part of the environment, nondeterministic\n",
              "3. explicitly model adversarial agents ← this is what we do\n",
              "- **perfect information** - \"fully observable\"\n",
              "- **zero-sum** - one player's wins are another player's losses. no win-win.\n",
              "- MAX moves first (wants to maximize utility). MIN wants to minimize.\n",
              "\n",
              "game formal defn:\n",
              "\n",
              "- S0: initial state\n",
              "- TO-MOVE(s): player to move in state s\n",
              "- ACTIONS(s): set of legal moves\n",
              "- RESULT(s, a): transition model\n",
              "- IS-TERMINAL(s): true when game is over\n",
              "- UTILITY(s, p): final numeric value when game ends (e.g. chess win = 1, loss = 0, draw = 1/2)\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "**minimax search**\n",
              "\n",
              "- **minimax value** of each state gives optimal strategy, MINIMAX(s)\n",
              "    - MAX's utility, assuming both players play optimally to the end of the game\n",
              "    - terminal nodes' utility is just from the utility function\n",
              "- minimax search alg - find best move for MAX by attempting all actions, recursive alg which searches all the way to leaves and backs up the minimax values through the tree\n",
              "\n",
              "```python\n",
              "function MINIMAX-SEARCH(game, state) returns an action\n",
              "\tplayer = game.TO-MOVE(state)\n",
              "\tvalue, move = MAX-VALUE(game, state)\n",
              "\treturn move\n",
              "\n",
              "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY, null\n",
              "\tv = -infinity\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n",
              "\t\tif v2 > v then\n",
              "\t\t\tv, move = v2, a\n",
              "\treturn v, move\n",
              "\n",
              "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY, null\n",
              "\tv = infinity\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n",
              "\tif v2 < v then\n",
              "\t\tv, move = v2, a\n",
              "\treturn v, move\n",
              "```\n",
              "\n",
              "- complete depth-first exploration of game tree\n",
              "    - time complexity = O(b^m), b = legal moves at each point. m = max depth.\n",
              "    - space complexity = O(bm)\n",
              "\n",
              "**multiplayer games -** value gets replaced with *vector* of values. but you also have to deal with alliances\n",
              "\n",
              "**alpha-beta pruning**\n",
              "\n",
              "- prune sub-trees to save time and space\n",
              "- for a node n that player can move to, if player has a better choice at the same level or higher up, then player will never move to n ⇒ prune\n",
              "- $\u0007lpha$ = highest-value choice found so far for MAX (at least)\n",
              "- $\beta$ = lowest-value choice found so far for MIN (at most)\n",
              "\n",
              "```python\n",
              "function ALPHA-BETA-SEARCH(game, state) returns an action\n",
              "\tplayer = game.TO-MOVE(state)\n",
              "\tvalue, move = MAX-VALUE(game, state, -inf, +inf)\n",
              "\treturn move\n",
              "\n",
              "function MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
              "\tif game is terminal, return utility, null\n",
              "\tv = -inf\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MIN-VALUE(game, result, alpha, beta)\n",
              "\t\tif v2 > v then\n",
              "\t\t\tv, move = v2, a\n",
              "\t\t\talpha = MAX(alpha, v)\n",
              "\t\tif v >= beta then return v, move\n",
              "\treturn v, move\n",
              "\n",
              "function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY\n",
              "\tv = +inf\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MAX-VALUE(game, result, alpha, beta)\n",
              "\t\tif v2 < v then\n",
              "\t\t\tv, move = v2, a\n",
              "\t\t\tbeta = MIN(beta, v)\n",
              "\t\tif v <= a then return v, move\n",
              "\treturn v, move\n",
              "```\n",
              "\n",
              "- highly dependent on order — perfect ordering would result in $O(b^{m/2})$ nodes, √b instead of b branching factor\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "- cut off search early and apply a heuristic evaluation function to states\n",
              "\n",
              "**evaluation functions**\n",
              "\n",
              "- returns an estimate of the expected utility. for terminal states EVAL(s, p) = UTILITY(s, p). for non-terminal states, UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p)\n",
              "- calculate various features (e.g. chess: number of white pawns, queens, etc...)\n",
              "    - rules come from knowledge, culture of the game\n",
              "\n",
              "**cutting off search**\n",
              "\n",
              "- most straightforward = set a fixed depth limit. more robust = iterative deepening.\n",
              "- **quiscent** - positions where no pending move can change the evaluation\n",
              "    - for non-quiscent positions, continue searching\n",
              "- **horizon effect** - inevitable move by opponent is delayed past depth cutoff\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "- stochastic games include a random element. must include **chance nodes** labeled with roll and probability and use expected value.\n",
              "- **expectiminimax value**\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "### game formulation\n",
              "\n",
              "games need to have an opponent\n",
              "\n",
              "- 5.11.1997 deep blue (ibm) beats garry kasparov in chess\n",
              "- AlphaGo beats grandmaster lee sedol (>> more configurations than chess)\n",
              "\n",
              "simplest game environment: multiagent, static (no change while an agent is deliberating), discrete (finite set of percepts and actinos), fully observable (complete state is visible to sensor), strategic (next state is determined by current state, action by agent, and action of opponent)\n",
              "\n",
              "key properties of our games:\n",
              "\n",
              "1. two players alternate moves\n",
              "2. zero-sum: one player's loss is another's gain\n",
              "3. clear set of legal moves\n",
              "4. well-defined outcomes (win, lose, draw)\n",
              "\n",
              "more complicated games: most card games, scrabble, real-time strategy games (starcraft), cooperative games\n",
              "\n",
              "formalizing game setup:\n",
              "\n",
              "1. two players: **max** and **min** (max moves first)\n",
              "2. **max** and **min** take turns until the game is over\n",
              "3. winner gets award, loser gets penalty\n",
              "\n",
              "game as search:\n",
              "\n",
              "- initial state (e.g. board configuration of chess)\n",
              "- successor function: list of (move, state) pairs specifying legal moves\n",
              "- terminal test: is the game finished?\n",
              "- utility function: gives numerical value of terminal states\n",
              "- **max** uses search tree to determine next move\n",
              "\n",
              "### game tree\n",
              "\n",
              "**hexapawn**\n",
              "\n",
              "- played on a 3x3 chessboard. 6 pawn pieces.\n",
              "- only standard pawn moves: (a) a pawn moves forward one square onto an empty square. (b) pawn \"captures\" an opponent pawn by moving diagonally forward one square if square contains opposing pawn. remove opposing pawn from board.\n",
              "- player $P_1$ wins against $P_2$ when: one of P1's pawns reaches the far side of the board, $P_2$ cannot move because no legal moves possible, $P_2$ has no pawns left\n",
              "\n",
              "represent game problem as a tree\n",
              "\n",
              "- nodes = board positions\n",
              "- edges = legal moves\n",
              "- root node = first position in which a decision must be made\n",
              "- adversarial search: best move for me, best move for them?\n",
              "\n",
              "max moves first (attempts to maximize max's outcome). max's opponent (min) attempts to minimize max's outcome.\n",
              "\n",
              "even levels represent max. odd levels represent min.\n",
              "\n",
              "$f$ assigns real-number scores to 'board positions'. terminal nodes represent the way the game could end.\n",
              "\n",
              "$f(n)$ evaluation function\n",
              "\n",
              "- based on *static features* of that board alone.\n",
              "- $f(n) > 0$ if MAX is winning in position $n$\n",
              "- $f(n) = 0$ if position $n$ is tied\n",
              "- $f(n) < 0$ if MIN is winning in position $n$\n",
              "- e.g. for tic tac toe, $f(n)$ = # of potential three-lines for X - # of potential three-lines for O\n",
              "\n",
              "### minimax rules\n",
              "\n",
              "idea: make the best move for MAX assuming that MIN always replies with the best move for MIN\n",
              "\n",
              "**easily computed by recursive process**\n",
              "\n",
              "- **backed-up** value of each node is tree determined by the values of its children\n",
              "- for MAX node: backed-up value is **maximum** of the values of its children\n",
              "- for MIN node: backed-up value is **minimum** of values of its children\n",
              "\n",
              "**minimax procedure**\n",
              "\n",
              "1. start with current position as MAX node\n",
              "2. expand game tree a fixed number of ply (may not always be able to reach end-state, truncated search)\n",
              "3. apply evaluation function to leaf positions\n",
              "4. calculate back-up values bottom-up\n",
              "5. pick move assigned to MAX at root\n",
              "6. wait for MIN to respond\n",
              "\n",
              "```python\n",
              "def max-value(state):\n",
              "\tif (state in terminal state): return state's utility\n",
              "\tv = -infinity\n",
              "\tfor successor of state:\n",
              "\t\tv = max(v, min-value(successor))\n",
              "\treturn v\n",
              "\n",
              "def min-value(state):\n",
              "\tif (state in terminal state): return state's utility\n",
              "\tv =-infinity\n",
              "\tfor successor of state:\n",
              "\t\tv = min(v, max-value(successor))\n",
              "\treturn v \n",
              "```\n",
              "\n",
              "### alpha-beta pruning\n",
              "\n",
              "stop evaluating a branch whenever:\n",
              "\n",
              "$\u0007lpha$: MAX's current lower bound on MAX's outcome\n",
              "\n",
              "- never allows a move worse than $\u0007lpha$\n",
              "\n",
              "$\beta$: MIN's current upper bound on MIN's outcome\n",
              "\n",
              "- never allows a move better than $\beta$\n",
              "\n",
              "### expectimax\n",
              "\n",
              "uncertain outcomes: rolling dice, shuffled card games, \n",
              "\n",
              "- model tree as before but max nodes and chance nodes. chances nodes say how likely branch is.\n",
              "\n",
              "expectimax: compute average score under optimal play.\n",
              "\n",
              "- calculate *expected utilities* (weighted average / expectation)\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 83,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "constraint satisfaction problem consists of:\n",
        "\n",
        "1. X, set of variables $\\{X_1,...,X_n\\}$\n",
        "2. D, set of domains $\\{D_1,...,D_n\\}$. $D_i$ is the set of allowable values for variable $X_i$\n",
        "3. C, set of constraints on value combinations\n",
        "- CSPs assign values to variables. **consistent** **assignment doesn't violate any constraints. **complete** assignment - every variable has a value. **solution -** complete, consistent assignment.\n",
        "    - **partial assignment** - some unassigned variables. **partial solution** - consistent partial assignment.\n",
        "- **constraint graph** - nodes = variables, edge = two variables in a constraint.\n",
        "\n",
        "types of constraints:\n",
        "\n",
        "- **unary constraint** - restricts value to single variable (e.g. SA ≠ green)\n",
        "- **binary constraint** - relates two variables (eg. SA ≠ NSW)\n",
        "- **ternary constraint** - (e.g. X < Y < Z)\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- constraint propagation: use constraints to reduce # of legal values for a variable\n",
        "- **local consistency** - enforce local consistency to eliminate inconsistent values\n",
        "\n",
        "**node consistency** - all values in domain satisfy unary constraints\n",
        "\n",
        "**arc consistency** - satisfy binary constraints\n",
        "\n",
        "- sometimes does nothing (e.g. australia map coloring problem - valid value for the other variable for each value of the domain)\n",
        "- **AC-3** enforces arc-consistency for every variable. maintains a queue of arcs.\n",
        "\n",
        "```jsx\n",
        "function AC-3(csp) returns false if an inconsistency if found, true otherwise\n",
        "\tqueue = queue of arcs, initialized to all arcs in csp\n",
        "\twhile queue isn't empty\n",
        "\t\t(x_i, x_j) = pop(queue)\n",
        "\t\tif REVISE(csp, x_i, x_j) then\n",
        "\t\t\tif size(D_i) = 0 then return false\n",
        "\t\t\tfor each x_k in x_i.neighbors - {x_j} do\n",
        "\t\t\t\tadd (x_k, x_i) to queue\n",
        "\treturn true\n",
        "\n",
        "function REVISE(csp, x_i, x_j) returns true iff we revise the domain of x_i\n",
        "\trevised = false\n",
        "\tfor each x in D_i do\n",
        "\t\tif no value y in D_j allows (x, y) to satisfy the constraint between X_i and X_j then\n",
        "\t\t\tdelete x from D_i\n",
        "\t\t\trevised = true\n",
        "\treturn revised\n",
        "```\n",
        "\n",
        "- complexity: with n variables, domain size of at most d, and c arcs, checking consistency of arcs is $O(d^2)$ so total run-time is $O(cd^3)$\n",
        "\n",
        "**path consistency** - triples of variables\n",
        "\n",
        "**k-consistency** - strongly consistent if also (k - 1)-consistent, (k - 2)-consistent, etc...\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "- CSPs are commutative since order of assigning actions does not matter.\n",
        "\n",
        "```jsx\n",
        "function BACKTRACKING-SEARCH(csp) returns a solution or failure\n",
        "\treturn BACKTRACK(csp, {})\n",
        "\n",
        "function BACKTRACK(csp, assignment) returns a solution or failure\n",
        "\tif assignment is complete then return assignment\n",
        "\tvar = SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n",
        "\tfor each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n",
        "\t\tif value is consistent with assignment then\n",
        "\t\t\tadd {var = value} to assignment\n",
        "\t\t\tinferences = INFERENCE(csp, var, assignment)\n",
        "\t\t\tif inferences != failure then\n",
        "\t\t\t\tadd inferences to csp\n",
        "\t\t\t\tresult = BACKTRACK(csp, assignment)\n",
        "\t\t\t\tif result != failure then return result\n",
        "\t\t\t\tremove inferences from csp\n",
        "\t\t\tremove {var = value} from assignment\n",
        "\treturn failure\n",
        "```\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "- min-conflicts: local search, select value which results in minimum number of conflicts with other variables\n",
        "- runtime of min-conflicts is independent of problem size\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "## module 6: constraint satisfaction problems\n",
        "\n",
        "### intro to CSPs\n",
        "\n",
        "assumptions about world: single agent, deterministic actions, fully observed state, discrete state space\n",
        "\n",
        "planning: sequence of actions\n",
        "\n",
        "- path to the goal is the important thing. paths have various costs, depths. heuristics give problem-specific guidance.\n",
        "\n",
        "*alternative - identify a good assignment to variables to reach goal state.*\n",
        "\n",
        "- goal itself is important, not the path. all paths have the same depth.\n",
        "- CSPs are specialized for identification problems.\n",
        "\n",
        "**constraint satisfaction problems**\n",
        "\n",
        "- represent *constraints* that solutions must satisfy in a uniform declarative language\n",
        "- general purpose search algorithms with no changes from problem to problem\n",
        "\n",
        "formal definition\n",
        "\n",
        "A CSP consists of:\n",
        "\n",
        "- finite set of variables $X_1, X_2,...,X_n$ (label for each variable)\n",
        "- nonempty *domain* of possible values for each variable $D_1, D_2,..., D_n$\n",
        "- finite set of constraints $C_1, C_2,...,C_m$\n",
        "    - each constraint $C_i$ limits the values that variables can take. a *state* is defined as an *assignment* of values to some or all variables\n",
        "- *consistent* assignment does not violate constraints\n",
        "\n",
        "e.g. Sudoku\n",
        "\n",
        "- constraints: all numbers in each row and column must be distinct. all 9 numbers in box must be different.\n",
        "- assignment is *complete* when every variable is assigned a value. *solution* is a complete, consistent assignment\n",
        "\n",
        "### deeper in CSP\n",
        "\n",
        "e.g. map-coloring\n",
        "\n",
        "- variables: WA, NT, Q, NSW, V, SA, T (states of australia)\n",
        "- domains: $D_i$ = {red, green, blue}\n",
        "- constraints: adj regions must have diff colors\n",
        "\n",
        "solutions: complete and consistent assignments\n",
        "\n",
        "benefits of CSP\n",
        "\n",
        "- clean specification of many problems, generic goal, successor function and heuristics\n",
        "- CSP \"knows\" which variables are violating a constraint, cut off search that doesn't lead to goal state.\n",
        "- automatically prune all branches that violate constraints. eliminate possibilities as fast as possible.\n",
        "\n",
        "CSP representations\n",
        "\n",
        "- *constraint graph -* nodes are variables, arcs are (binary) constraints\n",
        "    - simplifies search\n",
        "    - this CSP is a *binary* CSP since each constraint relates 2 variables\n",
        "- *standard representation pattern -* variables with values\n",
        "\n",
        "**discrete variables**\n",
        "\n",
        "- finite domains: $n$ variables, domain size of $d$ (d possible values) → $O(d^n)$ complete assignments\n",
        "- infinite domains: integers, strings, etc... need a constraint language\n",
        "\n",
        "**continuous variables**\n",
        "\n",
        "- linear constraints solvable in polynomial time in linear programming\n",
        "\n",
        "**varieties of constraints**\n",
        "\n",
        "- unary = single variable. binary = pairs of variables. higher-order = ≥3 variables.\n",
        "- preference (soft constraints, e.g. red > green) represented using a cost\n",
        "\n",
        "### CSP as a search problem\n",
        "\n",
        "**csp can easily be expressed as a search problem**\n",
        "\n",
        "- initial state: empty assignment {}\n",
        "- successor function: assign value to any unassigned variables\n",
        "- goal test: is the current assignment complete?\n",
        "- path cost: constant cost for every step\n",
        "\n",
        "solution is always found at depth $n$ for $n$ variables\n",
        "\n",
        "- each $n$ variable has to take on 1 value\n",
        "\n",
        "**search and branching factor:**\n",
        "\n",
        "- $n$ variables of domain size $d$\n",
        "- branching factor at root = $n * d$. next level is $(n - 1) * d$\n",
        "- tree has $n! * d^n$ leaves\n",
        "- variable assignments are commutative, order of application doesn't affect outcome.\n",
        "\n",
        "**search and *backtracking***\n",
        "\n",
        "- depth-first search for CSPs with single-variable assignment is called *backtracking* search\n",
        "- DFS that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign\n",
        "- basic *uninformed* algorithm for CSPs\n",
        "\n",
        "### heuristics to improve backtracking efficiency\n",
        "\n",
        "*general-purpose* methods & *general-purpose* heuristics can give huge gains in speed (on avg)\n",
        "\n",
        "**heuristics:**\n",
        "\n",
        "1. q: which variable to assign next?\n",
        "    1. most constrained variable (variable with *fewest legal values)*\n",
        "        - recognize failure as fast as possible. label nodes with number of legal values available.\n",
        "        - *minimum remaining values (MRV)* heuristic\n",
        "    2. (if ties) most constraining variable\n",
        "        - choose variable with fewest legal values, the one with the most constraints on remaining variable (e.g. greatest # of neighbors in coloring ex)\n",
        "2. q: in what order should variable's values be tried?\n",
        "    1. least constraining value? one that rules out the *fewest* values in the remaining variables.\n",
        "3. q: can we detect inevitable failure early?\n",
        "    1. **forward checking**\n",
        "        - idea: keep track of *remaining* legal variables for *unassigned* variables\n",
        "        - terminate search when any unassigned variable has no remaining legal values\n",
        "        - new data structure that keeps track of legal variables for unassigned variables\n",
        "        - propagates info from assigned to unassigned variables, but doesn't provide early detection for all failures → *constraint propagation* repeatedly enforces restraints\n",
        "\n",
        "### arc consistency\n",
        "\n",
        "idea 3: *inference* in CSPs\n",
        "\n",
        "**CSP solves combine search and inference**\n",
        "\n",
        "- search: assigning a value to a variable\n",
        "- constraint propagation (inference): eliminates possible values for a variable if the value violates local consistency.\n",
        "- *can do inference first or intertwine with search*\n",
        "\n",
        "**local consistency**\n",
        "\n",
        "- node consistency: satisfies unary constraints\n",
        "- arc consistency: satisfies binary constraints.\n",
        "\n",
        "$X_i$ is arc-consistent wrt $X_j$ if for every value $v$ in $D_i$, there is some value $w$ in $D_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$\n",
        "\n",
        "represented as a constraint graph: nodes are variables, edges are constraints. ⇒ convert to a directed graph.\n",
        "\n",
        "- given a pair of nodes $X_i$ and $X_j$, connected by a constraint edge, we represent this not by a single undirected edge, but as a pair of directed arcs (i, j) and (j, i).\n",
        "\n",
        "**arc consistency**\n",
        "\n",
        "- simplest form of propagation makes each arc **consistent**\n",
        "    - X → Y is consistent iff for every value x of X, there is some allowed y\n",
        "- if $X$ loses a value, recheck neighbors of $X$\n",
        "- given $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time worst case\n",
        "\n",
        "**e.g. Waltz Algorithm** (for computer vision)\n",
        "\n",
        "- every intersection could be interpreted as pointing inwards or outwards. treat each intersection as a variable and adj intersections impose constraints. solution is physically realizable 3D interpretations.\n",
        "\n",
        "**Waltz/Mackworth constraint propagation alg**\n",
        "\n",
        "1. assign every node in the constraint graph a set of all possible values\n",
        "2. repeat until there is no change in set of values associated with any node:\n",
        "    \n",
        "    ```python\n",
        "    for each node i:\n",
        "    \tfor each neighboring node j in the picture:\n",
        "    \t\tremove any value from i which is not arc consistent with j.\n",
        "    ```\n",
        "    \n",
        "\n",
        "**towards AC-3**\n",
        "\n",
        "1. at each iteration, we actually only need to examine nodes $X_i$ where at least one neighbor of $X_i$ has lost a value (ow no change)\n",
        "- maintain an arc of what we need to process. add back arcs to neighbors whenever a node had values removed.\n",
        "- worst cast analysis = $O(n^2d^3)$\n",
        "    - all nodes connected to every other nodes: $O(n^2)$\n",
        "    - with $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time\n",
        "    - each arc $(i, j)$ can only be inserted into the queue $d$ times\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 84,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "60f9798d-94fd-4b07-c03a-b44ac76f6419"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "constraint satisfaction problem consists of:\n",
              "\n",
              "1. X, set of variables $\\{X_1,...,X_n\\}$\n",
              "2. D, set of domains $\\{D_1,...,D_n\\}$. $D_i$ is the set of allowable values for variable $X_i$\n",
              "3. C, set of constraints on value combinations\n",
              "- CSPs assign values to variables. **consistent** **assignment doesn't violate any constraints. **complete** assignment - every variable has a value. **solution -** complete, consistent assignment.\n",
              "    - **partial assignment** - some unassigned variables. **partial solution** - consistent partial assignment.\n",
              "- **constraint graph** - nodes = variables, edge = two variables in a constraint.\n",
              "\n",
              "types of constraints:\n",
              "\n",
              "- **unary constraint** - restricts value to single variable (e.g. SA ≠ green)\n",
              "- **binary constraint** - relates two variables (eg. SA ≠ NSW)\n",
              "- **ternary constraint** - (e.g. X < Y < Z)\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "- constraint propagation: use constraints to reduce # of legal values for a variable\n",
              "- **local consistency** - enforce local consistency to eliminate inconsistent values\n",
              "\n",
              "**node consistency** - all values in domain satisfy unary constraints\n",
              "\n",
              "**arc consistency** - satisfy binary constraints\n",
              "\n",
              "- sometimes does nothing (e.g. australia map coloring problem - valid value for the other variable for each value of the domain)\n",
              "- **AC-3** enforces arc-consistency for every variable. maintains a queue of arcs.\n",
              "\n",
              "```jsx\n",
              "function AC-3(csp) returns false if an inconsistency if found, true otherwise\n",
              "\tqueue = queue of arcs, initialized to all arcs in csp\n",
              "\twhile queue isn't empty\n",
              "\t\t(x_i, x_j) = pop(queue)\n",
              "\t\tif REVISE(csp, x_i, x_j) then\n",
              "\t\t\tif size(D_i) = 0 then return false\n",
              "\t\t\tfor each x_k in x_i.neighbors - {x_j} do\n",
              "\t\t\t\tadd (x_k, x_i) to queue\n",
              "\treturn true\n",
              "\n",
              "function REVISE(csp, x_i, x_j) returns true iff we revise the domain of x_i\n",
              "\trevised = false\n",
              "\tfor each x in D_i do\n",
              "\t\tif no value y in D_j allows (x, y) to satisfy the constraint between X_i and X_j then\n",
              "\t\t\tdelete x from D_i\n",
              "\t\t\trevised = true\n",
              "\treturn revised\n",
              "```\n",
              "\n",
              "- complexity: with n variables, domain size of at most d, and c arcs, checking consistency of arcs is $O(d^2)$ so total run-time is $O(cd^3)$\n",
              "\n",
              "**path consistency** - triples of variables\n",
              "\n",
              "**k-consistency** - strongly consistent if also (k - 1)-consistent, (k - 2)-consistent, etc...\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "- CSPs are commutative since order of assigning actions does not matter.\n",
              "\n",
              "```jsx\n",
              "function BACKTRACKING-SEARCH(csp) returns a solution or failure\n",
              "\treturn BACKTRACK(csp, {})\n",
              "\n",
              "function BACKTRACK(csp, assignment) returns a solution or failure\n",
              "\tif assignment is complete then return assignment\n",
              "\tvar = SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n",
              "\tfor each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n",
              "\t\tif value is consistent with assignment then\n",
              "\t\t\tadd {var = value} to assignment\n",
              "\t\t\tinferences = INFERENCE(csp, var, assignment)\n",
              "\t\t\tif inferences != failure then\n",
              "\t\t\t\tadd inferences to csp\n",
              "\t\t\t\tresult = BACKTRACK(csp, assignment)\n",
              "\t\t\t\tif result != failure then return result\n",
              "\t\t\t\tremove inferences from csp\n",
              "\t\t\tremove {var = value} from assignment\n",
              "\treturn failure\n",
              "```\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "- min-conflicts: local search, select value which results in minimum number of conflicts with other variables\n",
              "- runtime of min-conflicts is independent of problem size\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "## module 6: constraint satisfaction problems\n",
              "\n",
              "### intro to CSPs\n",
              "\n",
              "assumptions about world: single agent, deterministic actions, fully observed state, discrete state space\n",
              "\n",
              "planning: sequence of actions\n",
              "\n",
              "- path to the goal is the important thing. paths have various costs, depths. heuristics give problem-specific guidance.\n",
              "\n",
              "*alternative - identify a good assignment to variables to reach goal state.*\n",
              "\n",
              "- goal itself is important, not the path. all paths have the same depth.\n",
              "- CSPs are specialized for identification problems.\n",
              "\n",
              "**constraint satisfaction problems**\n",
              "\n",
              "- represent *constraints* that solutions must satisfy in a uniform declarative language\n",
              "- general purpose search algorithms with no changes from problem to problem\n",
              "\n",
              "formal definition\n",
              "\n",
              "A CSP consists of:\n",
              "\n",
              "- finite set of variables $X_1, X_2,...,X_n$ (label for each variable)\n",
              "- nonempty *domain* of possible values for each variable $D_1, D_2,..., D_n$\n",
              "- finite set of constraints $C_1, C_2,...,C_m$\n",
              "    - each constraint $C_i$ limits the values that variables can take. a *state* is defined as an *assignment* of values to some or all variables\n",
              "- *consistent* assignment does not violate constraints\n",
              "\n",
              "e.g. Sudoku\n",
              "\n",
              "- constraints: all numbers in each row and column must be distinct. all 9 numbers in box must be different.\n",
              "- assignment is *complete* when every variable is assigned a value. *solution* is a complete, consistent assignment\n",
              "\n",
              "### deeper in CSP\n",
              "\n",
              "e.g. map-coloring\n",
              "\n",
              "- variables: WA, NT, Q, NSW, V, SA, T (states of australia)\n",
              "- domains: $D_i$ = {red, green, blue}\n",
              "- constraints: adj regions must have diff colors\n",
              "\n",
              "solutions: complete and consistent assignments\n",
              "\n",
              "benefits of CSP\n",
              "\n",
              "- clean specification of many problems, generic goal, successor function and heuristics\n",
              "- CSP \"knows\" which variables are violating a constraint, cut off search that doesn't lead to goal state.\n",
              "- automatically prune all branches that violate constraints. eliminate possibilities as fast as possible.\n",
              "\n",
              "CSP representations\n",
              "\n",
              "- *constraint graph -* nodes are variables, arcs are (binary) constraints\n",
              "    - simplifies search\n",
              "    - this CSP is a *binary* CSP since each constraint relates 2 variables\n",
              "- *standard representation pattern -* variables with values\n",
              "\n",
              "**discrete variables**\n",
              "\n",
              "- finite domains: $n$ variables, domain size of $d$ (d possible values) → $O(d^n)$ complete assignments\n",
              "- infinite domains: integers, strings, etc... need a constraint language\n",
              "\n",
              "**continuous variables**\n",
              "\n",
              "- linear constraints solvable in polynomial time in linear programming\n",
              "\n",
              "**varieties of constraints**\n",
              "\n",
              "- unary = single variable. binary = pairs of variables. higher-order = ≥3 variables.\n",
              "- preference (soft constraints, e.g. red > green) represented using a cost\n",
              "\n",
              "### CSP as a search problem\n",
              "\n",
              "**csp can easily be expressed as a search problem**\n",
              "\n",
              "- initial state: empty assignment {}\n",
              "- successor function: assign value to any unassigned variables\n",
              "- goal test: is the current assignment complete?\n",
              "- path cost: constant cost for every step\n",
              "\n",
              "solution is always found at depth $n$ for $n$ variables\n",
              "\n",
              "- each $n$ variable has to take on 1 value\n",
              "\n",
              "**search and branching factor:**\n",
              "\n",
              "- $n$ variables of domain size $d$\n",
              "- branching factor at root = $n * d$. next level is $(n - 1) * d$\n",
              "- tree has $n! * d^n$ leaves\n",
              "- variable assignments are commutative, order of application doesn't affect outcome.\n",
              "\n",
              "**search and *backtracking***\n",
              "\n",
              "- depth-first search for CSPs with single-variable assignment is called *backtracking* search\n",
              "- DFS that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign\n",
              "- basic *uninformed* algorithm for CSPs\n",
              "\n",
              "### heuristics to improve backtracking efficiency\n",
              "\n",
              "*general-purpose* methods & *general-purpose* heuristics can give huge gains in speed (on avg)\n",
              "\n",
              "**heuristics:**\n",
              "\n",
              "1. q: which variable to assign next?\n",
              "    1. most constrained variable (variable with *fewest legal values)*\n",
              "        - recognize failure as fast as possible. label nodes with number of legal values available.\n",
              "        - *minimum remaining values (MRV)* heuristic\n",
              "    2. (if ties) most constraining variable\n",
              "        - choose variable with fewest legal values, the one with the most constraints on remaining variable (e.g. greatest # of neighbors in coloring ex)\n",
              "2. q: in what order should variable's values be tried?\n",
              "    1. least constraining value? one that rules out the *fewest* values in the remaining variables.\n",
              "3. q: can we detect inevitable failure early?\n",
              "    1. **forward checking**\n",
              "        - idea: keep track of *remaining* legal variables for *unassigned* variables\n",
              "        - terminate search when any unassigned variable has no remaining legal values\n",
              "        - new data structure that keeps track of legal variables for unassigned variables\n",
              "        - propagates info from assigned to unassigned variables, but doesn't provide early detection for all failures → *constraint propagation* repeatedly enforces restraints\n",
              "\n",
              "### arc consistency\n",
              "\n",
              "idea 3: *inference* in CSPs\n",
              "\n",
              "**CSP solves combine search and inference**\n",
              "\n",
              "- search: assigning a value to a variable\n",
              "- constraint propagation (inference): eliminates possible values for a variable if the value violates local consistency.\n",
              "- *can do inference first or intertwine with search*\n",
              "\n",
              "**local consistency**\n",
              "\n",
              "- node consistency: satisfies unary constraints\n",
              "- arc consistency: satisfies binary constraints.\n",
              "\n",
              "$X_i$ is arc-consistent wrt $X_j$ if for every value $v$ in $D_i$, there is some value $w$ in $D_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$\n",
              "\n",
              "represented as a constraint graph: nodes are variables, edges are constraints. ⇒ convert to a directed graph.\n",
              "\n",
              "- given a pair of nodes $X_i$ and $X_j$, connected by a constraint edge, we represent this not by a single undirected edge, but as a pair of directed arcs (i, j) and (j, i).\n",
              "\n",
              "**arc consistency**\n",
              "\n",
              "- simplest form of propagation makes each arc **consistent**\n",
              "    - X → Y is consistent iff for every value x of X, there is some allowed y\n",
              "- if $X$ loses a value, recheck neighbors of $X$\n",
              "- given $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time worst case\n",
              "\n",
              "**e.g. Waltz Algorithm** (for computer vision)\n",
              "\n",
              "- every intersection could be interpreted as pointing inwards or outwards. treat each intersection as a variable and adj intersections impose constraints. solution is physically realizable 3D interpretations.\n",
              "\n",
              "**Waltz/Mackworth constraint propagation alg**\n",
              "\n",
              "1. assign every node in the constraint graph a set of all possible values\n",
              "2. repeat until there is no change in set of values associated with any node:\n",
              "    \n",
              "    ```python\n",
              "    for each node i:\n",
              "    \tfor each neighboring node j in the picture:\n",
              "    \t\tremove any value from i which is not arc consistent with j.\n",
              "    ```\n",
              "    \n",
              "\n",
              "**towards AC-3**\n",
              "\n",
              "1. at each iteration, we actually only need to examine nodes $X_i$ where at least one neighbor of $X_i$ has lost a value (ow no change)\n",
              "- maintain an arc of what we need to process. add back arcs to neighbors whenever a node had values removed.\n",
              "- worst cast analysis = $O(n^2d^3)$\n",
              "    - all nodes connected to every other nodes: $O(n^2)$\n",
              "    - with $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time\n",
              "    - each arc $(i, j)$ can only be inserted into the queue $d$ times\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 85,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "- knowledge base: set of sentences. sentence is expressed in a knowledge representation language.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "- performance measure: +1000 for climbing out of cave, -1000 for falling into pit, -1 for each action taken, -10 for using arrow.\n",
        "- environment: 4x4 grid of rooms. random location for gold and wumpus.\n",
        "- actuators: move forward, turn left, turn right.\n",
        "- sensors: perceives a *stench* in adjacent squares to wumpus. perceives *breeze* adjacent to pit. *glitter* adjacent to gold. *bump* if it hits wall. *scream* when killed xd\n",
        "- deterministic, discrete, static, single-agent, sequential, partially observable\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "- defines the *semantics* or meaning of sentences.\n",
        "- $M(\\alpha)$ = set of all models of $\\alpha$ where $\\alpha$ is true\n",
        "- entailment ⇒ a sentence that follows logically from another sentence, a |= b\n",
        "    - a |= b iff in every model where a is true, b is true\n",
        "    \n",
        "    $$a |= b \\text{ iff } M(a) \\subseteq M(b)$$\n",
        "    \n",
        "    - if in every model in which KB is true, a is true, then KB |= a\n",
        "- completeness = can derive any entailed sentence\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "- atomic sentences: single proposition symbol\n",
        "- proposition symbol: single variable\n",
        "- complex sentences: combination of simple sentences with parenthesis and logical connectives\n",
        "- logical connectives: not, and, or, implies, biconditional\n",
        "\n",
        "```jsx\n",
        "function TT-ENTAILS?(KB, a) returns true or false\n",
        "\tinputs: KB (knowledge base), a (sentence in propositional logic)\n",
        "\tsymbols = list of proposition symbols in KB and a\n",
        "\treturn TT-CHECK-ALL(KB, a, symbols, {})\n",
        "\n",
        "function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n",
        "\tif symbols is empty then\n",
        "\t\tif PL-TRUE(KB, model) then return PL-TRUE(a, model)\n",
        "\t\telse return true\n",
        "\telse\n",
        "\t\tP = first(symbols)\n",
        "\t\trest = rest(symbols)\n",
        "\t\treturn (TT-CHECK-ALL(KB, a, rest, model (union) {P = true}) \n",
        "\t\t\t\t\t&& TT-CHECK-ALL(KB, a, rest, model (union) {P = false})\n",
        "```\n",
        "\n",
        "- $2^n$ models for $n$ symbols. $O(2^n)$ worst-case time complexity, space complexity = $O(n)$.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "- a and b are logically equivalent iff a |= b and b |= a\n",
        "- **valid** if true in *all* models, always true (e.g. a || -a)\n",
        "- **satisfiability** if able to be satisfied by some model\n",
        "    - a is valid iff -a is unsatisfiable. a is satisfiable iff -a is not valid.\n",
        "- **modus ponens**: a ⇒ b, a / b. whenever any sentence of a ⇒ b and a are given, sentence b can be inferred.\n",
        "\n",
        "**conjunctive normal form**\n",
        "\n",
        "1. eliminate ↔ . a ↔ b gets replaced with (a ⇒ b) && (b ⇒ a)\n",
        "2. eliminate ⇒, a ⇒ b gets replaced with -a || b\n",
        "3. move negations inwards.\n",
        "    \n",
        "    -(-a) = a\n",
        "    \n",
        "    -(a && b) = -a || -b\n",
        "    \n",
        "    -(a || b) = -a && -b\n",
        "    \n",
        "4. apply distributivity to avoid nested && and ||\n",
        "    \n",
        "    a && (b || c) = (a && b) || (a && c)\n",
        "    \n",
        "    a || (b && c) = (a || b) && (a || c)\n",
        "    \n",
        "\n",
        "**definite clause** - disjunction of literals where exactly one is positive.\n",
        "\n",
        "**horn clauses -** disjunction of literals where at most one is positive (includes all definite clauses)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "### knowledge-based agents 1\n",
        "\n",
        "- **knowledge-based agents** use a process of **reasoning** over an internal representation of knowledge to decide what action to take\n",
        "    - problem-solving agents perform search over states. very limited and atomic, very difficult to add sophisticated questions \"take me to the nearest habitable planet where i can store my perishable cargo\".\n",
        "- knowledge base (KB) contains a set of sentences written in a *knowledge representation language*, contains some facts about the world\n",
        "    - e.g. *Hoth is a planet* ⇒ planet(hoth); *Hoth is far from its sun ⇒* far_from(hoth, sol)\n",
        "        - natural language sentence ⇒ knowledge representation language sentence\n",
        "1. axioms - given sentence\n",
        "2. derived sentences - new sentence derived from others sentences\n",
        "- KB has some initial background information and an agent adds info through observations\n",
        "\n",
        "### hunt the wampas\n",
        "\n",
        "**wampa world**\n",
        "\n",
        "- r2d2 (our knowledge-based agent) explores a cave consisting of rooms connected by passages. there is a wampa which eats r2d2s in the cave. some rooms have traps. goal is: collect luke, exit world, don't get eaten.\n",
        "- environment: a 4x4 grid of rooms.\n",
        "- performance measure: +1000 points for rescuing Luke, -1000 for falling into a pit, -1 for each action taken, -10 for using up blaster fire\n",
        "- actuators: move forward, turn; grab to pick up luke, shoot, climb\n",
        "- sensors: limit sensors to current square, perceives bump when it walks into a wall\n",
        "- deterministic, discrete, static, single-agent; sequential; partially observable\n",
        "\n",
        "### knowledge-based agents 2\n",
        "\n",
        "**logic**: serve as general class of represetnations for knowledge-based agents\n",
        "\n",
        "- KB is sentences in representation language, has a syntax that specifies well-formed sentences.\n",
        "- defines sentence semantics and meaning\n",
        "\n",
        "**possible worlds and models**\n",
        "\n",
        "- models have a fixed set of *truth values*\n",
        "- if sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$ of $m$ is a model of $\\alpha$\n",
        "\n",
        "**logical entailment**\n",
        "\n",
        "- entailment relation between sentences, a sentence logically follows another one.\n",
        "\n",
        "$$a \\models b \\text{ iff } M(a) \\subseteq M(b) $$\n",
        "\n",
        "knowledge base is a set of sentences. KB is false in models that contradict what the agent knows.\n",
        "\n",
        "### propositional logic\n",
        "\n",
        "**atomic sentences** represented with a single **propositional symbol**\n",
        "\n",
        "- propositional symbol stands for a statement that can be true or false\n",
        "- W_{1, 3} = there is a Wampa at location [1, 3]. this can be true or false.\n",
        "\n",
        "complex sentences use logical connectives to combine simpler sentences\n",
        "\n",
        "biconditional: P ↔ Q\n",
        "\n",
        "- T, T ⇒ T\n",
        "- T, F ⇒ F\n",
        "- F, T ⇒ F\n",
        "- F, F ⇒ T\n",
        "\n",
        "### knowledge bases\n",
        "\n",
        "### theorem proving 1\n",
        "\n",
        "rewrite sentences using logical equivalence\n",
        "\n",
        "commutativity of and and or: **a && b = b && a, a || b = b || a**\n",
        "\n",
        "associativity: **(a && b) && c = (a && (b && c))**\n",
        "\n",
        "contrapositive: **a ⇒ b = -a ⇒ -b**\n",
        "\n",
        "implication elimination: **a ⇒ b = -a || b**\n",
        "\n",
        "biconditional elimination: **a ↔ b = (a ⇒ b) && (b ⇒ a)**\n",
        "\n",
        "de morgan: **-(a && b) = -a || -b**\n",
        "\n",
        "de morgan: **-(a || b) =  (-a && -b)**\n",
        "\n",
        "distributivity of &&: **(a && b) || c = (a || c) && (b || c)**\n",
        "\n",
        "distributivity of ||: **(a || b) && c = (a && c) || (b && c)**\n",
        "\n",
        "**monotonicity:** if $KB \\models \\alpha$ then $KB \\land \\beta \\models \\alpha$.\n",
        "\n",
        "### theorem proving 2\n",
        "\n",
        "**conjunctive normal form**\n",
        "\n",
        "1. eliminate ↔ by replacing a ↔ b with (a ⇒ b) && (b ⇒ a)\n",
        "2. eliminate ⇒ by replacing a ⇒ b with -a || b\n",
        "3. move - inwards (eliminate double negation and apply de morgan's rules)\n",
        "4. sentence contains nested || and && operators applied to literals. apply distributivity law to distribut || over && wherever possible.\n",
        "\n",
        "- empty clause arises when we have two contradictory unit clauses, like P && -P\n",
        "\n",
        "**definite clause**: disjunction of literals where exactly one is positive\n",
        "\n",
        "**horn clause**: disjunction of literals where at least one is positive\n",
        "\n",
        "- includes definite clauses\n",
        "- clauses with no positive literals\n",
        "\n",
        "forward chaining algorithm\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 86,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "8080f48d-9dc1-4a1a-c6b3-e04a149a4b11"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "- knowledge base: set of sentences. sentence is expressed in a knowledge representation language.\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "\n",
              "- performance measure: +1000 for climbing out of cave, -1000 for falling into pit, -1 for each action taken, -10 for using arrow.\n",
              "- environment: 4x4 grid of rooms. random location for gold and wumpus.\n",
              "- actuators: move forward, turn left, turn right.\n",
              "- sensors: perceives a *stench* in adjacent squares to wumpus. perceives *breeze* adjacent to pit. *glitter* adjacent to gold. *bump* if it hits wall. *scream* when killed xd\n",
              "- deterministic, discrete, static, single-agent, sequential, partially observable\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "- defines the *semantics* or meaning of sentences.\n",
              "- $M(\u0007lpha)$ = set of all models of $\u0007lpha$ where $\u0007lpha$ is true\n",
              "- entailment ⇒ a sentence that follows logically from another sentence, a |= b\n",
              "    - a |= b iff in every model where a is true, b is true\n",
              "    \n",
              "    $$a |= b \text{ iff } M(a) \\subseteq M(b)$$\n",
              "    \n",
              "    - if in every model in which KB is true, a is true, then KB |= a\n",
              "- completeness = can derive any entailed sentence\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "- atomic sentences: single proposition symbol\n",
              "- proposition symbol: single variable\n",
              "- complex sentences: combination of simple sentences with parenthesis and logical connectives\n",
              "- logical connectives: not, and, or, implies, biconditional\n",
              "\n",
              "```jsx\n",
              "function TT-ENTAILS?(KB, a) returns true or false\n",
              "\tinputs: KB (knowledge base), a (sentence in propositional logic)\n",
              "\tsymbols = list of proposition symbols in KB and a\n",
              "\treturn TT-CHECK-ALL(KB, a, symbols, {})\n",
              "\n",
              "function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n",
              "\tif symbols is empty then\n",
              "\t\tif PL-TRUE(KB, model) then return PL-TRUE(a, model)\n",
              "\t\telse return true\n",
              "\telse\n",
              "\t\tP = first(symbols)\n",
              "\t\trest = rest(symbols)\n",
              "\t\treturn (TT-CHECK-ALL(KB, a, rest, model (union) {P = true}) \n",
              "\t\t\t\t\t&& TT-CHECK-ALL(KB, a, rest, model (union) {P = false})\n",
              "```\n",
              "\n",
              "- $2^n$ models for $n$ symbols. $O(2^n)$ worst-case time complexity, space complexity = $O(n)$.\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "- a and b are logically equivalent iff a |= b and b |= a\n",
              "- **valid** if true in *all* models, always true (e.g. a || -a)\n",
              "- **satisfiability** if able to be satisfied by some model\n",
              "    - a is valid iff -a is unsatisfiable. a is satisfiable iff -a is not valid.\n",
              "- **modus ponens**: a ⇒ b, a / b. whenever any sentence of a ⇒ b and a are given, sentence b can be inferred.\n",
              "\n",
              "**conjunctive normal form**\n",
              "\n",
              "1. eliminate ↔ . a ↔ b gets replaced with (a ⇒ b) && (b ⇒ a)\n",
              "2. eliminate ⇒, a ⇒ b gets replaced with -a || b\n",
              "3. move negations inwards.\n",
              "    \n",
              "    -(-a) = a\n",
              "    \n",
              "    -(a && b) = -a || -b\n",
              "    \n",
              "    -(a || b) = -a && -b\n",
              "    \n",
              "4. apply distributivity to avoid nested && and ||\n",
              "    \n",
              "    a && (b || c) = (a && b) || (a && c)\n",
              "    \n",
              "    a || (b && c) = (a || b) && (a || c)\n",
              "    \n",
              "\n",
              "**definite clause** - disjunction of literals where exactly one is positive.\n",
              "\n",
              "**horn clauses -** disjunction of literals where at most one is positive (includes all definite clauses)\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "### knowledge-based agents 1\n",
              "\n",
              "- **knowledge-based agents** use a process of **reasoning** over an internal representation of knowledge to decide what action to take\n",
              "    - problem-solving agents perform search over states. very limited and atomic, very difficult to add sophisticated questions \"take me to the nearest habitable planet where i can store my perishable cargo\".\n",
              "- knowledge base (KB) contains a set of sentences written in a *knowledge representation language*, contains some facts about the world\n",
              "    - e.g. *Hoth is a planet* ⇒ planet(hoth); *Hoth is far from its sun ⇒* far_from(hoth, sol)\n",
              "        - natural language sentence ⇒ knowledge representation language sentence\n",
              "1. axioms - given sentence\n",
              "2. derived sentences - new sentence derived from others sentences\n",
              "- KB has some initial background information and an agent adds info through observations\n",
              "\n",
              "### hunt the wampas\n",
              "\n",
              "**wampa world**\n",
              "\n",
              "- r2d2 (our knowledge-based agent) explores a cave consisting of rooms connected by passages. there is a wampa which eats r2d2s in the cave. some rooms have traps. goal is: collect luke, exit world, don't get eaten.\n",
              "- environment: a 4x4 grid of rooms.\n",
              "- performance measure: +1000 points for rescuing Luke, -1000 for falling into a pit, -1 for each action taken, -10 for using up blaster fire\n",
              "- actuators: move forward, turn; grab to pick up luke, shoot, climb\n",
              "- sensors: limit sensors to current square, perceives bump when it walks into a wall\n",
              "- deterministic, discrete, static, single-agent; sequential; partially observable\n",
              "\n",
              "### knowledge-based agents 2\n",
              "\n",
              "**logic**: serve as general class of represetnations for knowledge-based agents\n",
              "\n",
              "- KB is sentences in representation language, has a syntax that specifies well-formed sentences.\n",
              "- defines sentence semantics and meaning\n",
              "\n",
              "**possible worlds and models**\n",
              "\n",
              "- models have a fixed set of *truth values*\n",
              "- if sentence $\u0007lpha$ is true in model $m$, then $m$ satisfies $\u0007lpha$ of $m$ is a model of $\u0007lpha$\n",
              "\n",
              "**logical entailment**\n",
              "\n",
              "- entailment relation between sentences, a sentence logically follows another one.\n",
              "\n",
              "$$a \\models b \text{ iff } M(a) \\subseteq M(b) $$\n",
              "\n",
              "knowledge base is a set of sentences. KB is false in models that contradict what the agent knows.\n",
              "\n",
              "### propositional logic\n",
              "\n",
              "**atomic sentences** represented with a single **propositional symbol**\n",
              "\n",
              "- propositional symbol stands for a statement that can be true or false\n",
              "- W_{1, 3} = there is a Wampa at location [1, 3]. this can be true or false.\n",
              "\n",
              "complex sentences use logical connectives to combine simpler sentences\n",
              "\n",
              "biconditional: P ↔ Q\n",
              "\n",
              "- T, T ⇒ T\n",
              "- T, F ⇒ F\n",
              "- F, T ⇒ F\n",
              "- F, F ⇒ T\n",
              "\n",
              "### knowledge bases\n",
              "\n",
              "### theorem proving 1\n",
              "\n",
              "rewrite sentences using logical equivalence\n",
              "\n",
              "commutativity of and and or: **a && b = b && a, a || b = b || a**\n",
              "\n",
              "associativity: **(a && b) && c = (a && (b && c))**\n",
              "\n",
              "contrapositive: **a ⇒ b = -a ⇒ -b**\n",
              "\n",
              "implication elimination: **a ⇒ b = -a || b**\n",
              "\n",
              "biconditional elimination: **a ↔ b = (a ⇒ b) && (b ⇒ a)**\n",
              "\n",
              "de morgan: **-(a && b) = -a || -b**\n",
              "\n",
              "de morgan: **-(a || b) =  (-a && -b)**\n",
              "\n",
              "distributivity of &&: **(a && b) || c = (a || c) && (b || c)**\n",
              "\n",
              "distributivity of ||: **(a || b) && c = (a && c) || (b && c)**\n",
              "\n",
              "**monotonicity:** if $KB \\models \u0007lpha$ then $KB \\land \beta \\models \u0007lpha$.\n",
              "\n",
              "### theorem proving 2\n",
              "\n",
              "**conjunctive normal form**\n",
              "\n",
              "1. eliminate ↔ by replacing a ↔ b with (a ⇒ b) && (b ⇒ a)\n",
              "2. eliminate ⇒ by replacing a ⇒ b with -a || b\n",
              "3. move - inwards (eliminate double negation and apply de morgan's rules)\n",
              "4. sentence contains nested || and && operators applied to literals. apply distributivity law to distribut || over && wherever possible.\n",
              "\n",
              "- empty clause arises when we have two contradictory unit clauses, like P && -P\n",
              "\n",
              "**definite clause**: disjunction of literals where exactly one is positive\n",
              "\n",
              "**horn clause**: disjunction of literals where at least one is positive\n",
              "\n",
              "- includes definite clauses\n",
              "- clauses with no positive literals\n",
              "\n",
              "forward chaining algorithm\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 87,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "6886d707-06e1-4deb-b9ca-e68a0c39831a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "- **turing test** - human asks a series of questions to determine if subject is a human or computer.\n",
              "\n",
              "\"laws of thought\" approach: *logic* as an irrefutable reasoning process.\n",
              "\n",
              "\"rational agent\" approach\n",
              "\n",
              "- **agent** - a subject that acts. **rational agent** - acts to achieve the best (expected) outcome.\n",
              "    - advantages over other approaches: (1) greater generality in approaches to achieve rationality. (2) mathematically defined, easy to measure & define.\n",
              "\n",
              "**value alignment problem** - objectives of machine should be aligned with the human.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "- (John Searle) **weak AI -** machines *act* like they are intelligent. **strong AI** - machines *are* consciously thinking.\n",
              "- Godel's incompleteness theorem\n",
              "    \n",
              "    $G(F)$ is a sentence of $F$, but cannot be proved within $F$\n",
              "    \n",
              "    If $F$ is consistent, then $G(F)$ is true.\n",
              "    \n",
              "- Roger Penrose: *I cannot consistently assert that this sentence is true.*\n",
              "    - if true ⇒ contradiction ⇒ therefore must be true\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "- an **agent** perceives the **environment** through sensors and acts through **actuators**\n",
              "- **percept** - what an agent is perceiving. **percept sequence** - history of everything the agent has perceived.\n",
              "- **agent function** - maps a percept sequence to an action, describes an agent's behavior. abstract mathematical description.\n",
              "- **agent program** - concrete implementation of the agent function (agent program ≠ agent function)\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "- **rational agent** is an agent that does *the right thing*, as defined by **consequentialism**: evaluating behavior by its consequences.\n",
              "- a **performance measure** evaluates any given sequence of environment states.\n",
              "    - better to design measures based on what one wants to be achieved, not how the agent should behave\n",
              "\n",
              "rationality depends on:\n",
              "\n",
              "1. performance measure, defines success\n",
              "2. agent's prior knowledge of environment\n",
              "3. performable actions\n",
              "4. agent's percept sequence\n",
              "- **rational agent defn** - for each possible percept sequence, a rational agent should choose the action which maximizes the performance measure, given the percept sequence and prior knowledge of the agent.\n",
              "- **omniscience** - when the agent knows the *actual* outcome of its actions. impossible in reality. rationality ≠ perfection, but instead maximizes *expected* performance.\n",
              "- **autonomy** - how much an agent relies on prior knowledge from the designer vs own percepts and learning. it's an evolutionary process :)\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "- **task environments** - \"problems\"\n",
              "    - **PEAS** (Performance, Environment, Actuators, Sensors)\n",
              "    - e.g. taxi driver - P: safe, fast, legal; E: roads, police, pedestrians; A: steering, acelerator, brake; S: cameras, radar, speedometer\n",
              "\n",
              "**fully observable v. partially observable**\n",
              "\n",
              "- fully observable - sensors have access to complete relevant (in terms of performance measure) environment state at every point.\n",
              "- partially observable - noisy / inaccurate sensors (e.g. self-driving cars)\n",
              "\n",
              "**single-agent v. multiagent**\n",
              "\n",
              "- multi-agent - another agent's behavior is maximizing a performance value which depends on A's behavior (e.g. chess)\n",
              "    - chess is a *competitive* multiagent environment\n",
              "    - taxi-driving is a partially *cooperative* multiagent environment\n",
              "- single-agent - one agent (e.g. crossword puzzle)\n",
              "\n",
              "**deterministic v. nondeterministic**\n",
              "\n",
              "- deterministic - next state is determined by current state and action\n",
              "- non-deterministic - uncertainty, most real situations (also known as stochastic if w/ probabilities)\n",
              "\n",
              "**episodic v. sequential**\n",
              "\n",
              "- episodic - experience divided into atomic episodes where agent receives a percept and does an action. actions don't depend on previous actions.\n",
              "- sequential - current decision affects future decisions (e.g. chess, driving)\n",
              "\n",
              "**static v. dynamic**\n",
              "\n",
              "- dynamic - environment changes while agent is deciding action\n",
              "- semidynamic - environment might not change but agent's score does (e.g. chess with a clock)\n",
              "\n",
              "**discrete v. continuous:** taxi-driving is continuous. chess is discrete.\n",
              "\n",
              "**known v. unknown**\n",
              "\n",
              "- not strictly an environment property. more an agent property.\n",
              "- known - given outcomes for all actions. can have *known* partially observable games, like solitaire.\n",
              "\n",
              "*hardest case = partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown* (e.g. self-driving)\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "- *agent = architecture + program.* AI designs an agent program which implements the agent function.\n",
              "- agent programs take current percept from sensors as input and return an action to actuators.\n",
              "    - a simple lookup table is exponential in size.\n",
              "\n",
              "**simple reflex agents**\n",
              "\n",
              "- selects actions based on *current* percept. ignores rest of percept history.\n",
              "- condition-action rule - percept sensor input establishes a condition which triggers some action.\n",
              "- can create infinite loops (e.g. on clean, the roomba turns left forever :/, can prevent this with randomization)\n",
              "\n",
              "**model-based reflex agents**\n",
              "\n",
              "- to handle partial observability: agent maintains some kind of internal state to represent unobserved aspects (e.g. keeping track of where other cars are if they can't be seen)\n",
              "    - requires info on how the world changes over time (effects of agent's actions and changes irrespective of agent)\n",
              "- \"how the world work\" ⇒ **transition model**\n",
              "- **sensor model** - how world's state is reflected by percepts (e.g. what does a car braking in front look like in the camera?)\n",
              "- transition model + sensor model → model-based agent\n",
              "\n",
              "**goal-based agents**\n",
              "\n",
              "- decisions depend on the goal.\n",
              "- simple when goal satisfaction results from a single actions. search and planning required for long sequences of actions.\n",
              "- involves future considerations...less efficient but more flexible.\n",
              "\n",
              "**utility-based agents**\n",
              "\n",
              "- goals are a binary distinction - success or failures. a better performance measure compares *utility.*\n",
              "- **utility function** - internalization of performance measure.\n",
              "    - determining appropriate tradeoffs when there are conflicting goals (e.g. speed v. safety)\n",
              "    - several goals with uncertainty - utility can weigh the likelihood against importance\n",
              "- rational utility-based agent chooses the action which maximizes the **expected utility** of the action outcomes\n",
              "\n",
              "**learning agents**\n",
              "\n",
              "- allows agents to be in unknown environments and gain competency\n",
              "- learning element is responsible for making improvements (feedback from *critic*). performance element selects external actions (percepts, actions).\n",
              "- **problem generator** - suggests improving actions. encourages agent to explore a lil.\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "### ai & philosophy\n",
              "\n",
              "- **descartes**: *cogito ergo sum* (i think therefore i am)\n",
              "    - *dualism* - mind is incorporeal or spiritual, separate from body\n",
              "- **alan turing**: the imitation game, is it possible for a machine to imitate a human so plausibly that a human can't tell it is a machine?\n",
              "- **john searle**: the chinese room\n",
              "    - turing problem can be solved through simple symbol manipulation, not an indicator of true intelligence but just syntax rules\n",
              "    - appearance of conversation ≠ intelligence\n",
              "    - strong vs. weak AI: weak AI gives appearance of intelligence. must be something foundational about biological brains which allow for strong AI.\n",
              "- ELIZA: early NLP therapist.\n",
              "- **daniel dennett:** brain in a vat\n",
              "    - need to diffuse a bomb without radiation - DoD removes brain from body and sends it in a vat. \"Where am I?\" is the brain me or the body?\n",
              "    - replaced all the neurons and information flow of the brain, is it conscious?\n",
              "\n",
              "### rational agents\n",
              "\n",
              "**acting rationally**\n",
              "\n",
              "**agent:** anything that *perceives* its environment through *sensors* and can *act* on its environment through *actuators*\n",
              "\n",
              "- *percept -* agent's perceptual inputs at any given instance\n",
              "- specified by an *agent function* $f: P \rightarrow a$, maps a sequence of percept vectors $P$ to an action $a$ from a set $A$\n",
              "- *agent program* is the concrete implementation to produce the function\n",
              "    - e.g. a giant table that maps every possible sequence of percepts to an action\n",
              "        - but this is exponential in length. need more sophisticated algs\n",
              "- agent = architecture + program\n",
              "- e.g. humans, robots, thermostats (perceives environment, adjusts boiler to inc temp), roombas\n",
              "\n",
              "**rational agent**: for each possible percept sequence $P$, a rational agent selects an action $a$ to maximize the expected value of its performance measure.\n",
              "\n",
              "- *consequentialism* - evaluate an agent's behavior by its consequences\n",
              "    - *Herbert Simon, A Behavioral Model of Rational Choice*\n",
              "- *performance measure* - objective criterion for success of an agent's behavior\n",
              "    - better to design performance measures according to **what you want to be achieved**, rather than how it should behave (+1 for each time the robot cleans a square vs. +1 for each clean square at time T, first might result in robot maximizing by cleaning one square over and over again)\n",
              "- computational limitations make *complete rationality* unachievable.\n",
              "\n",
              "### task environments\n",
              "\n",
              "**task environment -** problem specification for which the agent is a solution\n",
              "\n",
              "- PEAS specifies the task environment: Performance measure, Environment, Actuators, Sensors\n",
              "\n",
              "ex) automated taxi driver\n",
              "\n",
              "- performance measure: safe, fast, legal, comfortable, maximize profits\n",
              "- environment: roads, other traffic, pedestrians\n",
              "- actuators: steering, accelerator, brake, signal, horn\n",
              "- sensors: cameras, LIDAR, GPS, speedometer\n",
              "\n",
              "**fully observable:** task agent sensors can detect all relevant aspects (e.g. chess)\n",
              "\n",
              "**partially observable:** only have access to info perceived by sensors (e.g. self-driving car, pedestrians may be hidden, noisy/inaccurate sensors)\n",
              "\n",
              "**deterministic:** know with certainty the result of an action. resulting state is completely knowable based on current state.\n",
              "\n",
              "**nondeterministic:** outcome is uncertain. many possible resulting states. games of chance.\n",
              "\n",
              "- often also **stochastic** (probabilistic)\n",
              "\n",
              "**episodic**: choice of each action is not dependent on previous actions (e.g. robot picking out defective parts)\n",
              "\n",
              "**sequential:** action effects future sequence of actions (e.g. cars)\n",
              "\n",
              "**static:** state doesn't change until agent finishes deciding action (e.g. crossword)\n",
              "\n",
              "**dynamic:** environment is constantly changing (e.g. cars)\n",
              "\n",
              "- can be semi-dynamic if score changes (e.g. clock in chess)\n",
              "\n",
              "**discrete:** finite set of possible actions (board games)\n",
              "\n",
              "**continuous:** inifinite possible actions (oil temperature settings)\n",
              "\n",
              "**simple agent:** only one agent (crossword)\n",
              "\n",
              "**multi agent:** treat other agents as rational (chess)\n",
              "\n",
              "- when something's behavior can be best described as having its own performance measure, it should be its own agent\n",
              "\n",
              "hardest environment: continuous, partially observable, stochastic, multi-agent\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "### Homework 1 Answers\n",
              "\n",
              "Python is dynamically typed, meaning declared variables are untyped but objects \n",
              "created at runtime have typings. Essentially, this allows for redefining variables \n",
              "to different types without error.\n",
              "\n",
              "```\n",
              "a = \"string\"\n",
              "a = 5\n",
              "```\n",
              "\n",
              "Python is strongly typed, meaning object types are defined and cannot be coerced\n",
              "into other types. Changing the type of an object requires explicit casting.\n",
              "For example, a = 5 + \"string\" will throw an error because the types of the two\n",
              "are not the same.\n",
              "\n",
              "Dictionary keys cannot be lists since they are mutable. If we use a list as a key,\n",
              "but modify the list object, then the key inside the dictionary has changed.\n",
              "\n",
              "The solution would be to use tuples instead. If all the points are 2-dimensional,\n",
              "changing [0,0] to (0,0) converts the key to a tuple. Tuples have a fixed length,\n",
              "and are immutable.\n",
              "\n",
              "concatenate2 is better. In concatenate1, using += creates a new string in each\n",
              "iteration, and copies the old string over in addition to the new string every time.\n",
              "In concatenate2, using .join() doesn't create intermediate strings and only copies \n",
              "each string once.\n",
              "\n",
              "- immutable: tuples, strings\n",
              "- mutable: sets, dictionaries, lists\n",
              "\n",
              "---\n",
              "```\n",
              "mathematicians_list = [\"Babbage\", \"Einstein\" \"Leibniz\"]\n",
              "mathematicians_list[:][0] = \"Godel\"\n",
              "```\n",
              "creates a copy of the list and replaces name but original list remains the same.\n",
              "\n",
              "Which of the following pieces of code will generate an error? Select all that apply.\n",
              "{\"a\": 3, \"b\": 2, [1,2]: 2} -- all keys of dictionary must be same type\n",
              "first_two = set(); first_two.add(\"one\"); first_two.remove(\"two\") -- cannot remove nonexistent element from set\n",
              "{\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4} -- cannot add dictionaries\n",
              "a = '123'; a[1] = '1' -- cannot index into string\n",
              "b = (1, 2, 3); b[1] = 1 -- cannot mutate a tuple\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "- **problem-solving agent** - agent that plans ahead, considers an action sequence to get to the goal state. this process is **search**.\n",
              "- **informed** algorithms - agent knows how far it is from the goal.\n",
              "- **uninformed** - no estimate of distance to goal.\n",
              "- in a fully observable, deterministic, known environment, solution to any problem is a fixed sequence of actions.\n",
              "\n",
              "formal defn of a search problem:\n",
              "\n",
              "- state space\n",
              "- initial state\n",
              "- set of goal states\n",
              "- action space\n",
              "- transition model - describes what each action does\n",
              "- action cost function - numeric cost of applying an action in a state\n",
              "\n",
              "---\n",
              "\n",
              "- **optimal solution** - lowest path cost among all solutions\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "**standardized problem** - theorhetical, illustrates problem-solving methods and used as a benchmark\n",
              "\n",
              "- **grid world**: 2D array, agent moves left/right and diagonally. cells can contain objects which are picked up, pushed, etc...\n",
              "    - states: cells\n",
              "    - initial state\n",
              "    - actions: suck, move left, move right\n",
              "    - transition model: suck removes dirt from the cell, forward moves forward, backward, etc...\n",
              "    - goal state: all cells are clean\n",
              "    - action cost: each action costs 1\n",
              "- **sokoban puzzle**: push a number of boxes to storage locations, one box / cell\n",
              "- **sliding-tile puzzle**: variants include rush-hour puzzle, 8-puzzle (8 tiles in 9 cells)\n",
              "\n",
              "**real-world problem** - solutions are actually used.\n",
              "\n",
              "- **route-finding problem**: websites, GPS, airline travel-planning\n",
              "    - states: time and place, historical info (previous flight costs, etc...)\n",
              "    - init state: home airport\n",
              "    - actions: take any flight in any class seat, leaving after current time\n",
              "    - transition model: arrival state and time\n",
              "    - goal state: destination city\n",
              "    - action cost: monetary cost, wait time, flight time, etc...\n",
              "- **touring problems**: TSP (visit every city with cost < C)\n",
              "- **VLSI layout**: position millions of components and connections to minimize area, circuit delays, stray capacitance...\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "- **search alg** - search problem as input, solution or failure returned.\n",
              "    - **search tree** gets imposed over state-space graph. **nodes** are states in the state space, **edges** are actions. **root** = init state. each node has a unique path back to the root.\n",
              "- **frontier** separates the interior region (all states have been expanded) and exterior region (not yet reached). usually a queue.\n",
              "\n",
              "**best-first search**: expand the node with the minimum evaluation function, $f(n)$\n",
              "\n",
              "```python\n",
              "function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure\n",
              "\tnode = initial state, problem.INIT\n",
              "\tfrontier = priority queue, ordered by f, with node as an element\n",
              "\treached = lookup table, add node to this\n",
              "\twhile frontier is not empty do\n",
              "\t\tnode = pop(frontier)\n",
              "\t\tif node is goal state then return node\n",
              "\t\tfor every child in EXPAND(problem, node)\n",
              "\t\t\ts = child.STATE\n",
              "\t\t\tif s is not in reached or child.PATHCOST < reached[s].PATH_COST then\n",
              "\t\t\t\treached[s] = child\n",
              "\t\t\t\tadd child to frontier\n",
              "\treturn failure\n",
              "\n",
              "function EXPAND(problem, node) yields nodes\n",
              "\ts = node.STATE\n",
              "\tfor every action in problems.ACTIONS(s)\n",
              "\t\ts' = problem.RESULT(s, action)\n",
              "\t\tcost = node.PATH-COST + problem.ACTION-COST(s, action, s')\n",
              "\t\tyield NODE(STATE=s', PARENT=node, ACTION=acton, PATH-COST=cost)\n",
              "```\n",
              "\n",
              "- nodes have state, parent, action, path-cost\n",
              "- types of queues\n",
              "    - priority queue - pops node with minimum cost. used in best-first search.\n",
              "    - FIFO queue - first-in-first-out, breadth-first search\n",
              "    - LIFO queue - last-in-first-out, stack, depth-first search\n",
              "- a complete search tree is *infinite* since it allows repeated states and **redundant paths**\n",
              "- **graph search** checks for redundant paths. best-first search is a graph search alg since we check for *reached*\n",
              "\n",
              "**alg performance**\n",
              "\n",
              "- **complete** if it's guaranteed to find a soln when there is one and report failure if not.\n",
              "- **cost optimality**\n",
              "- **time complexity & space complexity**\n",
              "    - d (depth) - number of actions in an optimal soln\n",
              "    - m - max number of actions in any path\n",
              "    - b (branching factor) - number of successors of a node to consider\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "- uninformed - no information on how close a state is to the goal\n",
              "\n",
              "**breadth-first search**\n",
              "\n",
              "- useful when all actions with the same cost\n",
              "- complete even on infinite spaces\n",
              "- best-first search where evaluation function, f(n) is node's depth\n",
              "    - use FIFO queue instead of priority\n",
              "    - reached is a set of states\n",
              "    - early goal test - check whether a node is a solution when generated\n",
              "    - always finds soln with minimal number of actions.\n",
              "    - cost-optimal when all actions have the same cost, not otherwise. but complete for all problems.\n",
              "    - time and space complexity: $O(b^d)$\n",
              "        - space is a bigger problem than time.\n",
              "\n",
              "```python\n",
              "function UNIFORM-COST-SEARCH(problem) returns solution node or failure\n",
              "\treturn BEST-FIRST-SEARCH(problem, PATH-COST)\n",
              "```\n",
              "\n",
              "**iterative deepening search**\n",
              "\n",
              "- pick a good $l$ value by trying all values until a solution is found or depth-limited search returns *failure* (not cutoff)\n",
              "- modest mem reqs: $O(bd)$ when there's a solution, $O(bm)$ without solution\n",
              "- time complexity = $O(b^d)$ when there's a solution, $O(b^m)$ without soln\n",
              "- optimal when all actions have same cost, complete on finite acyclic states\n",
              "\n",
              "```python\n",
              "function ITERATIVE-DEEPENING-SEARCH(problem) returns soln node or failure\n",
              "\tfor depth = 0 to infinity\n",
              "\t\tresult = DEPTH-LIMITED-SEARCH(problem, depth)\n",
              "\t\tif result != cutoff then return result\n",
              "```\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "### search problems\n",
              "\n",
              "- **reflex agent:** selects an action based only on the current precept, igonres the rest of the percept history\n",
              "- **problem-solving agent**: considers a sequence of actions to form a path to a goal state. sequence = solution.\n",
              "- example sliding-tile puzzle (8-puzzle)\n",
              "- map navigation\n",
              "\n",
              "### search problem formulation\n",
              "\n",
              "**formal problem definition,** representation\n",
              "\n",
              "1. states: a set $S$ \n",
              "2. initial state: $s_i \\in S$\n",
              "3. actions: a set $A$, $\forall s$, actions that we can take from any state\n",
              "4. transition model: for all actions, $result(s, a) → s_r$, $s_r$ is called a successor of $s$\n",
              "5. path cost: must be additive (e.g. sum of distances, number of actions, etc...)\n",
              "    1. $c(x, a_xy)$ is the step cost, assumed to be ≥ 0\n",
              "6. goal test: $goal(s)$ is true or false\n",
              "- **ex) vacuum world**\n",
              "    1. states: 2-square grid world. each cell can be dirty or not.\n",
              "        1. 2 cells * 2 positions * 2 possibilities (dirt or not) = 8 states\n",
              "        2. $n$ cells, $n 2^n$ states\n",
              "    2. one state is designated as the initial state\n",
              "    3. actions: suck, move left, right\n",
              "    4. transition: suck = removes dirt, move = move in that direction, unless we hit a wall.\n",
              "    5. action cost: uniform cost, each action costs 1.\n",
              "    6. goal state: everything is clean.\n",
              "\n",
              "**solutions and optimal solutions:**\n",
              "\n",
              "- a solution is a sequence of actions from the initial state to a goal state\n",
              "- **optimal solution**: no solution has a lower path cost\n",
              "- **ex) 8-puzzle**\n",
              "    1. states: list of 9 locations\n",
              "    2. initial state: single array or list\n",
              "    3. actions: set of possible moves {left, right, up, down}\n",
              "    4. transition model\n",
              "    5. goal test: iterate through and in ascending order\n",
              "    6. path cost: number of actions to reach goal, each action = 1\n",
              "\n",
              "*state space:* set of all states reachable from the initial state by any sequence of actions\n",
              "\n",
              "*path*: sequence of actions leading from one state, $s_j$ to another state $s_k$\n",
              "\n",
              "*frontier:* states available for expanding\n",
              "\n",
              "*solution:* path from the initial state $s_i$ to a state $s_f$ that satisfies the goal test\n",
              "\n",
              "### basic search algs\n",
              "\n",
              "- initialize frontier → choose a node on the frontier to expand → add resulting states to frontier (while frontier is not empty)\n",
              "- repeatedly visiting the same state is a problem → turns a linear problem into an exponential problem\n",
              "- algorithm is **complete** **if the algorithm is guaranteed to find a solution if there is one, and to correctly report failure when there is not\n",
              "\n",
              "### uninformed (blind) search strategies\n",
              "\n",
              "- A search method is **uninformed** if it only has access to the problem definition\n",
              "\n",
              "definitions for evaluation\n",
              "\n",
              "- completeness - always find the solution?\n",
              "- optimality - finds a least cost solution?\n",
              "- time complexity\n",
              "- space complexity\n",
              "\n",
              "time/space complexity variables: \n",
              "\n",
              "- $b$, a maximum branching factor of search tree\n",
              "- $d$, depth of shallowest goal node\n",
              "- $m$, max length of any potential path\n",
              "\n",
              "### bfs/dfs\n",
              "\n",
              "- bfs: expand shallowest unexpanded node, FIFO frontier queue\n",
              "    - complete\n",
              "    - time complexity: $O(b^d)$\n",
              "    - space complexity: $O(b^d)$\n",
              "    - optimal: yes if one step = one cost\n",
              "    - use if possible infinite paths, some solns have short paths\n",
              "- dfs: expand deepest node, LIFO\n",
              "    - incomplete - fails in loops\n",
              "    - time complexity: $O(b^m)$\n",
              "    - space complexity: $O(b*m)$\n",
              "    - optimal: yes if one step = one cost\n",
              "    - use if space-restricted, wrong paths are terminated quickly, search can be fine-tuned quickly\n",
              "\n",
              "### depth limited search and iterative deepening search\n",
              "\n",
              "depth limited search\n",
              "\n",
              "- DFS with depth limit $l$\n",
              "- no infinite-path problem\n",
              "- optimal if $l = d$, otherwise if $l < d$ then incomplete, if $l > d$ then not optimal\n",
              "\n",
              "iterative deepening search\n",
              "\n",
              "- general strategy to find best depth limit $l$\n",
              "    - key idea: use depth-limited search as subroutine and increase $l$\n",
              "- complete & optimal (if step cost = 1)\n",
              "- time complexity: $O(b^d)$\n",
              "- space complexity: $O(bd)$\n",
              "\n",
              "### review questions\n",
              "\n",
              "- uninformed complete algs: BFS, uniform-cost search, iterative deepening, bidirectional\n",
              "- uninformed optimal algs: same as above.\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "- informed search - domain-specific hints about goals\n",
              "- **heuristic function,** h(n) - estimated cost of the cheapest path from state at node to goal\n",
              "\n",
              "**greedy best-first search**\n",
              "\n",
              "- first expands node with lowest h(n) so f(n) = h(n)\n",
              "- e.g. route-finding problem in Romania uses **straight-line distance** heuristic\n",
              "- complete in finite spaces, not in infinite ones\n",
              "- time/space complexity = O(|V|), can be reduced to O(bm) with a good heuristic\n",
              "- not necessarily optimal solution\n",
              "\n",
              "**A* search**\n",
              "\n",
              "- best-first search with evaluation function\n",
              "    \n",
              "    $$f(n) = g(n) + h(n)$$\n",
              "    \n",
              "    - g(n) = path cost from initial state to node n\n",
              "    - h(n) = estimated cost of shortest path from n to goal state.\n",
              "    - f(n) = estimated cost of best path that continues from n to goal\n",
              "- complete\n",
              "- cost-optimal if heuristic is **admissible**: never overestimates cost to reach goal\n",
              "    - with an inadmissable heuristic: cost-optimal if (1) there is one cost-optimal path on which h(n) is admissable for all nodes on the path or (2) optimal soln has cost C* and second-best has cost C2 and h(n) overestimates some costs but never > C2 - C*\n",
              "- **consistency**: a heuristic h(n) is consistent if for every node and every successor n' of n, (form of triangle inequality)\n",
              "    \n",
              "    $$h(n) \\leq c(n, a, n') + h(n')$$\n",
              "    \n",
              "    - every consistent heuristic is admissable (but not other way around)\n",
              "    - first time we reach a state is optimal\n",
              "- **surely expanded nodes** - A* expands all nodes reachable from the initial state with f(n) < C*\n",
              "    - does not expand any nodes with f(n) > C*\n",
              "- optimally efficient - one algorithm may choose the optimal one first while another alg doesn't, but no difference in \"optimal efficiency\"\n",
              "- **prunes** search tree nodes that don't lead to the optimal solution\n",
              "- number of expanded nodes can be exponential in the length of the solution\n",
              "\n",
              "**satisficing search: inadmissable heuristics and weighted A***\n",
              "\n",
              "- explore less nodes but settle for **satisficing** solutions, \"good enough\"\n",
              "- weighted A* search weighs heuristic more heavily\n",
              "    \n",
              "    $$f(n) = g(n) + W*h(n), W>1$$\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "- **effective branching factor b*** - branching factor a uniform tree of depth d (solution depth) needs to contain N+1 nodes, where N is the total number of nodes generated\n",
              "    \n",
              "    $$N + 1 = 1 + b^* + (b^*)^2 + ... + (b^*)^d$$\n",
              "    \n",
              "    - e.g. A* finds a soln at depth 5 with 52 nodes ⇒ b* = 1.92\n",
              "    - well-designed heuristic has b* = 1. and a lower branching factor (but heuristic function values) is \"essentially\" always better.\n",
              "- if for any node n, h2(n) ≥ h1(n), then h2 **dominates** h1\n",
              "- **relaxed problem** - fewer restrictions on the actions. supergraph of the state space. *cost of an optimal soln to a relaxed problem is an admissable heuristic for the original problem*.\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "### uniform cost search\n",
              "\n",
              "- search algorithm for *weighted paths*\n",
              "- motivation: map navigation problems\n",
              "    - path cost = $g(N) = depth(N)$\n",
              "- expand node with *lowest path cost*\n",
              "- frontier uses a priority queue, ordered by $g(n)$\n",
              "\n",
              "subtle but significant differences from BFS:\n",
              "\n",
              "- tests if a node is a goal state when it is selected for expansion, not when it's added to frontier\n",
              "- updates a node on the frontier if a better path to same state is found\n",
              "- could be multiple ways of getting to the node, *not guaranteed to have lowest path cost when enqueued*\n",
              "\n",
              "shape of search draws a map of equivalence classes.\n",
              "\n",
              "### heuristic functions\n",
              "\n",
              "- best-first search is based on an evaluation function $f(n)$\n",
              "- simple, useful heuristic. an approximation of travel that reduces problem space (e.g. straight-line distance)\n",
              "    - **must be an underestimate of true path cost**\n",
              "\n",
              "### greedy bfs\n",
              "\n",
              "best-first search: select node for expansion with minimal evaluation function $f(n)$. use priority queue.\n",
              "\n",
              "- completely ignores $g(n)$\n",
              "\n",
              "### a* search\n",
              "\n",
              "- key idea: avoid expanding paths that are already expensive, but expand most promising first.\n",
              "- $f(n) = g(n) + h(n)$\n",
              "    - $g(n)$ is actual cost to reach node\n",
              "    - $h(n)$ estimated cost to get from node to goal\n",
              "    - $f(n)$ estimated total cost of path through $n$ to goal\n",
              "- implementation: frontier queue as priority queue by increasing $f(n)$\n",
              "\n",
              "**admissible** heuristics: a heuristic $h(n)$ is admissible if it never overestimates the cost to reach the goal (*optimistic*)\n",
              "\n",
              "- slow down bad plans but never outweigh true costs. ensures true best plan will always be expanded.\n",
              "- $\forall n, h(n) \\leq h*n, h(n) \\geq 0$\n",
              "\n",
              "if $h(n)$ is admissible, then a* search is optimal.\n",
              "\n",
              "**relaxed problems**\n",
              "\n",
              "- cost of an optimal solution to a relaxed problem is an admissable heuristic for the original problem\n",
              "\n",
              "measure if a heuristic is better than another (h1 *dominates* h2 if $h_2(n) \\geq h_1(n)$ for all $n$)\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "- **competitive environments** - ≥2 agents have conflicting goals ⇒ adversarila search\n",
              "1. economy - consider a large number of agents in aggregate\n",
              "2. adversarial agents are part of the environment, nondeterministic\n",
              "3. explicitly model adversarial agents ← this is what we do\n",
              "- **perfect information** - \"fully observable\"\n",
              "- **zero-sum** - one player's wins are another player's losses. no win-win.\n",
              "- MAX moves first (wants to maximize utility). MIN wants to minimize.\n",
              "\n",
              "game formal defn:\n",
              "\n",
              "- S0: initial state\n",
              "- TO-MOVE(s): player to move in state s\n",
              "- ACTIONS(s): set of legal moves\n",
              "- RESULT(s, a): transition model\n",
              "- IS-TERMINAL(s): true when game is over\n",
              "- UTILITY(s, p): final numeric value when game ends (e.g. chess win = 1, loss = 0, draw = 1/2)\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "**minimax search**\n",
              "\n",
              "- **minimax value** of each state gives optimal strategy, MINIMAX(s)\n",
              "    - MAX's utility, assuming both players play optimally to the end of the game\n",
              "    - terminal nodes' utility is just from the utility function\n",
              "- minimax search alg - find best move for MAX by attempting all actions, recursive alg which searches all the way to leaves and backs up the minimax values through the tree\n",
              "\n",
              "```python\n",
              "function MINIMAX-SEARCH(game, state) returns an action\n",
              "\tplayer = game.TO-MOVE(state)\n",
              "\tvalue, move = MAX-VALUE(game, state)\n",
              "\treturn move\n",
              "\n",
              "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY, null\n",
              "\tv = -infinity\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n",
              "\t\tif v2 > v then\n",
              "\t\t\tv, move = v2, a\n",
              "\treturn v, move\n",
              "\n",
              "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY, null\n",
              "\tv = infinity\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n",
              "\tif v2 < v then\n",
              "\t\tv, move = v2, a\n",
              "\treturn v, move\n",
              "```\n",
              "\n",
              "- complete depth-first exploration of game tree\n",
              "    - time complexity = O(b^m), b = legal moves at each point. m = max depth.\n",
              "    - space complexity = O(bm)\n",
              "\n",
              "**multiplayer games -** value gets replaced with *vector* of values. but you also have to deal with alliances\n",
              "\n",
              "**alpha-beta pruning**\n",
              "\n",
              "- prune sub-trees to save time and space\n",
              "- for a node n that player can move to, if player has a better choice at the same level or higher up, then player will never move to n ⇒ prune\n",
              "- $\u0007lpha$ = highest-value choice found so far for MAX (at least)\n",
              "- $\beta$ = lowest-value choice found so far for MIN (at most)\n",
              "\n",
              "```python\n",
              "function ALPHA-BETA-SEARCH(game, state) returns an action\n",
              "\tplayer = game.TO-MOVE(state)\n",
              "\tvalue, move = MAX-VALUE(game, state, -inf, +inf)\n",
              "\treturn move\n",
              "\n",
              "function MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
              "\tif game is terminal, return utility, null\n",
              "\tv = -inf\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MIN-VALUE(game, result, alpha, beta)\n",
              "\t\tif v2 > v then\n",
              "\t\t\tv, move = v2, a\n",
              "\t\t\talpha = MAX(alpha, v)\n",
              "\t\tif v >= beta then return v, move\n",
              "\treturn v, move\n",
              "\n",
              "function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair\n",
              "\tif game is terminal then return game.UTILITY\n",
              "\tv = +inf\n",
              "\tfor each action\n",
              "\t\tv2, a2 = MAX-VALUE(game, result, alpha, beta)\n",
              "\t\tif v2 < v then\n",
              "\t\t\tv, move = v2, a\n",
              "\t\t\tbeta = MIN(beta, v)\n",
              "\t\tif v <= a then return v, move\n",
              "\treturn v, move\n",
              "```\n",
              "\n",
              "- highly dependent on order — perfect ordering would result in $O(b^{m/2})$ nodes, √b instead of b branching factor\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "- cut off search early and apply a heuristic evaluation function to states\n",
              "\n",
              "**evaluation functions**\n",
              "\n",
              "- returns an estimate of the expected utility. for terminal states EVAL(s, p) = UTILITY(s, p). for non-terminal states, UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p)\n",
              "- calculate various features (e.g. chess: number of white pawns, queens, etc...)\n",
              "    - rules come from knowledge, culture of the game\n",
              "\n",
              "**cutting off search**\n",
              "\n",
              "- most straightforward = set a fixed depth limit. more robust = iterative deepening.\n",
              "- **quiscent** - positions where no pending move can change the evaluation\n",
              "    - for non-quiscent positions, continue searching\n",
              "- **horizon effect** - inevitable move by opponent is delayed past depth cutoff\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "- stochastic games include a random element. must include **chance nodes** labeled with roll and probability and use expected value.\n",
              "- **expectiminimax value**\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "### game formulation\n",
              "\n",
              "games need to have an opponent\n",
              "\n",
              "- 5.11.1997 deep blue (ibm) beats garry kasparov in chess\n",
              "- AlphaGo beats grandmaster lee sedol (>> more configurations than chess)\n",
              "\n",
              "simplest game environment: multiagent, static (no change while an agent is deliberating), discrete (finite set of percepts and actinos), fully observable (complete state is visible to sensor), strategic (next state is determined by current state, action by agent, and action of opponent)\n",
              "\n",
              "key properties of our games:\n",
              "\n",
              "1. two players alternate moves\n",
              "2. zero-sum: one player's loss is another's gain\n",
              "3. clear set of legal moves\n",
              "4. well-defined outcomes (win, lose, draw)\n",
              "\n",
              "more complicated games: most card games, scrabble, real-time strategy games (starcraft), cooperative games\n",
              "\n",
              "formalizing game setup:\n",
              "\n",
              "1. two players: **max** and **min** (max moves first)\n",
              "2. **max** and **min** take turns until the game is over\n",
              "3. winner gets award, loser gets penalty\n",
              "\n",
              "game as search:\n",
              "\n",
              "- initial state (e.g. board configuration of chess)\n",
              "- successor function: list of (move, state) pairs specifying legal moves\n",
              "- terminal test: is the game finished?\n",
              "- utility function: gives numerical value of terminal states\n",
              "- **max** uses search tree to determine next move\n",
              "\n",
              "### game tree\n",
              "\n",
              "**hexapawn**\n",
              "\n",
              "- played on a 3x3 chessboard. 6 pawn pieces.\n",
              "- only standard pawn moves: (a) a pawn moves forward one square onto an empty square. (b) pawn \"captures\" an opponent pawn by moving diagonally forward one square if square contains opposing pawn. remove opposing pawn from board.\n",
              "- player $P_1$ wins against $P_2$ when: one of P1's pawns reaches the far side of the board, $P_2$ cannot move because no legal moves possible, $P_2$ has no pawns left\n",
              "\n",
              "represent game problem as a tree\n",
              "\n",
              "- nodes = board positions\n",
              "- edges = legal moves\n",
              "- root node = first position in which a decision must be made\n",
              "- adversarial search: best move for me, best move for them?\n",
              "\n",
              "max moves first (attempts to maximize max's outcome). max's opponent (min) attempts to minimize max's outcome.\n",
              "\n",
              "even levels represent max. odd levels represent min.\n",
              "\n",
              "$f$ assigns real-number scores to 'board positions'. terminal nodes represent the way the game could end.\n",
              "\n",
              "$f(n)$ evaluation function\n",
              "\n",
              "- based on *static features* of that board alone.\n",
              "- $f(n) > 0$ if MAX is winning in position $n$\n",
              "- $f(n) = 0$ if position $n$ is tied\n",
              "- $f(n) < 0$ if MIN is winning in position $n$\n",
              "- e.g. for tic tac toe, $f(n)$ = # of potential three-lines for X - # of potential three-lines for O\n",
              "\n",
              "### minimax rules\n",
              "\n",
              "idea: make the best move for MAX assuming that MIN always replies with the best move for MIN\n",
              "\n",
              "**easily computed by recursive process**\n",
              "\n",
              "- **backed-up** value of each node is tree determined by the values of its children\n",
              "- for MAX node: backed-up value is **maximum** of the values of its children\n",
              "- for MIN node: backed-up value is **minimum** of values of its children\n",
              "\n",
              "**minimax procedure**\n",
              "\n",
              "1. start with current position as MAX node\n",
              "2. expand game tree a fixed number of ply (may not always be able to reach end-state, truncated search)\n",
              "3. apply evaluation function to leaf positions\n",
              "4. calculate back-up values bottom-up\n",
              "5. pick move assigned to MAX at root\n",
              "6. wait for MIN to respond\n",
              "\n",
              "```python\n",
              "def max-value(state):\n",
              "\tif (state in terminal state): return state's utility\n",
              "\tv = -infinity\n",
              "\tfor successor of state:\n",
              "\t\tv = max(v, min-value(successor))\n",
              "\treturn v\n",
              "\n",
              "def min-value(state):\n",
              "\tif (state in terminal state): return state's utility\n",
              "\tv =-infinity\n",
              "\tfor successor of state:\n",
              "\t\tv = min(v, max-value(successor))\n",
              "\treturn v \n",
              "```\n",
              "\n",
              "### alpha-beta pruning\n",
              "\n",
              "stop evaluating a branch whenever:\n",
              "\n",
              "$\u0007lpha$: MAX's current lower bound on MAX's outcome\n",
              "\n",
              "- never allows a move worse than $\u0007lpha$\n",
              "\n",
              "$\beta$: MIN's current upper bound on MIN's outcome\n",
              "\n",
              "- never allows a move better than $\beta$\n",
              "\n",
              "### expectimax\n",
              "\n",
              "uncertain outcomes: rolling dice, shuffled card games, \n",
              "\n",
              "- model tree as before but max nodes and chance nodes. chances nodes say how likely branch is.\n",
              "\n",
              "expectimax: compute average score under optimal play.\n",
              "\n",
              "- calculate *expected utilities* (weighted average / expectation)\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "constraint satisfaction problem consists of:\n",
              "\n",
              "1. X, set of variables $\\{X_1,...,X_n\\}$\n",
              "2. D, set of domains $\\{D_1,...,D_n\\}$. $D_i$ is the set of allowable values for variable $X_i$\n",
              "3. C, set of constraints on value combinations\n",
              "- CSPs assign values to variables. **consistent** **assignment doesn't violate any constraints. **complete** assignment - every variable has a value. **solution -** complete, consistent assignment.\n",
              "    - **partial assignment** - some unassigned variables. **partial solution** - consistent partial assignment.\n",
              "- **constraint graph** - nodes = variables, edge = two variables in a constraint.\n",
              "\n",
              "types of constraints:\n",
              "\n",
              "- **unary constraint** - restricts value to single variable (e.g. SA ≠ green)\n",
              "- **binary constraint** - relates two variables (eg. SA ≠ NSW)\n",
              "- **ternary constraint** - (e.g. X < Y < Z)\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "- constraint propagation: use constraints to reduce # of legal values for a variable\n",
              "- **local consistency** - enforce local consistency to eliminate inconsistent values\n",
              "\n",
              "**node consistency** - all values in domain satisfy unary constraints\n",
              "\n",
              "**arc consistency** - satisfy binary constraints\n",
              "\n",
              "- sometimes does nothing (e.g. australia map coloring problem - valid value for the other variable for each value of the domain)\n",
              "- **AC-3** enforces arc-consistency for every variable. maintains a queue of arcs.\n",
              "\n",
              "```jsx\n",
              "function AC-3(csp) returns false if an inconsistency if found, true otherwise\n",
              "\tqueue = queue of arcs, initialized to all arcs in csp\n",
              "\twhile queue isn't empty\n",
              "\t\t(x_i, x_j) = pop(queue)\n",
              "\t\tif REVISE(csp, x_i, x_j) then\n",
              "\t\t\tif size(D_i) = 0 then return false\n",
              "\t\t\tfor each x_k in x_i.neighbors - {x_j} do\n",
              "\t\t\t\tadd (x_k, x_i) to queue\n",
              "\treturn true\n",
              "\n",
              "function REVISE(csp, x_i, x_j) returns true iff we revise the domain of x_i\n",
              "\trevised = false\n",
              "\tfor each x in D_i do\n",
              "\t\tif no value y in D_j allows (x, y) to satisfy the constraint between X_i and X_j then\n",
              "\t\t\tdelete x from D_i\n",
              "\t\t\trevised = true\n",
              "\treturn revised\n",
              "```\n",
              "\n",
              "- complexity: with n variables, domain size of at most d, and c arcs, checking consistency of arcs is $O(d^2)$ so total run-time is $O(cd^3)$\n",
              "\n",
              "**path consistency** - triples of variables\n",
              "\n",
              "**k-consistency** - strongly consistent if also (k - 1)-consistent, (k - 2)-consistent, etc...\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "- CSPs are commutative since order of assigning actions does not matter.\n",
              "\n",
              "```jsx\n",
              "function BACKTRACKING-SEARCH(csp) returns a solution or failure\n",
              "\treturn BACKTRACK(csp, {})\n",
              "\n",
              "function BACKTRACK(csp, assignment) returns a solution or failure\n",
              "\tif assignment is complete then return assignment\n",
              "\tvar = SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n",
              "\tfor each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n",
              "\t\tif value is consistent with assignment then\n",
              "\t\t\tadd {var = value} to assignment\n",
              "\t\t\tinferences = INFERENCE(csp, var, assignment)\n",
              "\t\t\tif inferences != failure then\n",
              "\t\t\t\tadd inferences to csp\n",
              "\t\t\t\tresult = BACKTRACK(csp, assignment)\n",
              "\t\t\t\tif result != failure then return result\n",
              "\t\t\t\tremove inferences from csp\n",
              "\t\t\tremove {var = value} from assignment\n",
              "\treturn failure\n",
              "```\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "- min-conflicts: local search, select value which results in minimum number of conflicts with other variables\n",
              "- runtime of min-conflicts is independent of problem size\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "## module 6: constraint satisfaction problems\n",
              "\n",
              "### intro to CSPs\n",
              "\n",
              "assumptions about world: single agent, deterministic actions, fully observed state, discrete state space\n",
              "\n",
              "planning: sequence of actions\n",
              "\n",
              "- path to the goal is the important thing. paths have various costs, depths. heuristics give problem-specific guidance.\n",
              "\n",
              "*alternative - identify a good assignment to variables to reach goal state.*\n",
              "\n",
              "- goal itself is important, not the path. all paths have the same depth.\n",
              "- CSPs are specialized for identification problems.\n",
              "\n",
              "**constraint satisfaction problems**\n",
              "\n",
              "- represent *constraints* that solutions must satisfy in a uniform declarative language\n",
              "- general purpose search algorithms with no changes from problem to problem\n",
              "\n",
              "formal definition\n",
              "\n",
              "A CSP consists of:\n",
              "\n",
              "- finite set of variables $X_1, X_2,...,X_n$ (label for each variable)\n",
              "- nonempty *domain* of possible values for each variable $D_1, D_2,..., D_n$\n",
              "- finite set of constraints $C_1, C_2,...,C_m$\n",
              "    - each constraint $C_i$ limits the values that variables can take. a *state* is defined as an *assignment* of values to some or all variables\n",
              "- *consistent* assignment does not violate constraints\n",
              "\n",
              "e.g. Sudoku\n",
              "\n",
              "- constraints: all numbers in each row and column must be distinct. all 9 numbers in box must be different.\n",
              "- assignment is *complete* when every variable is assigned a value. *solution* is a complete, consistent assignment\n",
              "\n",
              "### deeper in CSP\n",
              "\n",
              "e.g. map-coloring\n",
              "\n",
              "- variables: WA, NT, Q, NSW, V, SA, T (states of australia)\n",
              "- domains: $D_i$ = {red, green, blue}\n",
              "- constraints: adj regions must have diff colors\n",
              "\n",
              "solutions: complete and consistent assignments\n",
              "\n",
              "benefits of CSP\n",
              "\n",
              "- clean specification of many problems, generic goal, successor function and heuristics\n",
              "- CSP \"knows\" which variables are violating a constraint, cut off search that doesn't lead to goal state.\n",
              "- automatically prune all branches that violate constraints. eliminate possibilities as fast as possible.\n",
              "\n",
              "CSP representations\n",
              "\n",
              "- *constraint graph -* nodes are variables, arcs are (binary) constraints\n",
              "    - simplifies search\n",
              "    - this CSP is a *binary* CSP since each constraint relates 2 variables\n",
              "- *standard representation pattern -* variables with values\n",
              "\n",
              "**discrete variables**\n",
              "\n",
              "- finite domains: $n$ variables, domain size of $d$ (d possible values) → $O(d^n)$ complete assignments\n",
              "- infinite domains: integers, strings, etc... need a constraint language\n",
              "\n",
              "**continuous variables**\n",
              "\n",
              "- linear constraints solvable in polynomial time in linear programming\n",
              "\n",
              "**varieties of constraints**\n",
              "\n",
              "- unary = single variable. binary = pairs of variables. higher-order = ≥3 variables.\n",
              "- preference (soft constraints, e.g. red > green) represented using a cost\n",
              "\n",
              "### CSP as a search problem\n",
              "\n",
              "**csp can easily be expressed as a search problem**\n",
              "\n",
              "- initial state: empty assignment {}\n",
              "- successor function: assign value to any unassigned variables\n",
              "- goal test: is the current assignment complete?\n",
              "- path cost: constant cost for every step\n",
              "\n",
              "solution is always found at depth $n$ for $n$ variables\n",
              "\n",
              "- each $n$ variable has to take on 1 value\n",
              "\n",
              "**search and branching factor:**\n",
              "\n",
              "- $n$ variables of domain size $d$\n",
              "- branching factor at root = $n * d$. next level is $(n - 1) * d$\n",
              "- tree has $n! * d^n$ leaves\n",
              "- variable assignments are commutative, order of application doesn't affect outcome.\n",
              "\n",
              "**search and *backtracking***\n",
              "\n",
              "- depth-first search for CSPs with single-variable assignment is called *backtracking* search\n",
              "- DFS that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign\n",
              "- basic *uninformed* algorithm for CSPs\n",
              "\n",
              "### heuristics to improve backtracking efficiency\n",
              "\n",
              "*general-purpose* methods & *general-purpose* heuristics can give huge gains in speed (on avg)\n",
              "\n",
              "**heuristics:**\n",
              "\n",
              "1. q: which variable to assign next?\n",
              "    1. most constrained variable (variable with *fewest legal values)*\n",
              "        - recognize failure as fast as possible. label nodes with number of legal values available.\n",
              "        - *minimum remaining values (MRV)* heuristic\n",
              "    2. (if ties) most constraining variable\n",
              "        - choose variable with fewest legal values, the one with the most constraints on remaining variable (e.g. greatest # of neighbors in coloring ex)\n",
              "2. q: in what order should variable's values be tried?\n",
              "    1. least constraining value? one that rules out the *fewest* values in the remaining variables.\n",
              "3. q: can we detect inevitable failure early?\n",
              "    1. **forward checking**\n",
              "        - idea: keep track of *remaining* legal variables for *unassigned* variables\n",
              "        - terminate search when any unassigned variable has no remaining legal values\n",
              "        - new data structure that keeps track of legal variables for unassigned variables\n",
              "        - propagates info from assigned to unassigned variables, but doesn't provide early detection for all failures → *constraint propagation* repeatedly enforces restraints\n",
              "\n",
              "### arc consistency\n",
              "\n",
              "idea 3: *inference* in CSPs\n",
              "\n",
              "**CSP solves combine search and inference**\n",
              "\n",
              "- search: assigning a value to a variable\n",
              "- constraint propagation (inference): eliminates possible values for a variable if the value violates local consistency.\n",
              "- *can do inference first or intertwine with search*\n",
              "\n",
              "**local consistency**\n",
              "\n",
              "- node consistency: satisfies unary constraints\n",
              "- arc consistency: satisfies binary constraints.\n",
              "\n",
              "$X_i$ is arc-consistent wrt $X_j$ if for every value $v$ in $D_i$, there is some value $w$ in $D_j$ that satisfies the binary constraint on the arc between $X_i$ and $X_j$\n",
              "\n",
              "represented as a constraint graph: nodes are variables, edges are constraints. ⇒ convert to a directed graph.\n",
              "\n",
              "- given a pair of nodes $X_i$ and $X_j$, connected by a constraint edge, we represent this not by a single undirected edge, but as a pair of directed arcs (i, j) and (j, i).\n",
              "\n",
              "**arc consistency**\n",
              "\n",
              "- simplest form of propagation makes each arc **consistent**\n",
              "    - X → Y is consistent iff for every value x of X, there is some allowed y\n",
              "- if $X$ loses a value, recheck neighbors of $X$\n",
              "- given $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time worst case\n",
              "\n",
              "**e.g. Waltz Algorithm** (for computer vision)\n",
              "\n",
              "- every intersection could be interpreted as pointing inwards or outwards. treat each intersection as a variable and adj intersections impose constraints. solution is physically realizable 3D interpretations.\n",
              "\n",
              "**Waltz/Mackworth constraint propagation alg**\n",
              "\n",
              "1. assign every node in the constraint graph a set of all possible values\n",
              "2. repeat until there is no change in set of values associated with any node:\n",
              "    \n",
              "    ```python\n",
              "    for each node i:\n",
              "    \tfor each neighboring node j in the picture:\n",
              "    \t\tremove any value from i which is not arc consistent with j.\n",
              "    ```\n",
              "    \n",
              "\n",
              "**towards AC-3**\n",
              "\n",
              "1. at each iteration, we actually only need to examine nodes $X_i$ where at least one neighbor of $X_i$ has lost a value (ow no change)\n",
              "- maintain an arc of what we need to process. add back arcs to neighbors whenever a node had values removed.\n",
              "- worst cast analysis = $O(n^2d^3)$\n",
              "    - all nodes connected to every other nodes: $O(n^2)$\n",
              "    - with $d$ values, checking arc $(i, j)$ takes $O(d^2)$ time\n",
              "    - each arc $(i, j)$ can only be inserted into the queue $d$ times\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "- knowledge base: set of sentences. sentence is expressed in a knowledge representation language.\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "\n",
              "- performance measure: +1000 for climbing out of cave, -1000 for falling into pit, -1 for each action taken, -10 for using arrow.\n",
              "- environment: 4x4 grid of rooms. random location for gold and wumpus.\n",
              "- actuators: move forward, turn left, turn right.\n",
              "- sensors: perceives a *stench* in adjacent squares to wumpus. perceives *breeze* adjacent to pit. *glitter* adjacent to gold. *bump* if it hits wall. *scream* when killed xd\n",
              "- deterministic, discrete, static, single-agent, sequential, partially observable\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "- defines the *semantics* or meaning of sentences.\n",
              "- $M(\u0007lpha)$ = set of all models of $\u0007lpha$ where $\u0007lpha$ is true\n",
              "- entailment ⇒ a sentence that follows logically from another sentence, a |= b\n",
              "    - a |= b iff in every model where a is true, b is true\n",
              "    \n",
              "    $$a |= b \text{ iff } M(a) \\subseteq M(b)$$\n",
              "    \n",
              "    - if in every model in which KB is true, a is true, then KB |= a\n",
              "- completeness = can derive any entailed sentence\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "- atomic sentences: single proposition symbol\n",
              "- proposition symbol: single variable\n",
              "- complex sentences: combination of simple sentences with parenthesis and logical connectives\n",
              "- logical connectives: not, and, or, implies, biconditional\n",
              "\n",
              "```jsx\n",
              "function TT-ENTAILS?(KB, a) returns true or false\n",
              "\tinputs: KB (knowledge base), a (sentence in propositional logic)\n",
              "\tsymbols = list of proposition symbols in KB and a\n",
              "\treturn TT-CHECK-ALL(KB, a, symbols, {})\n",
              "\n",
              "function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n",
              "\tif symbols is empty then\n",
              "\t\tif PL-TRUE(KB, model) then return PL-TRUE(a, model)\n",
              "\t\telse return true\n",
              "\telse\n",
              "\t\tP = first(symbols)\n",
              "\t\trest = rest(symbols)\n",
              "\t\treturn (TT-CHECK-ALL(KB, a, rest, model (union) {P = true}) \n",
              "\t\t\t\t\t&& TT-CHECK-ALL(KB, a, rest, model (union) {P = false})\n",
              "```\n",
              "\n",
              "- $2^n$ models for $n$ symbols. $O(2^n)$ worst-case time complexity, space complexity = $O(n)$.\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "- a and b are logically equivalent iff a |= b and b |= a\n",
              "- **valid** if true in *all* models, always true (e.g. a || -a)\n",
              "- **satisfiability** if able to be satisfied by some model\n",
              "    - a is valid iff -a is unsatisfiable. a is satisfiable iff -a is not valid.\n",
              "- **modus ponens**: a ⇒ b, a / b. whenever any sentence of a ⇒ b and a are given, sentence b can be inferred.\n",
              "\n",
              "**conjunctive normal form**\n",
              "\n",
              "1. eliminate ↔ . a ↔ b gets replaced with (a ⇒ b) && (b ⇒ a)\n",
              "2. eliminate ⇒, a ⇒ b gets replaced with -a || b\n",
              "3. move negations inwards.\n",
              "    \n",
              "    -(-a) = a\n",
              "    \n",
              "    -(a && b) = -a || -b\n",
              "    \n",
              "    -(a || b) = -a && -b\n",
              "    \n",
              "4. apply distributivity to avoid nested && and ||\n",
              "    \n",
              "    a && (b || c) = (a && b) || (a && c)\n",
              "    \n",
              "    a || (b && c) = (a || b) && (a || c)\n",
              "    \n",
              "\n",
              "**definite clause** - disjunction of literals where exactly one is positive.\n",
              "\n",
              "**horn clauses -** disjunction of literals where at most one is positive (includes all definite clauses)\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "### knowledge-based agents 1\n",
              "\n",
              "- **knowledge-based agents** use a process of **reasoning** over an internal representation of knowledge to decide what action to take\n",
              "    - problem-solving agents perform search over states. very limited and atomic, very difficult to add sophisticated questions \"take me to the nearest habitable planet where i can store my perishable cargo\".\n",
              "- knowledge base (KB) contains a set of sentences written in a *knowledge representation language*, contains some facts about the world\n",
              "    - e.g. *Hoth is a planet* ⇒ planet(hoth); *Hoth is far from its sun ⇒* far_from(hoth, sol)\n",
              "        - natural language sentence ⇒ knowledge representation language sentence\n",
              "1. axioms - given sentence\n",
              "2. derived sentences - new sentence derived from others sentences\n",
              "- KB has some initial background information and an agent adds info through observations\n",
              "\n",
              "### hunt the wampas\n",
              "\n",
              "**wampa world**\n",
              "\n",
              "- r2d2 (our knowledge-based agent) explores a cave consisting of rooms connected by passages. there is a wampa which eats r2d2s in the cave. some rooms have traps. goal is: collect luke, exit world, don't get eaten.\n",
              "- environment: a 4x4 grid of rooms.\n",
              "- performance measure: +1000 points for rescuing Luke, -1000 for falling into a pit, -1 for each action taken, -10 for using up blaster fire\n",
              "- actuators: move forward, turn; grab to pick up luke, shoot, climb\n",
              "- sensors: limit sensors to current square, perceives bump when it walks into a wall\n",
              "- deterministic, discrete, static, single-agent; sequential; partially observable\n",
              "\n",
              "### knowledge-based agents 2\n",
              "\n",
              "**logic**: serve as general class of represetnations for knowledge-based agents\n",
              "\n",
              "- KB is sentences in representation language, has a syntax that specifies well-formed sentences.\n",
              "- defines sentence semantics and meaning\n",
              "\n",
              "**possible worlds and models**\n",
              "\n",
              "- models have a fixed set of *truth values*\n",
              "- if sentence $\u0007lpha$ is true in model $m$, then $m$ satisfies $\u0007lpha$ of $m$ is a model of $\u0007lpha$\n",
              "\n",
              "**logical entailment**\n",
              "\n",
              "- entailment relation between sentences, a sentence logically follows another one.\n",
              "\n",
              "$$a \\models b \text{ iff } M(a) \\subseteq M(b) $$\n",
              "\n",
              "knowledge base is a set of sentences. KB is false in models that contradict what the agent knows.\n",
              "\n",
              "### propositional logic\n",
              "\n",
              "**atomic sentences** represented with a single **propositional symbol**\n",
              "\n",
              "- propositional symbol stands for a statement that can be true or false\n",
              "- W_{1, 3} = there is a Wampa at location [1, 3]. this can be true or false.\n",
              "\n",
              "complex sentences use logical connectives to combine simpler sentences\n",
              "\n",
              "biconditional: P ↔ Q\n",
              "\n",
              "- T, T ⇒ T\n",
              "- T, F ⇒ F\n",
              "- F, T ⇒ F\n",
              "- F, F ⇒ T\n",
              "\n",
              "### knowledge bases\n",
              "\n",
              "### theorem proving 1\n",
              "\n",
              "rewrite sentences using logical equivalence\n",
              "\n",
              "commutativity of and and or: **a && b = b && a, a || b = b || a**\n",
              "\n",
              "associativity: **(a && b) && c = (a && (b && c))**\n",
              "\n",
              "contrapositive: **a ⇒ b = -a ⇒ -b**\n",
              "\n",
              "implication elimination: **a ⇒ b = -a || b**\n",
              "\n",
              "biconditional elimination: **a ↔ b = (a ⇒ b) && (b ⇒ a)**\n",
              "\n",
              "de morgan: **-(a && b) = -a || -b**\n",
              "\n",
              "de morgan: **-(a || b) =  (-a && -b)**\n",
              "\n",
              "distributivity of &&: **(a && b) || c = (a || c) && (b || c)**\n",
              "\n",
              "distributivity of ||: **(a || b) && c = (a && c) || (b && c)**\n",
              "\n",
              "**monotonicity:** if $KB \\models \u0007lpha$ then $KB \\land \beta \\models \u0007lpha$.\n",
              "\n",
              "### theorem proving 2\n",
              "\n",
              "**conjunctive normal form**\n",
              "\n",
              "1. eliminate ↔ by replacing a ↔ b with (a ⇒ b) && (b ⇒ a)\n",
              "2. eliminate ⇒ by replacing a ⇒ b with -a || b\n",
              "3. move - inwards (eliminate double negation and apply de morgan's rules)\n",
              "4. sentence contains nested || and && operators applied to literals. apply distributivity law to distribut || over && wherever possible.\n",
              "\n",
              "- empty clause arises when we have two contradictory unit clauses, like P && -P\n",
              "\n",
              "**definite clause**: disjunction of literals where exactly one is positive\n",
              "\n",
              "**horn clause**: disjunction of literals where at least one is positive\n",
              "\n",
              "- includes definite clauses\n",
              "- clauses with no positive literals\n",
              "\n",
              "forward chaining algorithm\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
