{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_Midterm_Notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f396858b-b212-483b-bc22-55e976cf007e"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d2796da4-b765-4585-8389-5397c890c164"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"Paul Lin\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "-Capabilities needed: \n",
        "- Turing Test (natural language processing, knowledge representation, automated reasoning, ML)\n",
        "- Total Turing Test (computer vision, robotics)\\n\n",
        "-Ways to learn about human thought: introspection (own thought), psychological experiment (person in action), brain imaging (brain in action)\\n\n",
        "-Value Alignment: chess (machine with win objective: sabotage players, bribe referee), car (multiple objective: safety vs speed)\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",
        "-Arguments from Disability: machine can never do \"X\" (kind, enjoy strawberry, fall in love, use words properly)\\n\n",
        "-Godel's Incompleteness Theorem: construct sentence G(F) where\n",
        "- G(F) is sentence of F ... but unable to be proved within F\n",
        "- if F consistent then G(F) is true\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "-Chinese Room: human given Chinese instruction, transcribe instructions, output intelligent Chinese response, but no thinking is involved\\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "-Environment: can be anything; in practice: universe part where states matter and are affected/percieved by agent/agent actions\\n\n",
        "-Action: choice dependant on built-in knowledge and percept sequence (only up to date)\\n\n",
        "-Agent: Function (mathematical description, take entire percept history) vs Program (concrete implementation, take only current precept)\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "-Rationality Factors\\n\n",
        "- Performance Measure / Criterion of Success\n",
        "- Agent's prior knowledge of environment\n",
        "- Action agent can perform\n",
        "- Agent's percept sequence to date\\n\n",
        "-Omniscience: not required (since rationality only dependant on percept sequence to date)\\n\n",
        "-Autonomy: required (must be able to improve knowledge; i.e.: wasp/catepillar example), but can be developed (not needed from start)\n",
        "\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "-Most Difficult: partially observable, multiagent, nondeterministic, dynamic, continuous, unknown (e.g.: driving in new country)\\n\n",
        "-Fully Observable vs Partially Observable\n",
        "- Fully Observable: advantage (agent no need to maintain internal state of world)\n",
        "- Partially Observable: cause (noise, inaccurate sensor, missing data)\n",
        "- Unobservable: cause (no sensor)\\n\n",
        "-Single Agent vs Multiagent\n",
        "- Multiagent: competitive (chess) vs cooperative (taxi)\\n\n",
        "-Deterministic vs Non-Deterministic\n",
        "- Stochastic: quantitative probability (e.g.: 25% of rain)\n",
        "- Non-Deterministic: non-quantitative chance (e.g.: may rain)\\n\n",
        "-Episodic vs Sequential\n",
        "- Episodic: agent percieve/perform single action, each episode independent of previous episodes (e.g.: assembly line defective parts spotting)\n",
        "- Sequential: cons (need to think ahead)\\n\n",
        "-Static vs Dynamic\n",
        "- Dynamic: taxi\n",
        "- Semidynamic: chess with clock\n",
        "- Static: crossword puzzle\\n\n",
        "-Discrete vs Continuous: for state of environment, time handling, percepts & actions\n",
        "- Discrete: chess (finite number of states)\n",
        "- Continuous: taxi (continuous actions, speed)\\n\n",
        "-Known vs Unkown: for state of knowledge of environment (NOT environment)\n",
        "- Known + Partially Observable: solitaire (know rules, don't know card)\n",
        "- Unknown + Fully Observable: video game (know screen, don't know what buttons do)\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "-Simple Reflex Agent\n",
        "- Workings: select based on current precept while ignoring precept history\n",
        "- Characteristic: only works if fully observable, often infinite loop if partially observable\\n\n",
        "-Model-Based Reflex Agent\n",
        "- Workings: select while keeping internal state (may reflect unobservable world parts)\n",
        "- Requirements for updating internal state information: transition model & sensor model\n",
        "- Transition Model: how does world change over time? (e.g.: if steering wheel is clockwise, car turns clockwise)\n",
        "- Sensor Model: how is state of world reflected in agent's percept? (e.g.: if camera is wet, image is partially observable)\\n\n",
        "-Goal-Based Agent\n",
        "- Insufficiencies: only knowing state (e.g.: at road junction ... turn left, right, or straight?)\n",
        "- Workings: keep track of goal information (desirable outcomes)\n",
        "- Characteristics: future-facing, less efficient but more flexibile\\n\n",
        "-Utility-Based Agent\n",
        "- Insufficiencies: knowing goal (e.g.: many routes, which is quickest/fastest?)\n",
        "- Workings: use utility function (internal performance measure) to find best method to reach goal\n",
        "- Characteristics: conflicting goals (specify appropriate tradeoffs), several goals (weigh likelihood to importance)\\n\n",
        "-Learning Agent: 4 components, bring component to closer agreement with performance\n",
        "- Learning Element: makes improvements\n",
        "- Performance Element: select external action\n",
        "- Critic: gives feedback on performance based on fixed standard\n",
        "- Problem Generator: suggest action for new/informative experience\\n\n",
        "-Expressiveness: more expressive = more concise & more complex reasoning\n",
        "- Atomic Represntation: world is indivisible, state has no internal structure\n",
        "- Factored Representation: state has attribute values\n",
        "- Structured Representation: state has objects with attributes and relationships\\n\n",
        "-Mappings\n",
        "- Localist Representation: 1-1 mapping between concept & memory location\n",
        "- Distributed Representation: representation spread over memory location, memory location may be in multiple concepts\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "<h3>ARTIFICIAL INTELLIGENCE IN PHILOSOPHY</h3>\n",
        "-Rene Descartes (Dualism): tests via language, automatons can never properly use language\\n\n",
        "-Alan Turing (Imitation Game): machine can pass as human in conversation\\n\n",
        "-John Searle (Chinese Room): strong AI (actual thinking, has cognitive ability/conscious thinking) vs weak AI (simulating thinking, no real understanding)\\n\n",
        "-Daniel Dennett (Brain in a Vat): brain removed from body and placed in vat\n",
        "<h3>RATIONAL AGENTS</h3>\n",
        "-Agent Function ($f:P->a$): maping of sequence of percept (p) to action (a)\\n\n",
        "-Agent Examples: human (sensors: eyes, acutators: hands, legs), robots (sensors: camera, actuator: motors)\\n\n",
        "<h3>RATIONAL BEHAVIOR</h3>\n",
        "-Performance Measure design: better to base on agent achievements than agent procedure\\n\n",
        "-Omniscience: omniscience does not equal guarenteed success, agents need not be omniscience\n",
        "<h3>TASK ENVIRONMENTS</h3>\n",
        "-Task Environment Components: P (performance measure), E (Environment), A (Actuator), S (Sensor)\\n\n",
        "-PEAS Example (Taxi): P (safe, fast, profit), E (road, pedestrian), A (brake, steering), S (camera, GPS)\\n\n",
        "-Agent Goal: 1) construct agent function to maximize performance measure, 2) design agent program to implement on architecture\\n\n",
        "-Environment: hardest (continuous, partially observable, stochastic, multiagent) vs easiest (static, fully observable, deterministic, discrete)\\n\n",
        "-Agent Types: reflex agent (select action based on current percept) vs problem solving agent (plan ahead, consider sequence of actions)\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",
        "\"Dualism\": \"mind exists separately from body\",\n",
        "\"Agent\": \"anything that use sensor to percieve environment and act on it through actuators, agent = architecure + program\",\n",
        "\"Percept\": \"agent's perceptual inputs\",\n",
        "\"Percept Sequence\": \"historical log of everything agent percieved\",\n",
        "\"Agent Function\": \"map of percept sequence to action\",\n",
        "\"Agent Program\": \"program that runs physical architecture to produce agent function (i.e.: table)\",\n",
        "\"Rational Agent\": \"rationally-behaving (maximize expected performance measure) agents based on percept sequence so far\",\n",
        "\"Performance Measure\": \"criterion for deciding success of agent behavior via evaluation on sequence of environment states\",\n",
        "\"Value Alignment Problem\": \"machine value/objective aligned with humans (chess/car example)\",\n",
        "\"Good Old-Fashioned AI\": \"simple logical agents\",\n",
        "\"Embodied Cognition\": \"cannot seperate brian function from environment, since brain is in body and body in environment\",\n",
        "\"Biological Naturalism\": \"mental states (high-level) derived from neuron physical process (low-level)\",\n",
        "\"Consciousness/Qualia\": \"capability to expereince living and be aware of environment/outside world\",\n",
        "\"Consequentialism\": \"agent action judged by consequences, not actions\",\n",
        "\"Omniscience\": \"capability to know outcome of actions and act accordingly\",\n",
        "\"Autonomy\": \"capability to learn/compensate for/correct on prior knowledge information (partial/incorrect)\",\n",
        "\"Fully Observable\": \"environment in which agent's sensor has access to all state at all time\",\n",
        "\"Multiagent\": \"environment in which B exhibits behaviors that maximize a performance measure affected by agent A's action\",\n",
        "\"Deterministic\": \"environment in which next environment state completely determined by current state/action\",\n",
        "\"Episodic\": \"environment in which agent experience can be divided\",\n",
        "\"Sequential\": \"environment in which current decision affects all future decisions\",\n",
        "\"Dynamic\": \"environment in which environments can change while agent thinks\",\n",
        "\"Semi-Dynamic\": \"environment in which environment does not change but agent or performance does\",\n",
        "\"Known\": \"environment in which all outcome/outcome probability are given\",\n",
        "\"Condition-Action Rules\": \"if-else statements\",\n",
        "\"Transition Model\": \"model for describing how next state is dependant on current state/action\",\n",
        "\"Sensor Model\": \"model for describing how world state is seen/refelected by agent precepts\",\n",
        "}\n",
        "\n",
        "module1_definitions = {key: module1_definitions[key] for key in sorted(module1_definitions.keys())}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "985bbc40-b9ae-4041-fc7f-a17f84210a51"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n-Capabilities needed: \n- Turing Test (natural language processing, knowledge representation, automated reasoning, ML)\n- Total Turing Test (computer vision, robotics)\n\n-Ways to learn about human thought: introspection (own thought), psychological experiment (person in action), brain imaging (brain in action)\n\n-Value Alignment: chess (machine with win objective: sabotage players, bribe referee), car (multiple objective: safety vs speed)\n \n\n## AIMA Chapter 27.1 The Limits of AI\n\n-Arguments from Disability: machine can never do \"X\" (kind, enjoy strawberry, fall in love, use words properly)\n\n-Godel's Incompleteness Theorem: construct sentence G(F) where\n- G(F) is sentence of F ... but unable to be proved within F\n- if F consistent then G(F) is true\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n-Chinese Room: human given Chinese instruction, transcribe instructions, output intelligent Chinese response, but no thinking is involved\n\n\n\n## AIMA 2.1 Agents and Environments\n\n-Environment: can be anything; in practice: universe part where states matter and are affected/percieved by agent/agent actions\n\n-Action: choice dependant on built-in knowledge and percept sequence (only up to date)\n\n-Agent: Function (mathematical description, take entire percept history) vs Program (concrete implementation, take only current precept)\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n-Rationality Factors\n\n- Performance Measure / Criterion of Success\n- Agent's prior knowledge of environment\n- Action agent can perform\n- Agent's percept sequence to date\n\n-Omniscience: not required (since rationality only dependant on percept sequence to date)\n\n-Autonomy: required (must be able to improve knowledge; i.e.: wasp/catepillar example), but can be developed (not needed from start)\n\n \n\n## AIMA 2.3 The Nature of Environments\n\n-Most Difficult: partially observable, multiagent, nondeterministic, dynamic, continuous, unknown (e.g.: driving in new country)\n\n-Fully Observable vs Partially Observable\n- Fully Observable: advantage (agent no need to maintain internal state of world)\n- Partially Observable: cause (noise, inaccurate sensor, missing data)\n- Unobservable: cause (no sensor)\n\n-Single Agent vs Multiagent\n- Multiagent: competitive (chess) vs cooperative (taxi)\n\n-Deterministic vs Non-Deterministic\n- Stochastic: quantitative probability (e.g.: 25% of rain)\n- Non-Deterministic: non-quantitative chance (e.g.: may rain)\n\n-Episodic vs Sequential\n- Episodic: agent percieve/perform single action, each episode independent of previous episodes (e.g.: assembly line defective parts spotting)\n- Sequential: cons (need to think ahead)\n\n-Static vs Dynamic\n- Dynamic: taxi\n- Semidynamic: chess with clock\n- Static: crossword puzzle\n\n-Discrete vs Continuous: for state of environment, time handling, percepts & actions\n- Discrete: chess (finite number of states)\n- Continuous: taxi (continuous actions, speed)\n\n-Known vs Unkown: for state of knowledge of environment (NOT environment)\n- Known + Partially Observable: solitaire (know rules, don't know card)\n- Unknown + Fully Observable: video game (know screen, don't know what buttons do)\n\n\n## AIMA 2.4 The Structure of Agents\n\n-Simple Reflex Agent\n- Workings: select based on current precept while ignoring precept history\n- Characteristic: only works if fully observable, often infinite loop if partially observable\n\n-Model-Based Reflex Agent\n- Workings: select while keeping internal state (may reflect unobservable world parts)\n- Requirements for updating internal state information: transition model & sensor model\n- Transition Model: how does world change over time? (e.g.: if steering wheel is clockwise, car turns clockwise)\n- Sensor Model: how is state of world reflected in agent's percept? (e.g.: if camera is wet, image is partially observable)\n\n-Goal-Based Agent\n- Insufficiencies: only knowing state (e.g.: at road junction ... turn left, right, or straight?)\n- Workings: keep track of goal information (desirable outcomes)\n- Characteristics: future-facing, less efficient but more flexibile\n\n-Utility-Based Agent\n- Insufficiencies: knowing goal (e.g.: many routes, which is quickest/fastest?)\n- Workings: use utility function (internal performance measure) to find best method to reach goal\n- Characteristics: conflicting goals (specify appropriate tradeoffs), several goals (weigh likelihood to importance)\n\n-Learning Agent: 4 components, bring component to closer agreement with performance\n- Learning Element: makes improvements\n- Performance Element: select external action\n- Critic: gives feedback on performance based on fixed standard\n- Problem Generator: suggest action for new/informative experience\n\n-Expressiveness: more expressive = more concise & more complex reasoning\n- Atomic Represntation: world is indivisible, state has no internal structure\n- Factored Representation: state has attribute values\n- Structured Representation: state has objects with attributes and relationships\n\n-Mappings\n- Localist Representation: 1-1 mapping between concept & memory location\n- Distributed Representation: representation spread over memory location, memory location may be in multiple concepts\n\n## Module 1 Lecture Notes\n\n<h3>ARTIFICIAL INTELLIGENCE IN PHILOSOPHY</h3>\n-Rene Descartes (Dualism): tests via language, automatons can never properly use language\n\n-Alan Turing (Imitation Game): machine can pass as human in conversation\n\n-John Searle (Chinese Room): strong AI (actual thinking, has cognitive ability/conscious thinking) vs weak AI (simulating thinking, no real understanding)\n\n-Daniel Dennett (Brain in a Vat): brain removed from body and placed in vat\n<h3>RATIONAL AGENTS</h3>\n-Agent Function ($f:P->a$): maping of sequence of percept (p) to action (a)\n\n-Agent Examples: human (sensors: eyes, acutators: hands, legs), robots (sensors: camera, actuator: motors)\n\n<h3>RATIONAL BEHAVIOR</h3>\n-Performance Measure design: better to base on agent achievements than agent procedure\n\n-Omniscience: omniscience does not equal guarenteed success, agents need not be omniscience\n<h3>TASK ENVIRONMENTS</h3>\n-Task Environment Components: P (performance measure), E (Environment), A (Actuator), S (Sensor)\n\n-PEAS Example (Taxi): P (safe, fast, profit), E (road, pedestrian), A (brake, steering), S (camera, GPS)\n\n-Agent Goal: 1) construct agent function to maximize performance measure, 2) design agent program to implement on architecture\n\n-Environment: hardest (continuous, partially observable, stochastic, multiagent) vs easiest (static, fully observable, deterministic, discrete)\n\n-Agent Types: reflex agent (select action based on current percept) vs problem solving agent (plan ahead, consider sequence of actions)\n\n\n## Module 1 Definitions\n* **Agent** - anything that use sensor to percieve environment and act on it through actuators, agent = architecure + program\n* **Agent function** - map of percept sequence to action\n* **Agent program** - program that runs physical architecture to produce agent function (i.e.: table)\n* **Autonomy** - capability to learn/compensate for/correct on prior knowledge information (partial/incorrect)\n* **Biological naturalism** - mental states (high-level) derived from neuron physical process (low-level)\n* **Condition-action rules** - if-else statements\n* **Consciousness/qualia** - capability to expereince living and be aware of environment/outside world\n* **Consequentialism** - agent action judged by consequences, not actions\n* **Deterministic** - environment in which next environment state completely determined by current state/action\n* **Dualism** - mind exists separately from body\n* **Dynamic** - environment in which environments can change while agent thinks\n* **Embodied cognition** - cannot seperate brian function from environment, since brain is in body and body in environment\n* **Episodic** - environment in which agent experience can be divided\n* **Fully observable** - environment in which agent's sensor has access to all state at all time\n* **Good old-fashioned ai** - simple logical agents\n* **Known** - environment in which all outcome/outcome probability are given\n* **Multiagent** - environment in which B exhibits behaviors that maximize a performance measure affected by agent A's action\n* **Omniscience** - capability to know outcome of actions and act accordingly\n* **Percept** - agent's perceptual inputs\n* **Percept sequence** - historical log of everything agent percieved\n* **Performance measure** - criterion for deciding success of agent behavior via evaluation on sequence of environment states\n* **Rational agent** - rationally-behaving (maximize expected performance measure) agents based on percept sequence so far\n* **Semi-dynamic** - environment in which environment does not change but agent or performance does\n* **Sensor model** - model for describing how world state is seen/refelected by agent precepts\n* **Sequential** - environment in which current decision affects all future decisions\n* **Transition model** - model for describing how next state is dependant on current state/action\n* **Value alignment problem** - machine value/objective aligned with humans (chess/car example)\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",
        "<h3>INTRO TO PYTHON</h3>\n",
        "-References: == (checks if variable point to object of same value), is (check if variables point to same object) \\n\n",
        "-Mutability: strings (immutable), lists (mutable), [:] creates shallow copy of new object\n",
        "<h3>SEQUENCE TYPES</h3>\n",
        "-Sequence Types: tuple (immutable, mixed types), strings (immutable), list (mutable, mixed types)\\n\n",
        "-Slicing: returns copy, [i:j] (i...j-1), [i:-j] (i...n-j), [::k] (every k)\\n\n",
        "-List Operations: append, insert, index (index of first occurence), count (number of occurence), remove (remove first occurence)\\n\n",
        "<h3>FOR LOOPS</h3>\n",
        "-Filtered List Comprehension: [elem for elem in li if elem > 4]\n",
        "<h3>ITERATORS</h3>\n",
        "-Advantages: efficient memory usage\n",
        "<h3>GENERATORS</h3>\n",
        "-yield: generator method runs until encountering yield statement, then stops and returns yielded value \\n\n",
        "-xrange vs range: xrange (generator), range (keeps n values in memory before starting loop) \\n\n",
        "-Generator Pro: maintain local state, values computed as needed, no storing entire sequence in memory, one pass aggregation, infinite sequences \\n\n",
        "-Generator Con: inspect individual elements\n",
        "<h3>MISC</h3>\n",
        "-ERROR:  first_two = set(); first_two.add(\"one\"); first_two.remove(\"two\")\\n\n",
        "-ERROR: {\"A\": 3, \"B\": 2} + {\"C\": 3, \"D\": 4}\\n\n",
        "-NOT ERROR: d = ({ }, { }); d[1][1] = 1\\n\n",
        "-SUBLIST: [(x, y) for x in [1,2,3] for y in [1,2,3]] = [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]\n",
        "\"\"\"\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"Strong Typing\": \"fixed type object, only compatible type operations allowed by interpreter\",\n",
        "\"Dynamic Typing\": \"variables can be any type, only come into existance at assginment\",\n",
        "\"Iterators\": \"objects with *next* method (Python does not have *hasnext*)\",\n",
        "\"Iterable\": \"has *iter* method to return iterator object\"\n",
        "}\n",
        "module2_definitions = {key: module2_definitions[key] for key in sorted(module2_definitions.keys())}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 657
        },
        "outputId": "8e3a95a8-f893-427e-9fd1-fb2d2965fc65"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \n<h3>INTRO TO PYTHON</h3>\n-References: == (checks if variable point to object of same value), is (check if variables point to same object) \n\n-Mutability: strings (immutable), lists (mutable), [:] creates shallow copy of new object\n<h3>SEQUENCE TYPES</h3>\n-Sequence Types: tuple (immutable, mixed types), strings (immutable), list (mutable, mixed types)\n\n-Slicing: returns copy, [i:j] (i...j-1), [i:-j] (i...n-j), [::k] (every k)\n\n-List Operations: append, insert, index (index of first occurence), count (number of occurence), remove (remove first occurence)\n\n<h3>FOR LOOPS</h3>\n-Filtered List Comprehension: [elem for elem in li if elem > 4]\n<h3>ITERATORS</h3>\n-Advantages: efficient memory usage\n<h3>GENERATORS</h3>\n-yield: generator method runs until encountering yield statement, then stops and returns yielded value \n\n-xrange vs range: xrange (generator), range (keeps n values in memory before starting loop) \n\n-Generator Pro: maintain local state, values computed as needed, no storing entire sequence in memory, one pass aggregation, infinite sequences \n\n-Generator Con: inspect individual elements\n\n\n## Module 2 Definitions\n* **Dynamic typing** - variables can be any type, only come into existance at assginment\n* **Iterable** - has *iter* method to return iterator object\n* **Iterators** - objects with *next* method (Python does not have *hasnext*)\n* **Strong typing** - fixed type object, only compatible type operations allowed by interpreter\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",
        "-Steps to Problem Solving: goal formulating, problem formulating, search, execution\\n\n",
        "-Looping: Open Loop (fully observable, deterministic, known, agent ignores precepts) vs Closed Loop\\n\n",
        "-Abstractions\\n\n",
        "- Valid: abstraction able to elaborate any solution into more detailed world\n",
        "- Useful: abstraction able to carry out action in easier manner than original problem \"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "-Standardized Problems: grid world, sliding-tile puzzle, sokoban puzzle\\n\n",
        "-Real-World Problems: route-finding, touring, VLSI layout, robot navigation, assembly sequencing,  \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "-Best-First Search Algorithm: iterate and perform the following\n",
        "- Choose frontier node with minimum ```f(n): if goal, return; else, expand```\n",
        "- For each child node: ```if not reached, add to frontier; else, re-add if lower path```\\n\n",
        "-Search Algorithm Node Components: node state, node parent, node action, node path cost\\n\n",
        "-Algorithm Evaluation: completeness, cost optimality, time complexity, space complexity\\n\n",
        "-State Space Components:\n",
        "- Depth ($d$): number of action in optimal solution\n",
        "- Max depth ($m$): max depth of action in any path\n",
        "- Branching Factor ($b$): number of successor / node\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "-Breadth-First Search\n",
        "- Number of Nodes (expansions): $d=0 (b), d=1 (b^2), ... , d=d (b^d)$; total = $O(b^d)$\\n\n",
        "-Uniform-Cost Search / Dijkstra’s Algorithm\n",
        "- Checking: checks for goal at expansion (pop off queue), not at generation (add to queue)\n",
        "- High Complexity: can explore large trees of low cost before useful, high-cost paths\n",
        "- Equal Cost Complexity: simplifies to $b^{(d+1)}$, same as BFS\\n\n",
        "-Depth-First Search\n",
        "- State Spaces: finite (efficient/complete), acyclic (many paths to same state, complete), cyclic (infinite loop), infinite (infinite path)\n",
        "- Backtracking: only considering one successor at a time, memory reduced to $m$ (only one path)\\n\n",
        "-Iterative Deepening Search\n",
        "- Idea: regenerate nodes at each level (sacrifice time for space)\n",
        "- Time Complexiy: solution exists ($b^d$), solution does not exist ($b^m$)\n",
        "- Number of Nodes: $(d)(b^1) + (d-1)(b^2) + ... (1)(b^d)$ (nodes at bottom only generated once, at top generated $d$ times)\\n\n",
        "-Bidirectional Search\n",
        "- Idea: simultaneously search forward from initial and backward from goal with two frontier/reach states\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "<h3>SEARCH PROBLEMS</h3>\n",
        "-Solution as fixed sequence: fully observable, deterministic, known\\n\n",
        "-Solution as future actions: branching strategy, partially observable, nondeterministic\\n\n",
        "<h3>SEARCH PROBLEM FORMULATIONS</h3>\n",
        "-Problem Definition: State (set $S$), Initial state ($s \\exists S$), Actions ($A$), Transition Model ($(s, a) -> s_r$), Goal State ($Goal(s)$),\\n\n",
        "Path Cost /Action Cost Function (Performance Measure): additive, $c(x,a,y)$ for action $a$ and states $x, y$\\n\n",
        "<h3>BASIC SEARCH ALGORITHMS</h3>\n",
        "-Search Types\\n\n",
        "- Tree Search: treats different paths to same node as distinct\n",
        "- Graph Search: tree search while checking if node has been visited before adding into queue\\n\n",
        "<h3>BFS & DFS</h3>\n",
        "-BFS: FIFO\\n\n",
        "- Usage: possible infinite paths, some solutions have short paths, can quickly discard unlikely path\\n\n",
        "-DFS: LIFO\n",
        "- Characteristics: incomplete (fail in infinite-depth/loops), not optimal (return first found solution, even if not cheapest)\n",
        "- Usage: restricted space, multiple solutions with long paths/wrong paths (quick termination), can quickly fine-tune paths\\n\n",
        "<h3>DEPTH LIMITED SEARCH & ITERATIVE DEEPENING SEARCH</h3>\n",
        "-Depth Limited Search\\n\n",
        "- Characteristics: $l=d$ (solution found), $l < d$ (incomplete), $l > d$ (not optimal)\\n\n",
        "-Iterative Deepening Search\n",
        "- Algorithm: for $l = 0 ->$ infinity, perform depth limited search to $l$\n",
        "- Space Complexity: at $d=0$ (0 node), $d=1$ ($b^1$ node), $d=2$ ($b + b^2$ node), $d=3$ ($b + b^2 + b^3$) node\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 representations\",\n",
        "\"Search\": \"process that problem-solving agent undertake to find solution\",\n",
        "\"Solution\": \"sequence of actions that form a path from initial state to goal state\",\n",
        "\"Optimal Solution\": \"solution that has lowest path cost\",\n",
        "\"State Space\": \"set of all states reachable from intial state by any sequence of actions\",\n",
        "\"Standardized Problems\": \"problems for exhibiting problem solving methods\",\n",
        "\"Real-World Problems\": \"problems for actual usage, with idiosyncacies\",\n",
        "\"Completeness\": \"if solution, algorithm can find it; else: algorithm detect failure\",\n",
        "\"Cost Optimality\": \"algorithm returns lowest path cost solution\",\n",
        "\"Uninformed Search\": \"search problems with only access to problem definition\"\n",
        "}\n",
        "\n",
        "module3_definitions = {key: module3_definitions[key] for key in sorted(module3_definitions.keys())}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b49b5c1e-21f1-45e1-f2f9-27b72c5180a2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n-Steps to Problem Solving: goal formulating, problem formulating, search, execution\n\n-Looping: Open Loop (fully observable, deterministic, known, agent ignores precepts) vs Closed Loop\n\n-Abstractions\n\n- Valid: abstraction able to elaborate any solution into more detailed world\n- Useful: abstraction able to carry out action in easier manner than original problem \n\n## AIMA Chapter 3.2 Example Problems\n\n-Standardized Problems: grid world, sliding-tile puzzle, sokoban puzzle\n\n-Real-World Problems: route-finding, touring, VLSI layout, robot navigation, assembly sequencing,  \n\n## AIMA Chapter 3.3 Search Algorithms\n\n-Best-First Search Algorithm: iterate and perform the following\n- Choose frontier node with minimum ```f(n): if goal, return; else, expand```\n- For each child node: ```if not reached, add to frontier; else, re-add if lower path```\n\n-Search Algorithm Node Components: node state, node parent, node action, node path cost\n\n-Algorithm Evaluation: completeness, cost optimality, time complexity, space complexity\n\n-State Space Components:\n- Depth ($d$): number of action in optimal solution\n- Max depth ($m$): max depth of action in any path\n- Branching Factor ($b$): number of successor / node\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n-Breadth-First Search\n- Number of Nodes (expansions): $d=0 (b), d=1 (b^2), ... , d=d (b^d)$; total = $O(b^d)$\n\n-Uniform-Cost Search / Dijkstra’s Algorithm\n- Checking: checks for goal at expansion (pop off queue), not at generation (add to queue)\n- High Complexity: can explore large trees of low cost before useful, high-cost paths\n- Equal Cost Complexity: simplifies to $b^{(d+1)}$, same as BFS\n\n-Depth-First Search\n- State Spaces: finite (efficient/complete), acyclic (many paths to same state, complete), cyclic (infinite loop), infinite (infinite path)\n- Backtracking: only considering one successor at a time, memory reduced to $m$ (only one path)\n\n-Iterative Deepening Search\n- Idea: regenerate nodes at each level (sacrifice time for space)\n- Time Complexiy: solution exists ($b^d$), solution does not exist ($b^m$)\n- Number of Nodes: $(d)(b^1) + (d-1)(b^2) + ... (1)(b^d)$ (nodes at bottom only generated once, at top generated $d$ times)\n\n-Bidirectional Search\n- Idea: simultaneously search forward from initial and backward from goal with two frontier/reach states\n\n## Module 3 Lecture Notes\n\n<h3>SEARCH PROBLEMS</h3>\n-Solution as fixed sequence: fully observable, deterministic, known\n\n-Solution as future actions: branching strategy, partially observable, nondeterministic\n\n<h3>SEARCH PROBLEM FORMULATIONS</h3>\n-Problem Definition: State (set $S$), Initial state ($s \\exists S$), Actions ($A$), Transition Model ($(s, a) -> s_r$), Goal State ($Goal(s)$),\n\nPath Cost /Action Cost Function (Performance Measure): additive, $c(x,a,y)$ for action $a$ and states $x, y$\n\n<h3>BASIC SEARCH ALGORITHMS</h3>\n-Search Types\n\n- Tree Search: treats different paths to same node as distinct\n- Graph Search: tree search while checking if node has been visited before adding into queue\n\n<h3>BFS & DFS</h3>\n-BFS: FIFO\n\n- Usage: possible infinite paths, some solutions have short paths, can quickly discard unlikely path\n\n-DFS: LIFO\n- Characteristics: incomplete (fail in infinite-depth/loops), not optimal (return first found solution, even if not cheapest)\n- Usage: restricted space, multiple solutions with long paths/wrong paths (quick termination), can quickly fine-tune paths\n\n<h3>DEPTH LIMITED SEARCH & ITERATIVE DEEPENING SEARCH</h3>\n-Depth Limited Search\n\n- Characteristics: $l=d$ (solution found), $l < d$ (incomplete), $l > d$ (not optimal)\n\n-Iterative Deepening Search\n- Algorithm: for $l = 0 ->$ infinity, perform depth limited search to $l$\n- Space Complexity: at $d=0$ (0 node), $d=1$ ($b^1$ node), $d=2$ ($b + b^2$ node), $d=3$ ($b + b^2 + b^3$) node\n \n\n## Module 3 Definitions\n* **Completeness** - if solution, algorithm can find it; else: algorithm detect failure\n* **Cost optimality** - algorithm returns lowest path cost solution\n* **Optimal solution** - solution that has lowest path cost\n* **Problem-solving agent** - an agent that can formulate a plan via search; use atomic representations\n* **Real-world problems** - problems for actual usage, with idiosyncacies\n* **Search** - process that problem-solving agent undertake to find solution\n* **Solution** - sequence of actions that form a path from initial state to goal state\n* **Standardized problems** - problems for exhibiting problem solving methods\n* **State space** - set of all states reachable from intial state by any sequence of actions\n* **Uninformed search** - search problems with only access to problem definition\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",
        "-Greedy Best-First Search\n",
        "- Characteristics: complete (only in finite state space), space and time complexity $O(V)$\\n\n",
        "-Inadmissible Heuristics\n",
        "- Case 1: optimal path found; if for $C^*$ (optimal) and $C$ (second-best), $h(n)$ overestimates less than $C2-C^*$\n",
        "- Case 2: path found, for any path in which $h(n)$ is admissible for all nodes $n$ on path\\n\n",
        "-A* Search\n",
        "- Consistency vs Admissibility: consistency stronger than admissibility; all consistent are admissible ... not vice versa\n",
        "- Consistency Feature: first reaching will be shortest path, don't need to wait for expansion\\n\n",
        "-Search Contours\n",
        "- Uniform Cost-Search: basis ($g(n)$), shape (circular), monotonic (always)\n",
        "- A* Search: basis ($g(n)+h(n)$), shape (narrow around optimal path), monotonic (consistent, $h(n) = c(n, a, n') + h(n')$)\n",
        "- Nodes: $f(n) < C^*$ (surely expanded, always reached), $f(n)=C^*$ (may reached before selecting goal), $f(n)>C*$ (never reached)\\n\n",
        "-Weighted A Search:\n",
        "- Evaluation Function: $f(n) = g(n) + w * n$ where $w > 1$\n",
        "- Purpose: trades correctness (not optimal, solution between $C^*$ and $W * C^*$) for efficiency (less node explored)\n",
        "- Types: Bounded Suboptimal Search (solution within $W$ factor of $C^*$), Bounded-Cost Search (solution $<= C$), Unbounded-Cost Search (any fast solution)\\n\n",
        "-Memory-Bounded Search\n",
        "- Beam Search: algorithm (limit frontier size to: best $k$, within $f-score$, $delta - f-score$), characteristic (incomplete and suboptimal)\n",
        "- Iterative Deepening Search: algorithm (cutoff set at smallest f-score of node exceeding previous iteration), characteristic (works well for steps, poorly if every node with different f-score)\n",
        "- Recursive Best First Search: algorithm (recursive DFS, use $f_limit$ to track $f_value$ of best alternative path, if current node > limit ... unwind),\n",
        "  characteristic (optimal if $h(n)$ is admissible), space complexity ($O(d)$), time complexity (dependant on heuristic accuracy & frequency of path changes)\n",
        "- Simplifed Memory Bounded A* Search: algorithm (expand best leaf until memory is full, regenerates subtree only if all desendants are forgotten), characteirstic (complete, optimal)\\n\n",
        "-Bidirectional Heuristic Search\n",
        "- Consideration: analyze pair of verticies for expansion, rather than single node\n",
        "- Evaluation: $max(2 * g(n), g(n) + h(n))$, can come from either frontiers \"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "-Pattern Database\n",
        "- Purpose: store solution cost for every subproblem instance\n",
        "- Example: for 8-tile problem, take 1-4 patterns\n",
        "- Multiple Databases: diminishing returns, each database with own admissible heuristic (take max value of heuristics)\n",
        "- Disjoint Databases: combine multiple pattern database, need to ensure databases are disjoint (1234: cost of moving 1,2,3,4 ... not all)\\n\n",
        "-Precomputation\n",
        "- Purpose: conduct expensive operations that are amortized over multiple searches\n",
        "- Landmark: for each vertex $v$ and landmark $l \\exists L$, compute $C^*(v, L)$\n",
        "- Inadmissible: $h(n) = min(C^*(n, L) + C^*(L, goal)))$ for all landmarks $l$; optimal if pass through landmark, overestimates if not\n",
        "- Admissible: $h(n) = max(|C^*(n, L) - C^*(goal, L)|)$ for all landmarks $l$; find goal distance if in configuration: n->goal->landmark\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" <h3></h3>\n",
        "<h3>GREEDY BEST-FIRST SEARCH</h3>\n",
        "-Evaluation Function: $f(n) = h(n)$\\n\n",
        "-Characteristics: not optimal, not complete (can be stuck in loop)\n",
        "<h3>A* SEARCH</h3>\n",
        "-Evaluation Function: $f(n) = g(n) + h(n)$; $g(n)$: actual cost to reach node, $h(n)$: estimated cost to node\\n\n",
        "-Admissible Heuristics\n",
        "- Admissibility: inadmissible (break optimality, pushes good options down in PQ), admissible (slows down but never outweighs true cost)\n",
        "- Defining Heuristics: cost of exact solution to relaxed problem\n",
        "- Worst: $h(n) = 0$; dominated by all heuristics\n",
        "- Best: $h^*(n)$ ... underestimates, but get as close/accurate to goal as possible; dominates all heuristics\\n\n",
        "-Optimality Proof: for any nodes A (optimal), n (ancestor of A or A), B (subptimal), $f(n) <= f(A) < f(B)$ so n expands before B\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Heuristic Knowledge\" : \"useful knoweldge, but not necesarily correct\",\n",
        "\"Heuristic Function\": \"return estimate of distance from node n to goal\",\n",
        "\"Admissible Heuristics\": \"never overestimates,  for all node $n$, $h(n) <= h*(n)$ (true cost) and $h(n) >= 0$\",\n",
        "\"Optimistic Heuristics\": \"admissible heuristics\",\n",
        "\"Relaxed Problem\": \"problem with less action restrictions; state-space is supergraph (more edges)\",\n",
        "\"Dominance\": \"h2 dominates if $h_2(n) >= h_1(n)$ for all n and both are admissible\",\n",
        "\"Informed Search\": \"search strategies capable of using domain-specific hints to find solution\",\n",
        "\"Consistent Heuristics\": \"for node $n$ and successor $n'$, $h(n) <= c(n, a, n') + h(n')$\",\n",
        "\"Optimistically Efficient\": \"search strategy for any algorithm of same intial state and heuristic, expand all surely expanded nodes\",\n",
        "\"Satisficing Search\": \"search strategy for finding solutions that are suboptimal, but 'good enough'\",\n",
        "\"Effective Branching Factor\": \"$N/D$\"\n",
        "}\n",
        "module4_definitions = {key: module4_definitions[key] for key in sorted(module4_definitions.keys())}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "682833ba-8e60-48e5-bc82-a754664d3676"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n-Greedy Best-First Search\n- Characteristics: complete (only in finite state space), space and time complexity $O(V)$\n\n-Inadmissible Heuristics\n- Case 1: optimal path found; if for $C^*$ (optimal) and $C$ (second-best), $h(n)$ overestimates less than $C2-C^*$\n- Case 2: path found, for any path in which $h(n)$ is admissible for all nodes $n$ on path\n\n-A* Search\n- Consistency vs Admissibility: consistency stronger than admissibility; all consistent are admissible ... not vice versa\n- Consistency Feature: first reaching will be shortest path, don't need to wait for expansion\n\n-Search Contours\n- Uniform Cost-Search: basis ($g(n)$), shape (circular), monotonic (always)\n- A* Search: basis ($g(n)+h(n)$), shape (narrow around optimal path), monotonic (consistent, $h(n) = c(n, a, n') + h(n')$)\n- Nodes: $f(n) < C^*$ (surely expanded, always reached), $f(n)=C^*$ (may reached before selecting goal), $f(n)>C*$ (never reached)\n\n-Weighted A Search:\n- Evaluation Function: $f(n) = g(n) + w * n$ where $w > 1$\n- Purpose: trades correctness (not optimal, solution between $C^*$ and $W * C^*$) for efficiency (less node explored)\n- Types: Bounded Suboptimal Search (solution within $W$ factor of $C^*$), Bounded-Cost Search (solution $<= C$), Unbounded-Cost Search (any fast solution)\n\n-Memory-Bounded Search\n- Beam Search: algorithm (limit frontier size to: best $k$, within $f-score$, $delta - f-score$), characteristic (incomplete and suboptimal)\n- Iterative Deepening Search: algorithm (cutoff set at smallest f-score of node exceeding previous iteration), characteristic (works well for steps, poorly if every node with different f-score)\n- Recursive Best First Search: algorithm (recursive DFS, use $f_limit$ to track $f_value$ of best alternative path, if current node > limit ... unwind),\n  characteristic (optimal if $h(n)$ is admissible), space complexity ($O(d)$), time complexity (dependant on heuristic accuracy & frequency of path changes)\n- Simplifed Memory Bounded A* Search: algorithm (expand best leaf until memory is full, regenerates subtree only if all desendants are forgotten), characteirstic (complete, optimal)\n\n-Bidirectional Heuristic Search\n- Consideration: analyze pair of verticies for expansion, rather than single node\n- Evaluation: $max(2 * g(n), g(n) + h(n))$, can come from either frontiers \n\n## AIMA Chapter 3.6 Heuristic Functions\n\n-Pattern Database\n- Purpose: store solution cost for every subproblem instance\n- Example: for 8-tile problem, take 1-4 patterns\n- Multiple Databases: diminishing returns, each database with own admissible heuristic (take max value of heuristics)\n- Disjoint Databases: combine multiple pattern database, need to ensure databases are disjoint (1234: cost of moving 1,2,3,4 ... not all)\n\n-Precomputation\n- Purpose: conduct expensive operations that are amortized over multiple searches\n- Landmark: for each vertex $v$ and landmark $l \\exists L$, compute $C^*(v, L)$\n- Inadmissible: $h(n) = min(C^*(n, L) + C^*(L, goal)))$ for all landmarks $l$; optimal if pass through landmark, overestimates if not\n- Admissible: $h(n) = max(|C^*(n, L) - C^*(goal, L)|)$ for all landmarks $l$; find goal distance if in configuration: n->goal->landmark\n \n\n## Module 4 Lecture Notes\n <h3></h3>\n<h3>GREEDY BEST-FIRST SEARCH</h3>\n-Evaluation Function: $f(n) = h(n)$\n\n-Characteristics: not optimal, not complete (can be stuck in loop)\n<h3>A* SEARCH</h3>\n-Evaluation Function: $f(n) = g(n) + h(n)$; $g(n)$: actual cost to reach node, $h(n)$: estimated cost to node\n\n-Admissible Heuristics\n- Admissibility: inadmissible (break optimality, pushes good options down in PQ), admissible (slows down but never outweighs true cost)\n- Defining Heuristics: cost of exact solution to relaxed problem\n- Worst: $h(n) = 0$; dominated by all heuristics\n- Best: $h^*(n)$ ... underestimates, but get as close/accurate to goal as possible; dominates all heuristics\n\n-Optimality Proof: for any nodes A (optimal), n (ancestor of A or A), B (subptimal), $f(n) <= f(A) < f(B)$ so n expands before B\n \n\n## Module 4 Definitions\n* **Admissible heuristics** - never overestimates,  for all node $n$, $h(n) <= h*(n)$ (true cost) and $h(n) >= 0$\n* **Consistent heuristics** - for node $n$ and successor $n'$, $h(n) <= c(n, a, n') + h(n')$\n* **Dominance** - h2 dominates if $h_2(n) >= h_1(n)$ for all n and both are admissible\n* **Effective branching factor** - $N/D$\n* **Heuristic function** - return estimate of distance from node n to goal\n* **Heuristic knowledge** - useful knoweldge, but not necesarily correct\n* **Informed search** - search strategies capable of using domain-specific hints to find solution\n* **Optimistic heuristics** - admissible heuristics\n* **Optimistically efficient** - search strategy for any algorithm of same intial state and heuristic, expand all surely expanded nodes\n* **Relaxed problem** - problem with less action restrictions; state-space is supergraph (more edges)\n* **Satisficing search** - search strategy for finding solutions that are suboptimal, but 'good enough'\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",
        "-Game Definition: initial state (board set-up), to-move (player performing move), actions (legal moves in state $s$), result (transition model of state resulting from action a in state s),\n",
        "is-terminal (terminl test for if game is over), utility (final numeric value when game ends in terminal state)\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "-MinMax Algorithm: DFS, time ($O(b^m)$), space ($O(bm)$ of all action at once; $O(m)$ if one action at a time)\\n\n",
        "-Multiplayer Games: replace single node values witha vector values\n",
        "- Terminal State: vectors as utility state of each player\n",
        "- Non-Terminal State: vectors as utility vector of successor state with highest value for player at node\\n\n",
        "-Move Ordering\n",
        "- Perfect Ordering: reduce nodes examined to ($O(b^{(m/2))}$), branching factor ($b^{(1/2)}$)\n",
        "- Transpositions Table: cached for easy lookup\n",
        "- Strategy Types: Type A (wide and shallow, small branching factors) vs Type B (deep and narrow, large branching factors)\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "-$Eval(s, p)$: returns estimate of expected utility to reduce computation time\\n\n",
        "-Terminal State: Eval = Utility vs Non-Terminal State: utility(loss, p) <= Eval(s, p) <= Utility(win, p)\\n\n",
        "-Cutting off Search: reduce search space\n",
        "- Method 1: limit depth\n",
        "- Method 2: set time limit, at time limit, return deepest completed search\n",
        "- Method 3: Quiscient Search: return false non-quiscient results\n",
        "- Method 4: Singular Extensions to mitigate horizon focus\\n\n",
        "-Forward Pruning\n",
        "- Purpose: tradeoff computation time for error risk\n",
        "- Beam Search: at each ply, consider only $n$ best moves,\n",
        "- ProbCut: calculate probability with shallow pruning & expereince to prune nodes probably outisde (alpha, beta) window\n",
        "- Lat Move reduction: if assuming move ordering in order, only re-run full-depth search if returned value greater than alpha\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "-ExpectiMax Runtime: $O(b^m n^m)$\\n\n",
        "-Effects of Probabilities: blows up the consideration space \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "-Formulas\n",
        "- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n",
        "- $P(RESULT(a)=s') = Sum of (P(s) * P(s'|s, a))$ for all states (s): probability that $s$ reaches $s'$ after taking $a$\n",
        "- $EU(a) = Sum of P(RESULT(a)=s') * U(s')$ for all states (s')\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "-Utility Theory\n",
        "- Orderability: agent cannot avoide deciding preference, must either prefer one or rate as equal\n",
        "- Transitivity: if agent prefers A > B and B > C, agent prefers A > C\n",
        "- Continuity: if agent prefers A > B > C, there exist some probability p where agent indifferent towards B (for sure) and A ($p$) or C ($1-p$)\n",
        "- Substitutability: if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\n",
        "- Monotonicity: if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\n",
        "- Decomposability: compounded lotteries can be reduced to simpler ones with probability laws\\n\n",
        "-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\\n \n",
        "-Expected Utility of Lottery: $U(L) = \\sum_{i}p_i * U(S_i)$\\n\n",
        "-Utility Function: exists for all rational agent, not necessarily unique\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\\n\n",
        "-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\\n\n",
        "-Bias: selecting action with highest utility, estimates are overly optimistic\\n\n",
        "-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "<h3>GAME FORMULATION</h3>\n",
        "-Key Game Properties: two players, zero-sum, clear set of legal moves, well-defined outcomes\\n\n",
        "-Game Search Steps: consider all legal successors to current state, evaluate successor board position, pick move with best board state, repeat\\n\n",
        "-Game Trees: nodes (board positions), edges (legal moves)\\n\n",
        "-Evaluation Functions: $f(n) > 0$ (max is winning),  $f(n) = 0$ (draw), $f(n) < 0$ (min is winning)\n",
        "<h3>MINMAX RULES</h3>\n",
        "-MinMax Procedures\\n\n",
        "- Expand game tree a fix number of $ply$\n",
        "- Apply evaluation function to leaf positions\n",
        "- Calculate back-up values bottom-up\n",
        "- Pick move assigned to MAX at root\n",
        "- Wait for MIN to respond\\n\n",
        "-Pruning\\n\n",
        "- alpha (-inf): MAX's current lower bound, never allow worse score than alpha, don't evaluate branch if v >= B (MIN never select this MAX node)\n",
        "- beta (+inf): MIN's current upper bound, never allow better score than Beta, don't evaluate branch if v <= A (MAX never select this MIN node)\\n\n",
        "<h3>EXPECTMAX</h3>\n",
        "-Causes for Unpredictability: explicit randomness (dice), suboptimal opponent, failed actions\\n\n",
        "-ExpectiMax\n",
        "- Algorithm: computes average score under optimal play\n",
        "- Nodes: max (same), min (chance nodes with uncertain outcomes, take weighted average)\n",
        "- Space: greatly increases (have to simulate more states and opponent simulating)\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Perfect Information / Zero-Sum Games\": \"games in which one player's loss is another player's gain\",\n",
        "\"Evaluation Functions\": \"functio that determines quality of board position based on static features\",\n",
        "\"Transpositions\": \"different permutations of move sequences may lead to same board positions\",\n",
        "\"Type A Strategy\": \"strategy in which all moves at given depth considered and estimated with heuristics\",\n",
        "\"Type B Strategy\": \"strategy in which only promising strategies explored deeply\",\n",
        "\"Quiescent\": \"board positions with successor states not swinging evaluations (e.g.: queen capture)\",\n",
        "\"Horizon Effect\": \"impeding opponent move will cause serious damage, but is temporarily delayable (e.g.: bishop capture)\",\n",
        "\"Singular Extension\": \"set of moves clearly the best for a given board position\",\n",
        "\"Forward Pruning\": \"pruning of moves that seem bad (may actually be good)\",\n",
        "\"Policy\": \"maping of possible state to best move for given state\",\n",
        "\"Stochastic games\": \"games with random elements and probability\",\n",
        "\"Maximum Expected Utility\": \"principle in which rational agent chooses action that maximize agent EU\",\n",
        "\"Lottery\": \"set out action outcomes, denoted by $L=[p_1, S_1; p_2, S_2; ... p_n, S_n]$\",\n",
        "\"Value Function / Ordinal Utility Function\": \"ranking of preferences of states\",\n",
        "\"Prefernce Elicitation\": \"the process of finding human utility function by presenting choice and using observed preferences\",\n",
        "\"Normalized Utility\": \"utility with scale between 0 (worst) and 1 (best)\",\n",
        "\"Micromort\": \"one in a million chance of death\",\n",
        "\"Certainty Equivalent\": \"value agent accepts for sure instead of lottery chance\",\n",
        "\"Insurance Premium\": \"Lottery EMV - certainty equivalent\",\n",
        "\"Certainity Effect\": \"people are likely to prefer certain outcomes\",\n",
        "\"Anchoring Effect\": \"people prefer relative utility judgements to absolute judgement\"\n",
        "}\n",
        "module5_definitions = {key: module5_definitions[key] for key in sorted(module5_definitions.keys())}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0f88ec90-c560-4d43-ea2e-c16b230dd102"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n-Game Definition: initial state (board set-up), to-move (player performing move), actions (legal moves in state $s$), result (transition model of state resulting from action a in state s),\nis-terminal (terminl test for if game is over), utility (final numeric value when game ends in terminal state)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n-MinMax Algorithm: DFS, time ($O(b^m)$), space ($O(bm)$ of all action at once; $O(m)$ if one action at a time)\n\n-Multiplayer Games: replace single node values witha vector values\n- Terminal State: vectors as utility state of each player\n- Non-Terminal State: vectors as utility vector of successor state with highest value for player at node\n\n-Move Ordering\n- Perfect Ordering: reduce nodes examined to ($O(b^{(m/2))}$), branching factor ($b^{(1/2)}$)\n- Transpositions Table: cached for easy lookup\n- Strategy Types: Type A (wide and shallow, small branching factors) vs Type B (deep and narrow, large branching factors)\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n-$Eval(s, p)$: returns estimate of expected utility to reduce computation time\n\n-Terminal State: Eval = Utility vs Non-Terminal State: utility(loss, p) <= Eval(s, p) <= Utility(win, p)\n\n-Cutting off Search: reduce search space\n- Method 1: limit depth\n- Method 2: set time limit, at time limit, return deepest completed search\n- Method 3: Quiscient Search: return false non-quiscient results\n- Method 4: Singular Extensions to mitigate horizon focus\n\n-Forward Pruning\n- Purpose: tradeoff computation time for error risk\n- Beam Search: at each ply, consider only $n$ best moves,\n- ProbCut: calculate probability with shallow pruning & expereince to prune nodes probably outisde (alpha, beta) window\n- Lat Move reduction: if assuming move ordering in order, only re-run full-depth search if returned value greater than alpha\n \n\n## AIMA Chapter 5.5 Stochastic Games\n\n-ExpectiMax Runtime: $O(b^m n^m)$\n\n-Effects of Probabilities: blows up the consideration space \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n-Formulas\n- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n- $P(RESULT(a)=s') = Sum of (P(s) * P(s'|s, a))$ for all states (s): probability that $s$ reaches $s'$ after taking $a$\n- $EU(a) = Sum of P(RESULT(a)=s') * U(s')$ for all states (s')\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n-Utility Theory\n- Orderability: agent cannot avoide deciding preference, must either prefer one or rate as equal\n- Transitivity: if agent prefers A > B and B > C, agent prefers A > C\n- Continuity: if agent prefers A > B > C, there exist some probability p where agent indifferent towards B (for sure) and A ($p$) or C ($1-p$)\n- Substitutability: if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\n- Monotonicity: if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\n- Decomposability: compounded lotteries can be reduced to simpler ones with probability laws\n\n-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\n \n-Expected Utility of Lottery: $U(L) = \\sum_{i}p_i * U(S_i)$\n\n-Utility Function: exists for all rational agent, not necessarily unique\n\n## AIMA Chapter 16.3 Utility Functions\n\n-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\n\n-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\n\n-Bias: selecting action with highest utility, estimates are overly optimistic\n\n-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\n\n\n\n## Module 5 Lecture Notes\n \n<h3>GAME FORMULATION</h3>\n-Key Game Properties: two players, zero-sum, clear set of legal moves, well-defined outcomes\n\n-Game Search Steps: consider all legal successors to current state, evaluate successor board position, pick move with best board state, repeat\n\n-Game Trees: nodes (board positions), edges (legal moves)\n\n-Evaluation Functions: $f(n) > 0$ (max is winning),  $f(n) = 0$ (draw), $f(n) < 0$ (min is winning)\n<h3>MINMAX RULES</h3>\n-MinMax Procedures\n\n- Expand game tree a fix number of $ply$\n- Apply evaluation function to leaf positions\n- Calculate back-up values bottom-up\n- Pick move assigned to MAX at root\n- Wait for MIN to respond\n\n-Pruning\n\n- alpha (-inf): MAX's current lower bound, never allow worse score than alpha, don't evaluate branch if v >= B (MIN never select this MAX node)\n- beta (+inf): MIN's current upper bound, never allow better score than Beta, don't evaluate branch if v <= A (MAX never select this MIN node)\n\n<h3>EXPECTMAX</h3>\n-Causes for Unpredictability: explicit randomness (dice), suboptimal opponent, failed actions\n\n-ExpectiMax\n- Algorithm: computes average score under optimal play\n- Nodes: max (same), min (chance nodes with uncertain outcomes, take weighted average)\n- Space: greatly increases (have to simulate more states and opponent simulating)\n \n\n## Module 5 Definitions\n* **Anchoring effect** - people prefer relative utility judgements to absolute judgement\n* **Certainity effect** - people are likely to prefer certain outcomes\n* **Certainty equivalent** - value agent accepts for sure instead of lottery chance\n* **Evaluation functions** - functio that determines quality of board position based on static features\n* **Forward pruning** - pruning of moves that seem bad (may actually be good)\n* **Horizon effect** - impeding opponent move will cause serious damage, but is temporarily delayable (e.g.: bishop capture)\n* **Insurance premium** - Lottery EMV - certainty equivalent\n* **Lottery** - set out action outcomes, denoted by $L=[p_1, S_1; p_2, S_2; ... p_n, S_n]$\n* **Maximum expected utility** - principle in which rational agent chooses action that maximize agent EU\n* **Micromort** - one in a million chance of death\n* **Normalized utility** - utility with scale between 0 (worst) and 1 (best)\n* **Perfect information / zero-sum games** - games in which one player's loss is another player's gain\n* **Policy** - maping of possible state to best move for given state\n* **Prefernce elicitation** - the process of finding human utility function by presenting choice and using observed preferences\n* **Quiescent** - board positions with successor states not swinging evaluations (e.g.: queen capture)\n* **Singular extension** - set of moves clearly the best for a given board position\n* **Stochastic games** - games with random elements and probability\n* **Transpositions** - different permutations of move sequences may lead to same board positions\n* **Type a strategy** - strategy in which all moves at given depth considered and estimated with heuristics\n* **Type b strategy** - strategy in which only promising strategies explored deeply\n* **Value function / ordinal utility function** - ranking of preferences of states\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",
        "-Constraint Graphs: nodes (variables), edges (constraints)\\n\n",
        "-Types of CSPs\n",
        "- Finite vs Infinite: infinite domains (use implicit constraints: $T_1 + d_1 <= T_2$)\n",
        "- Continuous vs Discrete: continuous (e.g.: Hubble Telescope)\n",
        "-Constraints: unary (single variable), binary (two variables), global (3+ variables)\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "-Node Consistency\n",
        "- Definition: variable domain value satisfy unary constraint\n",
        "- Example: SA dislike green, SA has domain ${red, blue}$ (no green)\\n\n",
        "-Arc Consistency\n",
        "- Definition: domain value satisfy varable binary constriants\n",
        "- Transformation: any n-ary constraint can be converted into binary constraints\n",
        "- Communitavity: X arc-consistent to Y does NOT mean Y arc-consistent to X\\n\n",
        "-Path Consistency\n",
        "- Definition: ${X_i, X_j}$ path-consistent to $X_m$ if for every consistent assignment ${X_i = a, X_j = b}$, exists $X_m$ satisfying ${X_i, X_m}$ & ${X_j, X_m}$\\n\n",
        "-K-Consistency\n",
        "- Definition: for any set of consistent assignment to $k-1$ variables, consitent values can always be assigned to kth variable\n",
        "- Solving Strongly-n Consistent: choose consistent value for $X_1$, for $X_2$ (graph is 2-consistent), for $X_3$ (graph is 3-consistent),\n",
        "                                for each variable $V_i$ ... search $d$ values in domain: $O(n^2 * d)\\n\n",
        "-Global Constraints\n",
        "- Example: Sudko Alldiff (all row numbers are different)\n",
        "- Algorithm: delete variable with singleton domain, delete variable value from remaining variables, repeat as long as singleton variable\\n\n",
        "-Bounds\n",
        "- Bound Propogation: domains represented by upper and lower bounds\n",
        "- Bound Consistent: for every $X$ and its upper and lower bound, there exists some $Y$ satisfying constraint between $X$ and $Y$ for every variable $Y$\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "-Space Complexity ($n$ variables and $d$ domain size): $d^n$ number of leaves (commutativty reduces leaves)\\n\n",
        "-Variable and Value Ordering: which variable assigned next, and in what order?\n",
        "- MRV: most-constrained / fail-first variable\n",
        "- Degree Heuristic: select variable with largest constraints (to reudce branching factor)\n",
        "- Least-Constraing Value\\n\n",
        "-Iterleaving Search and Inference: what inference performed at each step in search?\n",
        "- Forward Checking: whenever $X$ is assigned, establish arc consistency for $X$ and neighbor $Y$ by deleting inconsistent values from $Y$ domain\n",
        "- Maintaining Arc Consistency: detect inconsistencies, after assigning value to $X_i$, AC-3 performed with starting queue of arcs ($X_j, X_i$) for unassigned neighbors of $X_i$, more powerful than forward checking since recursively propogate constraints when changes made to domains of variables\\n\n",
        "-Intelligent Backtracking: can backtrack more than one step?\n",
        "- Backtracking: can fail if previous assignment does not resolve constraint problem\n",
        "- Backjumping: conflict set supplied by forward checking (at forward checking of $X=x$ and delete value from $Y$, add $X=x$ to $Y$ conflict set)\n",
        "- Conflict Directed Backjumping: $conf(X_i) = conf(X_i) \\cup conf(X_j) - {X_i}$\\n\n",
        "-Constraint Learning: can save and resue partial search results?\n",
        "- No-good: create cache or constraint in CSP\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "-Min-Conflicts Heuristics: \"identify value assignment with minimum number of conflicts, change  change value to fit constraints\\n\n",
        "-Tabu Search: keeping list of recently visited states and forbidding return to them\\n\n",
        "-Constraint Weighting: concentrate search on important constraints, have all constraints start at one and incremented per violation\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "-Connected Components ($n$ total variables, $c$ variables / CSP, $d$ domain): $n/c$ subproblems each with $d^c$ work ... $O(d^c nc)$ vs $O(d^n)$\\n\n",
        "-Tree Problems\n",
        "- Algorithm: topologically sort, choose value for parent, choose valid value for child (no need for backtracking)\n",
        "- Time Complexity: creating topological sort $O(n)$, domain comparisons $d$ for two variables, total time $O(nd^2)$, linear\\n\n",
        "-Cutset Conditioning: better memory (linear)\n",
        "- Choose subset $S$ of CSP variable such that constraint graph becomes tree after removing $S$\n",
        "- For each possible assignment to variables in S: remove domains of remaining variable inconsistent with S assignment, return solution\n",
        "- Runtime (cycle cutset size c $c$): $O(d^c * (n-c) * d^2)$... try $d^c$ combination of values for variables in $S$, $n-c$ for each tree, and $d^2$ for each domain\\n\n",
        "-Tree Decomposition Requirements: better time\n",
        "- Every variable in original problem appears in >= 1 node\n",
        "- If two variables connected by constraint in original problem, appear in at least one node\n",
        "- If variable appears in two nodes, must appear in  every node along path connecting node (variable must have same value in every node)\n",
        "- Runtime ( number of tree nodes $n$, size of largest domain $d$): $O(nd^2)$ with Tree-CSP Solver\n",
        "- Runtime with minimal tree width: $O(nd^{(w+1)})$\\n\n",
        "-Value Symmetry\n",
        "- Example: WA, NT, SA must be different colors, but 3! assignments of different colors\n",
        "- Add symmetry-breaking constraints: NT < SA < WA for alphabet coloring\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" <h3></h3>\n",
        "<h3>INTRO TO CSPs</h3>\n",
        "-Components of CSP\\n\n",
        "- Finite Set of Variables: $X_1, X_2, ..., X_n$\\n\n",
        "- Nonempty domain of possible values for each variable: $D_1, D_2, ..., D_N$ where $D_1 = {v_1, ..., v_k}$\\n\n",
        "- Finite Set of Constraints: $C_1, C_2, ... C_m$\\n\n",
        "-CSP Solution: complete and consistent assignment\\n\n",
        "-CSP Benefits\n",
        "- Clean specificiation of problems: no need for specific heuristics\n",
        "- CSP know variables violating constraints: can focus search\n",
        "- CSP automatically prune branches violating constraint: reduce search space\\n\n",
        "<h3>CSPs AS SEARCH PROBLEMS</h3>\n",
        "-Initial State: empty assignment {}\\n\n",
        "-Successor Function: assign value to unassigned variable without conflict\\n\n",
        "-Goal Test: complete assignment\\n\n",
        "-Path Cost: constant cost for eery step\\n\n",
        "-Size: $n$ variables (each with domain size $d$), branching factor at level l $(n-l)*d$, total leaves ($n! * d^n$)\n",
        "<h3>HEURISTICS TO IMPROVING BACKTRACKING EFFICIENCY</h3>\n",
        "-Which variable to assign next?: most contrained variable (variable with least legal values)\\n\n",
        "-Which variable values to assign?: least constraining values\\n\n",
        "-How to detect imminent failure?: Forward checking (terminatenate search if unassigned variable has no legal values)\\n\n",
        "- Can't detect all failures (two adjacent states both left with one and same color)\\n\n",
        "<h3>ARC CONSISTENCY AND AC3</h3>\n",
        "-CSP Solvers: search (assign value to variable) and constrint propogation/inference (eliminate possible values violating local consistency)\\n\n",
        "-Local Consistency: Node (1/unary), Arc (2/Binary), Path (3+)\\n\n",
        "-Walts/Mackworth Constraints Propogation Algorithms\n",
        "- Assign every node in constraint graph a set of all possible values\n",
        "- Repeat until no change in set of values: for each node i ... for each nieghboring node j ... remove any value from i not arc consistent with j\\n\n",
        "-AC3 Inefficiencies\n",
        "- Each Iteration: only need to examine $X_i$ where at least one neighbor lost a value in previous iteration\n",
        "- If $X_i$ lose value due to $Y_j$, don't need to check $Y_j$ on next iteration\n",
        "- Remove $X_i$ can only make $Y_j$ arc inconsistent with $X_i$, so only check if (j, i) is still arc-consistent\\n\n",
        "-Time Complexity\n",
        "- Number of Arcs: $O(n^2)$, if all nodes connected to ever other nodes\n",
        "- Checking Arcs: $O(d^2)$ for d arcs\n",
        "- Inserting Arcs into Queue: $O(d)$, each arc inserted $O(d)$ times ($X_i$ has at most $d$ values to delete)\n",
        "- Total: $O(n^2 * d^3)$\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Consistent\" : \"solution not breaking the constraints\",\n",
        "\"Backtracking\": \"DFS on single-variable assignments\",\n",
        "\"Arc Consistency\": \"X -> Y as consistent iff for every x of X, there exists allowed y\",\n",
        "\"Constraint Propogation\": \"reducing legal values of a variable via available constrains\",\n",
        "\"Strongly K-Consistent\": \"CSPs consistent from k, k-1, ... 1\",\n",
        "\"Global Constraints\": \"constraints involving arbitraryn number of variables\",\n",
        "\"Minimum Remaining Values\": \"picks variable most likely to fail\",\n",
        "\"Least Constraing Value\": \"pick values with least constraints on neighbors\",\n",
        "\"Chronological Backtracking\": \"after branch failure, back up to preceding variable of most recent decision point\",\n",
        "\"Backjumping\": \"backtracking to most recent assignment in conflict set\",\n",
        "\"Conflict-Directed Backumping\": \"backtracking to preceding variable AND all subsequent variables causing conflict\",\n",
        "\"Constraint Learning\": \"finding min set of variabel from conflict set cauisng issues\",\n",
        "\"No-Good\": \"variable assignments doomed to fail\",\n",
        "\"Directional Arc Consistency\": \"for every $X_i$ arcconsistent for each $X_j$ for $j>i$\",\n",
        "\"Tree Width\": \"minimum width of tree decompositions\",\n",
        "\"CSP\": \"Constraint Satisication Problem, state with variable/value and conditions for constraints on variables\"\n",
        "}\n",
        "module6_definitions = {key: module6_definitions[key] for key in sorted(module6_definitions.keys())}"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1d0615cf-1632-43f6-9eee-a6ba13524e58"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n-Constraint Graphs: nodes (variables), edges (constraints)\n\n-Types of CSPs\n- Finite vs Infinite: infinite domains (use implicit constraints: $T_1 + d_1 <= T_2$)\n- Continuous vs Discrete: continuous (e.g.: Hubble Telescope)\n-Constraints: unary (single variable), binary (two variables), global (3+ variables)\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n-Node Consistency\n- Definition: variable domain value satisfy unary constraint\n- Example: SA dislike green, SA has domain ${red, blue}$ (no green)\n\n-Arc Consistency\n- Definition: domain value satisfy varable binary constriants\n- Transformation: any n-ary constraint can be converted into binary constraints\n- Communitavity: X arc-consistent to Y does NOT mean Y arc-consistent to X\n\n-Path Consistency\n- Definition: ${X_i, X_j}$ path-consistent to $X_m$ if for every consistent assignment ${X_i = a, X_j = b}$, exists $X_m$ satisfying ${X_i, X_m}$ & ${X_j, X_m}$\n\n-K-Consistency\n- Definition: for any set of consistent assignment to $k-1$ variables, consitent values can always be assigned to kth variable\n- Solving Strongly-n Consistent: choose consistent value for $X_1$, for $X_2$ (graph is 2-consistent), for $X_3$ (graph is 3-consistent),\n                                for each variable $V_i$ ... search $d$ values in domain: $O(n^2 * d)\n\n-Global Constraints\n- Example: Sudko Alldiff (all row numbers are different)\n- Algorithm: delete variable with singleton domain, delete variable value from remaining variables, repeat as long as singleton variable\n\n-Bounds\n- Bound Propogation: domains represented by upper and lower bounds\n- Bound Consistent: for every $X$ and its upper and lower bound, there exists some $Y$ satisfying constraint between $X$ and $Y$ for every variable $Y$\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n-Space Complexity ($n$ variables and $d$ domain size): $d^n$ number of leaves (commutativty reduces leaves)\n\n-Variable and Value Ordering: which variable assigned next, and in what order?\n- MRV: most-constrained / fail-first variable\n- Degree Heuristic: select variable with largest constraints (to reudce branching factor)\n- Least-Constraing Value\n\n-Iterleaving Search and Inference: what inference performed at each step in search?\n- Forward Checking: whenever $X$ is assigned, establish arc consistency for $X$ and neighbor $Y$ by deleting inconsistent values from $Y$ domain\n- Maintaining Arc Consistency: detect inconsistencies, after assigning value to $X_i$, AC-3 performed with starting queue of arcs ($X_j, X_i$) for unassigned neighbors of $X_i$, more powerful than forward checking since recursively propogate constraints when changes made to domains of variables\n\n-Intelligent Backtracking: can backtrack more than one step?\n- Backtracking: can fail if previous assignment does not resolve constraint problem\n- Backjumping: conflict set supplied by forward checking (at forward checking of $X=x$ and delete value from $Y$, add $X=x$ to $Y$ conflict set)\n- Conflict Directed Backjumping: $conf(X_i) = conf(X_i) \\cup conf(X_j) - {X_i}$\n\n-Constraint Learning: can save and resue partial search results?\n- No-good: create cache or constraint in CSP\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n-Min-Conflicts Heuristics: \"identify value assignment with minimum number of conflicts, change  change value to fit constraints\n\n-Tabu Search: keeping list of recently visited states and forbidding return to them\n\n-Constraint Weighting: concentrate search on important constraints, have all constraints start at one and incremented per violation\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\n-Connected Components ($n$ total variables, $c$ variables / CSP, $d$ domain): $n/c$ subproblems each with $d^c$ work ... $O(d^c nc)$ vs $O(d^n)$\n\n-Tree Problems\n- Algorithm: topologically sort, choose value for parent, choose valid value for child (no need for backtracking)\n- Time Complexity: creating topological sort $O(n)$, domain comparisons $d$ for two variables, total time $O(nd^2)$, linear\n\n-Cutset Conditioning: better memory (linear)\n- Choose subset $S$ of CSP variable such that constraint graph becomes tree after removing $S$\n- For each possible assignment to variables in S: remove domains of remaining variable inconsistent with S assignment, return solution\n- Runtime (cycle cutset size c $c$): $O(d^c * (n-c) * d^2)$... try $d^c$ combination of values for variables in $S$, $n-c$ for each tree, and $d^2$ for each domain\n\n-Tree Decomposition Requirements: better time\n- Every variable in original problem appears in >= 1 node\n- If two variables connected by constraint in original problem, appear in at least one node\n- If variable appears in two nodes, must appear in  every node along path connecting node (variable must have same value in every node)\n- Runtime ( number of tree nodes $n$, size of largest domain $d$): $O(nd^2)$ with Tree-CSP Solver\n- Runtime with minimal tree width: $O(nd^{(w+1)})$\n\n-Value Symmetry\n- Example: WA, NT, SA must be different colors, but 3! assignments of different colors\n- Add symmetry-breaking constraints: NT < SA < WA for alphabet coloring\n \n\n## Module 6 Lecture Notes\n <h3></h3>\n<h3>INTRO TO CSPs</h3>\n-Components of CSP\n\n- Finite Set of Variables: $X_1, X_2, ..., X_n$\n\n- Nonempty domain of possible values for each variable: $D_1, D_2, ..., D_N$ where $D_1 = {v_1, ..., v_k}$\n\n- Finite Set of Constraints: $C_1, C_2, ... C_m$\n\n-CSP Solution: complete and consistent assignment\n\n-CSP Benefits\n- Clean specificiation of problems: no need for specific heuristics\n- CSP know variables violating constraints: can focus search\n- CSP automatically prune branches violating constraint: reduce search space\n\n<h3>CSPs AS SEARCH PROBLEMS</h3>\n-Initial State: empty assignment {}\n\n-Successor Function: assign value to unassigned variable without conflict\n\n-Goal Test: complete assignment\n\n-Path Cost: constant cost for eery step\n\n-Size: $n$ variables (each with domain size $d$), branching factor at level l $(n-l)*d$, total leaves ($n! * d^n$)\n<h3>HEURISTICS TO IMPROVING BACKTRACKING EFFICIENCY</h3>\n-Which variable to assign next?: most contrained variable (variable with least legal values)\n\n-Which variable values to assign?: least constraining values\n\n-How to detect imminent failure?: Forward checking (terminatenate search if unassigned variable has no legal values)\n\n- Can't detect all failures (two adjacent states both left with one and same color)\n\n<h3>ARC CONSISTENCY AND AC3</h3>\n-CSP Solvers: search (assign value to variable) and constrint propogation/inference (eliminate possible values violating local consistency)\n\n-Local Consistency: Node (1/unary), Arc (2/Binary), Path (3+)\n\n-Walts/Mackworth Constraints Propogation Algorithms\n- Assign every node in constraint graph a set of all possible values\n- Repeat until no change in set of values: for each node i ... for each nieghboring node j ... remove any value from i not arc consistent with j\n\n-AC3 Inefficiencies\n- Each Iteration: only need to examine $X_i$ where at least one neighbor lost a value in previous iteration\n- If $X_i$ lose value due to $Y_j$, don't need to check $Y_j$ on next iteration\n- Remove $X_i$ can only make $Y_j$ arc inconsistent with $X_i$, so only check if (j, i) is still arc-consistent\n\n-Time Complexity\n- Number of Arcs: $O(n^2)$, if all nodes connected to ever other nodes\n- Checking Arcs: $O(d^2)$ for d arcs\n- Inserting Arcs into Queue: $O(d)$, each arc inserted $O(d)$ times ($X_i$ has at most $d$ values to delete)\n- Total: $O(n^2 * d^3)$\n \n\n## Module 6 Definitions\n* **Arc consistency** - X -> Y as consistent iff for every x of X, there exists allowed y\n* **Backjumping** - backtracking to most recent assignment in conflict set\n* **Backtracking** - DFS on single-variable assignments\n* **Csp** - Constraint Satisication Problem, state with variable/value and conditions for constraints on variables\n* **Chronological backtracking** - after branch failure, back up to preceding variable of most recent decision point\n* **Conflict-directed backumping** - backtracking to preceding variable AND all subsequent variables causing conflict\n* **Consistent** - solution not breaking the constraints\n* **Constraint learning** - finding min set of variabel from conflict set cauisng issues\n* **Constraint propogation** - reducing legal values of a variable via available constrains\n* **Directional arc consistency** - for every $X_i$ arcconsistent for each $X_j$ for $j>i$\n* **Global constraints** - constraints involving arbitraryn number of variables\n* **Least constraing value** - pick values with least constraints on neighbors\n* **Minimum remaining values** - picks variable most likely to fail\n* **No-good** - variable assignments doomed to fail\n* **Strongly k-consistent** - CSPs consistent from k, k-1, ... 1\n* **Tree width** - minimum width of tree decompositions\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",
        "-Sentence Types: Axioms and Derived Sentences\\n\n",
        "-Agent: TELLS KB its percption, ASK KB what action to perform, TELLS KB which action is chosen and executes action\\n\n",
        "-Approaches: Declarative (TELL sentences until agent operates environment) vs Procedural (encoded desired behaviors)\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "-PEAS\n",
        "- Performance: 1000 for finding gold, -1000 for pit/wumpus, -1 for action taken (encourage shortest path), -10 for using arrow\n",
        "- Environment: 4x4 room grid\n",
        "- Actuators: move forward, turn left, turn right, grab, shoot, climb\n",
        "- Sensors: [Stench, Breeze, Glitter, Bump, Scream]\\n\n",
        "-Environment: deterministic, discrete, static, singleagent, seqquential, partially observable\\n\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "-Syntax: 'x+y=4' as well formed, 'x4y+=' as not\\n\n",
        "-Semantics: 'x+y=4' as true in world where x,y=2 and false in world where x,y=1\\n\n",
        "-Model: 'x+y=4' possible models as different assignments of x and y\\n\n",
        "-Entailemnt: x=0 entails xy=0\\n\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "-Sentences: Atomic Sentences (single propositional symbol) vs Complex Sentences sentence with logical connectives\\n\n",
        "-Connectives (in order): negation, conjunction (and), disjunction (or), implication (premise/antecedent, conclusion/consequence), biconditional (iff)\\n\n",
        "-TT Entails Algorithm: recursive enumeration, sound , complete, exponential to input\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "-Validity and Satisfiability: a|=b B iff (a /\\ not B) is unsatisfiable, a satisfiable iff not a is not valid\\n\n",
        "-Unit Resolution: take two clause and produce new clause containing all literals of two original clauses, except complementary ltierals\\n\n",
        "-Resolution Completeness: proving ground resolution theorem contrapositive ... if RC(S) not empty set, S is satisfiable\\n\n",
        "-Constructing model for S: for i from 1 to k\n",
        "- If clause in RC(S) contains not $P_i$ and all other literals are false for $P_1, ..., P_i-1$, $P_i$ = false\n",
        "- Else: $P_i$ = True\\n\n",
        "-Resolution Model Proof: assuming at some $i$, $P_i$ causes $C$ to be false ... then all other literals in $C$ must be flase by assignments from $P_1, ... P_i-1$\\n\n",
        "-Definite Clause: (not L \\/ not Breeze \\/ B)\n",
        "- Every definite clause can be written as implication with premise (conjunction of positive literals) and conclusion (single positive literal)\n",
        "- Horn clause inference can be done with forward-chaining or backward-chaining\n",
        "- Deciding Horn Clause entailment is linear\\n\n",
        "-Forward Chaining Algorithm (sound and complete): determine if single proposition is entailed by knowledge base of definite clauses\n",
        "- Start: positive literals of knowledge base\n",
        "- If premise of implication are known, add conclusion to facts: if L and Breeze known for (L /\\ Breeze) -> B, add B\n",
        "- Repeat until no q is added or cannot make more inferences\\n\n",
        "-Backward Chaining\n",
        "- Start: q\n",
        "- Find implication in knowledge base whose conclusiosn is q\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "<h3>KNOWLEDGE-BASED AGENTS/LOGIC</h3>\n",
        "-Knowledge Base: false in models contradicting agent knowledge\\n\n",
        "-Representation Language: has syntax to specify well-formed sentences\\n\n",
        "-Logic: defines semantics (meaning) of sentences\\n\n",
        "-Semantics: defines truth with respect to possible worlds\\n\n",
        "-Models: M(a) as set of all models that satisfy sentence a\\n\n",
        "-Entailment: a|=B iff M(a) subset of M(B)\n",
        "<h3>THEOREM PROVING</h3>\n",
        "-Search for a Proof\n",
        "- Initial State: initial knowledge nase (set of statements)\n",
        "- Actions: inference rules applied to all sentences\n",
        "- Result: add statement to bottom half of KB\n",
        "- Goal: state containing sentence we are trying to prove\\n\n",
        "-Monotonicty: soundeness since adding additional information doesn't invalidate previous information\\n\n",
        "-Resolution: yields complete inference algorithm when coupeld with complete search algorithm\\n\n",
        "-Conjunctive Normal Form Steps\n",
        "- Eliminate <-> with (a -> B) /\\ (B -> a)\n",
        "- Eliminate -> with not a \\/ B\n",
        "- Repeatedly move not inwards (double negation, not /\\ - DeMorgan, not \\/ - Demorgan)\n",
        "- Apply distributivity law \\/ over /\\ if possible\\n\n",
        "-Resolution Algorithm: proofby contradition, show KB=a by showing KB /\\ a is unsatisfiable\n",
        "- Convert (KB /\\ not a) to CNF\n",
        "- Apply resolution rule to resulting clauses\n",
        "- Resolve every pair that contains completemtnary literals to produce new clause\n",
        "- If new cluse isn't present, add to set\n",
        "- Continue until: 1) no new classes to add (KB does not entail a), 2) two clause resolve to yield empty clause (KB does not entail a)\\n\n",
        "-Forward Chaining: data driven reasoning, start with known data and add premise as new precept comes in without specific query in mind\\n\n",
        "-Backward Chaining: goal-directed reasoning, start with query and find implication in KB whose conclusion is query\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge-Based Agents\" : \"agents that use reasoning to decide actions\",\n",
        "\"Knowledge Base\": \"set of sentences built from background information and observations\",\n",
        "\"Model\": \"possible worlds; mathematical abstraction with fixed set of truth values (true, false) for each sentence\",\n",
        "\"Entailment\": \"sentence logically follows from another sentence, a|=B iff every model in A is true in B\",\n",
        "\"Axiom\": \"given sentences, not derived from other sentences\",\n",
        "\"Inference\": \"deriving new sentences from existing sentences\",\n",
        "\"Syntax\": \"definition of how sentences are well-formed\",\n",
        "\"Semantics\": \"meaning of sentences\",\n",
        "\"Model Checking\": \"algorithm that list all possible models to check a true in all models KB is true, M(KB) subset of M(a)\",\n",
        "\"Sound/Truth-Preserving\": \"inference algorithm that derives only entailed sentences\",\n",
        "\"Complete\": \"inference algorithm capable of deriving any entailed instances\",\n",
        "\"Logical Equivalence\": \"two statements that are true for same set of models, a = B iff a|=B and B|=a\",\n",
        "\"Monotonicity\": \"if KB|=a then KB /\\ B |=a\",\n",
        "\"Resolution\": \"if l and m are complemtnary literals, they can be eliminated va unit resolution\",\n",
        "\"Theorem Proving\": \"process of applying inference rules to sentenes to construct proof\",\n",
        "\"Validity / Tautologies\": \"sentences valid in all models (P \\/ not P)\",\n",
        "\"Satisfiability\": \"sentences is true by some model\",\n",
        "\"Resolution Closure RC(S)\": \"set of all clauses derivable by applying resolution rule, final product of PL-Resolution\",\n",
        "\"Ground Resolution Theorem\": \"if clauses are unsatisfiable, reoslution closure yieldsempty set\",\n",
        "\"Definite Clause\": \"disjunction clause of literals where exactly one positive\",\n",
        "\"Horn Clause\": \"disjunction clause where at most one is positive\",\n",
        "\"Goal Clause\": \"clause where no positive literals\"\n",
        "\n",
        "}\n",
        "\n",
        "module7_definitions = {key: module7_definitions[key] for key in sorted(module7_definitions.keys())}"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f7625ab5-e73d-4792-97a8-65cff9e5cd65"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n-Sentence Types: Axioms and Derived Sentences\n\n-Agent: TELLS KB its percption, ASK KB what action to perform, TELLS KB which action is chosen and executes action\n\n-Approaches: Declarative (TELL sentences until agent operates environment) vs Procedural (encoded desired behaviors)\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n-PEAS\n- Performance: 1000 for finding gold, -1000 for pit/wumpus, -1 for action taken (encourage shortest path), -10 for using arrow\n- Environment: 4x4 room grid\n- Actuators: move forward, turn left, turn right, grab, shoot, climb\n- Sensors: [Stench, Breeze, Glitter, Bump, Scream]\n\n-Environment: deterministic, discrete, static, singleagent, seqquential, partially observable\n\n\n## AIMA Chapter 7.3 Logic\n\n-Syntax: 'x+y=4' as well formed, 'x4y+=' as not\n\n-Semantics: 'x+y=4' as true in world where x,y=2 and false in world where x,y=1\n\n-Model: 'x+y=4' possible models as different assignments of x and y\n\n-Entailemnt: x=0 entails xy=0\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n-Sentences: Atomic Sentences (single propositional symbol) vs Complex Sentences sentence with logical connectives\n\n-Connectives (in order): negation, conjunction (and), disjunction (or), implication (premise/antecedent, conclusion/consequence), biconditional (iff)\n\n-TT Entails Algorithm: recursive enumeration, sound , complete, exponential to input\n\n## AIMA 7.5 Propositional Theorem Proving\n \n-Validity and Satisfiability: a|=b B iff (a /\\ not B) is unsatisfiable, a satisfiable iff not a is not valid\n\n-Unit Resolution: take two clause and produce new clause containing all literals of two original clauses, except complementary ltierals\n\n-Resolution Completeness: proving ground resolution theorem contrapositive ... if RC(S) not empty set, S is satisfiable\n\n-Constructing model for S: for i from 1 to k\n- If clause in RC(S) contains not $P_i$ and all other literals are false for $P_1, ..., P_i-1$, $P_i$ = false\n- Else: $P_i$ = True\n\n-Resolution Model Proof: assuming at some $i$, $P_i$ causes $C$ to be false ... then all other literals in $C$ must be flase by assignments from $P_1, ... P_i-1$\n\n-Definite Clause: (not L \\/ not Breeze \\/ B)\n- Every definite clause can be written as implication with premise (conjunction of positive literals) and conclusion (single positive literal)\n- Horn clause inference can be done with forward-chaining or backward-chaining\n- Deciding Horn Clause entailment is linear\n\n-Forward Chaining Algorithm (sound and complete): determine if single proposition is entailed by knowledge base of definite clauses\n- Start: positive literals of knowledge base\n- If premise of implication are known, add conclusion to facts: if L and Breeze known for (L /\\ Breeze) -> B, add B\n- Repeat until no q is added or cannot make more inferences\n\n-Backward Chaining\n- Start: q\n- Find implication in knowledge base whose conclusiosn is q\n \n\n## Module 7 Lecture Notes\n\n<h3>KNOWLEDGE-BASED AGENTS/LOGIC</h3>\n-Knowledge Base: false in models contradicting agent knowledge\n\n-Representation Language: has syntax to specify well-formed sentences\n\n-Logic: defines semantics (meaning) of sentences\n\n-Semantics: defines truth with respect to possible worlds\n\n-Models: M(a) as set of all models that satisfy sentence a\n\n-Entailment: a|=B iff M(a) subset of M(B)\n<h3>THEOREM PROVING</h3>\n-Search for a Proof\n- Initial State: initial knowledge nase (set of statements)\n- Actions: inference rules applied to all sentences\n- Result: add statement to bottom half of KB\n- Goal: state containing sentence we are trying to prove\n\n-Monotonicty: soundeness since adding additional information doesn't invalidate previous information\n\n-Resolution: yields complete inference algorithm when coupeld with complete search algorithm\n\n-Conjunctive Normal Form Steps\n- Eliminate <-> with (a -> B) /\\ (B -> a)\n- Eliminate -> with not a \\/ B\n- Repeatedly move not inwards (double negation, not /\\ - DeMorgan, not \\/ - Demorgan)\n- Apply distributivity law \\/ over /\\ if possible\n\n-Resolution Algorithm: proofby contradition, show KB=a by showing KB /\\ a is unsatisfiable\n- Convert (KB /\\ not a) to CNF\n- Apply resolution rule to resulting clauses\n- Resolve every pair that contains completemtnary literals to produce new clause\n- If new cluse isn't present, add to set\n- Continue until: 1) no new classes to add (KB does not entail a), 2) two clause resolve to yield empty clause (KB does not entail a)\n\n-Forward Chaining: data driven reasoning, start with known data and add premise as new precept comes in without specific query in mind\n\n-Backward Chaining: goal-directed reasoning, start with query and find implication in KB whose conclusion is query\n \n\n## Module 7 Definitions\n* **Axiom** - given sentences, not derived from other sentences\n* **Complete** - inference algorithm capable of deriving any entailed instances\n* **Definite clause** - disjunction clause of literals where exactly one positive\n* **Entailment** - sentence logically follows from another sentence, a|=B iff every model in A is true in B\n* **Goal clause** - clause where no positive literals\n* **Ground resolution theorem** - if clauses are unsatisfiable, reoslution closure yieldsempty set\n* **Horn clause** - disjunction clause where at most one is positive\n* **Inference** - deriving new sentences from existing sentences\n* **Knowledge base** - set of sentences built from background information and observations\n* **Knowledge-based agents** - agents that use reasoning to decide actions\n* **Logical equivalence** - two statements that are true for same set of models, a = B iff a|=B and B|=a\n* **Model** - possible worlds; mathematical abstraction with fixed set of truth values (true, false) for each sentence\n* **Model checking** - algorithm that list all possible models to check a true in all models KB is true, M(KB) subset of M(a)\n* **Monotonicity** - if KB|=a then KB /\\ B |=a\n* **Resolution** - if l and m are complemtnary literals, they can be eliminated va unit resolution\n* **Resolution closure rc(s)** - set of all clauses derivable by applying resolution rule, final product of PL-Resolution\n* **Satisfiability** - sentences is true by some model\n* **Semantics** - meaning of sentences\n* **Sound/truth-preserving** - inference algorithm that derives only entailed sentences\n* **Syntax** - definition of how sentences are well-formed\n* **Theorem proving** - process of applying inference rules to sentenes to construct proof\n* **Validity / tautologies** - sentences valid in all models (P \\/ not P)\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": "155e8b25-95fc-484b-aea7-805f24f10473"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n-Capabilities needed: \n- Turing Test (natural language processing, knowledge representation, automated reasoning, ML)\n- Total Turing Test (computer vision, robotics)\n\n-Ways to learn about human thought: introspection (own thought), psychological experiment (person in action), brain imaging (brain in action)\n\n-Value Alignment: chess (machine with win objective: sabotage players, bribe referee), car (multiple objective: safety vs speed)\n \n\n## AIMA Chapter 27.1 The Limits of AI\n\n-Arguments from Disability: machine can never do \"X\" (kind, enjoy strawberry, fall in love, use words properly)\n\n-Godel's Incompleteness Theorem: construct sentence G(F) where\n- G(F) is sentence of F ... but unable to be proved within F\n- if F consistent then G(F) is true\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n-Chinese Room: human given Chinese instruction, transcribe instructions, output intelligent Chinese response, but no thinking is involved\n\n\n\n## AIMA 2.1 Agents and Environments\n\n-Environment: can be anything; in practice: universe part where states matter and are affected/percieved by agent/agent actions\n\n-Action: choice dependant on built-in knowledge and percept sequence (only up to date)\n\n-Agent: Function (mathematical description, take entire percept history) vs Program (concrete implementation, take only current precept)\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n-Rationality Factors\n\n- Performance Measure / Criterion of Success\n- Agent's prior knowledge of environment\n- Action agent can perform\n- Agent's percept sequence to date\n\n-Omniscience: not required (since rationality only dependant on percept sequence to date)\n\n-Autonomy: required (must be able to improve knowledge; i.e.: wasp/catepillar example), but can be developed (not needed from start)\n\n \n\n## AIMA 2.3 The Nature of Environments\n\n-Most Difficult: partially observable, multiagent, nondeterministic, dynamic, continuous, unknown (e.g.: driving in new country)\n\n-Fully Observable vs Partially Observable\n- Fully Observable: advantage (agent no need to maintain internal state of world)\n- Partially Observable: cause (noise, inaccurate sensor, missing data)\n- Unobservable: cause (no sensor)\n\n-Single Agent vs Multiagent\n- Multiagent: competitive (chess) vs cooperative (taxi)\n\n-Deterministic vs Non-Deterministic\n- Stochastic: quantitative probability (e.g.: 25% of rain)\n- Non-Deterministic: non-quantitative chance (e.g.: may rain)\n\n-Episodic vs Sequential\n- Episodic: agent percieve/perform single action, each episode independent of previous episodes (e.g.: assembly line defective parts spotting)\n- Sequential: cons (need to think ahead)\n\n-Static vs Dynamic\n- Dynamic: taxi\n- Semidynamic: chess with clock\n- Static: crossword puzzle\n\n-Discrete vs Continuous: for state of environment, time handling, percepts & actions\n- Discrete: chess (finite number of states)\n- Continuous: taxi (continuous actions, speed)\n\n-Known vs Unkown: for state of knowledge of environment (NOT environment)\n- Known + Partially Observable: solitaire (know rules, don't know card)\n- Unknown + Fully Observable: video game (know screen, don't know what buttons do)\n\n\n## AIMA 2.4 The Structure of Agents\n\n-Simple Reflex Agent\n- Workings: select based on current precept while ignoring precept history\n- Characteristic: only works if fully observable, often infinite loop if partially observable\n\n-Model-Based Reflex Agent\n- Workings: select while keeping internal state (may reflect unobservable world parts)\n- Requirements for updating internal state information: transition model & sensor model\n- Transition Model: how does world change over time? (e.g.: if steering wheel is clockwise, car turns clockwise)\n- Sensor Model: how is state of world reflected in agent's percept? (e.g.: if camera is wet, image is partially observable)\n\n-Goal-Based Agent\n- Insufficiencies: only knowing state (e.g.: at road junction ... turn left, right, or straight?)\n- Workings: keep track of goal information (desirable outcomes)\n- Characteristics: future-facing, less efficient but more flexibile\n\n-Utility-Based Agent\n- Insufficiencies: knowing goal (e.g.: many routes, which is quickest/fastest?)\n- Workings: use utility function (internal performance measure) to find best method to reach goal\n- Characteristics: conflicting goals (specify appropriate tradeoffs), several goals (weigh likelihood to importance)\n\n-Learning Agent: 4 components, bring component to closer agreement with performance\n- Learning Element: makes improvements\n- Performance Element: select external action\n- Critic: gives feedback on performance based on fixed standard\n- Problem Generator: suggest action for new/informative experience\n\n-Expressiveness: more expressive = more concise & more complex reasoning\n- Atomic Represntation: world is indivisible, state has no internal structure\n- Factored Representation: state has attribute values\n- Structured Representation: state has objects with attributes and relationships\n\n-Mappings\n- Localist Representation: 1-1 mapping between concept & memory location\n- Distributed Representation: representation spread over memory location, memory location may be in multiple concepts\n\n## Module 1 Lecture Notes\n\n<h3>ARTIFICIAL INTELLIGENCE IN PHILOSOPHY</h3>\n-Rene Descartes (Dualism): tests via language, automatons can never properly use language\n\n-Alan Turing (Imitation Game): machine can pass as human in conversation\n\n-John Searle (Chinese Room): strong AI (actual thinking, has cognitive ability/conscious thinking) vs weak AI (simulating thinking, no real understanding)\n\n-Daniel Dennett (Brain in a Vat): brain removed from body and placed in vat\n<h3>RATIONAL AGENTS</h3>\n-Agent Function ($f:P->a$): maping of sequence of percept (p) to action (a)\n\n-Agent Examples: human (sensors: eyes, acutators: hands, legs), robots (sensors: camera, actuator: motors)\n\n<h3>RATIONAL BEHAVIOR</h3>\n-Performance Measure design: better to base on agent achievements than agent procedure\n\n-Omniscience: omniscience does not equal guarenteed success, agents need not be omniscience\n<h3>TASK ENVIRONMENTS</h3>\n-Task Environment Components: P (performance measure), E (Environment), A (Actuator), S (Sensor)\n\n-PEAS Example (Taxi): P (safe, fast, profit), E (road, pedestrian), A (brake, steering), S (camera, GPS)\n\n-Agent Goal: 1) construct agent function to maximize performance measure, 2) design agent program to implement on architecture\n\n-Environment: hardest (continuous, partially observable, stochastic, multiagent) vs easiest (static, fully observable, deterministic, discrete)\n\n-Agent Types: reflex agent (select action based on current percept) vs problem solving agent (plan ahead, consider sequence of actions)\n\n\n## Module 1 Definitions\n* **Agent** - anything that use sensor to percieve environment and act on it through actuators, agent = architecure + program\n* **Agent function** - map of percept sequence to action\n* **Agent program** - program that runs physical architecture to produce agent function (i.e.: table)\n* **Autonomy** - capability to learn/compensate for/correct on prior knowledge information (partial/incorrect)\n* **Biological naturalism** - mental states (high-level) derived from neuron physical process (low-level)\n* **Condition-action rules** - if-else statements\n* **Consciousness/qualia** - capability to expereince living and be aware of environment/outside world\n* **Consequentialism** - agent action judged by consequences, not actions\n* **Deterministic** - environment in which next environment state completely determined by current state/action\n* **Dualism** - mind exists separately from body\n* **Dynamic** - environment in which environments can change while agent thinks\n* **Embodied cognition** - cannot seperate brian function from environment, since brain is in body and body in environment\n* **Episodic** - environment in which agent experience can be divided\n* **Fully observable** - environment in which agent's sensor has access to all state at all time\n* **Good old-fashioned ai** - simple logical agents\n* **Known** - environment in which all outcome/outcome probability are given\n* **Multiagent** - environment in which B exhibits behaviors that maximize a performance measure affected by agent A's action\n* **Omniscience** - capability to know outcome of actions and act accordingly\n* **Percept** - agent's perceptual inputs\n* **Percept sequence** - historical log of everything agent percieved\n* **Performance measure** - criterion for deciding success of agent behavior via evaluation on sequence of environment states\n* **Rational agent** - rationally-behaving (maximize expected performance measure) agents based on percept sequence so far\n* **Semi-dynamic** - environment in which environment does not change but agent or performance does\n* **Sensor model** - model for describing how world state is seen/refelected by agent precepts\n* **Sequential** - environment in which current decision affects all future decisions\n* **Transition model** - model for describing how next state is dependant on current state/action\n* **Value alignment problem** - machine value/objective aligned with humans (chess/car example)\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \n<h3>INTRO TO PYTHON</h3>\n-References: == (checks if variable point to object of same value), is (check if variables point to same object) \n\n-Mutability: strings (immutable), lists (mutable), [:] creates shallow copy of new object\n<h3>SEQUENCE TYPES</h3>\n-Sequence Types: tuple (immutable, mixed types), strings (immutable), list (mutable, mixed types)\n\n-Slicing: returns copy, [i:j] (i...j-1), [i:-j] (i...n-j), [::k] (every k)\n\n-List Operations: append, insert, index (index of first occurence), count (number of occurence), remove (remove first occurence)\n\n<h3>FOR LOOPS</h3>\n-Filtered List Comprehension: [elem for elem in li if elem > 4]\n<h3>ITERATORS</h3>\n-Advantages: efficient memory usage\n<h3>GENERATORS</h3>\n-yield: generator method runs until encountering yield statement, then stops and returns yielded value \n\n-xrange vs range: xrange (generator), range (keeps n values in memory before starting loop) \n\n-Generator Pro: maintain local state, values computed as needed, no storing entire sequence in memory, one pass aggregation, infinite sequences \n\n-Generator Con: inspect individual elements\n\n\n## Module 2 Definitions\n* **Dynamic typing** - variables can be any type, only come into existance at assginment\n* **Iterable** - has *iter* method to return iterator object\n* **Iterators** - objects with *next* method (Python does not have *hasnext*)\n* **Strong typing** - fixed type object, only compatible type operations allowed by interpreter\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n-Steps to Problem Solving: goal formulating, problem formulating, search, execution\n\n-Looping: Open Loop (fully observable, deterministic, known, agent ignores precepts) vs Closed Loop\n\n-Abstractions\n\n- Valid: abstraction able to elaborate any solution into more detailed world\n- Useful: abstraction able to carry out action in easier manner than original problem \n\n## AIMA Chapter 3.2 Example Problems\n\n-Standardized Problems: grid world, sliding-tile puzzle, sokoban puzzle\n\n-Real-World Problems: route-finding, touring, VLSI layout, robot navigation, assembly sequencing,  \n\n## AIMA Chapter 3.3 Search Algorithms\n\n-Best-First Search Algorithm: iterate and perform the following\n- Choose frontier node with minimum ```f(n): if goal, return; else, expand```\n- For each child node: ```if not reached, add to frontier; else, re-add if lower path```\n\n-Search Algorithm Node Components: node state, node parent, node action, node path cost\n\n-Algorithm Evaluation: completeness, cost optimality, time complexity, space complexity\n\n-State Space Components:\n- Depth ($d$): number of action in optimal solution\n- Max depth ($m$): max depth of action in any path\n- Branching Factor ($b$): number of successor / node\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n-Breadth-First Search\n- Number of Nodes (expansions): $d=0 (b), d=1 (b^2), ... , d=d (b^d)$; total = $O(b^d)$\n\n-Uniform-Cost Search / Dijkstra’s Algorithm\n- Checking: checks for goal at expansion (pop off queue), not at generation (add to queue)\n- High Complexity: can explore large trees of low cost before useful, high-cost paths\n- Equal Cost Complexity: simplifies to $b^{(d+1)}$, same as BFS\n\n-Depth-First Search\n- State Spaces: finite (efficient/complete), acyclic (many paths to same state, complete), cyclic (infinite loop), infinite (infinite path)\n- Backtracking: only considering one successor at a time, memory reduced to $m$ (only one path)\n\n-Iterative Deepening Search\n- Idea: regenerate nodes at each level (sacrifice time for space)\n- Time Complexiy: solution exists ($b^d$), solution does not exist ($b^m$)\n- Number of Nodes: $(d)(b^1) + (d-1)(b^2) + ... (1)(b^d)$ (nodes at bottom only generated once, at top generated $d$ times)\n\n-Bidirectional Search\n- Idea: simultaneously search forward from initial and backward from goal with two frontier/reach states\n\n## Module 3 Lecture Notes\n\n<h3>SEARCH PROBLEMS</h3>\n-Solution as fixed sequence: fully observable, deterministic, known\n\n-Solution as future actions: branching strategy, partially observable, nondeterministic\n\n<h3>SEARCH PROBLEM FORMULATIONS</h3>\n-Problem Definition: State (set $S$), Initial state ($s \\exists S$), Actions ($A$), Transition Model ($(s, a) -> s_r$), Goal State ($Goal(s)$),\n\nPath Cost /Action Cost Function (Performance Measure): additive, $c(x,a,y)$ for action $a$ and states $x, y$\n\n<h3>BASIC SEARCH ALGORITHMS</h3>\n-Search Types\n\n- Tree Search: treats different paths to same node as distinct\n- Graph Search: tree search while checking if node has been visited before adding into queue\n\n<h3>BFS & DFS</h3>\n-BFS: FIFO\n\n- Usage: possible infinite paths, some solutions have short paths, can quickly discard unlikely path\n\n-DFS: LIFO\n- Characteristics: incomplete (fail in infinite-depth/loops), not optimal (return first found solution, even if not cheapest)\n- Usage: restricted space, multiple solutions with long paths/wrong paths (quick termination), can quickly fine-tune paths\n\n<h3>DEPTH LIMITED SEARCH & ITERATIVE DEEPENING SEARCH</h3>\n-Depth Limited Search\n\n- Characteristics: $l=d$ (solution found), $l < d$ (incomplete), $l > d$ (not optimal)\n\n-Iterative Deepening Search\n- Algorithm: for $l = 0 ->$ infinity, perform depth limited search to $l$\n- Space Complexity: at $d=0$ (0 node), $d=1$ ($b^1$ node), $d=2$ ($b + b^2$ node), $d=3$ ($b + b^2 + b^3$) node\n \n\n## Module 3 Definitions\n* **Completeness** - if solution, algorithm can find it; else: algorithm detect failure\n* **Cost optimality** - algorithm returns lowest path cost solution\n* **Optimal solution** - solution that has lowest path cost\n* **Problem-solving agent** - an agent that can formulate a plan via search; use atomic representations\n* **Real-world problems** - problems for actual usage, with idiosyncacies\n* **Search** - process that problem-solving agent undertake to find solution\n* **Solution** - sequence of actions that form a path from initial state to goal state\n* **Standardized problems** - problems for exhibiting problem solving methods\n* **State space** - set of all states reachable from intial state by any sequence of actions\n* **Uninformed search** - search problems with only access to problem definition\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n-Greedy Best-First Search\n- Characteristics: complete (only in finite state space), space and time complexity $O(V)$\n\n-Inadmissible Heuristics\n- Case 1: optimal path found; if for $C^*$ (optimal) and $C$ (second-best), $h(n)$ overestimates less than $C2-C^*$\n- Case 2: path found, for any path in which $h(n)$ is admissible for all nodes $n$ on path\n\n-A* Search\n- Consistency vs Admissibility: consistency stronger than admissibility; all consistent are admissible ... not vice versa\n- Consistency Feature: first reaching will be shortest path, don't need to wait for expansion\n\n-Search Contours\n- Uniform Cost-Search: basis ($g(n)$), shape (circular), monotonic (always)\n- A* Search: basis ($g(n)+h(n)$), shape (narrow around optimal path), monotonic (consistent, $h(n) = c(n, a, n') + h(n')$)\n- Nodes: $f(n) < C^*$ (surely expanded, always reached), $f(n)=C^*$ (may reached before selecting goal), $f(n)>C*$ (never reached)\n\n-Weighted A Search:\n- Evaluation Function: $f(n) = g(n) + w * n$ where $w > 1$\n- Purpose: trades correctness (not optimal, solution between $C^*$ and $W * C^*$) for efficiency (less node explored)\n- Types: Bounded Suboptimal Search (solution within $W$ factor of $C^*$), Bounded-Cost Search (solution $<= C$), Unbounded-Cost Search (any fast solution)\n\n-Memory-Bounded Search\n- Beam Search: algorithm (limit frontier size to: best $k$, within $f-score$, $delta - f-score$), characteristic (incomplete and suboptimal)\n- Iterative Deepening Search: algorithm (cutoff set at smallest f-score of node exceeding previous iteration), characteristic (works well for steps, poorly if every node with different f-score)\n- Recursive Best First Search: algorithm (recursive DFS, use $f_limit$ to track $f_value$ of best alternative path, if current node > limit ... unwind),\n  characteristic (optimal if $h(n)$ is admissible), space complexity ($O(d)$), time complexity (dependant on heuristic accuracy & frequency of path changes)\n- Simplifed Memory Bounded A* Search: algorithm (expand best leaf until memory is full, regenerates subtree only if all desendants are forgotten), characteirstic (complete, optimal)\n\n-Bidirectional Heuristic Search\n- Consideration: analyze pair of verticies for expansion, rather than single node\n- Evaluation: $max(2 * g(n), g(n) + h(n))$, can come from either frontiers \n\n## AIMA Chapter 3.6 Heuristic Functions\n\n-Pattern Database\n- Purpose: store solution cost for every subproblem instance\n- Example: for 8-tile problem, take 1-4 patterns\n- Multiple Databases: diminishing returns, each database with own admissible heuristic (take max value of heuristics)\n- Disjoint Databases: combine multiple pattern database, need to ensure databases are disjoint (1234: cost of moving 1,2,3,4 ... not all)\n\n-Precomputation\n- Purpose: conduct expensive operations that are amortized over multiple searches\n- Landmark: for each vertex $v$ and landmark $l \\exists L$, compute $C^*(v, L)$\n- Inadmissible: $h(n) = min(C^*(n, L) + C^*(L, goal)))$ for all landmarks $l$; optimal if pass through landmark, overestimates if not\n- Admissible: $h(n) = max(|C^*(n, L) - C^*(goal, L)|)$ for all landmarks $l$; find goal distance if in configuration: n->goal->landmark\n \n\n## Module 4 Lecture Notes\n <h3></h3>\n<h3>GREEDY BEST-FIRST SEARCH</h3>\n-Evaluation Function: $f(n) = h(n)$\n\n-Characteristics: not optimal, not complete (can be stuck in loop)\n<h3>A* SEARCH</h3>\n-Evaluation Function: $f(n) = g(n) + h(n)$; $g(n)$: actual cost to reach node, $h(n)$: estimated cost to node\n\n-Admissible Heuristics\n- Admissibility: inadmissible (break optimality, pushes good options down in PQ), admissible (slows down but never outweighs true cost)\n- Defining Heuristics: cost of exact solution to relaxed problem\n- Worst: $h(n) = 0$; dominated by all heuristics\n- Best: $h^*(n)$ ... underestimates, but get as close/accurate to goal as possible; dominates all heuristics\n\n-Optimality Proof: for any nodes A (optimal), n (ancestor of A or A), B (subptimal), $f(n) <= f(A) < f(B)$ so n expands before B\n \n\n## Module 4 Definitions\n* **Admissible heuristics** - never overestimates,  for all node $n$, $h(n) <= h*(n)$ (true cost) and $h(n) >= 0$\n* **Consistent heuristics** - for node $n$ and successor $n'$, $h(n) <= c(n, a, n') + h(n')$\n* **Dominance** - h2 dominates if $h_2(n) >= h_1(n)$ for all n and both are admissible\n* **Effective branching factor** - $N/D$\n* **Heuristic function** - return estimate of distance from node n to goal\n* **Heuristic knowledge** - useful knoweldge, but not necesarily correct\n* **Informed search** - search strategies capable of using domain-specific hints to find solution\n* **Optimistic heuristics** - admissible heuristics\n* **Optimistically efficient** - search strategy for any algorithm of same intial state and heuristic, expand all surely expanded nodes\n* **Relaxed problem** - problem with less action restrictions; state-space is supergraph (more edges)\n* **Satisficing search** - search strategy for finding solutions that are suboptimal, but 'good enough'\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n-Game Definition: initial state (board set-up), to-move (player performing move), actions (legal moves in state $s$), result (transition model of state resulting from action a in state s),\nis-terminal (terminl test for if game is over), utility (final numeric value when game ends in terminal state)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n-MinMax Algorithm: DFS, time ($O(b^m)$), space ($O(bm)$ of all action at once; $O(m)$ if one action at a time)\n\n-Multiplayer Games: replace single node values witha vector values\n- Terminal State: vectors as utility state of each player\n- Non-Terminal State: vectors as utility vector of successor state with highest value for player at node\n\n-Move Ordering\n- Perfect Ordering: reduce nodes examined to ($O(b^{(m/2))}$), branching factor ($b^{(1/2)}$)\n- Transpositions Table: cached for easy lookup\n- Strategy Types: Type A (wide and shallow, small branching factors) vs Type B (deep and narrow, large branching factors)\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n-$Eval(s, p)$: returns estimate of expected utility to reduce computation time\n\n-Terminal State: Eval = Utility vs Non-Terminal State: utility(loss, p) <= Eval(s, p) <= Utility(win, p)\n\n-Cutting off Search: reduce search space\n- Method 1: limit depth\n- Method 2: set time limit, at time limit, return deepest completed search\n- Method 3: Quiscient Search: return false non-quiscient results\n- Method 4: Singular Extensions to mitigate horizon focus\n\n-Forward Pruning\n- Purpose: tradeoff computation time for error risk\n- Beam Search: at each ply, consider only $n$ best moves,\n- ProbCut: calculate probability with shallow pruning & expereince to prune nodes probably outisde (alpha, beta) window\n- Lat Move reduction: if assuming move ordering in order, only re-run full-depth search if returned value greater than alpha\n \n\n## AIMA Chapter 5.5 Stochastic Games\n\n-ExpectiMax Runtime: $O(b^m n^m)$\n\n-Effects of Probabilities: blows up the consideration space \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n-Formulas\n- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n- $P(RESULT(a)=s') = Sum of (P(s) * P(s'|s, a))$ for all states (s): probability that $s$ reaches $s'$ after taking $a$\n- $EU(a) = Sum of P(RESULT(a)=s') * U(s')$ for all states (s')\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n-Utility Theory\n- Orderability: agent cannot avoide deciding preference, must either prefer one or rate as equal\n- Transitivity: if agent prefers A > B and B > C, agent prefers A > C\n- Continuity: if agent prefers A > B > C, there exist some probability p where agent indifferent towards B (for sure) and A ($p$) or C ($1-p$)\n- Substitutability: if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\n- Monotonicity: if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\n- Decomposability: compounded lotteries can be reduced to simpler ones with probability laws\n\n-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\n \n-Expected Utility of Lottery: $U(L) = \\sum_{i}p_i * U(S_i)$\n\n-Utility Function: exists for all rational agent, not necessarily unique\n\n## AIMA Chapter 16.3 Utility Functions\n\n-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\n\n-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\n\n-Bias: selecting action with highest utility, estimates are overly optimistic\n\n-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\n\n\n\n## Module 5 Lecture Notes\n \n<h3>GAME FORMULATION</h3>\n-Key Game Properties: two players, zero-sum, clear set of legal moves, well-defined outcomes\n\n-Game Search Steps: consider all legal successors to current state, evaluate successor board position, pick move with best board state, repeat\n\n-Game Trees: nodes (board positions), edges (legal moves)\n\n-Evaluation Functions: $f(n) > 0$ (max is winning),  $f(n) = 0$ (draw), $f(n) < 0$ (min is winning)\n<h3>MINMAX RULES</h3>\n-MinMax Procedures\n\n- Expand game tree a fix number of $ply$\n- Apply evaluation function to leaf positions\n- Calculate back-up values bottom-up\n- Pick move assigned to MAX at root\n- Wait for MIN to respond\n\n-Pruning\n\n- alpha (-inf): MAX's current lower bound, never allow worse score than alpha, don't evaluate branch if v >= B (MIN never select this MAX node)\n- beta (+inf): MIN's current upper bound, never allow better score than Beta, don't evaluate branch if v <= A (MAX never select this MIN node)\n\n<h3>EXPECTMAX</h3>\n-Causes for Unpredictability: explicit randomness (dice), suboptimal opponent, failed actions\n\n-ExpectiMax\n- Algorithm: computes average score under optimal play\n- Nodes: max (same), min (chance nodes with uncertain outcomes, take weighted average)\n- Space: greatly increases (have to simulate more states and opponent simulating)\n \n\n## Module 5 Definitions\n* **Anchoring effect** - people prefer relative utility judgements to absolute judgement\n* **Certainity effect** - people are likely to prefer certain outcomes\n* **Certainty equivalent** - value agent accepts for sure instead of lottery chance\n* **Evaluation functions** - functio that determines quality of board position based on static features\n* **Forward pruning** - pruning of moves that seem bad (may actually be good)\n* **Horizon effect** - impeding opponent move will cause serious damage, but is temporarily delayable (e.g.: bishop capture)\n* **Insurance premium** - Lottery EMV - certainty equivalent\n* **Lottery** - set out action outcomes, denoted by $L=[p_1, S_1; p_2, S_2; ... p_n, S_n]$\n* **Maximum expected utility** - principle in which rational agent chooses action that maximize agent EU\n* **Micromort** - one in a million chance of death\n* **Normalized utility** - utility with scale between 0 (worst) and 1 (best)\n* **Perfect information / zero-sum games** - games in which one player's loss is another player's gain\n* **Policy** - maping of possible state to best move for given state\n* **Prefernce elicitation** - the process of finding human utility function by presenting choice and using observed preferences\n* **Quiescent** - board positions with successor states not swinging evaluations (e.g.: queen capture)\n* **Singular extension** - set of moves clearly the best for a given board position\n* **Stochastic games** - games with random elements and probability\n* **Transpositions** - different permutations of move sequences may lead to same board positions\n* **Type a strategy** - strategy in which all moves at given depth considered and estimated with heuristics\n* **Type b strategy** - strategy in which only promising strategies explored deeply\n* **Value function / ordinal utility function** - ranking of preferences of states\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n-Constraint Graphs: nodes (variables), edges (constraints)\n\n-Types of CSPs\n- Finite vs Infinite: infinite domains (use implicit constraints: $T_1 + d_1 <= T_2$)\n- Continuous vs Discrete: continuous (e.g.: Hubble Telescope)\n-Constraints: unary (single variable), binary (two variables), global (3+ variables)\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n-Node Consistency\n- Definition: variable domain value satisfy unary constraint\n- Example: SA dislike green, SA has domain ${red, blue}$ (no green)\n\n-Arc Consistency\n- Definition: domain value satisfy varable binary constriants\n- Transformation: any n-ary constraint can be converted into binary constraints\n- Communitavity: X arc-consistent to Y does NOT mean Y arc-consistent to X\n\n-Path Consistency\n- Definition: ${X_i, X_j}$ path-consistent to $X_m$ if for every consistent assignment ${X_i = a, X_j = b}$, exists $X_m$ satisfying ${X_i, X_m}$ & ${X_j, X_m}$\n\n-K-Consistency\n- Definition: for any set of consistent assignment to $k-1$ variables, consitent values can always be assigned to kth variable\n- Solving Strongly-n Consistent: choose consistent value for $X_1$, for $X_2$ (graph is 2-consistent), for $X_3$ (graph is 3-consistent),\n                                for each variable $V_i$ ... search $d$ values in domain: $O(n^2 * d)\n\n-Global Constraints\n- Example: Sudko Alldiff (all row numbers are different)\n- Algorithm: delete variable with singleton domain, delete variable value from remaining variables, repeat as long as singleton variable\n\n-Bounds\n- Bound Propogation: domains represented by upper and lower bounds\n- Bound Consistent: for every $X$ and its upper and lower bound, there exists some $Y$ satisfying constraint between $X$ and $Y$ for every variable $Y$\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n-Space Complexity ($n$ variables and $d$ domain size): $d^n$ number of leaves (commutativty reduces leaves)\n\n-Variable and Value Ordering: which variable assigned next, and in what order?\n- MRV: most-constrained / fail-first variable\n- Degree Heuristic: select variable with largest constraints (to reudce branching factor)\n- Least-Constraing Value\n\n-Iterleaving Search and Inference: what inference performed at each step in search?\n- Forward Checking: whenever $X$ is assigned, establish arc consistency for $X$ and neighbor $Y$ by deleting inconsistent values from $Y$ domain\n- Maintaining Arc Consistency: detect inconsistencies, after assigning value to $X_i$, AC-3 performed with starting queue of arcs ($X_j, X_i$) for unassigned neighbors of $X_i$, more powerful than forward checking since recursively propogate constraints when changes made to domains of variables\n\n-Intelligent Backtracking: can backtrack more than one step?\n- Backtracking: can fail if previous assignment does not resolve constraint problem\n- Backjumping: conflict set supplied by forward checking (at forward checking of $X=x$ and delete value from $Y$, add $X=x$ to $Y$ conflict set)\n- Conflict Directed Backjumping: $conf(X_i) = conf(X_i) \\cup conf(X_j) - {X_i}$\n\n-Constraint Learning: can save and resue partial search results?\n- No-good: create cache or constraint in CSP\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n-Min-Conflicts Heuristics: \"identify value assignment with minimum number of conflicts, change  change value to fit constraints\n\n-Tabu Search: keeping list of recently visited states and forbidding return to them\n\n-Constraint Weighting: concentrate search on important constraints, have all constraints start at one and incremented per violation\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\n-Connected Components ($n$ total variables, $c$ variables / CSP, $d$ domain): $n/c$ subproblems each with $d^c$ work ... $O(d^c nc)$ vs $O(d^n)$\n\n-Tree Problems\n- Algorithm: topologically sort, choose value for parent, choose valid value for child (no need for backtracking)\n- Time Complexity: creating topological sort $O(n)$, domain comparisons $d$ for two variables, total time $O(nd^2)$, linear\n\n-Cutset Conditioning: better memory (linear)\n- Choose subset $S$ of CSP variable such that constraint graph becomes tree after removing $S$\n- For each possible assignment to variables in S: remove domains of remaining variable inconsistent with S assignment, return solution\n- Runtime (cycle cutset size c $c$): $O(d^c * (n-c) * d^2)$... try $d^c$ combination of values for variables in $S$, $n-c$ for each tree, and $d^2$ for each domain\n\n-Tree Decomposition Requirements: better time\n- Every variable in original problem appears in >= 1 node\n- If two variables connected by constraint in original problem, appear in at least one node\n- If variable appears in two nodes, must appear in  every node along path connecting node (variable must have same value in every node)\n- Runtime ( number of tree nodes $n$, size of largest domain $d$): $O(nd^2)$ with Tree-CSP Solver\n- Runtime with minimal tree width: $O(nd^{(w+1)})$\n\n-Value Symmetry\n- Example: WA, NT, SA must be different colors, but 3! assignments of different colors\n- Add symmetry-breaking constraints: NT < SA < WA for alphabet coloring\n \n\n## Module 6 Lecture Notes\n <h3></h3>\n<h3>INTRO TO CSPs</h3>\n-Components of CSP\n\n- Finite Set of Variables: $X_1, X_2, ..., X_n$\n\n- Nonempty domain of possible values for each variable: $D_1, D_2, ..., D_N$ where $D_1 = {v_1, ..., v_k}$\n\n- Finite Set of Constraints: $C_1, C_2, ... C_m$\n\n-CSP Solution: complete and consistent assignment\n\n-CSP Benefits\n- Clean specificiation of problems: no need for specific heuristics\n- CSP know variables violating constraints: can focus search\n- CSP automatically prune branches violating constraint: reduce search space\n\n<h3>CSPs AS SEARCH PROBLEMS</h3>\n-Initial State: empty assignment {}\n\n-Successor Function: assign value to unassigned variable without conflict\n\n-Goal Test: complete assignment\n\n-Path Cost: constant cost for eery step\n\n-Size: $n$ variables (each with domain size $d$), branching factor at level l $(n-l)*d$, total leaves ($n! * d^n$)\n<h3>HEURISTICS TO IMPROVING BACKTRACKING EFFICIENCY</h3>\n-Which variable to assign next?: most contrained variable (variable with least legal values)\n\n-Which variable values to assign?: least constraining values\n\n-How to detect imminent failure?: Forward checking (terminatenate search if unassigned variable has no legal values)\n\n- Can't detect all failures (two adjacent states both left with one and same color)\n\n<h3>ARC CONSISTENCY AND AC3</h3>\n-CSP Solvers: search (assign value to variable) and constrint propogation/inference (eliminate possible values violating local consistency)\n\n-Local Consistency: Node (1/unary), Arc (2/Binary), Path (3+)\n\n-Walts/Mackworth Constraints Propogation Algorithms\n- Assign every node in constraint graph a set of all possible values\n- Repeat until no change in set of values: for each node i ... for each nieghboring node j ... remove any value from i not arc consistent with j\n\n-AC3 Inefficiencies\n- Each Iteration: only need to examine $X_i$ where at least one neighbor lost a value in previous iteration\n- If $X_i$ lose value due to $Y_j$, don't need to check $Y_j$ on next iteration\n- Remove $X_i$ can only make $Y_j$ arc inconsistent with $X_i$, so only check if (j, i) is still arc-consistent\n\n-Time Complexity\n- Number of Arcs: $O(n^2)$, if all nodes connected to ever other nodes\n- Checking Arcs: $O(d^2)$ for d arcs\n- Inserting Arcs into Queue: $O(d)$, each arc inserted $O(d)$ times ($X_i$ has at most $d$ values to delete)\n- Total: $O(n^2 * d^3)$\n \n\n## Module 6 Definitions\n* **Arc consistency** - X -> Y as consistent iff for every x of X, there exists allowed y\n* **Backjumping** - backtracking to most recent assignment in conflict set\n* **Backtracking** - DFS on single-variable assignments\n* **Csp** - Constraint Satisication Problem, state with variable/value and conditions for constraints on variables\n* **Chronological backtracking** - after branch failure, back up to preceding variable of most recent decision point\n* **Conflict-directed backumping** - backtracking to preceding variable AND all subsequent variables causing conflict\n* **Consistent** - solution not breaking the constraints\n* **Constraint learning** - finding min set of variabel from conflict set cauisng issues\n* **Constraint propogation** - reducing legal values of a variable via available constrains\n* **Directional arc consistency** - for every $X_i$ arcconsistent for each $X_j$ for $j>i$\n* **Global constraints** - constraints involving arbitraryn number of variables\n* **Least constraing value** - pick values with least constraints on neighbors\n* **Minimum remaining values** - picks variable most likely to fail\n* **No-good** - variable assignments doomed to fail\n* **Strongly k-consistent** - CSPs consistent from k, k-1, ... 1\n* **Tree width** - minimum width of tree decompositions\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n-Sentence Types: Axioms and Derived Sentences\n\n-Agent: TELLS KB its percption, ASK KB what action to perform, TELLS KB which action is chosen and executes action\n\n-Approaches: Declarative (TELL sentences until agent operates environment) vs Procedural (encoded desired behaviors)\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n-PEAS\n- Performance: 1000 for finding gold, -1000 for pit/wumpus, -1 for action taken (encourage shortest path), -10 for using arrow\n- Environment: 4x4 room grid\n- Actuators: move forward, turn left, turn right, grab, shoot, climb\n- Sensors: [Stench, Breeze, Glitter, Bump, Scream]\n\n-Environment: deterministic, discrete, static, singleagent, seqquential, partially observable\n\n\n## AIMA Chapter 7.3 Logic\n\n-Syntax: 'x+y=4' as well formed, 'x4y+=' as not\n\n-Semantics: 'x+y=4' as true in world where x,y=2 and false in world where x,y=1\n\n-Model: 'x+y=4' possible models as different assignments of x and y\n\n-Entailemnt: x=0 entails xy=0\n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n-Sentences: Atomic Sentences (single propositional symbol) vs Complex Sentences sentence with logical connectives\n\n-Connectives (in order): negation, conjunction (and), disjunction (or), implication (premise/antecedent, conclusion/consequence), biconditional (iff)\n\n-TT Entails Algorithm: recursive enumeration, sound , complete, exponential to input\n\n## AIMA 7.5 Propositional Theorem Proving\n \n-Validity and Satisfiability: a|=b B iff (a /\\ not B) is unsatisfiable, a satisfiable iff not a is not valid\n\n-Unit Resolution: take two clause and produce new clause containing all literals of two original clauses, except complementary ltierals\n\n-Resolution Completeness: proving ground resolution theorem contrapositive ... if RC(S) not empty set, S is satisfiable\n\n-Constructing model for S: for i from 1 to k\n- If clause in RC(S) contains not $P_i$ and all other literals are false for $P_1, ..., P_i-1$, $P_i$ = false\n- Else: $P_i$ = True\n\n-Resolution Model Proof: assuming at some $i$, $P_i$ causes $C$ to be false ... then all other literals in $C$ must be flase by assignments from $P_1, ... P_i-1$\n\n-Definite Clause: (not L \\/ not Breeze \\/ B)\n- Every definite clause can be written as implication with premise (conjunction of positive literals) and conclusion (single positive literal)\n- Horn clause inference can be done with forward-chaining or backward-chaining\n- Deciding Horn Clause entailment is linear\n\n-Forward Chaining Algorithm (sound and complete): determine if single proposition is entailed by knowledge base of definite clauses\n- Start: positive literals of knowledge base\n- If premise of implication are known, add conclusion to facts: if L and Breeze known for (L /\\ Breeze) -> B, add B\n- Repeat until no q is added or cannot make more inferences\n\n-Backward Chaining\n- Start: q\n- Find implication in knowledge base whose conclusiosn is q\n \n\n## Module 7 Lecture Notes\n\n<h3>KNOWLEDGE-BASED AGENTS/LOGIC</h3>\n-Knowledge Base: false in models contradicting agent knowledge\n\n-Representation Language: has syntax to specify well-formed sentences\n\n-Logic: defines semantics (meaning) of sentences\n\n-Semantics: defines truth with respect to possible worlds\n\n-Models: M(a) as set of all models that satisfy sentence a\n\n-Entailment: a|=B iff M(a) subset of M(B)\n<h3>THEOREM PROVING</h3>\n-Search for a Proof\n- Initial State: initial knowledge nase (set of statements)\n- Actions: inference rules applied to all sentences\n- Result: add statement to bottom half of KB\n- Goal: state containing sentence we are trying to prove\n\n-Monotonicty: soundeness since adding additional information doesn't invalidate previous information\n\n-Resolution: yields complete inference algorithm when coupeld with complete search algorithm\n\n-Conjunctive Normal Form Steps\n- Eliminate <-> with (a -> B) /\\ (B -> a)\n- Eliminate -> with not a \\/ B\n- Repeatedly move not inwards (double negation, not /\\ - DeMorgan, not \\/ - Demorgan)\n- Apply distributivity law \\/ over /\\ if possible\n\n-Resolution Algorithm: proofby contradition, show KB=a by showing KB /\\ a is unsatisfiable\n- Convert (KB /\\ not a) to CNF\n- Apply resolution rule to resulting clauses\n- Resolve every pair that contains completemtnary literals to produce new clause\n- If new cluse isn't present, add to set\n- Continue until: 1) no new classes to add (KB does not entail a), 2) two clause resolve to yield empty clause (KB does not entail a)\n\n-Forward Chaining: data driven reasoning, start with known data and add premise as new precept comes in without specific query in mind\n\n-Backward Chaining: goal-directed reasoning, start with query and find implication in KB whose conclusion is query\n \n\n## Module 7 Definitions\n* **Axiom** - given sentences, not derived from other sentences\n* **Complete** - inference algorithm capable of deriving any entailed instances\n* **Definite clause** - disjunction clause of literals where exactly one positive\n* **Entailment** - sentence logically follows from another sentence, a|=B iff every model in A is true in B\n* **Goal clause** - clause where no positive literals\n* **Ground resolution theorem** - if clauses are unsatisfiable, reoslution closure yieldsempty set\n* **Horn clause** - disjunction clause where at most one is positive\n* **Inference** - deriving new sentences from existing sentences\n* **Knowledge base** - set of sentences built from background information and observations\n* **Knowledge-based agents** - agents that use reasoning to decide actions\n* **Logical equivalence** - two statements that are true for same set of models, a = B iff a|=B and B|=a\n* **Model** - possible worlds; mathematical abstraction with fixed set of truth values (true, false) for each sentence\n* **Model checking** - algorithm that list all possible models to check a true in all models KB is true, M(KB) subset of M(a)\n* **Monotonicity** - if KB|=a then KB /\\ B |=a\n* **Resolution** - if l and m are complemtnary literals, they can be eliminated va unit resolution\n* **Resolution closure rc(s)** - set of all clauses derivable by applying resolution rule, final product of PL-Resolution\n* **Satisfiability** - sentences is true by some model\n* **Semantics** - meaning of sentences\n* **Sound/truth-preserving** - inference algorithm that derives only entailed sentences\n* **Syntax** - definition of how sentences are well-formed\n* **Theorem proving** - process of applying inference rules to sentenes to construct proof\n* **Validity / tautologies** - sentences valid in all models (P \\/ not P)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wcRlKSMO-iD-"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}