{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Tai_Nguyen_CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6f88bf5b-5425-4a9e-a1e6-6d7553eea97a"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 101,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3d9aeb9c-2599-4ddd-f169-14773329d623"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 102,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 103,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Rationality ~ intelligence ~ doing right thing. *Human vs. rational* and *though vs. behavior*.\n",
        "\n",
        "__Turing test__ helps answers \"Can machine thinks\". __Total Turing test__ additionally requires *interaction* with objects & people in real world (CV, robotics).\n",
        "\n",
        "How to know how human thinks: instropection (reflecting on own thoughts), psychological experiments (observing human in action), brain imaging (observing brain in action).\n",
        "\n",
        "Logical thinking requires *certain* knowledge of the world, othewise *probability* is required.\n",
        "\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 = \"\"\" *Argument from disability* is claim that \"machine can __never__ do X\": being kind, beautiful, friendly, humerous, falls in love, enjoys ice cream. Programs can __exceed__ human performance in some tasks but lag behind on others.\n",
        "\n",
        "One thing, they cannot be *exactly* human.\n",
        "\n",
        "__Mathematical objection__ comes from Turing & Godel, who prove certain math questions are *unanswerable* by formal systems by principle. \n",
        "\n",
        "Some arguments against Godel's incompleteness theorem.\n",
        "First, agents should not be ashamed if it establishes truth of some sentences that others can.\n",
        "Second, theorem applies to *mathematics*, __not__ to computers. But both humans and machines __cannot__ prove things impossible to prove (humans cannot get around limits).\n",
        "Third, theorem was only proven on systems that can only do arithmetic.\n",
        "\"\"\"\n",
        "\n",
        "chapter27_2 = \"\"\"  \n",
        "Turing says we never have *any* direct evidence about internal mental states of other humans, so would be a __polite convention__ to assume that everyone *thinks*.\n",
        "\n",
        "Philosopher Searle rejects \"polite convention\" by stating __Chinese room__: Image only-English-speaker human sitting inside room, copies Chinese characters and passes the papers back outside.\n",
        "Human does not understand any Chinese but still outputs, which is exactly what the computer would do. Just __symbol manipulation__, no brain.\n",
        "Searle is proponent of __biological naturalism__, meaning mental states are high-level emergent features caused by low-level physical process in *neurons*.\n",
        "\n",
        "__Consciousness__: awareness of outside world, self, and subjective experience of living. __Qualia__ is intrinsic nature of experiences. Turing thinks consciousness has __little__ to do with practice of AI.\n",
        "Only interested in modeling *intelligent behavior*, some *awareness*.\n",
        "\n",
        "Turing operationalizes the \"Can machines think\" question: Are there imaginable digital computers which would do well in *imitation game*?\"\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" __Agent function vs. agent program__ is abstract mathematical depscription versus agent program of concrete implementation run on *physical* system.\n",
        "\n",
        "Vacumn cleaner example...\n",
        "\n",
        "TRUE: __Touchless faucets__ can also be viewed as agent.\n",
        "\n",
        "FALSE: Agent's choice of action at given instant depends both on percept sequence and future perceptual inputs (it does not have to).\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" __Rational agent__is one that does the right thing. Notion \"right thing\" is equivalent to performance measures.\n",
        "Better to design measures according to what we want, not how we think *an agent* should behave.\n",
        "\n",
        "Example: Vacumn cleaner agent is awarded one point for each square cleaned at step over \"lifetime\" 1000 steps. Geography of environment is *priori* but dirt distribution/initial agent location is not.\n",
        "Only available actions are *Right, Left, Suck*. Agent perceives if location contains dirt.\n",
        "\n",
        "Circumtances above make agent __rational__, but when all dirt is cleaned up -> agent oscillate back and forth -> __irrational__.\n",
        "\n",
        "__Rationality vs. Omniscience__: Omniscient agent knows *actual* outcome of actions and act accordingly. It is usually __impossible__ in reality.\n",
        "Rationality $\\\\neq$ perfection, maximizing expected performance up *to date* $\\\\neq$ perfecting *actual* performance. __Rationality is not omniscience (guaranteed success)__.\n",
        "\n",
        "\n",
        "In extreme, environment is *priori* and completely predictable, does not learn anything but simply acts correctly. But can be *fragile*.\n",
        "If reliant too much on prior rather than self-learned percepts, agent __lacks autonomy__.\n",
        "\"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" Specifying __task environment__ with PEAS: Performance measure, Environment, Actuators, Sensors. ie. Taxi driver, software agent trading on auction/reselling (complex agent)...\n",
        "\n",
        "__Rational agent__ means for each possible percept sequence, rational agent selects action expected to maximize performance measure, given evidence provided by percept sequence & built-in knowledge,\n",
        "\n",
        "__Fully vs. Partially observable__: Fully observable is *convenient* because agent needs not maintain any internal state to keep track of world. Partial might be due to noisy or inaccurate sensors or missing states (vacumn does not know if dirt is in a other squares).\n",
        "If agent has *no sensors*, then environment is __unobservable__.\n",
        "\n",
        "__Single vs. multi-agent__: Solving puzzle vs. playing chess. *Chess* is __competitive__ multiagent environment. In taxi-driving, avoiding collisions maximizes performance measure, so driving taxi is partially __cooperative__ multiagent environ.\n",
        "\n",
        "Agent needs not worry about uncertainty in fully observable, deterministic environ. Partially observable environ can *appear* non-deterministic. Taxi driving is *non-deterministic* because traffic is unpredictable. Vacumn world is deterministic but if dirt __randomly appears__ then becomes non-deter.\n",
        "\n",
        "__Episodic vs. sequential__: In episodic, agent experience divided into *atomic* episodes, in each agent receives percept to perform single action (ie. independent classsification tasks). \n",
        "In sequential, current desicions *affect* future decisions.\n",
        "\n",
        "__Static vs. dynamic__: Dynamic environ constantly asks agent what it wants to do. __Semidynamic__ happens when agent's performance score changes. Taxi driving is dynamic. Chess, when playing with clock, is *semidynamic*.\n",
        "\n",
        "__Discrete vs. continuous__: Chess has *finite* number of distinct states and discrete set of percepts and moves. Taxi driving is continuous-state and continuous-time. Input from camera is discrete but continuous representing varying intensities/locations.\n",
        "\n",
        "__Known vs. unknown__: Agent's state of knowledge. __Different__ from observability. *Known* environ can be *partially* observable. *Unknown* environ can be *fully observable* (In video games, screen shows entire game state but you don't know what buttons do yet).\n",
        "Another example, driver does not know what *driving style* customer prefers.\n",
        "\n",
        "__Hardest case__ is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. ie. Taxi driving (but environ is mostly known). Driving rented car in new country with unfamiliar geography, traffic laws, and nervous passengers.\n",
        "\"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\" Engineer job: design __agent program__ that implements agent function.\n",
        "\n",
        "$$agent = architecture + program$$\n",
        "\n",
        "Key challenge to AI is to find programs that produces rational behavior *from smallish* program rather than vast exhaustive table.\n",
        "\n",
        "Some __types__ of agent programs: simple reflex agents, model-based, goal-based, utility-based.\n",
        "\n",
        "__Simple reflex__ is based on __condition-action rule__ ie. If car infront is braking then also brakes. Correct decision can be made just be current percept (only if environ is __fully observable__; just a little of unobservability can be serious).\n",
        "\n",
        "__Model-based__ helps deal with partial observability, parts of the world can yet see. Model means __internal state__ built from percept history.\n",
        "\n",
        "__Goal-based__ requires goal information describing desirable destination. __Search & planning__ help find action sequences that achieve agent's goals.\n",
        "\n",
        "__Utility-based__ is internalization of performance measure and own __\"happiness\"__.\n",
        "\n",
        "All agents can improve performance through __learning__.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"value alignment problem\": \"agreement between true *human* preferences and objectives put into machine \",\n",
        "\"provably beneficial\": \"we want agents useful to human\",\n",
        "\"weak AI\": \"idea that machine can act *as if* intelligent\",\n",
        "\"strong AI\": \"machines *actually* think consciously\",\n",
        "\"GOFAI\": \"Good Old-Fashioned AI that 'cannot produce durable results'\", \n",
        "\"agent\" : \"anything that can perceive its environment through __sensors__ and act through __actuators__\",\n",
        "\"percept\" : \"content perceived by agent's sensors\",\n",
        "\"percept sequence\" : \"complete history of everything agent has ever perceived\",\n",
        "\"agent function\": \"maps any percept sequence to action\",\n",
        "\"consequentialism\": \"evaluate agent's behavior by consequences\",\n",
        "\"information gathering\": \"Doing action to modify future percept\",\n",
        "\"deterministic\": \"If next state of environ is completely determined by current state AND agent executes action; given inputs = given outputs\",\n",
        "\"stochastic\": \"Deals explicitly with probabilities, can be equivalent to non-deterministic\",\n",
        "\"dynamic\": \"Environ can change while agent is deliberating\",\n",
        "\"semidynamic\": \"If environ is does not change with time but agent's performan score does\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 104,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f777f469-2d9d-4a3c-d038-caa0953b5da5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 105,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Rationality ~ intelligence ~ doing right thing. *Human vs. rational* and *though vs. behavior*.\n\n__Turing test__ helps answers \"Can machine thinks\". __Total Turing test__ additionally requires *interaction* with objects & people in real world (CV, robotics).\n\nHow to know how human thinks: instropection (reflecting on own thoughts), psychological experiments (observing human in action), brain imaging (observing brain in action).\n\nLogical thinking requires *certain* knowledge of the world, othewise *probability* is required.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n *Argument from disability* is claim that \"machine can __never__ do X\": being kind, beautiful, friendly, humerous, falls in love, enjoys ice cream. Programs can __exceed__ human performance in some tasks but lag behind on others.\n\nOne thing, they cannot be *exactly* human.\n\n__Mathematical objection__ comes from Turing & Godel, who prove certain math questions are *unanswerable* by formal systems by principle. \n\nSome arguments against Godel's incompleteness theorem.\nFirst, agents should not be ashamed if it establishes truth of some sentences that others can.\nSecond, theorem applies to *mathematics*, __not__ to computers. But both humans and machines __cannot__ prove things impossible to prove (humans cannot get around limits).\nThird, theorem was only proven on systems that can only do arithmetic.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n  \nTuring says we never have *any* direct evidence about internal mental states of other humans, so would be a __polite convention__ to assume that everyone *thinks*.\n\nPhilosopher Searle rejects \"polite convention\" by stating __Chinese room__: Image only-English-speaker human sitting inside room, copies Chinese characters and passes the papers back outside.\nHuman does not understand any Chinese but still outputs, which is exactly what the computer would do. Just __symbol manipulation__, no brain.\nSearle is proponent of __biological naturalism__, meaning mental states are high-level emergent features caused by low-level physical process in *neurons*.\n\n__Consciousness__: awareness of outside world, self, and subjective experience of living. __Qualia__ is intrinsic nature of experiences. Turing thinks consciousness has __little__ to do with practice of AI.\nOnly interested in modeling *intelligent behavior*, some *awareness*.\n\nTuring operationalizes the \"Can machines think\" question: Are there imaginable digital computers which would do well in *imitation game*?\"\n\n\n## AIMA 2.1 Agents and Environments\n __Agent function vs. agent program__ is abstract mathematical depscription versus agent program of concrete implementation run on *physical* system.\n\nVacumn cleaner example...\n\nTRUE: __Touchless faucets__ can also be viewed as agent.\n\nFALSE: Agent's choice of action at given instant depends both on percept sequence and future perceptual inputs (it does not have to).\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n __Rational agent__is one that does the right thing. Notion \"right thing\" is equivalent to performance measures.\nBetter to design measures according to what we want, not how we think *an agent* should behave.\n\nExample: Vacumn cleaner agent is awarded one point for each square cleaned at step over \"lifetime\" 1000 steps. Geography of environment is *priori* but dirt distribution/initial agent location is not.\nOnly available actions are *Right, Left, Suck*. Agent perceives if location contains dirt.\n\nCircumtances above make agent __rational__, but when all dirt is cleaned up -> agent oscillate back and forth -> __irrational__.\n\n__Rationality vs. Omniscience__: Omniscient agent knows *actual* outcome of actions and act accordingly. It is usually __impossible__ in reality.\nRationality $\\neq$ perfection, maximizing expected performance up *to date* $\\neq$ perfecting *actual* performance. __Rationality is not omniscience (guaranteed success)__.\n\n\nIn extreme, environment is *priori* and completely predictable, does not learn anything but simply acts correctly. But can be *fragile*.\nIf reliant too much on prior rather than self-learned percepts, agent __lacks autonomy__.\n\n\n## AIMA 2.3 The Nature of Environments\n Specifying __task environment__ with PEAS: Performance measure, Environment, Actuators, Sensors. ie. Taxi driver, software agent trading on auction/reselling (complex agent)...\n\n__Rational agent__ means for each possible percept sequence, rational agent selects action expected to maximize performance measure, given evidence provided by percept sequence & built-in knowledge,\n\n__Fully vs. Partially observable__: Fully observable is *convenient* because agent needs not maintain any internal state to keep track of world. Partial might be due to noisy or inaccurate sensors or missing states (vacumn does not know if dirt is in a other squares).\nIf agent has *no sensors*, then environment is __unobservable__.\n\n__Single vs. multi-agent__: Solving puzzle vs. playing chess. *Chess* is __competitive__ multiagent environment. In taxi-driving, avoiding collisions maximizes performance measure, so driving taxi is partially __cooperative__ multiagent environ.\n\nAgent needs not worry about uncertainty in fully observable, deterministic environ. Partially observable environ can *appear* non-deterministic. Taxi driving is *non-deterministic* because traffic is unpredictable. Vacumn world is deterministic but if dirt __randomly appears__ then becomes non-deter.\n\n__Episodic vs. sequential__: In episodic, agent experience divided into *atomic* episodes, in each agent receives percept to perform single action (ie. independent classsification tasks). \nIn sequential, current desicions *affect* future decisions.\n\n__Static vs. dynamic__: Dynamic environ constantly asks agent what it wants to do. __Semidynamic__ happens when agent's performance score changes. Taxi driving is dynamic. Chess, when playing with clock, is *semidynamic*.\n\n__Discrete vs. continuous__: Chess has *finite* number of distinct states and discrete set of percepts and moves. Taxi driving is continuous-state and continuous-time. Input from camera is discrete but continuous representing varying intensities/locations.\n\n__Known vs. unknown__: Agent's state of knowledge. __Different__ from observability. *Known* environ can be *partially* observable. *Unknown* environ can be *fully observable* (In video games, screen shows entire game state but you don't know what buttons do yet).\nAnother example, driver does not know what *driving style* customer prefers.\n\n__Hardest case__ is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. ie. Taxi driving (but environ is mostly known). Driving rented car in new country with unfamiliar geography, traffic laws, and nervous passengers.\n\n\n## AIMA 2.4 The Structure of Agents\n Engineer job: design __agent program__ that implements agent function.\n\n$$agent = architecture + program$$\n\nKey challenge to AI is to find programs that produces rational behavior *from smallish* program rather than vast exhaustive table.\n\nSome __types__ of agent programs: simple reflex agents, model-based, goal-based, utility-based.\n\n__Simple reflex__ is based on __condition-action rule__ ie. If car infront is braking then also brakes. Correct decision can be made just be current percept (only if environ is __fully observable__; just a little of unobservability can be serious).\n\n__Model-based__ helps deal with partial observability, parts of the world can yet see. Model means __internal state__ built from percept history.\n\n__Goal-based__ requires goal information describing desirable destination. __Search & planning__ help find action sequences that achieve agent's goals.\n\n__Utility-based__ is internalization of performance measure and own __\"happiness\"__.\n\nAll agents can improve performance through __learning__.\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Value alignment problem** - agreement between true *human* preferences and objectives put into machine \n* **Provably beneficial** - we want agents useful to human\n* **Weak ai** - idea that machine can act *as if* intelligent\n* **Strong ai** - machines *actually* think consciously\n* **Gofai** - Good Old-Fashioned AI that 'cannot produce durable results'\n* **Agent** - anything that can perceive its environment through __sensors__ and act through __actuators__\n* **Percept** - content perceived by agent's sensors\n* **Percept sequence** - complete history of everything agent has ever perceived\n* **Agent function** - maps any percept sequence to action\n* **Consequentialism** - evaluate agent's behavior by consequences\n* **Information gathering** - Doing action to modify future percept\n* **Deterministic** - If next state of environ is completely determined by current state AND agent executes action; given inputs = given outputs\n* **Stochastic** - Deals explicitly with probabilities, can be equivalent to non-deterministic\n* **Dynamic** - Environ can change while agent is deliberating\n* **Semidynamic** - If environ is does not change with time but agent's performan score does\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Nature: easy & intuitive language just as powerful as others, open source, understandable as English, suitability for everday tasks. Named after Monty Python.\n",
        "\n",
        "*Tuples*, *strings* are __immutable__. Dictionaries are unordered, work by hashing so keys must be immutable. __defaultdict__ and __Counter__ initializes non existent dict values.\n",
        "\n",
        "No function overloading like Java, which allows methods with same name. __Operator overloading__ is possible with special class methods.\n",
        "\n",
        "Functions are __first-class__objects: dynamiccally created, destroyed, passed to function, returned as values, other rights. *Higher order* functions take functions as input.\n",
        "\n",
        "```\n",
        "def compose(f, g, x): \n",
        "  return f(g(x))\n",
        "```\n",
        "\n",
        "Class can __extend__ definition of another class. To define *subclass*, put name of superclass in parentheses after subclass's name on first line of definition.\n",
        "\n",
        "```\n",
        "class AI_Student(Student):\n",
        "  fav = \"CIS 521\n",
        "```\n",
        "\n",
        "Class has \"magic\" methods: `__init__`, `__str__` (pretty printing), `__len__` (how len(obj) works), `__copy__`, `__cmp__` (how == works for class), `__add__` (how + works), `__neg__` (how negation works)\n",
        "\n",
        "Main method is `__main__`. Usually goes along with `__name__`, special variable.\n",
        "\n",
        "```\n",
        "if __name__=='__main__':\n",
        "```\n",
        "\n",
        "List & set comprehension (fast efficient one liner): `[a for a in list]`\n",
        "\n",
        "__Iterator objects__ have `__iter__` magic method. Its looping is made possible with `__next__()` method. Uses memory efficiently.\n",
        "\n",
        "__Generators__ are iterators that automatically get generated by `yield`. Benefits: Less code than standard iterator, maintains local state, values computed one at a time, good for aggregating, avoids storage of entire sequence, crucial for inifinite sequences.\n",
        "__Drawback__: Bad if we need to inspect individual values.\n",
        "\n",
        "```\n",
        "g = merge([2, 4], [1, 3, 5])  # output is [1,2,3,4,5]\n",
        "while True:\n",
        "   try:\n",
        "     print(g.__next__())\n",
        "   except StopIteration:\n",
        "     print(\"Done\")\n",
        "     break\n",
        "```\n",
        "\n",
        "List of functions is valid:\n",
        "`[add, sub]`\n",
        "\n",
        "\n",
        "__Facts__:\n",
        "\n",
        "Hash function takes message of arbitrary length and generates fixed length code (hashing/decoding a message).\n",
        "\n",
        "Mathematical operations can be perforamed on string.\n",
        "\n",
        "Tuple can be created without parentheses.\n",
        "\n",
        "TRUE: Function can take __unlimited__ number of arguments.\n",
        "\n",
        "`list[::]` means a deep copy.\n",
        "\n",
        "TRUE: Adding dicts can generate error. Different types of dict keys also generate error.\n",
        "\n",
        "__String__ are immutable, so `a='1,2,3'; a[1]='a'` generates error.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"author\": \"Guido van Rossum\",\n",
        "\"year\": \"1989\"\n",
        "}"
      ],
      "execution_count": 106,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b98d1fdd-0eaf-465d-a0a5-b79227733441"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 107,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Nature: easy & intuitive language just as powerful as others, open source, understandable as English, suitability for everday tasks. Named after Monty Python.\n\n*Tuples*, *strings* are __immutable__. Dictionaries are unordered, work by hashing so keys must be immutable. __defaultdict__ and __Counter__ initializes non existent dict values.\n\nNo function overloading like Java, which allows methods with same name. __Operator overloading__ is possible with special class methods.\n\nFunctions are __first-class__objects: dynamiccally created, destroyed, passed to function, returned as values, other rights. *Higher order* functions take functions as input.\n\n```\ndef compose(f, g, x): \n  return f(g(x))\n```\n\nClass can __extend__ definition of another class. To define *subclass*, put name of superclass in parentheses after subclass's name on first line of definition.\n\n```\nclass AI_Student(Student):\n  fav = \"CIS 521\n```\n\nClass has \"magic\" methods: `__init__`, `__str__` (pretty printing), `__len__` (how len(obj) works), `__copy__`, `__cmp__` (how == works for class), `__add__` (how + works), `__neg__` (how negation works)\n\nMain method is `__main__`. Usually goes along with `__name__`, special variable.\n\n```\nif __name__=='__main__':\n```\n\nList & set comprehension (fast efficient one liner): `[a for a in list]`\n\n__Iterator objects__ have `__iter__` magic method. Its looping is made possible with `__next__()` method. Uses memory efficiently.\n\n__Generators__ are iterators that automatically get generated by `yield`. Benefits: Less code than standard iterator, maintains local state, values computed one at a time, good for aggregating, avoids storage of entire sequence, crucial for inifinite sequences.\n__Drawback__: Bad if we need to inspect individual values.\n\n```\ng = merge([2, 4], [1, 3, 5])  # output is [1,2,3,4,5]\nwhile True:\n   try:\n     print(g.__next__())\n   except StopIteration:\n     print(\"Done\")\n     break\n```\n\nList of functions is valid:\n`[add, sub]`\n\n\n__Facts__:\n\nHash function takes message of arbitrary length and generates fixed length code (hashing/decoding a message).\n\nMathematical operations can be perforamed on string.\n\nTuple can be created without parentheses.\n\nTRUE: Function can take __unlimited__ number of arguments.\n\n`list[::]` means a deep copy.\n\nTRUE: Adding dicts can generate error. Different types of dict keys also generate error.\n\n__String__ are immutable, so `a='1,2,3'; a[1]='a'` generates error.\n\n\n\n## Module 2 Definitions\n* **Author** - Guido van Rossum\n* **Year** - 1989\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" In *fully observable, deterministic, known* environment, solution to any problem is fixed sequence of actions. \n",
        "Search problem can be defined as: __state space__ of possible states, __initial__ state, set of __goal states__, __actions__ available to the agent, __transition model__ that outputs\n",
        "results from doing action $a$ in state $s$, and __action cost function__ reflecting performance measure.\n",
        "\n",
        "Sequence of actions forms a path, and solution is path from initial to goal state.\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Problem examples... \"\"\"\n",
        "chapter3_3 = \"\"\" Search algo takes search problem as input and returns solution.\n",
        "\n",
        "__Best-first search__: choosing a node with minimum value of some *eval function*, *f(n)*. Return if state is goal, otherwise expand child nodes and add to frontier if has not been seen.\n",
        "\n",
        "__Redundant paths__: memorize previously reached states, BUT can also ignore it in limited memory space.\n",
        "__Graph search__ checks for redundant path, while __tree search_ does not (however, graph search is __faster__ since it sacrifices memory for time). \n",
        "We can compromise and just check for *cycle*.\n",
        "\n",
        "Measure performance: completeness (can solution be found and errors if not?), cost optimality, time & space complexity. Must be __systematic__ about it.\n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" __Breadth-first search (BFS)__ is *complete* even on infinite state spaces. Can be implemented as call to Best-first search where eval function *f(n)$ is depth of the node (number of actions).\n",
        "Here, FIFO beats priority queue. Can use __early goal test__ to check whether nodesis solution *as soon as* it is generated, rather __late goal test__ which waits until node gets popped off queue.\n",
        "\n",
        "BFS *always* guarantees minimum number of actions in output. Time & space complexity is $O(b^d)$. Drawback is memory! *Memory requiremwnts* are bigger probleme for BFS than *execution time*/\n",
        "\n",
        "__Dijkstra's__ algo is form of __uniform-cost search__, which spreads out in waves of uniform path cost (rather than waves of uniform depth). UCS is both *complete* and *cost-optimal*.\n",
        "Complexity is in terms of $C^*$, cost of optimal solution, and $\\in$, lower bound on cost of each action. Worst-case is $O(b^{1+[C^*/\\in]})$, likely __much__ greater than $b^d$\n",
        "When all action costs are equal, UCS = BFS.\n",
        "\n",
        "__Depth-first search (DFS)__ expands *deepest* node in frontier first. Can be implemented as call to Best-first where eval function $f$ is negative of the depth. *Usually* implemented as __tree-like search__ that forgets visited states.\n",
        "Proceeds to deepest level where nodes have no successors, then \"back up\" to next deepest node with unexpanded successors.\n",
        "\n",
        "DFS does not optimize for number of options, only returns first solution even though __not cheapest__. For finite state spaces that are trees, DFS is *efficient* and *complete*. In cycle spaces, can get in infinite loop.\n",
        "Generally, DFS is __incomplete__, but __memory-efficient__.\n",
        "\n",
        "Time complex $O(b^m)$. Memory complexity $O(bm)$, where *b* is branching factor and *m* is max depth.\n",
        "\n",
        "__Backtracking search__ is a variant that uses less memory. DFS is useful for CSPs,...\n",
        "\n",
        "__Depth-limited search__ limits depth $l$. Time complexity $O(b^l)$; space complexity $O(bl)$. Poor $l$ choice will be incomplete. Good depth limit requires *knowledge of problem*.\n",
        "\n",
        "__Iterative deepening search__ solves problem of picking good $l$ value by trying all starting from 0 until either solution is found or depth return *failure value* (rather than cutoff).\n",
        "*Combination* of BFS and DFS. Time complex $O(b^d)$ when solution exists, $O(bm)$ when none.\n",
        "\n",
        "TRUE: DFS in general has higher space complexity than iterative deepening.\n",
        "\n",
        "__Bidirectional search__ simultaneously starts forward from initial state and backwards from goal state. Motivation is $b^{d/2}+b^{d/2}$ is much less than $b^d$.\n",
        "Requires keeping track of 2 frontiers, 2 tables of visited states, and abiltiy to reason backwards. Time & space complex $O(b^{d/2})$.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "\"optimal solution\": \"Lowest path cost among all solutions\",\n",
        "\"frontier\": \"Where potential successors are put aside for later (ie. queue, stack)\",\n",
        "\"priority queue\": \"Pops node w/ minimum cost according to *f*, used in best-first search\",\n",
        "\"LIFO\": \"pops most recently added node __first__\",\n",
        "\"cycle\": \"Repeated state in search tree, special case of *redundant path*\",\n",
        "\"diameter\": \"Good depth limit chosen for depth-limited search by being informed about the game\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 108,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6fb8c5e9-fbee-4a3d-dbf5-da8d0e835467"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 109,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In *fully observable, deterministic, known* environment, solution to any problem is fixed sequence of actions. \nSearch problem can be defined as: __state space__ of possible states, __initial__ state, set of __goal states__, __actions__ available to the agent, __transition model__ that outputs\nresults from doing action $a$ in state $s$, and __action cost function__ reflecting performance measure.\n\nSequence of actions forms a path, and solution is path from initial to goal state.\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Problem examples... \n\n## AIMA Chapter 3.3 Search Algorithms\n Search algo takes search problem as input and returns solution.\n\n__Best-first search__: choosing a node with minimum value of some *eval function*, *f(n)*. Return if state is goal, otherwise expand child nodes and add to frontier if has not been seen.\n\n__Redundant paths__: memorize previously reached states, BUT can also ignore it in limited memory space.\n__Graph search__ checks for redundant path, while __tree search_ does not (however, graph search is __faster__ since it sacrifices memory for time). \nWe can compromise and just check for *cycle*.\n\nMeasure performance: completeness (can solution be found and errors if not?), cost optimality, time & space complexity. Must be __systematic__ about it.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n __Breadth-first search (BFS)__ is *complete* even on infinite state spaces. Can be implemented as call to Best-first search where eval function *f(n)$ is depth of the node (number of actions).\nHere, FIFO beats priority queue. Can use __early goal test__ to check whether nodesis solution *as soon as* it is generated, rather __late goal test__ which waits until node gets popped off queue.\n\nBFS *always* guarantees minimum number of actions in output. Time & space complexity is $O(b^d)$. Drawback is memory! *Memory requiremwnts* are bigger probleme for BFS than *execution time*/\n\n__Dijkstra's__ algo is form of __uniform-cost search__, which spreads out in waves of uniform path cost (rather than waves of uniform depth). UCS is both *complete* and *cost-optimal*.\nComplexity is in terms of $C^*$, cost of optimal solution, and $\\in$, lower bound on cost of each action. Worst-case is $O(b^{1+[C^*/\\in]})$, likely __much__ greater than $b^d$\nWhen all action costs are equal, UCS = BFS.\n\n__Depth-first search (DFS)__ expands *deepest* node in frontier first. Can be implemented as call to Best-first where eval function $f$ is negative of the depth. *Usually* implemented as __tree-like search__ that forgets visited states.\nProceeds to deepest level where nodes have no successors, then \"back up\" to next deepest node with unexpanded successors.\n\nDFS does not optimize for number of options, only returns first solution even though __not cheapest__. For finite state spaces that are trees, DFS is *efficient* and *complete*. In cycle spaces, can get in infinite loop.\nGenerally, DFS is __incomplete__, but __memory-efficient__.\n\nTime complex $O(b^m)$. Memory complexity $O(bm)$, where *b* is branching factor and *m* is max depth.\n\n__Backtracking search__ is a variant that uses less memory. DFS is useful for CSPs,...\n\n__Depth-limited search__ limits depth $l$. Time complexity $O(b^l)$; space complexity $O(bl)$. Poor $l$ choice will be incomplete. Good depth limit requires *knowledge of problem*.\n\n__Iterative deepening search__ solves problem of picking good $l$ value by trying all starting from 0 until either solution is found or depth return *failure value* (rather than cutoff).\n*Combination* of BFS and DFS. Time complex $O(b^d)$ when solution exists, $O(bm)$ when none.\n\nTRUE: DFS in general has higher space complexity than iterative deepening.\n\n__Bidirectional search__ simultaneously starts forward from initial state and backwards from goal state. Motivation is $b^{d/2}+b^{d/2}$ is much less than $b^d$.\nRequires keeping track of 2 frontiers, 2 tables of visited states, and abiltiy to reason backwards. Time & space complex $O(b^{d/2})$.\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Optimal solution** - Lowest path cost among all solutions\n* **Frontier** - Where potential successors are put aside for later (ie. queue, stack)\n* **Priority queue** - Pops node w/ minimum cost according to *f*, used in best-first search\n* **Lifo** - pops most recently added node __first__\n* **Cycle** - Repeated state in search tree, special case of *redundant path*\n* **Diameter** - Good depth limit chosen for depth-limited search by being informed about the game\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Heuristic made possible by being *informed*.\n",
        "\n",
        "__Greedy best-first search__, form of best-first, expands first node with lowest $h(n)$ (appeared closest to goal), with the optimism that chosen node leads to solution quickly.\n",
        "So eval function $f(n)=h(n)$.\n",
        "\n",
        "In route-finding, __straight-line distance__ heuristic. Solution found is __not cost optimal__ (fewest actions) BUT closest in terms of chosen heuristic.\n",
        "Best-case: $O(bm)$.\n",
        "\n",
        "__$A^*$ search__ uses eval function $f(n) = g(n) + h(n)$, where $g(n)$ is path cost from initial state to node $n$, $h(n)$ is estimated cost of shortest path from $n$ to goal state.\n",
        "\n",
        "$A^*$ is complete, requires optimistic and admissible heuristic.\n",
        "\n",
        "Heuristic $h(n)$ is consistent if for every node $n$ and successor $n'$ generated by action $a$, we have $h(n) \\leq cost(n,a,n') + h(n')$.\n",
        "This is __triangle inequality__. If heuristic is consistent, then single number $h(n)$ is less than sum of cost $c(n,a,n')$ and $h(n')$.\n",
        "\n",
        "With consistent heuristic, A* is __cost optimal__. With inadmissible heuristic, A* may not be cost-optimal. Additionally, A* is efficient for pruning away unnecessary tree node.\n",
        "\n",
        "__Bidirectional $A^*$__ is sometimes more efficient than $A^*$ itself.\n",
        "\n",
        "__IDA*__ (iterative deepening A* search), __RBFS__ (recursive best-first search), __SMA*__ (simplified memory-bounded A*) are robust, optimal search algo\n",
        "that use limited memory.\n",
        "\n",
        "__Beam search__ puts limit on size of frontier, making it incomplete and suboptimal. However, it *often* finds good solutions & runs faster than complete searches.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\" Choosing high *quality* heuristic means having __effective branching factor $b^$__. In \"8-puzzle\" game, *h(n)* can be __misplaced tiles__ or __Manhattan distance__.\n",
        "$h_2$ is better than $h_1$ if for any node $n$, $h_2(n) \\geq h_1(n)$. This means $h_2$ __dominates__ $h_1$.\n",
        "\n",
        "Addtionally, $h_2$ is also better if __effective branching factor__ $b^*$ also improves.\n",
        "\n",
        "When problem is *relaxed*, any optimal solution to original problem is also a solution to the relaxed. But __relaxed can have better solutions if added edges provide shortcuts__.\n",
        "Cost of optimal solution to relaxed is *admissible heuristic* to original problem.\n",
        "\n",
        "__Pattern databases__ stores exact solution costs for every possible subproblem instance.\n",
        "\n",
        "Generating heuristics with landmarks.\n",
        "....\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"$h(n)$\" : \"__estimated__ cost of cheapest path from state at node $n$ to goal state\",\n",
        "\"relaxed problem\": \"problem with fewer restrictions on actions\",\n",
        "\"admissibility\": \"one that *never* overestimates cost to reach a goal; *optimistic*\",\n",
        "\"search contour\": \"way to visualize a search\",\n",
        "\"monotonic\": \"cost of path always increases as one extends along a path\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 110,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 969
        },
        "cellView": "form",
        "outputId": "bf093975-0586-4a11-d921-ccb7b2c0c9c4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 111,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Heuristic made possible by being *informed*.\n\n__Greedy best-first search__, form of best-first, expands first node with lowest $h(n)$ (appeared closest to goal), with the optimism that chosen node leads to solution quickly.\nSo eval function $f(n)=h(n)$.\n\nIn route-finding, __straight-line distance__ heuristic. Solution found is __not cost optimal__ (fewest actions) BUT closest in terms of chosen heuristic.\nBest-case: $O(bm)$.\n\n__$A^*$ search__ uses eval function $f(n) = g(n) + h(n)$, where $g(n)$ is path cost from initial state to node $n$, $h(n)$ is estimated cost of shortest path from $n$ to goal state.\n\n$A^*$ is complete, requires optimistic and admissible heuristic.\n\nHeuristic $h(n)$ is consistent if for every node $n$ and successor $n'$ generated by action $a$, we have $h(n) \\leq cost(n,a,n') + h(n')$.\nThis is __triangle inequality__. If heuristic is consistent, then single number $h(n)$ is less than sum of cost $c(n,a,n')$ and $h(n')$.\n\nWith consistent heuristic, A* is __cost optimal__. With inadmissible heuristic, A* may not be cost-optimal. Additionally, A* is efficient for pruning away unnecessary tree node.\n\n__Bidirectional $A^*$__ is sometimes more efficient than $A^*$ itself.\n\n__IDA*__ (iterative deepening A* search), __RBFS__ (recursive best-first search), __SMA*__ (simplified memory-bounded A*) are robust, optimal search algo\nthat use limited memory.\n\n__Beam search__ puts limit on size of frontier, making it incomplete and suboptimal. However, it *often* finds good solutions & runs faster than complete searches.\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Choosing high *quality* heuristic means having __effective branching factor $b^$__. In \"8-puzzle\" game, *h(n)* can be __misplaced tiles__ or __Manhattan distance__.\n$h_2$ is better than $h_1$ if for any node $n$, $h_2(n) \\geq h_1(n)$. This means $h_2$ __dominates__ $h_1$.\n\nAddtionally, $h_2$ is also better if __effective branching factor__ $b^*$ also improves.\n\nWhen problem is *relaxed*, any optimal solution to original problem is also a solution to the relaxed. But __relaxed can have better solutions if added edges provide shortcuts__.\nCost of optimal solution to relaxed is *admissible heuristic* to original problem.\n\n__Pattern databases__ stores exact solution costs for every possible subproblem instance.\n\nGenerating heuristics with landmarks.\n....\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **$h(n)$** - __estimated__ cost of cheapest path from state at node $n$ to goal state\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Admissibility** - one that *never* overestimates cost to reach a goal; *optimistic*\n* **Search contour** - way to visualize a search\n* **Monotonic** - cost of path always increases as one extends along a path\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" 3 stances for multi-agent environment: First, an__economy__ with supply/demand to understand how everyone will act. \n",
        "Second, consider adversarial agents as environment parts that make it nondeterministic.\n",
        "Third, explicitly model agents using adversarial game-tree search.\n",
        "\n",
        "Eval functions can be used to estimate who is currently winning.\n",
        "\n",
        "Chess/Go are *deterministic, two-player, turn-taking, perfect info, zero-sum* games.\n",
        "\n",
        "Two players MAX, MIN. First mover is MAX. Formal definition:\n",
        "\n",
        "* $S_0$: Initial state\n",
        "\n",
        "* TO-MOVE(s): Player whose turn it is to move in state $s\n",
        "\n",
        "* ACTIONS(s): Set of legal moves in state $s$\n",
        "\n",
        "* RESULT(s, a): Transition model\n",
        "\n",
        "* IS-TERMINAL (s): Is game over?\n",
        "\n",
        "* UTILITY (s,p): Utility function which defines numeric value for player $p$ when game ends in terminal state $s$\n",
        "\n",
        "Together, initial states, ACTIONS function, RESULT function define a __state space graph__ where vertices are states, edges are moves, and state can be reach from multiple paths.\n",
        "Though a graph, can __superimpose__ serach tree over a part to determine what move to make.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" Minimax is recursive DFS that proceeds all the way down to the leaves of the tree, then BACKS UP following minimax.\n",
        "\n",
        "Time complexity: $O(b^m)$\n",
        "\n",
        "Space complexity: $O(bm)$ for algo that generates actions all at once, $O(m)$ for algo that generates one at a time, where b is branching, m is maximum depth.\n",
        "\n",
        "```\n",
        "function minimax_search(game,state):\n",
        "  player = game.TO-MOVE(state)\n",
        "  value, move = MAX-VALUE(game, state)\n",
        "  return move\n",
        "\n",
        "function max_value(game, state):\n",
        "  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n",
        "  v = -inf\n",
        "  for a in game.ACTIONS(state):\n",
        "    v2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 > v:\n",
        "      v, move = v2, a\n",
        "  return v, move\n",
        "\n",
        "function min_value(game, state):\n",
        "  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n",
        "  v = +inf\n",
        "  for a in game.ACTIONS(state):\n",
        "    v2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 > v:\n",
        "      v, move = v2, a\n",
        "  return v, move\n",
        "```\n",
        "\n",
        "Alpha-beta pruning can cut depth number of game states $b^m$ in half, meaning pruning space to $O(b^{m/2}$ at best (using iterative deepning first to sort could help). $\\alpha$ is highest-value found so far at any point along path for MAX (at least). $\\beta$ is lowest-valye found so far at any point along path for MIN (at most).\n",
        "\n",
        "$\\alpha$: \"lower bound\" highest value for MAX found so far.\n",
        "\n",
        "$\\beta$: \"higher bound\" lowest value for MIN found so far.\n",
        "\n",
        "Branches get pruned from left to right, so __order__ in which states examine matters.\n",
        "\n",
        "Adding dynamic move-ordering schemes can improve performance such as __iterative deepening__, searching one ply deep and ranking moves based on evaluations.\n",
        "Move ordercing can __more than__ make up for added search time, as we can find __killer moves__ (or best moves).\n",
        "\n",
        "Even with pruning & move ordering, Minimax does not work for all games, such as \"Chess\" and \"Go\" where too many states exist.\n",
        "\n",
        "Other explorative moves are __Type A vs. Type B__ strategies. Type A is *wide but shallow* (consder all moves to certain depth), Type B is *deep but narrow* (look for promising path first).\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" To make use of limited computation time, cut off search early and apply heuristic eval function to states to evaluate their utilities. Alternatively, \"Cutoff test\" returns True for terminal but decides when to cut off the search.\n",
        "\n",
        "$Eval(s,p)$ returns estimated expected utility of state $s$ to player $p$, similar to how heuristic returns estiamte of distance to the goal. For terminal, $ Eval(s,p)=UTILITY(s,p)$.\n",
        "For non-terminal, $UTILITY(loss,p) \\leq Eval(s,p) \\leq UTILITY(win,p)$.\n",
        "\n",
        "What makes good Eval function? First, not too long! Second, be strongly correlated with chances of winning (ie. number of chess left vs. opponent's). \"Expected value\" can be acceptable eval function for states.\n",
        "\n",
        "__Cutting off search__ can be used to manipulate search by imposing fixed depth limit. \n",
        "\n",
        "```\n",
        "if game.IS-CUTOFF(state, depth): return game.EVAL(state, player), null\n",
        "```\n",
        "\n",
        "Should only be applied to __quiescent__ states, meaning having no pending moves that \"wildly\" swing evaluation.\n",
        "For __non-quiescent__ eval function returns False and continues to find quiescent.\n",
        "\n",
        "When program is facing an opposing move that is unavoidable, damaging, unavoidable, they are suck in __horizon effect__.\n",
        "A strategy to mitigate horizon effect is to allow __singular extensions__, moves that are better than all other moves even when search would normally be cut off.\n",
        "Essentially, *stalling* by trying extra moves.\n",
        "\n",
        "__Forward puning__ prunes moves that *appear* poor but might be actually good, sacrificing computation time to limit risks of making errors (__Type B__ strategy).\n",
        "Some techniques include __Beam Search, Late Move Reduction__ (only works under assumption that move ordering is done well -- moves appear later in list are less likely to be good).\n",
        "\n",
        "\n",
        "__Lookup vs. Search__ speaks to how game could end based purely on producing policy rather than running any actual search.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" __Stochastic games__ introduce probability by including randomness. Calculate __expected value__ of a position and build up to __Expectiminimax value__.\n",
        "It is important to have evaluation function that returns values that are a *positive linear transformation* of probability of winning.\n",
        "Both probabilities of each action AND expecti-minimax values are included in minimax tree for Stochastic.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Agent assigns probability $P(s)$ to each possible current state.\n",
        "\n",
        "Transition model becomes $P(s'|s,a)$, probability that action $a$ in state $s$ reaches state $s'$.\n",
        "\n",
        "$P(RESULT(a)==s') = \\sum_s P(s) P(s' | s, a)$\n",
        "\n",
        "Addtionallly, agent's preferences are captured by __utility function__ $U(s)$\n",
        "\n",
        "__Maximum expected utility (MEU)__ says rational agent should choose action that maximizes expected utility. \n",
        "*\"If agent [does this], they achieve highest possible performance score (averaged over possible environments)\"*.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" MEU is not the only rational way. Could agent act rationally just by prefering one state over another (non-numeric)? Could they just try to minimize __loss__?\n",
        "\n",
        "Constraints on preferences:\n",
        "\n",
        "* $A \\succ B$ (succeed symbol): Agent prefers A over B\n",
        "\n",
        "* $A \\sim B$: agent is indifferent\n",
        "\n",
        "* $A \\succ \\sim B$: agent prefers A over B OR is indifferent\n",
        "\n",
        "Set of outcomes as __lottery__, each action as __ticket__.\n",
        "\n",
        "$L = [p_1, S_1; p_2, S_2; ... p_n; S_n]$\n",
        "\n",
        "There are 6 constraints required of any reasonable preference:\n",
        "\n",
        "1. Orderability: Rational agent must prefer one of two lotteries OR rate them as equally preferable\n",
        "\n",
        "2. Transitivity: If agent prefers A to B, and B to C, then agent prefers A to C\n",
        "\n",
        "3. Continuity: If some lottery B is between A and C in preference, then there is probability $p$ for which agent will be indifferent between getting B and lottery that yields A with probability $p$ and C with prob $1-p$\n",
        "\n",
        "4. Substitutability: If agent is indifferent between lotteries A and B then agent is indifferent between 2 more complex lotteries that are the same except B is substituted for A in one of them\n",
        "\n",
        "5. Monotonicity: When A and B are the same outcomes, if agent prefers A to B, then agent must prefer lottery with higher probability for A.\n",
        "\n",
        "6. Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability.\n",
        "\n",
        "These constraints are *axioms* of utility theory. An agent that violates an axiom will exhibit __irrational behavior__ in some situations.\n",
        "\n",
        "Utility theory are about __preferences__ and say *nothing* about utility function.\n",
        "\n",
        "__Existence of Utility Function__: If agent preferences obey axioms of utility, then there exists $U$ such that $U(A) > U(B)$ iff A is preferred to B and $U(A)=U(B)$ if indifferent.\n",
        "\n",
        "__Expected Utility of a Lottery__: Sum of probability of each outcome $\\times$ utility of the outcome.\n",
        "\n",
        "In deterministic environ, agent __needs only preference ranking on states__, numbers don't matter. This is called __value function__ or __ordinal util function__.\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" Utility functions map loterries to real numbers.\n",
        "\n",
        "If we want to build decision-theoretic system that acts on human behalf, we must know what the utility function is. __Preference elicitation__ means using observed preferences to pin down util function.\n",
        "\n",
        "__Normalized utilities__ scale values in range [0,1].\n",
        "\n",
        "Agencies in the US (FDA, EPA) use __value of a statistical life__ to determine costs and benefits of regulations/interventions. \n",
        "\n",
        "A common unit is __micromort__, one in million chance of death. Another measure is __QALY__, quality-adjusted life year.\n",
        "\n",
        "Money as utility. Agent exhibits __monotonic preference__ for more money, meaning agent prefers more money to less.\n",
        "\n",
        "Under __S-shaped utility curve__, if only focuses on positive part, for any lottery $L$, utility of being faced with lottery is less than utility of being handed expected monetary value: $U(L) < U(S_{EM(L)})$.\n",
        "\n",
        "Agents with S-curves are __risk-averse__, since they prefer sure thing with payoff less than expected monetary value (EMV) of a gample.\n",
        "\n",
        "On the other hand, at large negatives, behavior is __risk-seeking__.\n",
        "\n",
        "Value an agent will accept in lieu of lottery is __certainty equivalent__. People will accept 400 dollars instead of playing in a gamle that gives 1000 half the time and 0 dollars the other half.\n",
        "Here, certainty equivalent=400, EMV=500.\n",
        "\n",
        "In real world, true expected utility is hard to compute. We usually work with __estimated__ EU. \n",
        "We assume that our estimate is __unbiased__, meaning expected value of error $E[\\hat{EU}(a) - EU(a)] = 0$.\n",
        "\n",
        "__Optimizer's curse__: tendency for estimated utility of best choice to be too high.\n",
        "\n",
        "__Normative vs. descriptive theory__ is how a rational agent *should* act vs. how actual agents *do* act. Sometimes humans are irrational, so __certainty effect__, people are strongly attracted to *certain* gains.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect info\" : \"fully observable\",\n",
        "\"zero-sum\": \"good for one, bad for another\",\n",
        "\"move\": \"action\",\n",
        "\"position\": \"state\",\n",
        "\"transpositions\": \"cause of repeated states -- different permutations of move sequence ended in same position\",\n",
        "\"horizon effect\": \"arises when program faces opposing move that causes serious damage and unavoidable (trapped Queen), but can be stalled\",\n",
        "\"quiescent\": \"positions for which no pending move (such as capturing queen) that widly swing eval\",\n",
        "\"lottery\": \"way to think of possible outcomes $S_n$ with probabilities $p_n$\",\n",
        "\"preference elicitation\": \"presenting choices to human and use observe preferences to find $U$ utility function\",\n",
        "\"expected monetary value (EMV)\": \"expected value of tossing fair coin to win money\",\n",
        "\"insurance premium\": \"difference between lottery EMV and its certainty equivalent\",\n",
        "\"ambiguity aversion\": \"human irrationality; choosing known probability over unknown probability even though known is *bad*\",\n",
        "\"framing effect\": \"human irrationality; how wording of decision problem impacts agent's choices\",\n",
        "\"anchoring effect\": \"feels more comfortable making *relative* utility judgements rather than absolute ones\",\n",
        "\"Evolutionary pyschology\": \"human decision-making is not evolved enough to solve problems with probabilities and decimals\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 112,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2acc555d-e250-45c9-caa0-590778cb98f4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 113,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n 3 stances for multi-agent environment: First, an__economy__ with supply/demand to understand how everyone will act. \nSecond, consider adversarial agents as environment parts that make it nondeterministic.\nThird, explicitly model agents using adversarial game-tree search.\n\nEval functions can be used to estimate who is currently winning.\n\nChess/Go are *deterministic, two-player, turn-taking, perfect info, zero-sum* games.\n\nTwo players MAX, MIN. First mover is MAX. Formal definition:\n\n* $S_0$: Initial state\n\n* TO-MOVE(s): Player whose turn it is to move in state $s\n\n* ACTIONS(s): Set of legal moves in state $s$\n\n* RESULT(s, a): Transition model\n\n* IS-TERMINAL (s): Is game over?\n\n* UTILITY (s,p): Utility function which defines numeric value for player $p$ when game ends in terminal state $s$\n\nTogether, initial states, ACTIONS function, RESULT function define a __state space graph__ where vertices are states, edges are moves, and state can be reach from multiple paths.\nThough a graph, can __superimpose__ serach tree over a part to determine what move to make.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax is recursive DFS that proceeds all the way down to the leaves of the tree, then BACKS UP following minimax.\n\nTime complexity: $O(b^m)$\n\nSpace complexity: $O(bm)$ for algo that generates actions all at once, $O(m)$ for algo that generates one at a time, where b is branching, m is maximum depth.\n\n```\nfunction minimax_search(game,state):\n  player = game.TO-MOVE(state)\n  value, move = MAX-VALUE(game, state)\n  return move\n\nfunction max_value(game, state):\n  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n  v = -inf\n  for a in game.ACTIONS(state):\n    v2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v:\n      v, move = v2, a\n  return v, move\n\nfunction min_value(game, state):\n  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n  v = +inf\n  for a in game.ACTIONS(state):\n    v2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n    if v2 > v:\n      v, move = v2, a\n  return v, move\n```\n\nAlpha-beta pruning can cut depth number of game states $b^m$ in half, meaning pruning space to $O(b^{m/2}$ at best (using iterative deepning first to sort could help). $\u0007lpha$ is highest-value found so far at any point along path for MAX (at least). $\beta$ is lowest-valye found so far at any point along path for MIN (at most).\n\n$\u0007lpha$: \"lower bound\" highest value for MAX found so far.\n\n$\beta$: \"higher bound\" lowest value for MIN found so far.\n\nBranches get pruned from left to right, so __order__ in which states examine matters.\n\nAdding dynamic move-ordering schemes can improve performance such as __iterative deepening__, searching one ply deep and ranking moves based on evaluations.\nMove ordercing can __more than__ make up for added search time, as we can find __killer moves__ (or best moves).\n\nEven with pruning & move ordering, Minimax does not work for all games, such as \"Chess\" and \"Go\" where too many states exist.\n\nOther explorative moves are __Type A vs. Type B__ strategies. Type A is *wide but shallow* (consder all moves to certain depth), Type B is *deep but narrow* (look for promising path first).\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of limited computation time, cut off search early and apply heuristic eval function to states to evaluate their utilities. Alternatively, \"Cutoff test\" returns True for terminal but decides when to cut off the search.\n\n$Eval(s,p)$ returns estimated expected utility of state $s$ to player $p$, similar to how heuristic returns estiamte of distance to the goal. For terminal, $ Eval(s,p)=UTILITY(s,p)$.\nFor non-terminal, $UTILITY(loss,p) \\leq Eval(s,p) \\leq UTILITY(win,p)$.\n\nWhat makes good Eval function? First, not too long! Second, be strongly correlated with chances of winning (ie. number of chess left vs. opponent's). \"Expected value\" can be acceptable eval function for states.\n\n__Cutting off search__ can be used to manipulate search by imposing fixed depth limit. \n\n```\nif game.IS-CUTOFF(state, depth): return game.EVAL(state, player), null\n```\n\nShould only be applied to __quiescent__ states, meaning having no pending moves that \"wildly\" swing evaluation.\nFor __non-quiescent__ eval function returns False and continues to find quiescent.\n\nWhen program is facing an opposing move that is unavoidable, damaging, unavoidable, they are suck in __horizon effect__.\nA strategy to mitigate horizon effect is to allow __singular extensions__, moves that are better than all other moves even when search would normally be cut off.\nEssentially, *stalling* by trying extra moves.\n\n__Forward puning__ prunes moves that *appear* poor but might be actually good, sacrificing computation time to limit risks of making errors (__Type B__ strategy).\nSome techniques include __Beam Search, Late Move Reduction__ (only works under assumption that move ordering is done well -- moves appear later in list are less likely to be good).\n\n\n__Lookup vs. Search__ speaks to how game could end based purely on producing policy rather than running any actual search.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n __Stochastic games__ introduce probability by including randomness. Calculate __expected value__ of a position and build up to __Expectiminimax value__.\nIt is important to have evaluation function that returns values that are a *positive linear transformation* of probability of winning.\nBoth probabilities of each action AND expecti-minimax values are included in minimax tree for Stochastic.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent assigns probability $P(s)$ to each possible current state.\n\nTransition model becomes $P(s'|s,a)$, probability that action $a$ in state $s$ reaches state $s'$.\n\n$P(RESULT(a)==s') = \\sum_s P(s) P(s' | s, a)$\n\nAddtionallly, agent's preferences are captured by __utility function__ $U(s)$\n\n__Maximum expected utility (MEU)__ says rational agent should choose action that maximizes expected utility. \n*\"If agent [does this], they achieve highest possible performance score (averaged over possible environments)\"*.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n MEU is not the only rational way. Could agent act rationally just by prefering one state over another (non-numeric)? Could they just try to minimize __loss__?\n\nConstraints on preferences:\n\n* $A \\succ B$ (succeed symbol): Agent prefers A over B\n\n* $A \\sim B$: agent is indifferent\n\n* $A \\succ \\sim B$: agent prefers A over B OR is indifferent\n\nSet of outcomes as __lottery__, each action as __ticket__.\n\n$L = [p_1, S_1; p_2, S_2; ... p_n; S_n]$\n\nThere are 6 constraints required of any reasonable preference:\n\n1. Orderability: Rational agent must prefer one of two lotteries OR rate them as equally preferable\n\n2. Transitivity: If agent prefers A to B, and B to C, then agent prefers A to C\n\n3. Continuity: If some lottery B is between A and C in preference, then there is probability $p$ for which agent will be indifferent between getting B and lottery that yields A with probability $p$ and C with prob $1-p$\n\n4. Substitutability: If agent is indifferent between lotteries A and B then agent is indifferent between 2 more complex lotteries that are the same except B is substituted for A in one of them\n\n5. Monotonicity: When A and B are the same outcomes, if agent prefers A to B, then agent must prefer lottery with higher probability for A.\n\n6. Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability.\n\nThese constraints are *axioms* of utility theory. An agent that violates an axiom will exhibit __irrational behavior__ in some situations.\n\nUtility theory are about __preferences__ and say *nothing* about utility function.\n\n__Existence of Utility Function__: If agent preferences obey axioms of utility, then there exists $U$ such that $U(A) > U(B)$ iff A is preferred to B and $U(A)=U(B)$ if indifferent.\n\n__Expected Utility of a Lottery__: Sum of probability of each outcome $\times$ utility of the outcome.\n\nIn deterministic environ, agent __needs only preference ranking on states__, numbers don't matter. This is called __value function__ or __ordinal util function__.\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map loterries to real numbers.\n\nIf we want to build decision-theoretic system that acts on human behalf, we must know what the utility function is. __Preference elicitation__ means using observed preferences to pin down util function.\n\n__Normalized utilities__ scale values in range [0,1].\n\nAgencies in the US (FDA, EPA) use __value of a statistical life__ to determine costs and benefits of regulations/interventions. \n\nA common unit is __micromort__, one in million chance of death. Another measure is __QALY__, quality-adjusted life year.\n\nMoney as utility. Agent exhibits __monotonic preference__ for more money, meaning agent prefers more money to less.\n\nUnder __S-shaped utility curve__, if only focuses on positive part, for any lottery $L$, utility of being faced with lottery is less than utility of being handed expected monetary value: $U(L) < U(S_{EM(L)})$.\n\nAgents with S-curves are __risk-averse__, since they prefer sure thing with payoff less than expected monetary value (EMV) of a gample.\n\nOn the other hand, at large negatives, behavior is __risk-seeking__.\n\nValue an agent will accept in lieu of lottery is __certainty equivalent__. People will accept 400 dollars instead of playing in a gamle that gives 1000 half the time and 0 dollars the other half.\nHere, certainty equivalent=400, EMV=500.\n\nIn real world, true expected utility is hard to compute. We usually work with __estimated__ EU. \nWe assume that our estimate is __unbiased__, meaning expected value of error $E[\\hat{EU}(a) - EU(a)] = 0$.\n\n__Optimizer's curse__: tendency for estimated utility of best choice to be too high.\n\n__Normative vs. descriptive theory__ is how a rational agent *should* act vs. how actual agents *do* act. Sometimes humans are irrational, so __certainty effect__, people are strongly attracted to *certain* gains.\n\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect info** - fully observable\n* **Zero-sum** - good for one, bad for another\n* **Move** - action\n* **Position** - state\n* **Transpositions** - cause of repeated states -- different permutations of move sequence ended in same position\n* **Horizon effect** - arises when program faces opposing move that causes serious damage and unavoidable (trapped Queen), but can be stalled\n* **Quiescent** - positions for which no pending move (such as capturing queen) that widly swing eval\n* **Lottery** - way to think of possible outcomes $S_n$ with probabilities $p_n$\n* **Preference elicitation** - presenting choices to human and use observe preferences to find $U$ utility function\n* **Expected monetary value (emv)** - expected value of tossing fair coin to win money\n* **Insurance premium** - difference between lottery EMV and its certainty equivalent\n* **Ambiguity aversion** - human irrationality; choosing known probability over unknown probability even though known is *bad*\n* **Framing effect** - human irrationality; how wording of decision problem impacts agent's choices\n* **Anchoring effect** - feels more comfortable making *relative* utility judgements rather than absolute ones\n* **Evolutionary pyschology** - human decision-making is not evolved enough to solve problems with probabilities and decimals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" CSPs consist of 3 components:\n",
        "\n",
        "1) $X$: set of variables $\\{X_1,...,X_n\\}$\n",
        "\n",
        "2) $D$: set of domains $\\{D_1,...,D_n\\}$\n",
        "\n",
        "3) $C$: set of constrainst specifying allowable combinations of values.\n",
        "\n",
        "In details, $C_j$ are pairs of <*scope, rel*> where *scope* is tuple of variables in the constrainsts and $rel$ is relation that defines allowable values.\n",
        "If $X_1$ and $X_2$ have domain $\\{1,2,3\\}$ and constraints that $X_1 > X_2$, then relation is <$(X_1, X_2), \\{(3,1),(3,2),(2,1)\\}$>.\n",
        "CSPS deal with __assignments__ of values to variables. *Complete* assignment is one that assigns all variables (vs. *partial*). *Consistent* assignment is one that does not violate constrainsts.\n",
        "\n",
        "In map coloring example, we have variables $\\{WA, NT, Q, NSW, V, SA, T\\}$ and $\\{red, green, blue\\}$.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" __Inference in CSPS__, or constraint propagation, is using constraints to reduce number of legal values for variable (reducing domains in Sudoku).\n",
        "\n",
        "__Node consistency__ of single variable happens if all values in variable's domain satisfy unary constrainst, meaning reducing each variable domain by itself at the start (ie. Eliminate *color green* from the choices if nobody like green).\n",
        "\n",
        "__Arc consistency__ happens if every value in domain satisfies binary constraints (ie. Sudoku game). *AC-3* is example, where we iteratively revises $D_i$ and adds it to the beginning of the Queue - then do this until every domain is reduced to size 1.\n",
        "If not, domain=0 means solution *does not exist*.\n",
        "Time complexity of a single arc is $O(d^2)$, so $O(cd^3)$ is total worst-case time.\n",
        "\n",
        "__Path consistency__ tightens binary constraints by looking at *triples of variables* (stronger than arc consistent).\n",
        "\n",
        "__K-consistency__ is for any set of $k-1$ variables and for any consistent assignments, consistent value is assinged to $k$th variable. Also called \"strongly k-consistent\".\n",
        "Total run time is $O(n^2 \\cdot d)$.\n",
        "\n",
        "Constraint satifaction is NP-complete, any algo for establishing n-consistency must take time exponential in $n$ in the worst case. Also, might require that space is exponential in $n$.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking Search for CSPs is made possible with the __commutativity__ property, meaning order of set of actions does not matter (ie. considering $red$ or $blue$ first).\n",
        "\n",
        "How it works: Repeatedly chooses unassigned variable -> tries all values in domain of that variable -> extend each one into solution via recursive call -> If call succeeds, soltions returns; If not, assignment is restored to previous state and try next value.\n",
        "Note: Backtracking keeps only a __single__ representation and alters rather than creating new ones.\n",
        "\n",
        "In backtracking, `var = select_unassigned_Variable(csp, assignment)` chooses the next variable with fewest legal move, called \"minimum-remaining-values (MRV) heuristic.\n",
        "Same idea as \"fail-first\" heuristic since variable chosen first can reach 0. For MRV, __degree heuristic__, choosing variable whose options appear the most in other, can be tiebreaker.\n",
        "\n",
        "Once a var is selected, which value/option should be examined first? __Least-constrainsing-value__ heuristic rules out value with fewest choices for neighboring variables, leaving maximum flexibility for subsequent assignments.\n",
        "\n",
        "So variable selection (cell) __fail-first__, BUT value selection (options) __fail-last__ because the first helps backtracking faster, while the second reduce solution to one quicker.\n",
        "\n",
        "AC-3 reduces domains *before* the search, but we can *also* do inference! __Forward Checking__ assigns variable $X$ AND establish arc consistency at the same time. \n",
        "But FC is not as good as MAC (__Maintaining Arc Consistency__) because it does not look far ahead enough.\n",
        "\n",
        "Backjumping occurs when every value in domain is in conflict with current assignment; but forward checking detects such event and prevents search from reaching such a node!\n",
        "\n",
        "__Contrainst learning__: finding minimum set of variables from conflict set that causes the problem (the set is called __no-good__).\n",
        "No-goods can be used by forward checking or backjumping.\n",
        "\"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" Local search algo seach as __min-conflicts__ heuristic, selecting value with minimum number of conflicts with other vars, can be effective. \n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"*Structure* of problems can be used to find quick solutions:\n",
        "\n",
        "Breaking down tree into __independent subproblems__\n",
        "\n",
        "__Cutset Conditioning__ reduces constraint graph to a tree by assigning values to some vars so that remaining vars form a tree (linear memory).\n",
        "\n",
        "__Tree decomposition__ transforms CSP into tree of subproblems; efficient if *tree width* of constraint graph is small. With $w$ width, then time complexity is $O(nd^{w+1})$.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"CSP variables can be *discrete* or *continuous*.\n",
        "\n",
        "*Preference* (*red* is better than *green* ) can be __soft constraints__ represented by cost for each variable assignment.\n",
        "\n",
        "CSP can be expressed as search problem:\n",
        "\n",
        "* Initial state: empty assignment\n",
        "\n",
        "* Successor function: assign value to unassigned variable without constraint conflict\n",
        "\n",
        "* Goal test: current assignment is complete\n",
        "\n",
        "* Path cost: constant cost for every step\n",
        "\n",
        "Branching factor at root is $n*d$. At next level is $(n-1)*d$. Tree has $n!*d^n$ leaves, where $n$ is variables and $d$ is domain size.\n",
        "\n",
        "Depth-first search (uninformed) can be used! In CSP, DFS with single-variable assignments is called __backtracking__ search.\n",
        "This means algo uses DFS to choose one var at a time and backtracks when variable has not values left to assign.\n",
        "\n",
        "Heuristics can be used to improve efficiency:\n",
        "\n",
        "1. Choose variable with fewest legal values (MRV)\n",
        "\n",
        "2. Choose most constraining variable (one with most constraints on remaining variables)\n",
        "\n",
        "3. Choose least constraining value (rules out fewest values in remaining variables)\n",
        "\n",
        "4. __Forward checking__: keep track of remaining legal values for *unassigned* variables. Terminate search when domain of any reduced to zero (__AC3 & arc consistency__)\n",
        "\n",
        "__Cons_: Forward checking does not provide early detection for failures! __Constraint propagation__ can do this by also repeatedly enforces constraints locally.\n",
        "\n",
        "$Arc(i, j)$ is arc consistent iff every value $v$ on $X_i$ is consistent with some label on $Y_j$.\n",
        "\n",
        "In worst case, $O(d^2)$ time.\n",
        "\n",
        "```\n",
        "function AC-3(csp) return the CSP, possibly with reduced domains\n",
        "  inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\n",
        "  local variables: queue, a queue of arcs initially the arcs in csp\n",
        "  while queue is not empty do\n",
        "    (Xi, Xj) ¬queue.pop()\n",
        "    if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n",
        "      for each Xk in NEIGHBORS[Xi ] – {Xj} do \n",
        "        add (Xk, Xi) to queue \n",
        "\n",
        "function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n",
        "  removed ¬false\n",
        "  for each x in DOMAIN[Xi] do\n",
        "    if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n",
        "    then delete x from DOMAIN[Xi]; removed ¬true\n",
        "  return removed\n",
        "```\n",
        "\n",
        "Worst case complexity is $O(n^2 d^3)$ since each arc(i,j) can be inserted into queue $d$ times\n",
        "\n",
        "\"\"\"\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"unary constraints\": \"constraints that involve single variable\",\n",
        "\"binary constraints\": \"constraints that involve pairs of variables\",\n",
        "\"higher-order constraints\": \"constraints that invole 3 or more variables\",\n",
        "\"cycle cutset\": \"choosing subset $S$ for CSP variables so that constraint graph becomes tree after removal of $S$ (SA in the middle)\"\n",
        "}\n"
      ],
      "execution_count": 114,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c5d8e2c9-e772-43af-ebf3-817ea8212d85"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 115,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSPs consist of 3 components:\n\n1) $X$: set of variables $\\{X_1,...,X_n\\}$\n\n2) $D$: set of domains $\\{D_1,...,D_n\\}$\n\n3) $C$: set of constrainst specifying allowable combinations of values.\n\nIn details, $C_j$ are pairs of <*scope, rel*> where *scope* is tuple of variables in the constrainsts and $rel$ is relation that defines allowable values.\nIf $X_1$ and $X_2$ have domain $\\{1,2,3\\}$ and constraints that $X_1 > X_2$, then relation is <$(X_1, X_2), \\{(3,1),(3,2),(2,1)\\}$>.\nCSPS deal with __assignments__ of values to variables. *Complete* assignment is one that assigns all variables (vs. *partial*). *Consistent* assignment is one that does not violate constrainsts.\n\nIn map coloring example, we have variables $\\{WA, NT, Q, NSW, V, SA, T\\}$ and $\\{red, green, blue\\}$.\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n __Inference in CSPS__, or constraint propagation, is using constraints to reduce number of legal values for variable (reducing domains in Sudoku).\n\n__Node consistency__ of single variable happens if all values in variable's domain satisfy unary constrainst, meaning reducing each variable domain by itself at the start (ie. Eliminate *color green* from the choices if nobody like green).\n\n__Arc consistency__ happens if every value in domain satisfies binary constraints (ie. Sudoku game). *AC-3* is example, where we iteratively revises $D_i$ and adds it to the beginning of the Queue - then do this until every domain is reduced to size 1.\nIf not, domain=0 means solution *does not exist*.\nTime complexity of a single arc is $O(d^2)$, so $O(cd^3)$ is total worst-case time.\n\n__Path consistency__ tightens binary constraints by looking at *triples of variables* (stronger than arc consistent).\n\n__K-consistency__ is for any set of $k-1$ variables and for any consistent assignments, consistent value is assinged to $k$th variable. Also called \"strongly k-consistent\".\nTotal run time is $O(n^2 \\cdot d)$.\n\nConstraint satifaction is NP-complete, any algo for establishing n-consistency must take time exponential in $n$ in the worst case. Also, might require that space is exponential in $n$.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search for CSPs is made possible with the __commutativity__ property, meaning order of set of actions does not matter (ie. considering $red$ or $blue$ first).\n\nHow it works: Repeatedly chooses unassigned variable -> tries all values in domain of that variable -> extend each one into solution via recursive call -> If call succeeds, soltions returns; If not, assignment is restored to previous state and try next value.\nNote: Backtracking keeps only a __single__ representation and alters rather than creating new ones.\n\nIn backtracking, `var = select_unassigned_Variable(csp, assignment)` chooses the next variable with fewest legal move, called \"minimum-remaining-values (MRV) heuristic.\nSame idea as \"fail-first\" heuristic since variable chosen first can reach 0. For MRV, __degree heuristic__, choosing variable whose options appear the most in other, can be tiebreaker.\n\nOnce a var is selected, which value/option should be examined first? __Least-constrainsing-value__ heuristic rules out value with fewest choices for neighboring variables, leaving maximum flexibility for subsequent assignments.\n\nSo variable selection (cell) __fail-first__, BUT value selection (options) __fail-last__ because the first helps backtracking faster, while the second reduce solution to one quicker.\n\nAC-3 reduces domains *before* the search, but we can *also* do inference! __Forward Checking__ assigns variable $X$ AND establish arc consistency at the same time. \nBut FC is not as good as MAC (__Maintaining Arc Consistency__) because it does not look far ahead enough.\n\nBackjumping occurs when every value in domain is in conflict with current assignment; but forward checking detects such event and prevents search from reaching such a node!\n\n__Contrainst learning__: finding minimum set of variables from conflict set that causes the problem (the set is called __no-good__).\nNo-goods can be used by forward checking or backjumping.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algo seach as __min-conflicts__ heuristic, selecting value with minimum number of conflicts with other vars, can be effective. \n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n*Structure* of problems can be used to find quick solutions:\n\nBreaking down tree into __independent subproblems__\n\n__Cutset Conditioning__ reduces constraint graph to a tree by assigning values to some vars so that remaining vars form a tree (linear memory).\n\n__Tree decomposition__ transforms CSP into tree of subproblems; efficient if *tree width* of constraint graph is small. With $w$ width, then time complexity is $O(nd^{w+1})$.\n\n\n## Module 6 Lecture Notes\nCSP variables can be *discrete* or *continuous*.\n\n*Preference* (*red* is better than *green* ) can be __soft constraints__ represented by cost for each variable assignment.\n\nCSP can be expressed as search problem:\n\n* Initial state: empty assignment\n\n* Successor function: assign value to unassigned variable without constraint conflict\n\n* Goal test: current assignment is complete\n\n* Path cost: constant cost for every step\n\nBranching factor at root is $n*d$. At next level is $(n-1)*d$. Tree has $n!*d^n$ leaves, where $n$ is variables and $d$ is domain size.\n\nDepth-first search (uninformed) can be used! In CSP, DFS with single-variable assignments is called __backtracking__ search.\nThis means algo uses DFS to choose one var at a time and backtracks when variable has not values left to assign.\n\nHeuristics can be used to improve efficiency:\n\n1. Choose variable with fewest legal values (MRV)\n\n2. Choose most constraining variable (one with most constraints on remaining variables)\n\n3. Choose least constraining value (rules out fewest values in remaining variables)\n\n4. __Forward checking__: keep track of remaining legal values for *unassigned* variables. Terminate search when domain of any reduced to zero (__AC3 & arc consistency__)\n\n__Cons_: Forward checking does not provide early detection for failures! __Constraint propagation__ can do this by also repeatedly enforces constraints locally.\n\n$Arc(i, j)$ is arc consistent iff every value $v$ on $X_i$ is consistent with some label on $Y_j$.\n\nIn worst case, $O(d^2)$ time.\n\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\n  inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\n  local variables: queue, a queue of arcs initially the arcs in csp\n  while queue is not empty do\n    (Xi, Xj) ¬queue.pop()\n    if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n      for each Xk in NEIGHBORS[Xi ] – {Xj} do \n        add (Xk, Xi) to queue \n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n  removed ¬false\n  for each x in DOMAIN[Xi] do\n    if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n    then delete x from DOMAIN[Xi]; removed ¬true\n  return removed\n```\n\nWorst case complexity is $O(n^2 d^3)$ since each arc(i,j) can be inserted into queue $d$ times\n\n\n\n## Module 6 Definitions\n* **Unary constraints** - constraints that involve single variable\n* **Binary constraints** - constraints that involve pairs of variables\n* **Higher-order constraints** - constraints that invole 3 or more variables\n* **Cycle cutset** - choosing subset $S$ for CSP variables so that constraint graph becomes tree after removal of $S$ (SA in the middle)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" KB is a set of __sentences__, each expressed in __knowledge representation language__ and represents assertion about the world.\n",
        "TELL and ASK help add new knowledge and query what is known. Both may involve *inference* to derive new sentences from old. Knowledge-based agent program inputs *percept* and outputs *action*.\n",
        "\n",
        "*Declarative vs. Procedural* approaches. First means start with empty KB -> TELL sentences one by one until agent knows how to operate. Second means encoding desired behavior as program code.\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" Wumpus world is cave consisting of rooms connected by passageways. PEAS:\n",
        "\n",
        "__1) Performance measure__: +1000 for finding gold &c climbing out, -1000 for failling into pit/getting eaten by Wumpus, -1 for each action taken, -10 for using up arrow (to kill wumpus)\n",
        "\n",
        "__2) Environment__: A 4x4 grid of rooms. Agent starts bottom left [1,1] facing east. Locations of gold & wumpus are chosen uniformly at random. Each square other than START can be pit with Pr=0.2\n",
        "\n",
        "__3) Actuators__: Actions include forward, turn left, turn right. Climb can be used to get out of cave but only from [1,1]\n",
        "\n",
        "__4) Sensors__: 5 sensors. When adjacent (not diagonal) to wumpus, smells \"stench\". When adjacent to put, perceives \"breeze\". When at gold square, perceive \"glitter\". When into wall, perceive \"bump\". When wumpus is killed, it \"screams\" for whole cave.\n",
        "\n",
        "Percepts can be [Stench, Breeze, None, None, None].\n",
        "\n",
        "Characs: deterministic, discrete, static, single-agent.\n",
        "\n",
        "Example: Agent smells stench in [1,2], meaning wumpus is nearby. But cannot be in [1,1] by rule of game, and cannot be in [2,2] (or would have detected stench when in [2,1]) -> Infer that wumpus is in [1,3].\n",
        "This is a *difficult* inference, combining knowledge gained different times in different places. All *logical reasoning*.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\" ...\n",
        "\n",
        "__Logical entailment__ means sentence follows logically from another sentence. $A\\models B$ if in every model which A is true, B is also true. If notated $A\\subseteq B$ then A is *stronger assertion* than B.\n",
        "\n",
        "If inference algo $i$ derives A from KB, then $KB\\models A$ and A is drived from KB by i.\n",
        "\n",
        "Inference algo that derives only entailed sentence is __sounds__ or __truth preserving__. Desirable to check model for soundness and __completeness__, meaning an inference algo is only complete if it can derive any sentence that is entailed.\n",
        "Another factor to consider is __grounding__. KB *may not* be true in the real world, so __learning__ procedure is important.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" __Atomic__ sentences consist of a *single* proposition symbol. Possible to connect more with __logical connectives__: $\\\\neg$ (not), $\\\\vee$ (or), $\\wedge$ (and), $\\Rightarrow$ (implies), $\\Leftrightarrow$ (biconditional)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" Entailment can be done by __theorem proving__, applying rules of inference directly to setences in KB.\n",
        "\n",
        "__Conjunctive normal form__ (CNF):\n",
        "\n",
        "1) Replace $A \\Leftrightarrow B$ with $(A\\Rightarrow B) \\wedge (B\\Rightarrow A)$\n",
        "\n",
        "2) Replace $A\\Rightarrow B$ with $\\\\neg A\\\\vee B$ \n",
        "\n",
        "3) Move $\\\\neg$ inward through *double-negation* and *De Morgan*\n",
        "\n",
        "4) Apply *distributivity law* to distribute $\\\\vee$ over $\\wedge$\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"axiom\" : \"when sentence is taken as given without being derived from other sentences\",\n",
        "\"grounding\": \"connection between logical reasoning processes and real environment in which agent exists\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 116,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f87e0d2e-b1a5-4175-eec1-f9d2ea42ee47"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 117,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n KB is a set of __sentences__, each expressed in __knowledge representation language__ and represents assertion about the world.\nTELL and ASK help add new knowledge and query what is known. Both may involve *inference* to derive new sentences from old. Knowledge-based agent program inputs *percept* and outputs *action*.\n\n*Declarative vs. Procedural* approaches. First means start with empty KB -> TELL sentences one by one until agent knows how to operate. Second means encoding desired behavior as program code.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world is cave consisting of rooms connected by passageways. PEAS:\n\n__1) Performance measure__: +1000 for finding gold &c climbing out, -1000 for failling into pit/getting eaten by Wumpus, -1 for each action taken, -10 for using up arrow (to kill wumpus)\n\n__2) Environment__: A 4x4 grid of rooms. Agent starts bottom left [1,1] facing east. Locations of gold & wumpus are chosen uniformly at random. Each square other than START can be pit with Pr=0.2\n\n__3) Actuators__: Actions include forward, turn left, turn right. Climb can be used to get out of cave but only from [1,1]\n\n__4) Sensors__: 5 sensors. When adjacent (not diagonal) to wumpus, smells \"stench\". When adjacent to put, perceives \"breeze\". When at gold square, perceive \"glitter\". When into wall, perceive \"bump\". When wumpus is killed, it \"screams\" for whole cave.\n\nPercepts can be [Stench, Breeze, None, None, None].\n\nCharacs: deterministic, discrete, static, single-agent.\n\nExample: Agent smells stench in [1,2], meaning wumpus is nearby. But cannot be in [1,1] by rule of game, and cannot be in [2,2] (or would have detected stench when in [2,1]) -> Infer that wumpus is in [1,3].\nThis is a *difficult* inference, combining knowledge gained different times in different places. All *logical reasoning*.\n\n\n\n## AIMA Chapter 7.3 Logic\n ...\n\n__Logical entailment__ means sentence follows logically from another sentence. $A\\models B$ if in every model which A is true, B is also true. If notated $A\\subseteq B$ then A is *stronger assertion* than B.\n\nIf inference algo $i$ derives A from KB, then $KB\\models A$ and A is drived from KB by i.\n\nInference algo that derives only entailed sentence is __sounds__ or __truth preserving__. Desirable to check model for soundness and __completeness__, meaning an inference algo is only complete if it can derive any sentence that is entailed.\nAnother factor to consider is __grounding__. KB *may not* be true in the real world, so __learning__ procedure is important.\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n __Atomic__ sentences consist of a *single* proposition symbol. Possible to connect more with __logical connectives__: $\\neg$ (not), $\\vee$ (or), $\\wedge$ (and), $\\Rightarrow$ (implies), $\\Leftrightarrow$ (biconditional)\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Entailment can be done by __theorem proving__, applying rules of inference directly to setences in KB.\n\n__Conjunctive normal form__ (CNF):\n\n1) Replace $A \\Leftrightarrow B$ with $(A\\Rightarrow B) \\wedge (B\\Rightarrow A)$\n\n2) Replace $A\\Rightarrow B$ with $\\neg A\\vee B$ \n\n3) Move $\\neg$ inward through *double-negation* and *De Morgan*\n\n4) Apply *distributivity law* to distribute $\\vee$ over $\\wedge$\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Axiom** - when sentence is taken as given without being derived from other sentences\n* **Grounding** - connection between logical reasoning processes and real environment in which agent exists\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "8039083d-a897-49ac-c0c9-facc1122af2c"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 118,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Rationality ~ intelligence ~ doing right thing. *Human vs. rational* and *though vs. behavior*.\n\n__Turing test__ helps answers \"Can machine thinks\". __Total Turing test__ additionally requires *interaction* with objects & people in real world (CV, robotics).\n\nHow to know how human thinks: instropection (reflecting on own thoughts), psychological experiments (observing human in action), brain imaging (observing brain in action).\n\nLogical thinking requires *certain* knowledge of the world, othewise *probability* is required.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n *Argument from disability* is claim that \"machine can __never__ do X\": being kind, beautiful, friendly, humerous, falls in love, enjoys ice cream. Programs can __exceed__ human performance in some tasks but lag behind on others.\n\nOne thing, they cannot be *exactly* human.\n\n__Mathematical objection__ comes from Turing & Godel, who prove certain math questions are *unanswerable* by formal systems by principle. \n\nSome arguments against Godel's incompleteness theorem.\nFirst, agents should not be ashamed if it establishes truth of some sentences that others can.\nSecond, theorem applies to *mathematics*, __not__ to computers. But both humans and machines __cannot__ prove things impossible to prove (humans cannot get around limits).\nThird, theorem was only proven on systems that can only do arithmetic.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n  \nTuring says we never have *any* direct evidence about internal mental states of other humans, so would be a __polite convention__ to assume that everyone *thinks*.\n\nPhilosopher Searle rejects \"polite convention\" by stating __Chinese room__: Image only-English-speaker human sitting inside room, copies Chinese characters and passes the papers back outside.\nHuman does not understand any Chinese but still outputs, which is exactly what the computer would do. Just __symbol manipulation__, no brain.\nSearle is proponent of __biological naturalism__, meaning mental states are high-level emergent features caused by low-level physical process in *neurons*.\n\n__Consciousness__: awareness of outside world, self, and subjective experience of living. __Qualia__ is intrinsic nature of experiences. Turing thinks consciousness has __little__ to do with practice of AI.\nOnly interested in modeling *intelligent behavior*, some *awareness*.\n\nTuring operationalizes the \"Can machines think\" question: Are there imaginable digital computers which would do well in *imitation game*?\"\n\n\n## AIMA 2.1 Agents and Environments\n __Agent function vs. agent program__ is abstract mathematical depscription versus agent program of concrete implementation run on *physical* system.\n\nVacumn cleaner example...\n\nTRUE: __Touchless faucets__ can also be viewed as agent.\n\nFALSE: Agent's choice of action at given instant depends both on percept sequence and future perceptual inputs (it does not have to).\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n __Rational agent__is one that does the right thing. Notion \"right thing\" is equivalent to performance measures.\nBetter to design measures according to what we want, not how we think *an agent* should behave.\n\nExample: Vacumn cleaner agent is awarded one point for each square cleaned at step over \"lifetime\" 1000 steps. Geography of environment is *priori* but dirt distribution/initial agent location is not.\nOnly available actions are *Right, Left, Suck*. Agent perceives if location contains dirt.\n\nCircumtances above make agent __rational__, but when all dirt is cleaned up -> agent oscillate back and forth -> __irrational__.\n\n__Rationality vs. Omniscience__: Omniscient agent knows *actual* outcome of actions and act accordingly. It is usually __impossible__ in reality.\nRationality $\\neq$ perfection, maximizing expected performance up *to date* $\\neq$ perfecting *actual* performance. __Rationality is not omniscience (guaranteed success)__.\n\n\nIn extreme, environment is *priori* and completely predictable, does not learn anything but simply acts correctly. But can be *fragile*.\nIf reliant too much on prior rather than self-learned percepts, agent __lacks autonomy__.\n\n\n## AIMA 2.3 The Nature of Environments\n Specifying __task environment__ with PEAS: Performance measure, Environment, Actuators, Sensors. ie. Taxi driver, software agent trading on auction/reselling (complex agent)...\n\n__Rational agent__ means for each possible percept sequence, rational agent selects action expected to maximize performance measure, given evidence provided by percept sequence & built-in knowledge,\n\n__Fully vs. Partially observable__: Fully observable is *convenient* because agent needs not maintain any internal state to keep track of world. Partial might be due to noisy or inaccurate sensors or missing states (vacumn does not know if dirt is in a other squares).\nIf agent has *no sensors*, then environment is __unobservable__.\n\n__Single vs. multi-agent__: Solving puzzle vs. playing chess. *Chess* is __competitive__ multiagent environment. In taxi-driving, avoiding collisions maximizes performance measure, so driving taxi is partially __cooperative__ multiagent environ.\n\nAgent needs not worry about uncertainty in fully observable, deterministic environ. Partially observable environ can *appear* non-deterministic. Taxi driving is *non-deterministic* because traffic is unpredictable. Vacumn world is deterministic but if dirt __randomly appears__ then becomes non-deter.\n\n__Episodic vs. sequential__: In episodic, agent experience divided into *atomic* episodes, in each agent receives percept to perform single action (ie. independent classsification tasks). \nIn sequential, current desicions *affect* future decisions.\n\n__Static vs. dynamic__: Dynamic environ constantly asks agent what it wants to do. __Semidynamic__ happens when agent's performance score changes. Taxi driving is dynamic. Chess, when playing with clock, is *semidynamic*.\n\n__Discrete vs. continuous__: Chess has *finite* number of distinct states and discrete set of percepts and moves. Taxi driving is continuous-state and continuous-time. Input from camera is discrete but continuous representing varying intensities/locations.\n\n__Known vs. unknown__: Agent's state of knowledge. __Different__ from observability. *Known* environ can be *partially* observable. *Unknown* environ can be *fully observable* (In video games, screen shows entire game state but you don't know what buttons do yet).\nAnother example, driver does not know what *driving style* customer prefers.\n\n__Hardest case__ is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. ie. Taxi driving (but environ is mostly known). Driving rented car in new country with unfamiliar geography, traffic laws, and nervous passengers.\n\n\n## AIMA 2.4 The Structure of Agents\n Engineer job: design __agent program__ that implements agent function.\n\n$$agent = architecture + program$$\n\nKey challenge to AI is to find programs that produces rational behavior *from smallish* program rather than vast exhaustive table.\n\nSome __types__ of agent programs: simple reflex agents, model-based, goal-based, utility-based.\n\n__Simple reflex__ is based on __condition-action rule__ ie. If car infront is braking then also brakes. Correct decision can be made just be current percept (only if environ is __fully observable__; just a little of unobservability can be serious).\n\n__Model-based__ helps deal with partial observability, parts of the world can yet see. Model means __internal state__ built from percept history.\n\n__Goal-based__ requires goal information describing desirable destination. __Search & planning__ help find action sequences that achieve agent's goals.\n\n__Utility-based__ is internalization of performance measure and own __\"happiness\"__.\n\nAll agents can improve performance through __learning__.\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Value alignment problem** - agreement between true *human* preferences and objectives put into machine \n* **Provably beneficial** - we want agents useful to human\n* **Weak ai** - idea that machine can act *as if* intelligent\n* **Strong ai** - machines *actually* think consciously\n* **Gofai** - Good Old-Fashioned AI that 'cannot produce durable results'\n* **Agent** - anything that can perceive its environment through __sensors__ and act through __actuators__\n* **Percept** - content perceived by agent's sensors\n* **Percept sequence** - complete history of everything agent has ever perceived\n* **Agent function** - maps any percept sequence to action\n* **Consequentialism** - evaluate agent's behavior by consequences\n* **Information gathering** - Doing action to modify future percept\n* **Deterministic** - If next state of environ is completely determined by current state AND agent executes action; given inputs = given outputs\n* **Stochastic** - Deals explicitly with probabilities, can be equivalent to non-deterministic\n* **Dynamic** - Environ can change while agent is deliberating\n* **Semidynamic** - If environ is does not change with time but agent's performan score does\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Nature: easy & intuitive language just as powerful as others, open source, understandable as English, suitability for everday tasks. Named after Monty Python.\n\n*Tuples*, *strings* are __immutable__. Dictionaries are unordered, work by hashing so keys must be immutable. __defaultdict__ and __Counter__ initializes non existent dict values.\n\nNo function overloading like Java, which allows methods with same name. __Operator overloading__ is possible with special class methods.\n\nFunctions are __first-class__objects: dynamiccally created, destroyed, passed to function, returned as values, other rights. *Higher order* functions take functions as input.\n\n```\ndef compose(f, g, x): \n  return f(g(x))\n```\n\nClass can __extend__ definition of another class. To define *subclass*, put name of superclass in parentheses after subclass's name on first line of definition.\n\n```\nclass AI_Student(Student):\n  fav = \"CIS 521\n```\n\nClass has \"magic\" methods: `__init__`, `__str__` (pretty printing), `__len__` (how len(obj) works), `__copy__`, `__cmp__` (how == works for class), `__add__` (how + works), `__neg__` (how negation works)\n\nMain method is `__main__`. Usually goes along with `__name__`, special variable.\n\n```\nif __name__=='__main__':\n```\n\nList & set comprehension (fast efficient one liner): `[a for a in list]`\n\n__Iterator objects__ have `__iter__` magic method. Its looping is made possible with `__next__()` method. Uses memory efficiently.\n\n__Generators__ are iterators that automatically get generated by `yield`. Benefits: Less code than standard iterator, maintains local state, values computed one at a time, good for aggregating, avoids storage of entire sequence, crucial for inifinite sequences.\n__Drawback__: Bad if we need to inspect individual values.\n\n```\ng = merge([2, 4], [1, 3, 5])  # output is [1,2,3,4,5]\nwhile True:\n   try:\n     print(g.__next__())\n   except StopIteration:\n     print(\"Done\")\n     break\n```\n\nList of functions is valid:\n`[add, sub]`\n\n\n__Facts__:\n\nHash function takes message of arbitrary length and generates fixed length code (hashing/decoding a message).\n\nMathematical operations can be perforamed on string.\n\nTuple can be created without parentheses.\n\nTRUE: Function can take __unlimited__ number of arguments.\n\n`list[::]` means a deep copy.\n\nTRUE: Adding dicts can generate error. Different types of dict keys also generate error.\n\n__String__ are immutable, so `a='1,2,3'; a[1]='a'` generates error.\n\n\n\n## Module 2 Definitions\n* **Author** - Guido van Rossum\n* **Year** - 1989\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In *fully observable, deterministic, known* environment, solution to any problem is fixed sequence of actions. \nSearch problem can be defined as: __state space__ of possible states, __initial__ state, set of __goal states__, __actions__ available to the agent, __transition model__ that outputs\nresults from doing action $a$ in state $s$, and __action cost function__ reflecting performance measure.\n\nSequence of actions forms a path, and solution is path from initial to goal state.\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Problem examples... \n\n## AIMA Chapter 3.3 Search Algorithms\n Search algo takes search problem as input and returns solution.\n\n__Best-first search__: choosing a node with minimum value of some *eval function*, *f(n)*. Return if state is goal, otherwise expand child nodes and add to frontier if has not been seen.\n\n__Redundant paths__: memorize previously reached states, BUT can also ignore it in limited memory space.\n__Graph search__ checks for redundant path, while __tree search_ does not (however, graph search is __faster__ since it sacrifices memory for time). \nWe can compromise and just check for *cycle*.\n\nMeasure performance: completeness (can solution be found and errors if not?), cost optimality, time & space complexity. Must be __systematic__ about it.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n __Breadth-first search (BFS)__ is *complete* even on infinite state spaces. Can be implemented as call to Best-first search where eval function *f(n)$ is depth of the node (number of actions).\nHere, FIFO beats priority queue. Can use __early goal test__ to check whether nodesis solution *as soon as* it is generated, rather __late goal test__ which waits until node gets popped off queue.\n\nBFS *always* guarantees minimum number of actions in output. Time & space complexity is $O(b^d)$. Drawback is memory! *Memory requiremwnts* are bigger probleme for BFS than *execution time*/\n\n__Dijkstra's__ algo is form of __uniform-cost search__, which spreads out in waves of uniform path cost (rather than waves of uniform depth). UCS is both *complete* and *cost-optimal*.\nComplexity is in terms of $C^*$, cost of optimal solution, and $\\in$, lower bound on cost of each action. Worst-case is $O(b^{1+[C^*/\\in]})$, likely __much__ greater than $b^d$\nWhen all action costs are equal, UCS = BFS.\n\n__Depth-first search (DFS)__ expands *deepest* node in frontier first. Can be implemented as call to Best-first where eval function $f$ is negative of the depth. *Usually* implemented as __tree-like search__ that forgets visited states.\nProceeds to deepest level where nodes have no successors, then \"back up\" to next deepest node with unexpanded successors.\n\nDFS does not optimize for number of options, only returns first solution even though __not cheapest__. For finite state spaces that are trees, DFS is *efficient* and *complete*. In cycle spaces, can get in infinite loop.\nGenerally, DFS is __incomplete__, but __memory-efficient__.\n\nTime complex $O(b^m)$. Memory complexity $O(bm)$, where *b* is branching factor and *m* is max depth.\n\n__Backtracking search__ is a variant that uses less memory. DFS is useful for CSPs,...\n\n__Depth-limited search__ limits depth $l$. Time complexity $O(b^l)$; space complexity $O(bl)$. Poor $l$ choice will be incomplete. Good depth limit requires *knowledge of problem*.\n\n__Iterative deepening search__ solves problem of picking good $l$ value by trying all starting from 0 until either solution is found or depth return *failure value* (rather than cutoff).\n*Combination* of BFS and DFS. Time complex $O(b^d)$ when solution exists, $O(bm)$ when none.\n\nTRUE: DFS in general has higher space complexity than iterative deepening.\n\n__Bidirectional search__ simultaneously starts forward from initial state and backwards from goal state. Motivation is $b^{d/2}+b^{d/2}$ is much less than $b^d$.\nRequires keeping track of 2 frontiers, 2 tables of visited states, and abiltiy to reason backwards. Time & space complex $O(b^{d/2})$.\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Optimal solution** - Lowest path cost among all solutions\n* **Frontier** - Where potential successors are put aside for later (ie. queue, stack)\n* **Priority queue** - Pops node w/ minimum cost according to *f*, used in best-first search\n* **Lifo** - pops most recently added node __first__\n* **Cycle** - Repeated state in search tree, special case of *redundant path*\n* **Diameter** - Good depth limit chosen for depth-limited search by being informed about the game\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Heuristic made possible by being *informed*.\n\n__Greedy best-first search__, form of best-first, expands first node with lowest $h(n)$ (appeared closest to goal), with the optimism that chosen node leads to solution quickly.\nSo eval function $f(n)=h(n)$.\n\nIn route-finding, __straight-line distance__ heuristic. Solution found is __not cost optimal__ (fewest actions) BUT closest in terms of chosen heuristic.\nBest-case: $O(bm)$.\n\n__$A^*$ search__ uses eval function $f(n) = g(n) + h(n)$, where $g(n)$ is path cost from initial state to node $n$, $h(n)$ is estimated cost of shortest path from $n$ to goal state.\n\n$A^*$ is complete, requires optimistic and admissible heuristic.\n\nHeuristic $h(n)$ is consistent if for every node $n$ and successor $n'$ generated by action $a$, we have $h(n) \\leq cost(n,a,n') + h(n')$.\nThis is __triangle inequality__. If heuristic is consistent, then single number $h(n)$ is less than sum of cost $c(n,a,n')$ and $h(n')$.\n\nWith consistent heuristic, A* is __cost optimal__. With inadmissible heuristic, A* may not be cost-optimal. Additionally, A* is efficient for pruning away unnecessary tree node.\n\n__Bidirectional $A^*$__ is sometimes more efficient than $A^*$ itself.\n\n__IDA*__ (iterative deepening A* search), __RBFS__ (recursive best-first search), __SMA*__ (simplified memory-bounded A*) are robust, optimal search algo\nthat use limited memory.\n\n__Beam search__ puts limit on size of frontier, making it incomplete and suboptimal. However, it *often* finds good solutions & runs faster than complete searches.\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Choosing high *quality* heuristic means having __effective branching factor $b^$__. In \"8-puzzle\" game, *h(n)* can be __misplaced tiles__ or __Manhattan distance__.\n$h_2$ is better than $h_1$ if for any node $n$, $h_2(n) \\geq h_1(n)$. This means $h_2$ __dominates__ $h_1$.\n\nAddtionally, $h_2$ is also better if __effective branching factor__ $b^*$ also improves.\n\nWhen problem is *relaxed*, any optimal solution to original problem is also a solution to the relaxed. But __relaxed can have better solutions if added edges provide shortcuts__.\nCost of optimal solution to relaxed is *admissible heuristic* to original problem.\n\n__Pattern databases__ stores exact solution costs for every possible subproblem instance.\n\nGenerating heuristics with landmarks.\n....\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **$h(n)$** - __estimated__ cost of cheapest path from state at node $n$ to goal state\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Admissibility** - one that *never* overestimates cost to reach a goal; *optimistic*\n* **Search contour** - way to visualize a search\n* **Monotonic** - cost of path always increases as one extends along a path\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n 3 stances for multi-agent environment: First, an__economy__ with supply/demand to understand how everyone will act. \nSecond, consider adversarial agents as environment parts that make it nondeterministic.\nThird, explicitly model agents using adversarial game-tree search.\n\nEval functions can be used to estimate who is currently winning.\n\nChess/Go are *deterministic, two-player, turn-taking, perfect info, zero-sum* games.\n\nTwo players MAX, MIN. First mover is MAX. Formal definition:\n\n* $S_0$: Initial state\n\n* TO-MOVE(s): Player whose turn it is to move in state $s\n\n* ACTIONS(s): Set of legal moves in state $s$\n\n* RESULT(s, a): Transition model\n\n* IS-TERMINAL (s): Is game over?\n\n* UTILITY (s,p): Utility function which defines numeric value for player $p$ when game ends in terminal state $s$\n\nTogether, initial states, ACTIONS function, RESULT function define a __state space graph__ where vertices are states, edges are moves, and state can be reach from multiple paths.\nThough a graph, can __superimpose__ serach tree over a part to determine what move to make.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax is recursive DFS that proceeds all the way down to the leaves of the tree, then BACKS UP following minimax.\n\nTime complexity: $O(b^m)$\n\nSpace complexity: $O(bm)$ for algo that generates actions all at once, $O(m)$ for algo that generates one at a time, where b is branching, m is maximum depth.\n\n```\nfunction minimax_search(game,state):\n  player = game.TO-MOVE(state)\n  value, move = MAX-VALUE(game, state)\n  return move\n\nfunction max_value(game, state):\n  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n  v = -inf\n  for a in game.ACTIONS(state):\n    v2, a2 = MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v:\n      v, move = v2, a\n  return v, move\n\nfunction min_value(game, state):\n  if game.IS-TERMINAL(): return game.UTILITY(state, player), null\n  v = +inf\n  for a in game.ACTIONS(state):\n    v2, a2 = MAX-VALUE(game, game.RESULT(state, a))\n    if v2 > v:\n      v, move = v2, a\n  return v, move\n```\n\nAlpha-beta pruning can cut depth number of game states $b^m$ in half, meaning pruning space to $O(b^{m/2}$ at best (using iterative deepning first to sort could help). $\u0007lpha$ is highest-value found so far at any point along path for MAX (at least). $\beta$ is lowest-valye found so far at any point along path for MIN (at most).\n\n$\u0007lpha$: \"lower bound\" highest value for MAX found so far.\n\n$\beta$: \"higher bound\" lowest value for MIN found so far.\n\nBranches get pruned from left to right, so __order__ in which states examine matters.\n\nAdding dynamic move-ordering schemes can improve performance such as __iterative deepening__, searching one ply deep and ranking moves based on evaluations.\nMove ordercing can __more than__ make up for added search time, as we can find __killer moves__ (or best moves).\n\nEven with pruning & move ordering, Minimax does not work for all games, such as \"Chess\" and \"Go\" where too many states exist.\n\nOther explorative moves are __Type A vs. Type B__ strategies. Type A is *wide but shallow* (consder all moves to certain depth), Type B is *deep but narrow* (look for promising path first).\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of limited computation time, cut off search early and apply heuristic eval function to states to evaluate their utilities. Alternatively, \"Cutoff test\" returns True for terminal but decides when to cut off the search.\n\n$Eval(s,p)$ returns estimated expected utility of state $s$ to player $p$, similar to how heuristic returns estiamte of distance to the goal. For terminal, $ Eval(s,p)=UTILITY(s,p)$.\nFor non-terminal, $UTILITY(loss,p) \\leq Eval(s,p) \\leq UTILITY(win,p)$.\n\nWhat makes good Eval function? First, not too long! Second, be strongly correlated with chances of winning (ie. number of chess left vs. opponent's). \"Expected value\" can be acceptable eval function for states.\n\n__Cutting off search__ can be used to manipulate search by imposing fixed depth limit. \n\n```\nif game.IS-CUTOFF(state, depth): return game.EVAL(state, player), null\n```\n\nShould only be applied to __quiescent__ states, meaning having no pending moves that \"wildly\" swing evaluation.\nFor __non-quiescent__ eval function returns False and continues to find quiescent.\n\nWhen program is facing an opposing move that is unavoidable, damaging, unavoidable, they are suck in __horizon effect__.\nA strategy to mitigate horizon effect is to allow __singular extensions__, moves that are better than all other moves even when search would normally be cut off.\nEssentially, *stalling* by trying extra moves.\n\n__Forward puning__ prunes moves that *appear* poor but might be actually good, sacrificing computation time to limit risks of making errors (__Type B__ strategy).\nSome techniques include __Beam Search, Late Move Reduction__ (only works under assumption that move ordering is done well -- moves appear later in list are less likely to be good).\n\n\n__Lookup vs. Search__ speaks to how game could end based purely on producing policy rather than running any actual search.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n __Stochastic games__ introduce probability by including randomness. Calculate __expected value__ of a position and build up to __Expectiminimax value__.\nIt is important to have evaluation function that returns values that are a *positive linear transformation* of probability of winning.\nBoth probabilities of each action AND expecti-minimax values are included in minimax tree for Stochastic.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent assigns probability $P(s)$ to each possible current state.\n\nTransition model becomes $P(s'|s,a)$, probability that action $a$ in state $s$ reaches state $s'$.\n\n$P(RESULT(a)==s') = \\sum_s P(s) P(s' | s, a)$\n\nAddtionallly, agent's preferences are captured by __utility function__ $U(s)$\n\n__Maximum expected utility (MEU)__ says rational agent should choose action that maximizes expected utility. \n*\"If agent [does this], they achieve highest possible performance score (averaged over possible environments)\"*.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n MEU is not the only rational way. Could agent act rationally just by prefering one state over another (non-numeric)? Could they just try to minimize __loss__?\n\nConstraints on preferences:\n\n* $A \\succ B$ (succeed symbol): Agent prefers A over B\n\n* $A \\sim B$: agent is indifferent\n\n* $A \\succ \\sim B$: agent prefers A over B OR is indifferent\n\nSet of outcomes as __lottery__, each action as __ticket__.\n\n$L = [p_1, S_1; p_2, S_2; ... p_n; S_n]$\n\nThere are 6 constraints required of any reasonable preference:\n\n1. Orderability: Rational agent must prefer one of two lotteries OR rate them as equally preferable\n\n2. Transitivity: If agent prefers A to B, and B to C, then agent prefers A to C\n\n3. Continuity: If some lottery B is between A and C in preference, then there is probability $p$ for which agent will be indifferent between getting B and lottery that yields A with probability $p$ and C with prob $1-p$\n\n4. Substitutability: If agent is indifferent between lotteries A and B then agent is indifferent between 2 more complex lotteries that are the same except B is substituted for A in one of them\n\n5. Monotonicity: When A and B are the same outcomes, if agent prefers A to B, then agent must prefer lottery with higher probability for A.\n\n6. Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability.\n\nThese constraints are *axioms* of utility theory. An agent that violates an axiom will exhibit __irrational behavior__ in some situations.\n\nUtility theory are about __preferences__ and say *nothing* about utility function.\n\n__Existence of Utility Function__: If agent preferences obey axioms of utility, then there exists $U$ such that $U(A) > U(B)$ iff A is preferred to B and $U(A)=U(B)$ if indifferent.\n\n__Expected Utility of a Lottery__: Sum of probability of each outcome $\times$ utility of the outcome.\n\nIn deterministic environ, agent __needs only preference ranking on states__, numbers don't matter. This is called __value function__ or __ordinal util function__.\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map loterries to real numbers.\n\nIf we want to build decision-theoretic system that acts on human behalf, we must know what the utility function is. __Preference elicitation__ means using observed preferences to pin down util function.\n\n__Normalized utilities__ scale values in range [0,1].\n\nAgencies in the US (FDA, EPA) use __value of a statistical life__ to determine costs and benefits of regulations/interventions. \n\nA common unit is __micromort__, one in million chance of death. Another measure is __QALY__, quality-adjusted life year.\n\nMoney as utility. Agent exhibits __monotonic preference__ for more money, meaning agent prefers more money to less.\n\nUnder __S-shaped utility curve__, if only focuses on positive part, for any lottery $L$, utility of being faced with lottery is less than utility of being handed expected monetary value: $U(L) < U(S_{EM(L)})$.\n\nAgents with S-curves are __risk-averse__, since they prefer sure thing with payoff less than expected monetary value (EMV) of a gample.\n\nOn the other hand, at large negatives, behavior is __risk-seeking__.\n\nValue an agent will accept in lieu of lottery is __certainty equivalent__. People will accept 400 dollars instead of playing in a gamle that gives 1000 half the time and 0 dollars the other half.\nHere, certainty equivalent=400, EMV=500.\n\nIn real world, true expected utility is hard to compute. We usually work with __estimated__ EU. \nWe assume that our estimate is __unbiased__, meaning expected value of error $E[\\hat{EU}(a) - EU(a)] = 0$.\n\n__Optimizer's curse__: tendency for estimated utility of best choice to be too high.\n\n__Normative vs. descriptive theory__ is how a rational agent *should* act vs. how actual agents *do* act. Sometimes humans are irrational, so __certainty effect__, people are strongly attracted to *certain* gains.\n\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect info** - fully observable\n* **Zero-sum** - good for one, bad for another\n* **Move** - action\n* **Position** - state\n* **Transpositions** - cause of repeated states -- different permutations of move sequence ended in same position\n* **Horizon effect** - arises when program faces opposing move that causes serious damage and unavoidable (trapped Queen), but can be stalled\n* **Quiescent** - positions for which no pending move (such as capturing queen) that widly swing eval\n* **Lottery** - way to think of possible outcomes $S_n$ with probabilities $p_n$\n* **Preference elicitation** - presenting choices to human and use observe preferences to find $U$ utility function\n* **Expected monetary value (emv)** - expected value of tossing fair coin to win money\n* **Insurance premium** - difference between lottery EMV and its certainty equivalent\n* **Ambiguity aversion** - human irrationality; choosing known probability over unknown probability even though known is *bad*\n* **Framing effect** - human irrationality; how wording of decision problem impacts agent's choices\n* **Anchoring effect** - feels more comfortable making *relative* utility judgements rather than absolute ones\n* **Evolutionary pyschology** - human decision-making is not evolved enough to solve problems with probabilities and decimals\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSPs consist of 3 components:\n\n1) $X$: set of variables $\\{X_1,...,X_n\\}$\n\n2) $D$: set of domains $\\{D_1,...,D_n\\}$\n\n3) $C$: set of constrainst specifying allowable combinations of values.\n\nIn details, $C_j$ are pairs of <*scope, rel*> where *scope* is tuple of variables in the constrainsts and $rel$ is relation that defines allowable values.\nIf $X_1$ and $X_2$ have domain $\\{1,2,3\\}$ and constraints that $X_1 > X_2$, then relation is <$(X_1, X_2), \\{(3,1),(3,2),(2,1)\\}$>.\nCSPS deal with __assignments__ of values to variables. *Complete* assignment is one that assigns all variables (vs. *partial*). *Consistent* assignment is one that does not violate constrainsts.\n\nIn map coloring example, we have variables $\\{WA, NT, Q, NSW, V, SA, T\\}$ and $\\{red, green, blue\\}$.\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n __Inference in CSPS__, or constraint propagation, is using constraints to reduce number of legal values for variable (reducing domains in Sudoku).\n\n__Node consistency__ of single variable happens if all values in variable's domain satisfy unary constrainst, meaning reducing each variable domain by itself at the start (ie. Eliminate *color green* from the choices if nobody like green).\n\n__Arc consistency__ happens if every value in domain satisfies binary constraints (ie. Sudoku game). *AC-3* is example, where we iteratively revises $D_i$ and adds it to the beginning of the Queue - then do this until every domain is reduced to size 1.\nIf not, domain=0 means solution *does not exist*.\nTime complexity of a single arc is $O(d^2)$, so $O(cd^3)$ is total worst-case time.\n\n__Path consistency__ tightens binary constraints by looking at *triples of variables* (stronger than arc consistent).\n\n__K-consistency__ is for any set of $k-1$ variables and for any consistent assignments, consistent value is assinged to $k$th variable. Also called \"strongly k-consistent\".\nTotal run time is $O(n^2 \\cdot d)$.\n\nConstraint satifaction is NP-complete, any algo for establishing n-consistency must take time exponential in $n$ in the worst case. Also, might require that space is exponential in $n$.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search for CSPs is made possible with the __commutativity__ property, meaning order of set of actions does not matter (ie. considering $red$ or $blue$ first).\n\nHow it works: Repeatedly chooses unassigned variable -> tries all values in domain of that variable -> extend each one into solution via recursive call -> If call succeeds, soltions returns; If not, assignment is restored to previous state and try next value.\nNote: Backtracking keeps only a __single__ representation and alters rather than creating new ones.\n\nIn backtracking, `var = select_unassigned_Variable(csp, assignment)` chooses the next variable with fewest legal move, called \"minimum-remaining-values (MRV) heuristic.\nSame idea as \"fail-first\" heuristic since variable chosen first can reach 0. For MRV, __degree heuristic__, choosing variable whose options appear the most in other, can be tiebreaker.\n\nOnce a var is selected, which value/option should be examined first? __Least-constrainsing-value__ heuristic rules out value with fewest choices for neighboring variables, leaving maximum flexibility for subsequent assignments.\n\nSo variable selection (cell) __fail-first__, BUT value selection (options) __fail-last__ because the first helps backtracking faster, while the second reduce solution to one quicker.\n\nAC-3 reduces domains *before* the search, but we can *also* do inference! __Forward Checking__ assigns variable $X$ AND establish arc consistency at the same time. \nBut FC is not as good as MAC (__Maintaining Arc Consistency__) because it does not look far ahead enough.\n\nBackjumping occurs when every value in domain is in conflict with current assignment; but forward checking detects such event and prevents search from reaching such a node!\n\n__Contrainst learning__: finding minimum set of variables from conflict set that causes the problem (the set is called __no-good__).\nNo-goods can be used by forward checking or backjumping.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algo seach as __min-conflicts__ heuristic, selecting value with minimum number of conflicts with other vars, can be effective. \n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n*Structure* of problems can be used to find quick solutions:\n\nBreaking down tree into __independent subproblems__\n\n__Cutset Conditioning__ reduces constraint graph to a tree by assigning values to some vars so that remaining vars form a tree (linear memory).\n\n__Tree decomposition__ transforms CSP into tree of subproblems; efficient if *tree width* of constraint graph is small. With $w$ width, then time complexity is $O(nd^{w+1})$.\n\n\n## Module 6 Lecture Notes\nCSP variables can be *discrete* or *continuous*.\n\n*Preference* (*red* is better than *green* ) can be __soft constraints__ represented by cost for each variable assignment.\n\nCSP can be expressed as search problem:\n\n* Initial state: empty assignment\n\n* Successor function: assign value to unassigned variable without constraint conflict\n\n* Goal test: current assignment is complete\n\n* Path cost: constant cost for every step\n\nBranching factor at root is $n*d$. At next level is $(n-1)*d$. Tree has $n!*d^n$ leaves, where $n$ is variables and $d$ is domain size.\n\nDepth-first search (uninformed) can be used! In CSP, DFS with single-variable assignments is called __backtracking__ search.\nThis means algo uses DFS to choose one var at a time and backtracks when variable has not values left to assign.\n\nHeuristics can be used to improve efficiency:\n\n1. Choose variable with fewest legal values (MRV)\n\n2. Choose most constraining variable (one with most constraints on remaining variables)\n\n3. Choose least constraining value (rules out fewest values in remaining variables)\n\n4. __Forward checking__: keep track of remaining legal values for *unassigned* variables. Terminate search when domain of any reduced to zero (__AC3 & arc consistency__)\n\n__Cons_: Forward checking does not provide early detection for failures! __Constraint propagation__ can do this by also repeatedly enforces constraints locally.\n\n$Arc(i, j)$ is arc consistent iff every value $v$ on $X_i$ is consistent with some label on $Y_j$.\n\nIn worst case, $O(d^2)$ time.\n\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\n  inputs: csp, a binary csp with variables {X1, X2, ..., Xn}\n  local variables: queue, a queue of arcs initially the arcs in csp\n  while queue is not empty do\n    (Xi, Xj) ¬queue.pop()\n    if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n      for each Xk in NEIGHBORS[Xi ] – {Xj} do \n        add (Xk, Xi) to queue \n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true iff we remove a value\n  removed ¬false\n  for each x in DOMAIN[Xi] do\n    if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n    then delete x from DOMAIN[Xi]; removed ¬true\n  return removed\n```\n\nWorst case complexity is $O(n^2 d^3)$ since each arc(i,j) can be inserted into queue $d$ times\n\n\n\n## Module 6 Definitions\n* **Unary constraints** - constraints that involve single variable\n* **Binary constraints** - constraints that involve pairs of variables\n* **Higher-order constraints** - constraints that invole 3 or more variables\n* **Cycle cutset** - choosing subset $S$ for CSP variables so that constraint graph becomes tree after removal of $S$ (SA in the middle)\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n KB is a set of __sentences__, each expressed in __knowledge representation language__ and represents assertion about the world.\nTELL and ASK help add new knowledge and query what is known. Both may involve *inference* to derive new sentences from old. Knowledge-based agent program inputs *percept* and outputs *action*.\n\n*Declarative vs. Procedural* approaches. First means start with empty KB -> TELL sentences one by one until agent knows how to operate. Second means encoding desired behavior as program code.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world is cave consisting of rooms connected by passageways. PEAS:\n\n__1) Performance measure__: +1000 for finding gold &c climbing out, -1000 for failling into pit/getting eaten by Wumpus, -1 for each action taken, -10 for using up arrow (to kill wumpus)\n\n__2) Environment__: A 4x4 grid of rooms. Agent starts bottom left [1,1] facing east. Locations of gold & wumpus are chosen uniformly at random. Each square other than START can be pit with Pr=0.2\n\n__3) Actuators__: Actions include forward, turn left, turn right. Climb can be used to get out of cave but only from [1,1]\n\n__4) Sensors__: 5 sensors. When adjacent (not diagonal) to wumpus, smells \"stench\". When adjacent to put, perceives \"breeze\". When at gold square, perceive \"glitter\". When into wall, perceive \"bump\". When wumpus is killed, it \"screams\" for whole cave.\n\nPercepts can be [Stench, Breeze, None, None, None].\n\nCharacs: deterministic, discrete, static, single-agent.\n\nExample: Agent smells stench in [1,2], meaning wumpus is nearby. But cannot be in [1,1] by rule of game, and cannot be in [2,2] (or would have detected stench when in [2,1]) -> Infer that wumpus is in [1,3].\nThis is a *difficult* inference, combining knowledge gained different times in different places. All *logical reasoning*.\n\n\n\n## AIMA Chapter 7.3 Logic\n ...\n\n__Logical entailment__ means sentence follows logically from another sentence. $A\\models B$ if in every model which A is true, B is also true. If notated $A\\subseteq B$ then A is *stronger assertion* than B.\n\nIf inference algo $i$ derives A from KB, then $KB\\models A$ and A is drived from KB by i.\n\nInference algo that derives only entailed sentence is __sounds__ or __truth preserving__. Desirable to check model for soundness and __completeness__, meaning an inference algo is only complete if it can derive any sentence that is entailed.\nAnother factor to consider is __grounding__. KB *may not* be true in the real world, so __learning__ procedure is important.\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n __Atomic__ sentences consist of a *single* proposition symbol. Possible to connect more with __logical connectives__: $\\neg$ (not), $\\vee$ (or), $\\wedge$ (and), $\\Rightarrow$ (implies), $\\Leftrightarrow$ (biconditional)\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Entailment can be done by __theorem proving__, applying rules of inference directly to setences in KB.\n\n__Conjunctive normal form__ (CNF):\n\n1) Replace $A \\Leftrightarrow B$ with $(A\\Rightarrow B) \\wedge (B\\Rightarrow A)$\n\n2) Replace $A\\Rightarrow B$ with $\\neg A\\vee B$ \n\n3) Move $\\neg$ inward through *double-negation* and *De Morgan*\n\n4) Apply *distributivity law* to distribute $\\vee$ over $\\wedge$\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Axiom** - when sentence is taken as given without being derived from other sentences\n* **Grounding** - connection between logical reasoning processes and real environment in which agent exists\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rx8PsE0D7Xbp"
      },
      "source": [
        ""
      ],
      "execution_count": 118,
      "outputs": []
    }
  ]
}