{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ddong4_midterm_521_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": "84ee8aed-55db-4ab7-985c-63dea9261553"
      },
      "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": null,
      "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": "7c158d06-85fd-4188-e684-a16394220667"
      },
      "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": null,
      "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": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Turing Test: computer vs human interrogator for written questions. will need \\\n",
        "NLP, knowledge rep, automated reasoning, machine learning. \\n\n",
        "Total Turing Test: interact w/ real world - additional computer vision & robotics. \\n\n",
        "value alignment problem - comparison btwn true pref and obj/perf measure of machine \\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 = \"\"\" \n",
        "weak ai - pretend intelligent; strong ai - human-level AI \\n\n",
        "qualification problem - difficult to capture every behavior in logical rules \\n\n",
        "embodied cognition approach - system level where cog as a whole w/ sensory data \\n\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "biological naturalism - mental states are caused by neurons \\n\n",
        "qualia - experiences of living \\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"  \"\"\"\n",
        "chapter2_2 = \"\"\"  \"\"\"\n",
        "chapter2_3 = \"\"\"  \"\"\"\n",
        "chapter2_4 = \"\"\" agent = architecture + program \\n\n",
        "simple reflex agents: select based on current percept \\n\n",
        "model-based reflex agents: maintains internal state based on percept history \\n\n",
        "goal-based agents: includes search and planning \\n\n",
        "utility-based agents: include perf measure for best \"happy\" result (expected utility) \\n\n",
        "3 ways to rep states & transitions: atomic, factored, structured (state of objects). \\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Rene Descartes - principle of dualism, mind sep from body \\n\n",
        "John Searle 1935 - Chinese Room. didn't think turing test was good. \\n\n",
        "Daniel Dennett 1942 - Brain in a vat \\n\n",
        "4 views of AI - thinking humanly, thinking rationally, acting humanly, acting rationally \\n\n",
        "task environment - PEAS to guide; perf measure, env, actuators, sensors \\n\n",
        "6 types of task env: observability, # agents, deterministic vs nondet vs stochastic \\\n",
        "episodic vs seq, static vs dynamic, discrete vs continuous \\n\n",
        "semidynamic - env doesn't change w/ time but agent perf score does (chess w/ clock). \\n\n",
        "hardest env: continuous, partially obs, stoch, multiagent, unknown outcomes. \\n\n",
        "reflex agents vs problem solving agents: reflex chooses action based on current percept, \\\n",
        "problem solving plans ahead. \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"sensor input given instance\",\n",
        "\"agent function\" : \"map f:P->a; P percept vector, a action\",\n",
        "\"performance measure\" : \"success of agent's behavior\",\n",
        "\"\" : \"\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "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": "acf4da3a-2fca-4022-bd25-26b7593e9e13"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nTuring Test: computer vs human interrogator for written questions. will need NLP, knowledge rep, automated reasoning, machine learning. \n\nTotal Turing Test: interact w/ real world - additional computer vision & robotics. \n\nvalue alignment problem - comparison btwn true pref and obj/perf measure of machine \n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak ai - pretend intelligent; strong ai - human-level AI \n\nqualification problem - difficult to capture every behavior in logical rules \n\nembodied cognition approach - system level where cog as a whole w/ sensory data \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nbiological naturalism - mental states are caused by neurons \n\nqualia - experiences of living \n\n\n\n## AIMA 2.1 Agents and Environments\n  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n  \n\n## AIMA 2.3 The Nature of Environments\n  \n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\nsimple reflex agents: select based on current percept \n\nmodel-based reflex agents: maintains internal state based on percept history \n\ngoal-based agents: includes search and planning \n\nutility-based agents: include perf measure for best \"happy\" result (expected utility) \n\n3 ways to rep states & transitions: atomic, factored, structured (state of objects). \n\n\n\n## Module 1 Lecture Notes\n \nRene Descartes - principle of dualism, mind sep from body \n\nJohn Searle 1935 - Chinese Room. didn't think turing test was good. \n\nDaniel Dennett 1942 - Brain in a vat \n\n4 views of AI - thinking humanly, thinking rationally, acting humanly, acting rationally \n\ntask environment - PEAS to guide; perf measure, env, actuators, sensors \n\n6 types of task env: observability, # agents, deterministic vs nondet vs stochastic episodic vs seq, static vs dynamic, discrete vs continuous \n\nsemidynamic - env doesn't change w/ time but agent perf score does (chess w/ clock). \n\nhardest env: continuous, partially obs, stoch, multiagent, unknown outcomes. \n\nreflex agents vs problem solving agents: reflex chooses action based on current percept, problem solving plans ahead. \n\n\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - sensor input given instance\n* **Agent function** - map f:P->a; P percept vector, a action\n* **Performance measure** - success of agent's behavior\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "PEP 8 - official style guide for python code (Guido) \\n\n",
        "REPL env - read-evaluate-print loop. like jupyter notebook \\n\n",
        "Dynamic typing for python - do not have type signatures and updated based on assignment \\n\n",
        "Strings, int, tuple, bool are immutable \\n\n",
        "dict, set, lists are mutable \\n\n",
        "sort() in place, sorted() makes new copy \\n\n",
        "dictionary d = {'a': 'answer'}; d['a'] \\n\n",
        "functions begin w/ def __(d=\"optional default\" or *args for variable # of non-keyword arguments, **kwargs for dict): \\n\n",
        "magic methods start with __init__ (init is a constructor)\\n\n",
        "class methods always begin with self as an arg \\n\n",
        "main method: if __name__=='__main__': \\n\n",
        "Duck typing: establish suitability of an obj by det pres of methods \\n\n",
        "dictionary and set comprehension d = { k: v for k,v in list1 } \\n\n",
        "iterators (don't have hasnext() method, catch StopIteration exception) - for <item> in <iterable>: \\n\n",
        "Generators - are iterators that return generator w/ yield keyword. maintains local state info \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"ability to change val\",\n",
        "\"==\" : \"check vars pt to same val\",\n",
        "\"is\" : \"check if vars pt to same obj\",\n",
        "\"zip()\" : \"put two lists together by index into list of tuples\",\n",
        "\"first-class object\" : \"functions can have all the rights permissions as other vars.\",\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 599
        },
        "cellView": "form",
        "outputId": "e967ddd9-9ba0-4c68-88cb-1bf8a7e25ae3"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nPEP 8 - official style guide for python code (Guido) \n\nREPL env - read-evaluate-print loop. like jupyter notebook \n\nDynamic typing for python - do not have type signatures and updated based on assignment \n\nStrings, int, tuple, bool are immutable \n\ndict, set, lists are mutable \n\nsort() in place, sorted() makes new copy \n\ndictionary d = {'a': 'answer'}; d['a'] \n\nfunctions begin w/ def __(d=\"optional default\" or *args for variable # of non-keyword arguments, **kwargs for dict): \n\nmagic methods start with __init__ (init is a constructor)\n\nclass methods always begin with self as an arg \n\nmain method: if __name__=='__main__': \n\nDuck typing: establish suitability of an obj by det pres of methods \n\ndictionary and set comprehension d = { k: v for k,v in list1 } \n\niterators (don't have hasnext() method, catch StopIteration exception) - for <item> in <iterable>: \n\nGenerators - are iterators that return generator w/ yield keyword. maintains local state info \n\n\n\n\n## Module 2 Definitions\n* **Mutability** - ability to change val\n* **==** - check vars pt to same val\n* **Is** - check if vars pt to same obj\n* **Zip()** - put two lists together by index into list of tuples\n* **First-class object** - functions can have all the rights permissions as other vars.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "4-phase problem solving process: goal formulation, prob formulation, search, exec \\n\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "standardized vs real-world prob : standardized is exact like grid world prob. real-world is google maps. \\n\n",
        "VLSI layout prob - positioning chip components for optimality \\n\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "best-first search - basically bfs but w/ weighted costs \\n\n",
        "node data structure can hold node.state, node.parent, node.action, node.path-cost \\n\n",
        "priority queue - pops node w/ min cost (used in best-first search) \\n\n",
        "fifo queue - used in breadth-first search \\n\n",
        "lifo queue/stack - used in DFS \\n\n",
        "redundant paths - repeated state/cycle/loopy path \\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "breadth-first search - each state we pop out is optimal if it's goal, so can use early goal test \\\n",
        "and check for sol as soon as it's generated. \\n\n",
        "uniform-cost search/Dijkstra's algo - spread out in waves of uniform path-cost when there's a path cost \\n\n",
        "backtracking search - variant of dfs where only 1 successor generated at a time and modify original state. mem O(m) \\n\n",
        "bidirectional search - variant search forward from init and backward from goal for 2b^(d/2) time. \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "problem-solving agent - plans ahead - uses search and pathfinding to get to goal \\n\n",
        "branching strategy - diff future actions used for env part obs & nondet \\n\n",
        "6 things needed for Problem: 1. States; 2. Initial state; 3. Actions (set); 4. \\\n",
        "Transition Model (successors); 5. Path cost (perf measure); 6. Goal test (yes/no) \\n\n",
        "Search Prob Formulation - decide on initial state, goal state, poss intermediates. \\\n",
        "operator set (actions and transition models), and path cost func. \\n\n",
        "state space - abstract to capture properties for prob. \\n\n",
        "Tree Search Algo: generates possible paths from initial state (root). Nodes are \\\n",
        "from transition model. Different from graph search b/c tree search uses diff paths to same \\\n",
        "node as distinct. \\n\n",
        "```\n",
        "func tree-search(prob, strategy) return a sol or failure\n",
        "  Init frontier to init state of prob\n",
        "  do\n",
        "    if frontier empty return failure\n",
        "    choose leaf node for expansion according to strategy & remove from frontier\n",
        "    if node contains goal state then return sol\n",
        "    else expand the node and add resulting nodes to frontier\n",
        "```\n",
        "\n",
        "Graph search - augmented version of tree search to prevent redundancy. \\ \n",
        "Aug = see if state has been visited, if so then don't add to search. \\n\n",
        "```\n",
        "func graph-search - same as tree-search but w/ these augmentations\n",
        "  additional lines:: init the explored set to be empty\n",
        "  do\n",
        "    after looking at node, add node to explored set\n",
        "    during expansion, add node to frontier only if not in explored set\n",
        "```\n",
        "Evaluating Strategy: Completeness, optimality, time complexity, space complexity \\n\n",
        "Completeness - always find sol \\n\n",
        "Optimality - find least cost solution first \\n\n",
        "b - max branching factor of search tree \\n\n",
        "d - depth of shallowest goal node\\n\n",
        "m - max length of any path \\n\n",
        "BFS - time and space complexity both O(b^d) \\n\n",
        "DFS - time complexity O(b^m), linear space O(b*m) \\n\n",
        "DFS is not complete, as it can fail in inf-depth spaces (loops). also not cost optimal. \\n\n",
        "DFS vs BFS: DFS for space restrictions, wrong paths terminate quickly. BFS for \\\n",
        "poss inf paths. short path sol. \\n\n",
        "Depth-limited search - use depth limit l for a DFS. space O(bl) \\n\n",
        "\n",
        "Iterative deepening search - aug DFS and depth-limited search. increase depth limit l from 0 to inf per subroutine dls\\n\n",
        "ids total nodes constructed - depth 0: 0, depth 1: b^1, depth 2: b^2, so on and sum all. \\n\n",
        "ids time complexity O(b^d), space O(bd)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search. use atomic rep\",\n",
        "\"planning agents\" : \"use factored or structured rep of states\",\n",
        "\"solution\" : \"seq of actions from initial state to goal state\",\n",
        "\"state space\" : \"set of all states reachable from initial state by actions\",\n",
        "\"frontier\" : \"states available for expanding (successors)\",\n",
        "\"uninformed search\" : \"no weight given to nodes\",\n",
        "\"Breadth-first search\" : \"expand shallowest unexpanded node. FIFO frontier\", \n",
        "\"Depth-first search\" : \"expand deepest unexpanded node. LIFO frontier\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "04c8178a-2af7-425d-da42-497b838c99cd"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n4-phase problem solving process: goal formulation, prob formulation, search, exec \n\n\n\n## AIMA Chapter 3.2 Example Problems\n\nstandardized vs real-world prob : standardized is exact like grid world prob. real-world is google maps. \n\nVLSI layout prob - positioning chip components for optimality \n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nbest-first search - basically bfs but w/ weighted costs \n\nnode data structure can hold node.state, node.parent, node.action, node.path-cost \n\npriority queue - pops node w/ min cost (used in best-first search) \n\nfifo queue - used in breadth-first search \n\nlifo queue/stack - used in DFS \n\nredundant paths - repeated state/cycle/loopy path \n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nbreadth-first search - each state we pop out is optimal if it's goal, so can use early goal test and check for sol as soon as it's generated. \n\nuniform-cost search/Dijkstra's algo - spread out in waves of uniform path-cost when there's a path cost \n\nbacktracking search - variant of dfs where only 1 successor generated at a time and modify original state. mem O(m) \n\nbidirectional search - variant search forward from init and backward from goal for 2b^(d/2) time. \n\n\n\n\n## Module 3 Lecture Notes\n\nproblem-solving agent - plans ahead - uses search and pathfinding to get to goal \n\nbranching strategy - diff future actions used for env part obs & nondet \n\n6 things needed for Problem: 1. States; 2. Initial state; 3. Actions (set); 4. Transition Model (successors); 5. Path cost (perf measure); 6. Goal test (yes/no) \n\nSearch Prob Formulation - decide on initial state, goal state, poss intermediates. operator set (actions and transition models), and path cost func. \n\nstate space - abstract to capture properties for prob. \n\nTree Search Algo: generates possible paths from initial state (root). Nodes are from transition model. Different from graph search b/c tree search uses diff paths to same node as distinct. \n\n```\nfunc tree-search(prob, strategy) return a sol or failure\n  Init frontier to init state of prob\n  do\n    if frontier empty return failure\n    choose leaf node for expansion according to strategy & remove from frontier\n    if node contains goal state then return sol\n    else expand the node and add resulting nodes to frontier\n```\n\nGraph search - augmented version of tree search to prevent redundancy. \\ \nAug = see if state has been visited, if so then don't add to search. \n\n```\nfunc graph-search - same as tree-search but w/ these augmentations\n  additional lines:: init the explored set to be empty\n  do\n    after looking at node, add node to explored set\n    during expansion, add node to frontier only if not in explored set\n```\nEvaluating Strategy: Completeness, optimality, time complexity, space complexity \n\nCompleteness - always find sol \n\nOptimality - find least cost solution first \n\nb - max branching factor of search tree \n\nd - depth of shallowest goal node\n\nm - max length of any path \n\nBFS - time and space complexity both O(b^d) \n\nDFS - time complexity O(b^m), linear space O(b*m) \n\nDFS is not complete, as it can fail in inf-depth spaces (loops). also not cost optimal. \n\nDFS vs BFS: DFS for space restrictions, wrong paths terminate quickly. BFS for poss inf paths. short path sol. \n\nDepth-limited search - use depth limit l for a DFS. space O(bl) \n\n\nIterative deepening search - aug DFS and depth-limited search. increase depth limit l from 0 to inf per subroutine dls\n\nids total nodes constructed - depth 0: 0, depth 1: b^1, depth 2: b^2, so on and sum all. \n\nids time complexity O(b^d), space O(bd)\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search. use atomic rep\n* **Planning agents** - use factored or structured rep of states\n* **Solution** - seq of actions from initial state to goal state\n* **State space** - set of all states reachable from initial state by actions\n* **Frontier** - states available for expanding (successors)\n* **Uninformed search** - no weight given to nodes\n* **Breadth-first search** - expand shallowest unexpanded node. FIFO frontier\n* **Depth-first search** - expand deepest unexpanded node. LIFO frontier\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "A* must be admissible and consistent. \\n\n",
        "consistency - when heuristic is h(n) <= cost(n to successor n') + h(n') \\n\n",
        "consistency form of triangle inequality, where each side of the triangle can't be longer \\\n",
        "than sum of other two sides. \\n\n",
        "A* algo - for C* (cost of optimal solution), expands all nodes where f(n) < C* (surely expanded nodes) \\\n",
        ". A* might expand some on goal contour (f(n) = C*). never expands f(n) > C*. \\n\n",
        "satisficing solutions - suboptimal but good enough sol, done by using an inadmissible heuristic. \\n\n",
        "weighted A* search - somewhat greed search. Weight heuristic value more heavily by a multiplier (for satisficing). \\n\n",
        "A* search cost is O(b^(d-k))\n",
        "Memory A* - most mem used in frontier & reached states. \\n\n",
        "Ways to reduce mem - reference counts, then remove from reached table. Or Beam search, limit size of frontier. \\n\n",
        "Iterative-deepening A* search (IDA*) - saves mem, at a cost of visiting states multiple times. \\\n",
        "cutoff is f-cost (g+h) not (depth like standard).\\n\n",
        "Recursive best-first search (RBFS) - like best-first search but uses linear space. \\\n",
        "ability to rewind if a f_limit is exceeded from an alt path. optimal if heuristic is admissible.\\n\n",
        "MA* (memory-bounded A*) and SMA* (simplified MA*). reach a mem bound and drop bad leaves. \\n\n",
        "Bidirectional heuristic search - uses 2 diff eval func for each direction and \"meet up.\" \\n\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Quality of heuristic - can get by calculating effective branching factor b*. \\n\n",
        "Can generate heuristics from subproblems (Pattern databases to store exact solutions for subprobs (dynamic prog)). \\n\n",
        "Generate heuristic with landmarks - for maps, precomputate a few things for amortization. \\n\n",
        "differential heuristic - subtracts from a cost that's further (landmark) to optimal cost. \\n\n",
        "have agent learn to search better with metalevel state space & metalevel learning. \\n\n",
        "Experience-learning heuristic - construct from scratch a function (with luck) machine learning. \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "uniform-cost search (UCS) - tree search algo for weighted tree using path cost func g(n)\\\n",
        "implemented as priority queue (frontier). expand node w/ lowest path cost. unlike \\\n",
        "BFS, it tests if reached goal when selected for expansion instead of right away. \\\n",
        "follows cost contours. \\n\n",
        "heuristic func - use an evaluation strategy f(n) and order frontier queue by this. \\n\n",
        "Example Heuristics - Straight-line distances, Manhattan distance \\n\n",
        "Greedy best-first search : expand lowest f(n), implemented by priority queue. Use \\\n",
        "heuristic h(n) = f(n). is not optimal \\n\n",
        "```\n",
        "def greedy best-first search\n",
        "while frontier not empty:\n",
        "    set current as next in frontier\n",
        "    if goal, return\n",
        "    for successors in neighbors of current\n",
        "      if not in visited, place in priority queue based on heuristic func\n",
        "      add to visited\n",
        "```\n",
        "A* search - f(n) = g(n) + h(n). g(n) actual cost so far, h(n) estimated, f(n) total cost \\n\n",
        "A* implementation - frontier queue by f(n). Optimal w/ admissible heuristic. \\n\n",
        "Heuristics must be admissible (never overestimates), (optimistic - true cost always less) \\n\n",
        "Dominance - see which heuristic is better. if still admissible, higher cost one is more accurate \\n\n",
        "```\n",
        "def A*\n",
        "while frontier not empty:\n",
        "  set current as next in frontier\n",
        "  if goal, return\n",
        "  for successors in neighbors of current\n",
        "    cost = cost so far + weight to get to next\n",
        "    if not visited or if cost is less than previously visited (at the neighbor):\n",
        "        update cost of the neighbor\n",
        "        priority = cost + heuristic(goal from next)\n",
        "        put in priority queue(next, priority)\n",
        "        add current to visited\n",
        "```\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"relaxed prob\" : \"fewer restrict on actions vs original. use opt sol for relaxed prob as adm heuristic\",  \n",
        "\"\" : \"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b02a0274-8af7-4bcb-8987-e01f7f4cffd4"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nA* must be admissible and consistent. \n\nconsistency - when heuristic is h(n) <= cost(n to successor n') + h(n') \n\nconsistency form of triangle inequality, where each side of the triangle can't be longer than sum of other two sides. \n\nA* algo - for C* (cost of optimal solution), expands all nodes where f(n) < C* (surely expanded nodes) . A* might expand some on goal contour (f(n) = C*). never expands f(n) > C*. \n\nsatisficing solutions - suboptimal but good enough sol, done by using an inadmissible heuristic. \n\nweighted A* search - somewhat greed search. Weight heuristic value more heavily by a multiplier (for satisficing). \n\nA* search cost is O(b^(d-k))\nMemory A* - most mem used in frontier & reached states. \n\nWays to reduce mem - reference counts, then remove from reached table. Or Beam search, limit size of frontier. \n\nIterative-deepening A* search (IDA*) - saves mem, at a cost of visiting states multiple times. cutoff is f-cost (g+h) not (depth like standard).\n\nRecursive best-first search (RBFS) - like best-first search but uses linear space. ability to rewind if a f_limit is exceeded from an alt path. optimal if heuristic is admissible.\n\nMA* (memory-bounded A*) and SMA* (simplified MA*). reach a mem bound and drop bad leaves. \n\nBidirectional heuristic search - uses 2 diff eval func for each direction and \"meet up.\" \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nQuality of heuristic - can get by calculating effective branching factor b*. \n\nCan generate heuristics from subproblems (Pattern databases to store exact solutions for subprobs (dynamic prog)). \n\nGenerate heuristic with landmarks - for maps, precomputate a few things for amortization. \n\ndifferential heuristic - subtracts from a cost that's further (landmark) to optimal cost. \n\nhave agent learn to search better with metalevel state space & metalevel learning. \n\nExperience-learning heuristic - construct from scratch a function (with luck) machine learning. \n\n\n\n\n## Module 4 Lecture Notes\n\nuniform-cost search (UCS) - tree search algo for weighted tree using path cost func g(n)implemented as priority queue (frontier). expand node w/ lowest path cost. unlike BFS, it tests if reached goal when selected for expansion instead of right away. follows cost contours. \n\nheuristic func - use an evaluation strategy f(n) and order frontier queue by this. \n\nExample Heuristics - Straight-line distances, Manhattan distance \n\nGreedy best-first search : expand lowest f(n), implemented by priority queue. Use heuristic h(n) = f(n). is not optimal \n\n```\ndef greedy best-first search\nwhile frontier not empty:\n    set current as next in frontier\n    if goal, return\n    for successors in neighbors of current\n      if not in visited, place in priority queue based on heuristic func\n      add to visited\n```\nA* search - f(n) = g(n) + h(n). g(n) actual cost so far, h(n) estimated, f(n) total cost \n\nA* implementation - frontier queue by f(n). Optimal w/ admissible heuristic. \n\nHeuristics must be admissible (never overestimates), (optimistic - true cost always less) \n\nDominance - see which heuristic is better. if still admissible, higher cost one is more accurate \n\n```\ndef A*\nwhile frontier not empty:\n  set current as next in frontier\n  if goal, return\n  for successors in neighbors of current\n    cost = cost so far + weight to get to next\n    if not visited or if cost is less than previously visited (at the neighbor):\n        update cost of the neighbor\n        priority = cost + heuristic(goal from next)\n        put in priority queue(next, priority)\n        add current to visited\n```\n\n\n\n\n\n\n## Module 4 Definitions\n* **Relaxed prob** - fewer restrict on actions vs original. use opt sol for relaxed prob as adm heuristic\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "zero-sum game - good for one player is bad for the other.\\n\n",
        "Elements for game: initial state, to-move (player), actions, result (transition model), \\\n",
        "terminal test (if game is over), utility func(payoff func). \\n\n",
        "state space graph - made of init state, actions func, result func. Vertices are states, \\\n",
        "edges are moves, and state might be reached by mult paths. could be unbounded if inf repeat.\\n\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "minimax search - find best winning strategy for MAX.\n",
        "minimax decision - at root, the action that is the opt choice for MAX. \\n\n",
        "Minimax algo - time complexity O(b^m); m max depth of tree, b legal moves each pt. \\\n",
        "Space complexity O(bm) or O(m) dep on generated actions at a time. \\n\n",
        "transposition table - cache of heuristic values of states (end up in same pos). \\n\n",
        "Type A strategy - consider poss moves to a certain depth in search tree, then use heuristic. \\\n",
        "\"wide but shallow\"\\n\n",
        "Type B strategy - follow promising lines as far as poss. \"Deep but narrow\" tree search. \\n\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "heuristic alpha-beta search - save comp time and cut off search early. Replace \\\n",
        "terminal test w/ cutoff test. \\n\n",
        "cutoff - could modify to a fixed depth of search, or use iterative deepening. \\n\n",
        "horizon effect. \\n\n",
        "forward pruning - prune moves that appear to be poor, but might be good.\\n\n",
        "move ordering - to order the list to eval from potential good to bad moves. \\n\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games - random element. Utilizes chance nodes in addition to MAX and MIN. \\n\n",
        "expectiminimax. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Utility Function, expected utility. \\n\n",
        "Maximum expected utility (MEU) - rational agent should choose max exp util. \\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Constraints on rational pref - work off MEU principle to establish prefs. \\n\n",
        "6 constraints (axioms of utilty theory) that any pref relation need to obey. \\n\n",
        "1) orderability - given 2 lotteries, must prefer 1 or rate as equal. \\n\n",
        "2) transitivity - given 3 lotteries, A>B and B>C = A>C \\n\n",
        "3) continuity - if B is between A and C in pref, there's some prob p between A and C to be indifferent getting B. \\n\n",
        "4) substitutability - if indifferent between 2 lotteries A and B, can substitute. \\n\n",
        "5) monotonicity - if two possible outcomes A and B, if A > B, must choose lottery w/ higher prob for A. \\n\n",
        "6) decomposability - coumpound lotteries can be decomposed to simpler ones. \\n\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "micromort - one in a mil chance of death \\n\n",
        "QALY - quality-adjusted life year \\n\n",
        "certainty effect - pple prefer to chooce 100% things, don't need to compute probs. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Simplest game env - multiagent, static, discrete, fully obs, strategic.\\n\n",
        "Game setup - Max and Min, initial board state, successor func, terminal/game finished test, \\\n",
        "utility function. Use search tree to det best move. \\n\n",
        "Game tree - rep of prob space. node = board pos, edge = legal moves. \\n\n",
        "Evaluation function (f(n)) - based on board position. is pos if MAX is winning. \\n\n",
        "Minimax Rule - treate adversary as rational actor. recursive process max to min to max \\n\n",
        "Alpha-Beta Pruning - alpha=MAX's current lower bound on Max outcome. Beta=MIN's \\\n",
        "current upper bound on MIN's outcome.\\n\n",
        "alpha = \"at least\" best choice so far for MAX. when eval MIN node, v<=alpha MAX will \\\n",
        "never select that MIN node. \\n\n",
        "beta = \"at most\" best choice for MIN. when eval MAX node, v>=beta MIN will never select that\\n\n",
        "Expectimax search - for when result is random or opp unpredictable. will have MAX \\\n",
        "and chance nodes (instead of MIN). Calc expected utility by weighted avg of children.\\n\n",
        "expected value is sum (edges (chance) * value of roll)\\n\n",
        "can't prune easily in expectimax.\\n\n",
        "Expectminimax - have max -> chance -> min. have an chance \"env\" be an agent that can move after max.\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Minimax search\" : \"consists of state-space search tree, players alt turns, comput minimax val\",\n",
        "\"\" : \"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "16a96042-fbf6-44be-b485-6c23ecaaf034"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nzero-sum game - good for one player is bad for the other.\n\nElements for game: initial state, to-move (player), actions, result (transition model), terminal test (if game is over), utility func(payoff func). \n\nstate space graph - made of init state, actions func, result func. Vertices are states, edges are moves, and state might be reached by mult paths. could be unbounded if inf repeat.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nminimax search - find best winning strategy for MAX.\nminimax decision - at root, the action that is the opt choice for MAX. \n\nMinimax algo - time complexity O(b^m); m max depth of tree, b legal moves each pt. Space complexity O(bm) or O(m) dep on generated actions at a time. \n\ntransposition table - cache of heuristic values of states (end up in same pos). \n\nType A strategy - consider poss moves to a certain depth in search tree, then use heuristic. \"wide but shallow\"\n\nType B strategy - follow promising lines as far as poss. \"Deep but narrow\" tree search. \n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nheuristic alpha-beta search - save comp time and cut off search early. Replace terminal test w/ cutoff test. \n\ncutoff - could modify to a fixed depth of search, or use iterative deepening. \n\nhorizon effect. \n\nforward pruning - prune moves that appear to be poor, but might be good.\n\nmove ordering - to order the list to eval from potential good to bad moves. \n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games - random element. Utilizes chance nodes in addition to MAX and MIN. \n\nexpectiminimax. \n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nUtility Function, expected utility. \n\nMaximum expected utility (MEU) - rational agent should choose max exp util. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nConstraints on rational pref - work off MEU principle to establish prefs. \n\n6 constraints (axioms of utilty theory) that any pref relation need to obey. \n\n1) orderability - given 2 lotteries, must prefer 1 or rate as equal. \n\n2) transitivity - given 3 lotteries, A>B and B>C = A>C \n\n3) continuity - if B is between A and C in pref, there's some prob p between A and C to be indifferent getting B. \n\n4) substitutability - if indifferent between 2 lotteries A and B, can substitute. \n\n5) monotonicity - if two possible outcomes A and B, if A > B, must choose lottery w/ higher prob for A. \n\n6) decomposability - coumpound lotteries can be decomposed to simpler ones. \n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nmicromort - one in a mil chance of death \n\nQALY - quality-adjusted life year \n\ncertainty effect - pple prefer to chooce 100% things, don't need to compute probs. \n\n\n\n## Module 5 Lecture Notes\n\nSimplest game env - multiagent, static, discrete, fully obs, strategic.\n\nGame setup - Max and Min, initial board state, successor func, terminal/game finished test, utility function. Use search tree to det best move. \n\nGame tree - rep of prob space. node = board pos, edge = legal moves. \n\nEvaluation function (f(n)) - based on board position. is pos if MAX is winning. \n\nMinimax Rule - treate adversary as rational actor. recursive process max to min to max \n\nAlpha-Beta Pruning - alpha=MAX's current lower bound on Max outcome. Beta=MIN's current upper bound on MIN's outcome.\n\nalpha = \"at least\" best choice so far for MAX. when eval MIN node, v<=alpha MAX will never select that MIN node. \n\nbeta = \"at most\" best choice for MIN. when eval MAX node, v>=beta MIN will never select that\n\nExpectimax search - for when result is random or opp unpredictable. will have MAX and chance nodes (instead of MIN). Calc expected utility by weighted avg of children.\n\nexpected value is sum (edges (chance) * value of roll)\n\ncan't prune easily in expectimax.\n\nExpectminimax - have max -> chance -> min. have an chance \"env\" be an agent that can move after max.\n\n\n\n\n## Module 5 Definitions\n* **Minimax search** - consists of state-space search tree, players alt turns, comput minimax val\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "precedence constraint - when a task must occur before another task T1 + d1 <= T2 \\n\n",
        "disjunctive constraint - two tasks can't overlap in time (use OR statement)\\n\n",
        "continuous domain example - scheduling Hubble Space Telescope.\\n\n",
        "hypergraph - has ordinary nodes and hypernodes (squares that are n-ary constraints)\\n\n",
        "Alldiff - global constraint that every var involved must have diff values (sudoku).\\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "constraint propagation - use constraints to reduce num of legal vals for var.\\n\n",
        "node consistency - var satisfy unary constraint (e.g. SA dislike red)\\n\n",
        "arc consistent - binary constraints\\n\n",
        "AC-3 algo - enforce arc consistency. maintain queue of arcs. \\n\n",
        "k-consistency - CSP is k-consistent if any set of k-1 vars and any consistent val allows \\\n",
        "kth var to be assigned.\\n\n",
        "strongly k-consistent - if k-consistent but also (k-1)-consistent, so on...\\n\n",
        "Atmost constraint - resource constraint like num of personnel available.\\n\n",
        "bounds-consistent - lowerbound and upperbound values for var.\\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "backtracking search - when there's still vars w/ mult poss values. partial assign. \\\n",
        "Can be improved with domain-independent heuristics.\\n\n",
        "commutativity - order of a given set of actions doesn't matter \\n\n",
        "MAC (Maintaining Arc Consistency) Algo - detects inconsistencies unlike forward checking.\\\n",
        " If domain reduced to empty set, will backtrack immediately.\\n\n",
        "backjumping is redundant in forward-checking search or MAC. \\n\n",
        "Constraint learning - record the no-good assignments.\\n\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "min-conflicts heuristic - select val that results in min number of conflicts with others. \\n\n",
        "plateau search - sideways moves to another state w/ same score. done by tabu search technique\\n\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "find independent subproblems by finding connected components.\\n\n",
        "directional arc consistency (DAC) - any tree-structured CSP can be solved in time linear in the num of vars.\\n\n",
        "way 1) cycle cutset - want to remove a node to become a tree (to be able to solve in time linear)\\n\n",
        "way 2) tree decomposition - transform original into a tree for each node.\\n\n",
        "value symmetry - want to reduce search space by using symmetry-breaking constraint, put arbitrary order x<y<z.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "When goal itself important, not path -- use constraints specified in declarative lang. \\n\n",
        "CSP has: finite set of vars, nonempty domain of poss values, finite set of constraints, consistent assignment. \\n\n",
        "solution to csp has complete, consistent assignment. \\n\n",
        "Benefits: fail fast (can prune those that violate constraints), can solve generic goal. \\n\n",
        "Applications: map coloring, scheduling, sudoku. \\n\n",
        "constraint graph - nodes = vars, arcs/edges = (binary) constraints \\n\n",
        "CSP as search prob - need initial state, successor func, goal test, path cost. \\\n",
        "solution at depth n, use DFS. \\n\n",
        "CSP are commutative - order of any given set of actions or var assignments doesn't affect outcome. \\n\n",
        "Backtracking efficiency - general-purpose methods & general-purpose heuristics make efficient. \\n\n",
        "Heuristics used - 1. most constrained var, 2. most constraining var., 3. least constraining value, 4. forward checking. \\n\n",
        "1. Most constrained var - choose one w/ fewest legal values (MRV) min remaining values heuristic.\\n\n",
        "2. Most constraining - choose var w/ most constraints on remaining vars.\\n\n",
        "Towards arc consistency - forward checking. keep track of remaining legal vals for unassigned vars. \\n\n",
        "fwd checking allows constraint propagation - info from assigned constrain future. \\\n",
        "Doesn't provide early detection for failures.\\n\n",
        "Inference in CSP - Swapping between search and inference (to eliminate values if it would violate local consistency).\\n\n",
        "Arc consistency - can be done as a preprocess or after each assignment - check every X for allowed values. \\\n",
        "If X loses a value, check all neighbors. Time complexity O(d^2) if d values. \\n\n",
        "Waltz Algo - interpret line drawings as 3d objects.\\n\n",
        "Waltz/Mackworth Constraint Propagation Algo - Assign every node in constraint graph\\\n",
        " to set of all poss val. For each node remove value not arc consistent; repeat. Con: inefficient check all nodes. \\n\n",
        "AC-3 - same as above but only look for arc consistency when a neighbor loses a value. \\\n",
        "Maintain queue that tracks which arcs to check. add back to queue if a val is removed. \\n\n",
        "Time complexity: O(n^2*d^3). Planar graphs (no crossing edges): O(nd^3). \\n\n",
        "Path consistency - generalize arc-consistency from binary to mult constraints.\\n\n",
        "Cycle Cutset- to simplify to a tree choose a subset of verts that leaves a tree.\\n\n",
        "Backtracking - DFS built in chronological backtracking. Improved by finding conflict set and reassign.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint satisfcation problem\" : \"use constraints as general purpose algo\",    \n",
        "\"inference\" : \"utilize forward checking for constraint propagation\",\n",
        "\"backtracking search\" : \"DFS for CSP with single-var assignments, go back if incorrect sol\",\n",
        "\"arc consistency\" : \"if satisfy binary constraints between nodes as directed arcs in constraint graph\",\n",
        "\"constraint propagation\" : \"use constraints to eliminate labels to find all sols\",\n",
        "\"\" : \"\",\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "be26877f-7f39-482a-fa87-c74e24d302b8"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nprecedence constraint - when a task must occur before another task T1 + d1 <= T2 \n\ndisjunctive constraint - two tasks can't overlap in time (use OR statement)\n\ncontinuous domain example - scheduling Hubble Space Telescope.\n\nhypergraph - has ordinary nodes and hypernodes (squares that are n-ary constraints)\n\nAlldiff - global constraint that every var involved must have diff values (sudoku).\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nconstraint propagation - use constraints to reduce num of legal vals for var.\n\nnode consistency - var satisfy unary constraint (e.g. SA dislike red)\n\narc consistent - binary constraints\n\nAC-3 algo - enforce arc consistency. maintain queue of arcs. \n\nk-consistency - CSP is k-consistent if any set of k-1 vars and any consistent val allows kth var to be assigned.\n\nstrongly k-consistent - if k-consistent but also (k-1)-consistent, so on...\n\nAtmost constraint - resource constraint like num of personnel available.\n\nbounds-consistent - lowerbound and upperbound values for var.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nbacktracking search - when there's still vars w/ mult poss values. partial assign. Can be improved with domain-independent heuristics.\n\ncommutativity - order of a given set of actions doesn't matter \n\nMAC (Maintaining Arc Consistency) Algo - detects inconsistencies unlike forward checking. If domain reduced to empty set, will backtrack immediately.\n\nbackjumping is redundant in forward-checking search or MAC. \n\nConstraint learning - record the no-good assignments.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nmin-conflicts heuristic - select val that results in min number of conflicts with others. \n\nplateau search - sideways moves to another state w/ same score. done by tabu search technique\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nfind independent subproblems by finding connected components.\n\ndirectional arc consistency (DAC) - any tree-structured CSP can be solved in time linear in the num of vars.\n\nway 1) cycle cutset - want to remove a node to become a tree (to be able to solve in time linear)\n\nway 2) tree decomposition - transform original into a tree for each node.\n\nvalue symmetry - want to reduce search space by using symmetry-breaking constraint, put arbitrary order x<y<z.\n\n\n\n## Module 6 Lecture Notes\n\nWhen goal itself important, not path -- use constraints specified in declarative lang. \n\nCSP has: finite set of vars, nonempty domain of poss values, finite set of constraints, consistent assignment. \n\nsolution to csp has complete, consistent assignment. \n\nBenefits: fail fast (can prune those that violate constraints), can solve generic goal. \n\nApplications: map coloring, scheduling, sudoku. \n\nconstraint graph - nodes = vars, arcs/edges = (binary) constraints \n\nCSP as search prob - need initial state, successor func, goal test, path cost. solution at depth n, use DFS. \n\nCSP are commutative - order of any given set of actions or var assignments doesn't affect outcome. \n\nBacktracking efficiency - general-purpose methods & general-purpose heuristics make efficient. \n\nHeuristics used - 1. most constrained var, 2. most constraining var., 3. least constraining value, 4. forward checking. \n\n1. Most constrained var - choose one w/ fewest legal values (MRV) min remaining values heuristic.\n\n2. Most constraining - choose var w/ most constraints on remaining vars.\n\nTowards arc consistency - forward checking. keep track of remaining legal vals for unassigned vars. \n\nfwd checking allows constraint propagation - info from assigned constrain future. Doesn't provide early detection for failures.\n\nInference in CSP - Swapping between search and inference (to eliminate values if it would violate local consistency).\n\nArc consistency - can be done as a preprocess or after each assignment - check every X for allowed values. If X loses a value, check all neighbors. Time complexity O(d^2) if d values. \n\nWaltz Algo - interpret line drawings as 3d objects.\n\nWaltz/Mackworth Constraint Propagation Algo - Assign every node in constraint graph to set of all poss val. For each node remove value not arc consistent; repeat. Con: inefficient check all nodes. \n\nAC-3 - same as above but only look for arc consistency when a neighbor loses a value. Maintain queue that tracks which arcs to check. add back to queue if a val is removed. \n\nTime complexity: O(n^2*d^3). Planar graphs (no crossing edges): O(nd^3). \n\nPath consistency - generalize arc-consistency from binary to mult constraints.\n\nCycle Cutset- to simplify to a tree choose a subset of verts that leaves a tree.\n\nBacktracking - DFS built in chronological backtracking. Improved by finding conflict set and reassign.\n\n\n\n## Module 6 Definitions\n* **Constraint satisfcation problem** - use constraints as general purpose algo\n* **Inference** - utilize forward checking for constraint propagation\n* **Backtracking search** - DFS for CSP with single-var assignments, go back if incorrect sol\n* **Arc consistency** - if satisfy binary constraints between nodes as directed arcs in constraint graph\n* **Constraint propagation** - use constraints to eliminate labels to find all sols\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "procedural approach - encodes desired behaviors directly as program code.\\n\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "wumpus world - deterministic, discrete, static, and single-agent. \\n\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "syntax (of propositional logic) - defines allowable sentences.\\n\n",
        "disjunction = or (v looking one)\\n\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "theorem proving - applying rules of inference to construct of proof of desired sent.\\n\n",
        "DeMorgan's laws - neg(a ^ b) = (nega or negb). neg(a or b) = (nega ^ negb)\\n\n",
        "reductio ad absurdum - reduction to an absurd thing \\n\n",
        "CNF - conjunctive normal form - sentence expressed as conj of clauses. Clause = disjunction of literals.\\n\n",
        "definite clauses allow to write as implication form (negA or negB or C) = (A and B => C)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "types of sent - axioms and derived sentences. inference is deriving new sent from old.\\n\n",
        "Propositional logic - KB consists of sentences in rep lang, rep lang has syntax that are well-formed,\\\n",
        " semantics for meaning, semantics define truth for the model.\\n\n",
        " Models - have a fixed set of truth values T/F for each sentence. If no pit in [2,2], then M(alpha) all\\\n",
        "  instances where [2,2] doesn't have pit.\\n\n",
        "entailment - sentence follows logically from another sent. |= symbol \\n\n",
        "logical inference - entailment applied to derive conclusions.\\n\n",
        "propositional symbols - used to represent atomic sentences.\\n\n",
        "complex sentences - made using parenthese and logical connectives (not, and, or implies iff).\\n\n",
        "inference rules - used to derive proofs. the weird fraction-looking notation. \\n\n",
        "monotonicity implies soundness.\\n\n",
        "Resolution - the single inference rule that can yield complete inference algo. \\\n",
        "If li and m are complementary literals, we can eliminate them via unit resolution.\\n\n",
        "Every sentence is a conjunction of clauses (put in CNF).\\n\n",
        "Resolution Algo - show KB entails alpha by showing KB and not alpha is unsatisfiable. proof by contradiction.\\n\n",
        "horn clause allow res algo to run in linear time.\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"apply logic over internal rep of knowledge to decide action\",  \n",
        "\"knowledge base (KB)\" : \"sentence written in knowledge rep lang\",\n",
        "\"sound\" : \"inference algo should only derive entailed sent\",\n",
        "\"complete\" : \"inference algo is complete if it can derive all sent that are entailed.\",\n",
        "\"logical equiv\" : \"if two sent are true in same set of models\",\n",
        "\"monotonicity\" : \"adding anything to KB still makes the previous inference true\",\n",
        "\"definite clause\" : \"disjunction of literals where exactly one is pos\",\n",
        "\"horn clause\" : \"disjunction of literals where at most one is pos. if you apply resolution to horn, u get back horn\", \n",
        "\"forward chaining\" : \"data-driven reasoning. Add premises as percepts come in and then derive new conclusions. linear time\", \n",
        "\"backward chaining\" : \"goal-directed reasoning. find what made up a conclusion of a query\", \n",
        "\"\" : \"\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "599ff042-6e9a-4742-c70f-83bf92497f3f"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nprocedural approach - encodes desired behaviors directly as program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nwumpus world - deterministic, discrete, static, and single-agent. \n\n\n\n## AIMA Chapter 7.3 Logic\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nsyntax (of propositional logic) - defines allowable sentences.\n\ndisjunction = or (v looking one)\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\ntheorem proving - applying rules of inference to construct of proof of desired sent.\n\nDeMorgan's laws - neg(a ^ b) = (nega or negb). neg(a or b) = (nega ^ negb)\n\nreductio ad absurdum - reduction to an absurd thing \n\nCNF - conjunctive normal form - sentence expressed as conj of clauses. Clause = disjunction of literals.\n\ndefinite clauses allow to write as implication form (negA or negB or C) = (A and B => C)\n\n\n## Module 7 Lecture Notes\n\ntypes of sent - axioms and derived sentences. inference is deriving new sent from old.\n\nPropositional logic - KB consists of sentences in rep lang, rep lang has syntax that are well-formed, semantics for meaning, semantics define truth for the model.\n\n Models - have a fixed set of truth values T/F for each sentence. If no pit in [2,2], then M(alpha) all  instances where [2,2] doesn't have pit.\n\nentailment - sentence follows logically from another sent. |= symbol \n\nlogical inference - entailment applied to derive conclusions.\n\npropositional symbols - used to represent atomic sentences.\n\ncomplex sentences - made using parenthese and logical connectives (not, and, or implies iff).\n\ninference rules - used to derive proofs. the weird fraction-looking notation. \n\nmonotonicity implies soundness.\n\nResolution - the single inference rule that can yield complete inference algo. If li and m are complementary literals, we can eliminate them via unit resolution.\n\nEvery sentence is a conjunction of clauses (put in CNF).\n\nResolution Algo - show KB entails alpha by showing KB and not alpha is unsatisfiable. proof by contradiction.\n\nhorn clause allow res algo to run in linear time.\n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - apply logic over internal rep of knowledge to decide action\n* **Knowledge base (kb)** - sentence written in knowledge rep lang\n* **Sound** - inference algo should only derive entailed sent\n* **Complete** - inference algo is complete if it can derive all sent that are entailed.\n* **Logical equiv** - if two sent are true in same set of models\n* **Monotonicity** - adding anything to KB still makes the previous inference true\n* **Definite clause** - disjunction of literals where exactly one is pos\n* **Horn clause** - disjunction of literals where at most one is pos. if you apply resolution to horn, u get back horn\n* **Forward chaining** - data-driven reasoning. Add premises as percepts come in and then derive new conclusions. linear time\n* **Backward chaining** - goal-directed reasoning. find what made up a conclusion of a query\n* **** - \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": "39c72c63-2d97-414b-f3ad-7a069087cc18"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nTuring Test: computer vs human interrogator for written questions. will need NLP, knowledge rep, automated reasoning, machine learning. \n\nTotal Turing Test: interact w/ real world - additional computer vision & robotics. \n\nvalue alignment problem - comparison btwn true pref and obj/perf measure of machine \n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak ai - pretend intelligent; strong ai - human-level AI \n\nqualification problem - difficult to capture every behavior in logical rules \n\nembodied cognition approach - system level where cog as a whole w/ sensory data \n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nbiological naturalism - mental states are caused by neurons \n\nqualia - experiences of living \n\n\n\n## AIMA 2.1 Agents and Environments\n  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n  \n\n## AIMA 2.3 The Nature of Environments\n  \n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\nsimple reflex agents: select based on current percept \n\nmodel-based reflex agents: maintains internal state based on percept history \n\ngoal-based agents: includes search and planning \n\nutility-based agents: include perf measure for best \"happy\" result (expected utility) \n\n3 ways to rep states & transitions: atomic, factored, structured (state of objects). \n\n\n\n## Module 1 Lecture Notes\n \nRene Descartes - principle of dualism, mind sep from body \n\nJohn Searle 1935 - Chinese Room. didn't think turing test was good. \n\nDaniel Dennett 1942 - Brain in a vat \n\n4 views of AI - thinking humanly, thinking rationally, acting humanly, acting rationally \n\ntask environment - PEAS to guide; perf measure, env, actuators, sensors \n\n6 types of task env: observability, # agents, deterministic vs nondet vs stochastic episodic vs seq, static vs dynamic, discrete vs continuous \n\nsemidynamic - env doesn't change w/ time but agent perf score does (chess w/ clock). \n\nhardest env: continuous, partially obs, stoch, multiagent, unknown outcomes. \n\nreflex agents vs problem solving agents: reflex chooses action based on current percept, problem solving plans ahead. \n\n\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - sensor input given instance\n* **Agent function** - map f:P->a; P percept vector, a action\n* **Performance measure** - success of agent's behavior\n* **** - \n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nPEP 8 - official style guide for python code (Guido) \n\nREPL env - read-evaluate-print loop. like jupyter notebook \n\nDynamic typing for python - do not have type signatures and updated based on assignment \n\nStrings, int, tuple, bool are immutable \n\ndict, set, lists are mutable \n\nsort() in place, sorted() makes new copy \n\ndictionary d = {'a': 'answer'}; d['a'] \n\nfunctions begin w/ def __(d=\"optional default\" or *args for variable # of non-keyword arguments, **kwargs for dict): \n\nmagic methods start with __init__ (init is a constructor)\n\nclass methods always begin with self as an arg \n\nmain method: if __name__=='__main__': \n\nDuck typing: establish suitability of an obj by det pres of methods \n\ndictionary and set comprehension d = { k: v for k,v in list1 } \n\niterators (don't have hasnext() method, catch StopIteration exception) - for <item> in <iterable>: \n\nGenerators - are iterators that return generator w/ yield keyword. maintains local state info \n\n\n\n\n## Module 2 Definitions\n* **Mutability** - ability to change val\n* **==** - check vars pt to same val\n* **Is** - check if vars pt to same obj\n* **Zip()** - put two lists together by index into list of tuples\n* **First-class object** - functions can have all the rights permissions as other vars.\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n4-phase problem solving process: goal formulation, prob formulation, search, exec \n\n\n\n## AIMA Chapter 3.2 Example Problems\n\nstandardized vs real-world prob : standardized is exact like grid world prob. real-world is google maps. \n\nVLSI layout prob - positioning chip components for optimality \n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nbest-first search - basically bfs but w/ weighted costs \n\nnode data structure can hold node.state, node.parent, node.action, node.path-cost \n\npriority queue - pops node w/ min cost (used in best-first search) \n\nfifo queue - used in breadth-first search \n\nlifo queue/stack - used in DFS \n\nredundant paths - repeated state/cycle/loopy path \n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nbreadth-first search - each state we pop out is optimal if it's goal, so can use early goal test and check for sol as soon as it's generated. \n\nuniform-cost search/Dijkstra's algo - spread out in waves of uniform path-cost when there's a path cost \n\nbacktracking search - variant of dfs where only 1 successor generated at a time and modify original state. mem O(m) \n\nbidirectional search - variant search forward from init and backward from goal for 2b^(d/2) time. \n\n\n\n\n## Module 3 Lecture Notes\n\nproblem-solving agent - plans ahead - uses search and pathfinding to get to goal \n\nbranching strategy - diff future actions used for env part obs & nondet \n\n6 things needed for Problem: 1. States; 2. Initial state; 3. Actions (set); 4. Transition Model (successors); 5. Path cost (perf measure); 6. Goal test (yes/no) \n\nSearch Prob Formulation - decide on initial state, goal state, poss intermediates. operator set (actions and transition models), and path cost func. \n\nstate space - abstract to capture properties for prob. \n\nTree Search Algo: generates possible paths from initial state (root). Nodes are from transition model. Different from graph search b/c tree search uses diff paths to same node as distinct. \n\n```\nfunc tree-search(prob, strategy) return a sol or failure\n  Init frontier to init state of prob\n  do\n    if frontier empty return failure\n    choose leaf node for expansion according to strategy & remove from frontier\n    if node contains goal state then return sol\n    else expand the node and add resulting nodes to frontier\n```\n\nGraph search - augmented version of tree search to prevent redundancy. \\ \nAug = see if state has been visited, if so then don't add to search. \n\n```\nfunc graph-search - same as tree-search but w/ these augmentations\n  additional lines:: init the explored set to be empty\n  do\n    after looking at node, add node to explored set\n    during expansion, add node to frontier only if not in explored set\n```\nEvaluating Strategy: Completeness, optimality, time complexity, space complexity \n\nCompleteness - always find sol \n\nOptimality - find least cost solution first \n\nb - max branching factor of search tree \n\nd - depth of shallowest goal node\n\nm - max length of any path \n\nBFS - time and space complexity both O(b^d) \n\nDFS - time complexity O(b^m), linear space O(b*m) \n\nDFS is not complete, as it can fail in inf-depth spaces (loops). also not cost optimal. \n\nDFS vs BFS: DFS for space restrictions, wrong paths terminate quickly. BFS for poss inf paths. short path sol. \n\nDepth-limited search - use depth limit l for a DFS. space O(bl) \n\n\nIterative deepening search - aug DFS and depth-limited search. increase depth limit l from 0 to inf per subroutine dls\n\nids total nodes constructed - depth 0: 0, depth 1: b^1, depth 2: b^2, so on and sum all. \n\nids time complexity O(b^d), space O(bd)\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search. use atomic rep\n* **Planning agents** - use factored or structured rep of states\n* **Solution** - seq of actions from initial state to goal state\n* **State space** - set of all states reachable from initial state by actions\n* **Frontier** - states available for expanding (successors)\n* **Uninformed search** - no weight given to nodes\n* **Breadth-first search** - expand shallowest unexpanded node. FIFO frontier\n* **Depth-first search** - expand deepest unexpanded node. LIFO frontier\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nA* must be admissible and consistent. \n\nconsistency - when heuristic is h(n) <= cost(n to successor n') + h(n') \n\nconsistency form of triangle inequality, where each side of the triangle can't be longer than sum of other two sides. \n\nA* algo - for C* (cost of optimal solution), expands all nodes where f(n) < C* (surely expanded nodes) . A* might expand some on goal contour (f(n) = C*). never expands f(n) > C*. \n\nsatisficing solutions - suboptimal but good enough sol, done by using an inadmissible heuristic. \n\nweighted A* search - somewhat greed search. Weight heuristic value more heavily by a multiplier (for satisficing). \n\nA* search cost is O(b^(d-k))\nMemory A* - most mem used in frontier & reached states. \n\nWays to reduce mem - reference counts, then remove from reached table. Or Beam search, limit size of frontier. \n\nIterative-deepening A* search (IDA*) - saves mem, at a cost of visiting states multiple times. cutoff is f-cost (g+h) not (depth like standard).\n\nRecursive best-first search (RBFS) - like best-first search but uses linear space. ability to rewind if a f_limit is exceeded from an alt path. optimal if heuristic is admissible.\n\nMA* (memory-bounded A*) and SMA* (simplified MA*). reach a mem bound and drop bad leaves. \n\nBidirectional heuristic search - uses 2 diff eval func for each direction and \"meet up.\" \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nQuality of heuristic - can get by calculating effective branching factor b*. \n\nCan generate heuristics from subproblems (Pattern databases to store exact solutions for subprobs (dynamic prog)). \n\nGenerate heuristic with landmarks - for maps, precomputate a few things for amortization. \n\ndifferential heuristic - subtracts from a cost that's further (landmark) to optimal cost. \n\nhave agent learn to search better with metalevel state space & metalevel learning. \n\nExperience-learning heuristic - construct from scratch a function (with luck) machine learning. \n\n\n\n\n## Module 4 Lecture Notes\n\nuniform-cost search (UCS) - tree search algo for weighted tree using path cost func g(n)implemented as priority queue (frontier). expand node w/ lowest path cost. unlike BFS, it tests if reached goal when selected for expansion instead of right away. follows cost contours. \n\nheuristic func - use an evaluation strategy f(n) and order frontier queue by this. \n\nExample Heuristics - Straight-line distances, Manhattan distance \n\nGreedy best-first search : expand lowest f(n), implemented by priority queue. Use heuristic h(n) = f(n). is not optimal \n\n```\ndef greedy best-first search\nwhile frontier not empty:\n    set current as next in frontier\n    if goal, return\n    for successors in neighbors of current\n      if not in visited, place in priority queue based on heuristic func\n      add to visited\n```\nA* search - f(n) = g(n) + h(n). g(n) actual cost so far, h(n) estimated, f(n) total cost \n\nA* implementation - frontier queue by f(n). Optimal w/ admissible heuristic. \n\nHeuristics must be admissible (never overestimates), (optimistic - true cost always less) \n\nDominance - see which heuristic is better. if still admissible, higher cost one is more accurate \n\n```\ndef A*\nwhile frontier not empty:\n  set current as next in frontier\n  if goal, return\n  for successors in neighbors of current\n    cost = cost so far + weight to get to next\n    if not visited or if cost is less than previously visited (at the neighbor):\n        update cost of the neighbor\n        priority = cost + heuristic(goal from next)\n        put in priority queue(next, priority)\n        add current to visited\n```\n\n\n\n\n\n\n## Module 4 Definitions\n* **Relaxed prob** - fewer restrict on actions vs original. use opt sol for relaxed prob as adm heuristic\n* **** - \n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nzero-sum game - good for one player is bad for the other.\n\nElements for game: initial state, to-move (player), actions, result (transition model), terminal test (if game is over), utility func(payoff func). \n\nstate space graph - made of init state, actions func, result func. Vertices are states, edges are moves, and state might be reached by mult paths. could be unbounded if inf repeat.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nminimax search - find best winning strategy for MAX.\nminimax decision - at root, the action that is the opt choice for MAX. \n\nMinimax algo - time complexity O(b^m); m max depth of tree, b legal moves each pt. Space complexity O(bm) or O(m) dep on generated actions at a time. \n\ntransposition table - cache of heuristic values of states (end up in same pos). \n\nType A strategy - consider poss moves to a certain depth in search tree, then use heuristic. \"wide but shallow\"\n\nType B strategy - follow promising lines as far as poss. \"Deep but narrow\" tree search. \n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nheuristic alpha-beta search - save comp time and cut off search early. Replace terminal test w/ cutoff test. \n\ncutoff - could modify to a fixed depth of search, or use iterative deepening. \n\nhorizon effect. \n\nforward pruning - prune moves that appear to be poor, but might be good.\n\nmove ordering - to order the list to eval from potential good to bad moves. \n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games - random element. Utilizes chance nodes in addition to MAX and MIN. \n\nexpectiminimax. \n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nUtility Function, expected utility. \n\nMaximum expected utility (MEU) - rational agent should choose max exp util. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nConstraints on rational pref - work off MEU principle to establish prefs. \n\n6 constraints (axioms of utilty theory) that any pref relation need to obey. \n\n1) orderability - given 2 lotteries, must prefer 1 or rate as equal. \n\n2) transitivity - given 3 lotteries, A>B and B>C = A>C \n\n3) continuity - if B is between A and C in pref, there's some prob p between A and C to be indifferent getting B. \n\n4) substitutability - if indifferent between 2 lotteries A and B, can substitute. \n\n5) monotonicity - if two possible outcomes A and B, if A > B, must choose lottery w/ higher prob for A. \n\n6) decomposability - coumpound lotteries can be decomposed to simpler ones. \n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nmicromort - one in a mil chance of death \n\nQALY - quality-adjusted life year \n\ncertainty effect - pple prefer to chooce 100% things, don't need to compute probs. \n\n\n\n## Module 5 Lecture Notes\n\nSimplest game env - multiagent, static, discrete, fully obs, strategic.\n\nGame setup - Max and Min, initial board state, successor func, terminal/game finished test, utility function. Use search tree to det best move. \n\nGame tree - rep of prob space. node = board pos, edge = legal moves. \n\nEvaluation function (f(n)) - based on board position. is pos if MAX is winning. \n\nMinimax Rule - treate adversary as rational actor. recursive process max to min to max \n\nAlpha-Beta Pruning - alpha=MAX's current lower bound on Max outcome. Beta=MIN's current upper bound on MIN's outcome.\n\nalpha = \"at least\" best choice so far for MAX. when eval MIN node, v<=alpha MAX will never select that MIN node. \n\nbeta = \"at most\" best choice for MIN. when eval MAX node, v>=beta MIN will never select that\n\nExpectimax search - for when result is random or opp unpredictable. will have MAX and chance nodes (instead of MIN). Calc expected utility by weighted avg of children.\n\nexpected value is sum (edges (chance) * value of roll)\n\ncan't prune easily in expectimax.\n\nExpectminimax - have max -> chance -> min. have an chance \"env\" be an agent that can move after max.\n\n\n\n\n## Module 5 Definitions\n* **Minimax search** - consists of state-space search tree, players alt turns, comput minimax val\n* **** - \n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nprecedence constraint - when a task must occur before another task T1 + d1 <= T2 \n\ndisjunctive constraint - two tasks can't overlap in time (use OR statement)\n\ncontinuous domain example - scheduling Hubble Space Telescope.\n\nhypergraph - has ordinary nodes and hypernodes (squares that are n-ary constraints)\n\nAlldiff - global constraint that every var involved must have diff values (sudoku).\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nconstraint propagation - use constraints to reduce num of legal vals for var.\n\nnode consistency - var satisfy unary constraint (e.g. SA dislike red)\n\narc consistent - binary constraints\n\nAC-3 algo - enforce arc consistency. maintain queue of arcs. \n\nk-consistency - CSP is k-consistent if any set of k-1 vars and any consistent val allows kth var to be assigned.\n\nstrongly k-consistent - if k-consistent but also (k-1)-consistent, so on...\n\nAtmost constraint - resource constraint like num of personnel available.\n\nbounds-consistent - lowerbound and upperbound values for var.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nbacktracking search - when there's still vars w/ mult poss values. partial assign. Can be improved with domain-independent heuristics.\n\ncommutativity - order of a given set of actions doesn't matter \n\nMAC (Maintaining Arc Consistency) Algo - detects inconsistencies unlike forward checking. If domain reduced to empty set, will backtrack immediately.\n\nbackjumping is redundant in forward-checking search or MAC. \n\nConstraint learning - record the no-good assignments.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nmin-conflicts heuristic - select val that results in min number of conflicts with others. \n\nplateau search - sideways moves to another state w/ same score. done by tabu search technique\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nfind independent subproblems by finding connected components.\n\ndirectional arc consistency (DAC) - any tree-structured CSP can be solved in time linear in the num of vars.\n\nway 1) cycle cutset - want to remove a node to become a tree (to be able to solve in time linear)\n\nway 2) tree decomposition - transform original into a tree for each node.\n\nvalue symmetry - want to reduce search space by using symmetry-breaking constraint, put arbitrary order x<y<z.\n\n\n\n## Module 6 Lecture Notes\n\nWhen goal itself important, not path -- use constraints specified in declarative lang. \n\nCSP has: finite set of vars, nonempty domain of poss values, finite set of constraints, consistent assignment. \n\nsolution to csp has complete, consistent assignment. \n\nBenefits: fail fast (can prune those that violate constraints), can solve generic goal. \n\nApplications: map coloring, scheduling, sudoku. \n\nconstraint graph - nodes = vars, arcs/edges = (binary) constraints \n\nCSP as search prob - need initial state, successor func, goal test, path cost. solution at depth n, use DFS. \n\nCSP are commutative - order of any given set of actions or var assignments doesn't affect outcome. \n\nBacktracking efficiency - general-purpose methods & general-purpose heuristics make efficient. \n\nHeuristics used - 1. most constrained var, 2. most constraining var., 3. least constraining value, 4. forward checking. \n\n1. Most constrained var - choose one w/ fewest legal values (MRV) min remaining values heuristic.\n\n2. Most constraining - choose var w/ most constraints on remaining vars.\n\nTowards arc consistency - forward checking. keep track of remaining legal vals for unassigned vars. \n\nfwd checking allows constraint propagation - info from assigned constrain future. Doesn't provide early detection for failures.\n\nInference in CSP - Swapping between search and inference (to eliminate values if it would violate local consistency).\n\nArc consistency - can be done as a preprocess or after each assignment - check every X for allowed values. If X loses a value, check all neighbors. Time complexity O(d^2) if d values. \n\nWaltz Algo - interpret line drawings as 3d objects.\n\nWaltz/Mackworth Constraint Propagation Algo - Assign every node in constraint graph to set of all poss val. For each node remove value not arc consistent; repeat. Con: inefficient check all nodes. \n\nAC-3 - same as above but only look for arc consistency when a neighbor loses a value. Maintain queue that tracks which arcs to check. add back to queue if a val is removed. \n\nTime complexity: O(n^2*d^3). Planar graphs (no crossing edges): O(nd^3). \n\nPath consistency - generalize arc-consistency from binary to mult constraints.\n\nCycle Cutset- to simplify to a tree choose a subset of verts that leaves a tree.\n\nBacktracking - DFS built in chronological backtracking. Improved by finding conflict set and reassign.\n\n\n\n## Module 6 Definitions\n* **Constraint satisfcation problem** - use constraints as general purpose algo\n* **Inference** - utilize forward checking for constraint propagation\n* **Backtracking search** - DFS for CSP with single-var assignments, go back if incorrect sol\n* **Arc consistency** - if satisfy binary constraints between nodes as directed arcs in constraint graph\n* **Constraint propagation** - use constraints to eliminate labels to find all sols\n* **** - \n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nprocedural approach - encodes desired behaviors directly as program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nwumpus world - deterministic, discrete, static, and single-agent. \n\n\n\n## AIMA Chapter 7.3 Logic\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nsyntax (of propositional logic) - defines allowable sentences.\n\ndisjunction = or (v looking one)\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\ntheorem proving - applying rules of inference to construct of proof of desired sent.\n\nDeMorgan's laws - neg(a ^ b) = (nega or negb). neg(a or b) = (nega ^ negb)\n\nreductio ad absurdum - reduction to an absurd thing \n\nCNF - conjunctive normal form - sentence expressed as conj of clauses. Clause = disjunction of literals.\n\ndefinite clauses allow to write as implication form (negA or negB or C) = (A and B => C)\n\n\n## Module 7 Lecture Notes\n\ntypes of sent - axioms and derived sentences. inference is deriving new sent from old.\n\nPropositional logic - KB consists of sentences in rep lang, rep lang has syntax that are well-formed, semantics for meaning, semantics define truth for the model.\n\n Models - have a fixed set of truth values T/F for each sentence. If no pit in [2,2], then M(alpha) all  instances where [2,2] doesn't have pit.\n\nentailment - sentence follows logically from another sent. |= symbol \n\nlogical inference - entailment applied to derive conclusions.\n\npropositional symbols - used to represent atomic sentences.\n\ncomplex sentences - made using parenthese and logical connectives (not, and, or implies iff).\n\ninference rules - used to derive proofs. the weird fraction-looking notation. \n\nmonotonicity implies soundness.\n\nResolution - the single inference rule that can yield complete inference algo. If li and m are complementary literals, we can eliminate them via unit resolution.\n\nEvery sentence is a conjunction of clauses (put in CNF).\n\nResolution Algo - show KB entails alpha by showing KB and not alpha is unsatisfiable. proof by contradiction.\n\nhorn clause allow res algo to run in linear time.\n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - apply logic over internal rep of knowledge to decide action\n* **Knowledge base (kb)** - sentence written in knowledge rep lang\n* **Sound** - inference algo should only derive entailed sent\n* **Complete** - inference algo is complete if it can derive all sent that are entailed.\n* **Logical equiv** - if two sent are true in same set of models\n* **Monotonicity** - adding anything to KB still makes the previous inference true\n* **Definite clause** - disjunction of literals where exactly one is pos\n* **Horn clause** - disjunction of literals where at most one is pos. if you apply resolution to horn, u get back horn\n* **Forward chaining** - data-driven reasoning. Add premises as percepts come in and then derive new conclusions. linear time\n* **Backward chaining** - goal-directed reasoning. find what made up a conclusion of a query\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}