{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Christopher_YuCIS521_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": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "Intelligence can be defined as rationality, or an agent's ability to do the \"right thing.\"\n",
        "The Turing test is a test that measures a machine's ability to \"think like a human.\" If a human interrogator cannot determine if the responses are from a human or machine, then the machine passes.\n",
        "The machine thus needs: NLP, a knowledge representation, automated reasoning, and machine learning to adapt.\n",
        "In a total turing test, the physical simulation of a person is also necessary meaning, the machine also needs computer vision and robotics.\n",
        "The cognitive model says we can learn about human thought through introspection, psychological experiments, and brain imaging.\n",
        "\"Laws of thought model\": Aristotle was one of the first to codify \"right thinking,\" the field of logic, which requires some certain knowledge.\n",
        "Knowledge of probability helps us reason rigorously with uncertain information.\n",
        "Rational thought is not enough for rational action.\n",
        "AI focuses on the study and constreuction of agents that do the right thing-- this is the \"standard model\"\n",
        "Minimize cost, maximize rewards, minimize loss function, maximize utility, etc.\n",
        "In the long run, we have to break away from the standard model because it assumes we supply an objective to the machine.\n",
        "(value alignment problem-- how do we align values of machine + human)\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "Distinction between weak AI and strong AI (looking like you're intelligent vs actually being intelligent)\n",
        "embodied cognition: no sense to consider brain separately from body\n",
        "\n",
        "Argument from disability, machines lag in certain areas but are much better at others, not really solid\n",
        "\n",
        "Machines are bound by incompletness theorem\n",
        "\n",
        "turing test is kind of just a test of gullibility\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Can machines think is just a matter of definition\n",
        "Polite convetion -- we assume everyone thinks\n",
        "Chinese room argument - just processing info is not understanding / thinking\n",
        "biological naturalism - mental states are from neurons, neurons have unspecified processes that transistors do not\n",
        "Cells don't have any understanding either though\n",
        "qualia - intrinsic nature of experience\n",
        "Humans have empathy, but machines can run each other's code\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent is anything that can be viewed as perceiving its environment through sensors and\n",
        "acting upon that environment through actuators.\n",
        "An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
        "Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\n",
        "Internally, the agent function for an artificial agent will be\n",
        "implemented by an agent program. It is important to keep these two ideas distinct. The\n",
        "agent function is an abstract mathematical description; the agent program is a concrete\n",
        "implementation, running within some physical system.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "\n",
        "consequentialism: we evaluate an agent’s behavior by its consequences.\n",
        "desirability is captured by a performance measure that evaluates any given sequence of environment states.\n",
        "some agent designs have an explicit representation of the performance measure, while in other designs the performance measure is\n",
        "entirely implicit—the agent may do the right thing, but it doesn’t know why\n",
        "\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has\n",
        "\n",
        "rationality is not omniscience\n",
        "\n",
        "Doing actions in order to modify future percepts—\n",
        "sometimes called information gathering—is an important part of rationality\n",
        "\n",
        "A rational agent should be autonomous—it should learn what it can to compensate for partial or\n",
        "incorrect prior knowledge. \n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "task environments are\n",
        "essentially the “problems” to which rational agents are the “solutions.” \n",
        "\n",
        "PEAS (Performance, Environment, Actuators, Sensors) \n",
        "\n",
        "If an agent’s sensors give it access\n",
        "to the complete state of the environment at each point in time, then we say that the task\n",
        "environment is fully observable. A task environment is effectively fully observable if the\n",
        "sensors detect all aspects that are relevant to the choice of action; relevance, in turn,\n",
        "depends on the performance measure.\n",
        "\n",
        "If the agent has no sensors at all then the environment is unobservable.\n",
        "\n",
        "competitive vs cooperative multi agent\n",
        "\n",
        "Deterministic vs. nondeterministic. If the next state of the environment is completely\n",
        "determined by the current state and the action executed by the agent(s), then we say the\n",
        "environment is deterministic; otherwise, it is nondeterministic. Most real situations are so complex that it is impossible to keep track of all the unobserved aspects; for practical purposes, they must be treated as nondeterministic. \n",
        "\n",
        "stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain\n",
        "tomorrow”) and “nondeterministic” if the possibilities are listed without being quantified\n",
        "(e.g., “there’s a chance of rain tomorrow”).\n",
        "\n",
        "episodic - independent actions, sequential - actions have long term consequences\n",
        "\n",
        "dynamic - environment can change while deliberating\n",
        "semidynamic - performance changes while deliberating\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "The job of AI is to design an agent program that implements the agent function—the\n",
        "mapping from percepts to actions. We assume this program will run on some sort of\n",
        "computing device with physical sensors and actuators—we call this the agent architecture:\n",
        "\n",
        "agent = architecture + program .\n",
        "\n",
        "table driven approach to agent construction is doomed to fail because too much complexity, but technically correct\n",
        "\n",
        "The key challenge for AI is to find out how to write programs that, to the extent possible, produce\n",
        "rational behavior from a smallish program rather than from a vast table.\n",
        "\n",
        "simple reflex agent select actions on the basis of the current percept, ignoring the rest of the percept history. works only if the correct decision can be made on the basis of just the current percept, only if the environment is fully observable.\n",
        "\n",
        "escape from infinite loops is possible if the agent can randomize its actions. randomization can be good in multi agent, usually shouldn't be used in single agent\n",
        "\n",
        "Model based reflex agents:  agent should maintain some sort of internal state that\n",
        "depends on the percept history and thereby reflects at least some of the unobserved aspects\n",
        "of the current state,\n",
        "need a transition model of the world-- need info about how world changes over time- independent changes + agent changes,\n",
        "need sensor model -- how the state of the world ​is reflected in percepts\n",
        "\n",
        "\n",
        "goal based agent\n",
        "\n",
        "need info on which situations are desirable, search + planning find action sequences that achieve goals\n",
        "\n",
        "Utility based agent\n",
        "Goal is binary, utility is more granular comparison of states\n",
        "utility function is essentially an internalization of the performance measure.\n",
        "a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes\n",
        "\n",
        " model-free agent can learn what action is best in a particular situation\n",
        "without ever learning exactly how that action changes the environment.\n",
        "\n",
        "Learning agent\n",
        "Performance element + learning element\n",
        "The learning element uses feedback from the critic on how the agent is doing and determines how the\n",
        "performance element should be modified to do better in the future\n",
        "\n",
        "problem generator is responsible for suggesting actions that will lead to new and informative experiences.\n",
        "\n",
        "the performance standard distinguishes part of the incoming percept as a reward (or\n",
        "penalty) that provides direct feedback on the quality of the agent’s behavior. Hard-wired\n",
        "performance standards such as pain and hunger in animals can be understood in this way\n",
        "\n",
        "in atomic representation each state of the world is indivisible—it has no internal structure\n",
        "factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. \n",
        "structured representation, objects described explicitly\n",
        "more expressive representation can capture more more concisely\n",
        "one-to-one mapping between concepts and memory locations is localist representation\n",
        "if located in different places, distributed representation \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "There isn't really anything that is different from the reading\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content of agent's sensors\",\n",
        "\"rational agent\" : \"one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\",\n",
        "\"limited rationality\": \"act appropriately when there is not enough time to do all the computations\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b476fd9e-d79a-4528-dbae-7343177b6450"
      },
      "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": 4,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nIntelligence can be defined as rationality, or an agent's ability to do the \"right thing.\"\nThe Turing test is a test that measures a machine's ability to \"think like a human.\" If a human interrogator cannot determine if the responses are from a human or machine, then the machine passes.\nThe machine thus needs: NLP, a knowledge representation, automated reasoning, and machine learning to adapt.\nIn a total turing test, the physical simulation of a person is also necessary meaning, the machine also needs computer vision and robotics.\nThe cognitive model says we can learn about human thought through introspection, psychological experiments, and brain imaging.\n\"Laws of thought model\": Aristotle was one of the first to codify \"right thinking,\" the field of logic, which requires some certain knowledge.\nKnowledge of probability helps us reason rigorously with uncertain information.\nRational thought is not enough for rational action.\nAI focuses on the study and constreuction of agents that do the right thing-- this is the \"standard model\"\nMinimize cost, maximize rewards, minimize loss function, maximize utility, etc.\nIn the long run, we have to break away from the standard model because it assumes we supply an objective to the machine.\n(value alignment problem-- how do we align values of machine + human)\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nDistinction between weak AI and strong AI (looking like you're intelligent vs actually being intelligent)\nembodied cognition: no sense to consider brain separately from body\n\nArgument from disability, machines lag in certain areas but are much better at others, not really solid\n\nMachines are bound by incompletness theorem\n\nturing test is kind of just a test of gullibility\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nCan machines think is just a matter of definition\nPolite convetion -- we assume everyone thinks\nChinese room argument - just processing info is not understanding / thinking\nbiological naturalism - mental states are from neurons, neurons have unspecified processes that transistors do not\nCells don't have any understanding either though\nqualia - intrinsic nature of experience\nHumans have empathy, but machines can run each other's code\n\n\n## AIMA 2.1 Agents and Environments\n\nAn agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators.\nAn agent’s percept sequence is the complete history of everything the agent has ever perceived.\nMathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\nInternally, the agent function for an artificial agent will be\nimplemented by an agent program. It is important to keep these two ideas distinct. The\nagent function is an abstract mathematical description; the agent program is a concrete\nimplementation, running within some physical system.\n\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n\nconsequentialism: we evaluate an agent’s behavior by its consequences.\ndesirability is captured by a performance measure that evaluates any given sequence of environment states.\nsome agent designs have an explicit representation of the performance measure, while in other designs the performance measure is\nentirely implicit—the agent may do the right thing, but it doesn’t know why\n\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has\n\nrationality is not omniscience\n\nDoing actions in order to modify future percepts—\nsometimes called information gathering—is an important part of rationality\n\nA rational agent should be autonomous—it should learn what it can to compensate for partial or\nincorrect prior knowledge. \n\n\n\n## AIMA 2.3 The Nature of Environments\n\ntask environments are\nessentially the “problems” to which rational agents are the “solutions.” \n\nPEAS (Performance, Environment, Actuators, Sensors) \n\nIf an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task\nenvironment is fully observable. A task environment is effectively fully observable if the\nsensors detect all aspects that are relevant to the choice of action; relevance, in turn,\ndepends on the performance measure.\n\nIf the agent has no sensors at all then the environment is unobservable.\n\ncompetitive vs cooperative multi agent\n\nDeterministic vs. nondeterministic. If the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic. Most real situations are so complex that it is impossible to keep track of all the unobserved aspects; for practical purposes, they must be treated as nondeterministic. \n\nstochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain\ntomorrow”) and “nondeterministic” if the possibilities are listed without being quantified\n(e.g., “there’s a chance of rain tomorrow”).\n\nepisodic - independent actions, sequential - actions have long term consequences\n\ndynamic - environment can change while deliberating\nsemidynamic - performance changes while deliberating\n\n\n## AIMA 2.4 The Structure of Agents\n\nThe job of AI is to design an agent program that implements the agent function—the\nmapping from percepts to actions. We assume this program will run on some sort of\ncomputing device with physical sensors and actuators—we call this the agent architecture:\n\nagent = architecture + program .\n\ntable driven approach to agent construction is doomed to fail because too much complexity, but technically correct\n\nThe key challenge for AI is to find out how to write programs that, to the extent possible, produce\nrational behavior from a smallish program rather than from a vast table.\n\nsimple reflex agent select actions on the basis of the current percept, ignoring the rest of the percept history. works only if the correct decision can be made on the basis of just the current percept, only if the environment is fully observable.\n\nescape from infinite loops is possible if the agent can randomize its actions. randomization can be good in multi agent, usually shouldn't be used in single agent\n\nModel based reflex agents:  agent should maintain some sort of internal state that\ndepends on the percept history and thereby reflects at least some of the unobserved aspects\nof the current state,\nneed a transition model of the world-- need info about how world changes over time- independent changes + agent changes,\nneed sensor model -- how the state of the world ​is reflected in percepts\n\n\ngoal based agent\n\nneed info on which situations are desirable, search + planning find action sequences that achieve goals\n\nUtility based agent\nGoal is binary, utility is more granular comparison of states\nutility function is essentially an internalization of the performance measure.\na rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes\n\n model-free agent can learn what action is best in a particular situation\nwithout ever learning exactly how that action changes the environment.\n\nLearning agent\nPerformance element + learning element\nThe learning element uses feedback from the critic on how the agent is doing and determines how the\nperformance element should be modified to do better in the future\n\nproblem generator is responsible for\nsuggesting actions that will lead to new and informative experiences.\n\nthe performance standard distinguishes part of the incoming percept as a reward (or\npenalty) that provides direct feedback on the quality of the agent’s behavior. Hard-wired\nperformance standards such as pain and hunger in animals can be understood in this way\n\nin atomic representation each state of the world is indivisible—it has no internal structure\nfactored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. \nstructured representation, objects described explicitly\nmore expressive representation can capture more more concisely\none-to-one mapping between concepts and memory locations is localist representation\nif located in different places, distributed representation \n\n## Module 1 Lecture Notes\n\nThere isn't really anything that is different from the reading\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content of agent's sensors\n* **Rational agent** - one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n* **Limited rationality** - act appropriately when there is not enough time to do all the computations\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",
        "list comprehensions\n",
        "dict comprehenstion\n",
        "slice operator returns a copy\n",
        "sets and lists are non hashable and can't be keys in a dict (mutable)\n",
        "set remove throws an error if not found\n",
        "cannot add dictionaries\n",
        "you can perform some math on strings\n",
        "no tuple or string element assignment (immutable)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"whether an object can be changed after it is created\",\n",
        "}"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6c9789f4-242b-4b15-98f8-42d0e16986a9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\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",
        "\n",
        "4 step solving process: goal formulation, problem formulation, search, execution\n",
        "\n",
        "Before an agent can start searching, a well-defined problem must be formulated.\n",
        "\n",
        "A problem consists of five parts: the initial state, a set of actions, a transition model\n",
        "describing the results of those actions, a set of goal states, and an action cost function.\n",
        "\n",
        "model—an abstract mathematical description of the problem\n",
        "abstraction is removing detail from representation\n",
        "\n",
        "A sequence of actions forms a path, and a solution is a path from the initial state to a goal\n",
        "state. We assume that action costs are additive; that is, the total cost of a path is the sum of\n",
        "the individual action costs. An optimal solution has the lowest path cost among all\n",
        "solutions. \n",
        "\n",
        "open loop system- ignoring percepts is fine during execution, because model is perfect and solution is fixed\n",
        "closed loop system - not that\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "example problems\n",
        "\n",
        "grid world example:\n",
        "INITIAL STATE: Any state\n",
        "ACTIONS: move up down left right through\n",
        "TRANSITION MODEL: movements move the agent\n",
        "GOAL STATE: state where agent is at the goal \n",
        "ACTION COST: Each action costs 1.\n",
        "\n",
        "Touring problems need a set of locations visited\n",
        "vsli layout for circuits\n",
        "robot navigations\n",
        "assembly sequencing\n",
        "protein design\n",
        "\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Best first search selects nodes for expansion using to an evaluation function.\n",
        "\n",
        "completeness - guaranteed to find solution if there is one\n",
        "optimal - lowest cost\n",
        "time complexity - number of states / actions considered\n",
        "space complexity - memory req \n",
        "\n",
        "complexity measured in terms of depth and branching factor\n",
        "\n",
        "graph search - checks redundant paths\n",
        "tree search - doesn't\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "breadth first - shallowest first, optimal for unit action, complete, exponential space complexit\n",
        "uniform cost - lowest path cost g(n), optimal for general action costs (djikstra's), also exponential space\n",
        "depth first - deepest unexpanded node first, not complete or optimal, linear space complexity, depth limited adds depth bound\n",
        "backtracking search uses even less memory\n",
        "iteartive deepending search - above with increasing depth, complete when cycle checking is done, optimal for unit action, time complexity comparable to bfs, linear space complexity\n",
        "bidrectional search - expands from goal and initial\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" not much different from above \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f8c6dc37-627d-494b-d493-ce53672224a4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "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",
        "Informed search uses heuristic function h(n) to estimate cheapest path from node n to goal state\n",
        "greedy best first - expand with minimal h(n), not optimal but efficient\n",
        "\n",
        "admissible heuristic is one that never overestimates the cost to reach a goal\n",
        "consistent heuristic - triangle inequality, heuristic of n is <= cost of n to n' + heuristic of n\n",
        "straight line distance is consistent\n",
        "\n",
        "a* - minimal h(n) + g(n) (path cost), complete and optimal if h(n) is admissible, space complexity still a problem\n",
        "\n",
        "countours on a search map (show depth) expand outward as fronteir grows\n",
        "path costs are monotonic, always increase as you go along\n",
        "countours should expand towards goal with a good heuristic, narrowly stretching along optimal path\n",
        "\n",
        "C* = cost of optimal path\n",
        "A* expands all nodes that can be reached from initial state on path whever every node has f(n) < C* (surely expanded nodes)\n",
        "might expand some on the goal contour before selecting a goal node\n",
        "A* expands no nodes with f(n) > C*\n",
        "A* is thus optimal efficient, prunes away search tree nodes that are unnecessary to find optimal solution\n",
        "satisficing - goood enough\n",
        "we can use inadmissible heursitics, e.g. detour index to get satisficing\n",
        "\n",
        "weighted A* expands nodes with minimal g(n) + W*h(n)\n",
        "kind of greedy, more efficient\n",
        "in a bounded suboptimal search, solution guarenteed to be within factor of W (weighted a*)\n",
        "bounded cost search - cost less than some constant c\n",
        "unbounded-cost search - any cost, as long as we can find it quickly\n",
        "speedy search - heuristic based on how quickly we can find goal, regardless of cost\n",
        "\n",
        "save memory with a*\n",
        "reference counts - remove state from table when no more ways to reach the state\n",
        "beam search - limits size of fronteir, only keep k nodes with best h + g, incomplete + suboptimal\n",
        "ida* - cutoff at f-cost, new cutoff will be smallest f cost of exceeded cutoff, good when integer path cost\n",
        "recusrive best first search - keeps track of f value of best alt path, once exceeds limit, unwinds to alt path, replaces f-value of each node along back-up path as best f-value of its children\n",
        "\n",
        "sma* (simple memory bounded a*)\n",
        "expand best leaf until memory is full, drops worst leaf node when adding new one\n",
        "\n",
        "bidirectional a* is mostly good on average heuristics\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "city block distance - number non-diagonal moves to get to goal\n",
        "effective branching factor\n",
        "If thetotal number of nodes generated by A* for a particular problem is N and the solution depth\n",
        "is d then b* is the branching factor that a uniform tree of depth d would have to have in\n",
        "order to contain N nodes. \n",
        "N+1 = 1 +b* + b*^2 ... + b*^d\n",
        "\n",
        "a heuristic dominates another if h(n) >= h2(n) for any n\n",
        "a* with dominating h will never expand more nodes than alt except when breaking ties unluckily\n",
        "a problem with fewer restrictions on action is called relaxed\n",
        "solution to relaxed problem is admissible heuristic\n",
        "\n",
        "admissible heuristics can also be derived from solution cost of subproblem\n",
        "e.g. pattern database that stores every possible configuration of a subproblem, can be constructed by searching back from the goal\n",
        "disjoint pattern databases can be added\n",
        "landmark heuristics, precompute some optimal path costs between landmarks that you can use to go along\n",
        "also some shortcuts to check optimal multi action path\n",
        "not admissible by itself\n",
        "metalevel space / metalevel learning - look at the search tree as a state and avoid exploring unpromising subtrees\n",
        "can ML heuristics\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" not much different from above \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 826
        },
        "cellView": "form",
        "outputId": "9f66d7e9-e1f3-4067-8306-31b215150b8e"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed search uses heuristic function h(n) to estimate cheapest path from node n to goal state\ngreedy best first - expand with minimal h(n), not optimal but efficient\n\nadmissible heuristic is one that never overestimates the cost to reach a goal\nconsistent heuristic - triangle inequality, heuristic of n is <= cost of n to n' + heuristic of n\nstraight line distance is consistent\n\na* - minimal h(n) + g(n) (path cost), complete and optimal if h(n) is admissible, space complexity still a problem\n\ncountours on a search map (show depth) expand outward as fronteir grows\npath costs are monotonic, always increase as you go along\ncountours should expand towards goal with a good heuristic, narrowly stretching along optimal path\n\nC* = cost of optimal path\nA* expands all nodes that can be reached from initial state on path whever every node has f(n) < C* (surely expanded nodes)\nmight expand some on the goal contour before selecting a goal node\nA* expands no nodes with f(n) > C*\nA* is thus optimal efficient, prunes away search tree nodes that are unnecessary to find optimal solution\nsatisficing - goood enough\nwe can use inadmissible heursitics, e.g. detour index to get satisficing\n\nweighted A* expands nodes with minimal g(n) + W*h(n)\nkind of greedy, more efficient\nin a bounded suboptimal search, solution guarenteed to be within factor of W (weighted a*)\nbounded cost search - cost less than some constant c\nunbounded-cost search - any cost, as long as we can find it quickly\nspeedy search - heuristic based on how quickly we can find goal, regardless of cost\n\nsave memory with a*\nreference counts - remove state from table when no more ways to reach the state\nbeam search - limits size of fronteir, only keep k nodes with best h + g, incomplete + suboptimal\nida* - cutoff at f-cost, new cutoff will be smallest f cost of exceeded cutoff, good when integer path cost\nrecusrive best first search - keeps track of f value of best alt path, once exceeds limit, unwinds to alt path, replaces f-value of each node along back-up path as best f-value of its children\n\nsma* (simple memory bounded a*)\nexpand best leaf until memory is full, drops worst leaf node when adding new one\n\nbidirectional a* is mostly good on average heuristics\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\ncity block distance - number non-diagonal moves to get to goal\neffective branching factor\nIf thetotal number of nodes generated by A* for a particular problem is N and the solution depth\nis d then b* is the branching factor that a uniform tree of depth d would have to have in\norder to contain N nodes. \nN+1 = 1 +b* + b*^2 ... + b*^d\n\na heuristic dominates another if h(n) >= h2(n) for any n\na* with dominating h will never expand more nodes than alt except when breaking ties unluckily\na problem with fewer restrictions on action is called relaxed\nsolution to relaxed problem is admissible heuristic\n\nadmissible heuristics can also be derived from solution cost of subproblem\ne.g. pattern database that stores every possible configuration of a subproblem, can be constructed by searching back from the goal\ndisjoint pattern databases can be added\nlandmark heuristics, precompute some optimal path costs between landmarks that you can use to go along\nalso some shortcuts to check optimal multi action path\nnot admissible by itself\nmetalevel space / metalevel learning - look at the search tree as a state and avoid exploring unpromising subtrees\ncan ML heuristics\n\n\n## Module 4 Lecture Notes\n not much different from above \n\n## Module 4 Definitions\n* **Concept** - definition\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",
        "\n",
        "game can be defined as initial state, turn, actions, transition model, terminal, utility function\n",
        "\n",
        "deterministic, two-player, turn-taking, perfect information (fully observable), zero-sum games.\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "minimax generates optimal decisions for above\n",
        "backs up minimax values through the optimal\n",
        "minimax not always optimal if opponent is suboptimal\n",
        "\n",
        "alpha beta pruning-prune of nodes / subtrees if above player has better option higher up in the tree, because it would never take this option anyway\n",
        "alpha = best choice we have found so far at any choice along path for max (at least)\n",
        "beta = best choice we have found so far along the path for min (at most)\n",
        "\n",
        "very dependent on move order examination\n",
        "can use iterative deepending ish thing by evaluating one layer of moves then using that to inform move order\n",
        "best moves are called killer moves, killer move heuristic\n",
        "\n",
        "type a- wide but shallow\n",
        "type b- deep but narrow\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "replace terminal test with cutoff test to make use of limited computation time\n",
        "evaluation can't take too long\n",
        "(expected value)\n",
        "weighted linear function\n",
        "cutting off search, can do it based on depth\n",
        "should only be applied to position that are quiescent, no pending move that would wildly swing the evlaution\n",
        "quiescence search can be limited to capture moves \n",
        "horizon effect - might push things beyond the cutoff in a very losing position\n",
        "singular extensions - clearly better moves are allowed to go past the horizon even when cutoff\n",
        "forawrd pruning - prune moves that appear to be poor, but could be bad (e.g. beam search, take best n moves)\n",
        "late move reduction - move ordering is good, so moves that appear later are less likely to be good, so reduce depth\n",
        "\n",
        "can also just use a lookup for openings / endings to a game\n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "stochastic games need chance nodes in addition to min and max, have to use expected value\n",
        "expectiminimax value\n",
        "can bound average without looking at every chance node if you have a bound on the utility value\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "principle of maximum expected utility says rational agent should maximize expected utility\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "orderability - must make a decision- one better, or equal\n",
        "transitivity a > b, b > c means a > c\n",
        "continuity if b is between a and c, then there is some probability for a and c where surefire b is equivalent\n",
        "SUBSTITUTABILITY - if indifferent between a and b, then comparisons for more complex lotteries should be the same if a is switched for b\n",
        "monotonicity - if a is better than b, then the agent prefers the lottery that has a higher probability for a and vice versa\n",
        "DECOMPOSABILITY - can be reduced to simpler ones with probability\n",
        "if preferences obery above, there is a utility function\n",
        "expected utility is sum of probability times utility\n",
        "only needs preference ranking, don't specifically need numbers - value function, ordinal utility function\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "preference elicitation - present choices and use observed preferences to pin down underlying utility function\n",
        "choose between s and standard lottery\n",
        "\n",
        "value of statistical life, ~$10 mil\n",
        "\n",
        "micromort, one in a million chance of death, actual behavior reflex lower monetary value for micromort\n",
        "\n",
        "qaly, quality adjusted life year, shorter life expectancy better than disability\n",
        "\n",
        "risk averse in gains, risk seeking in losses\n",
        "\n",
        "difference between emv of loterry and certainty equivalent is insurance premium\n",
        "\n",
        "small changes will be approx linear, linear curves are risk neutral\n",
        "\n",
        "optimizer's curse - estimated EU of best choice is too high\n",
        "\n",
        "decision theory is normative, describes should\n",
        "descriptive theory describes how it actually is\n",
        "\n",
        "framing effect\n",
        "anchoring effect\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" not different from above \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "39ec8635-89e2-4f2f-99f8-00aecd47f6ca"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\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",
        "CSP has X- set of variables\n",
        "D - set of domains\n",
        "C - set of constraints that allow combinations of values\n",
        "\n",
        "constraint is scope (variables) and relation that defines what values those variables can take on\n",
        "\n",
        "consistent = no constraints violated \n",
        "\n",
        "CSPS assign values\n",
        "solution is a complete assignment, where every variable has an assignment\n",
        "\n",
        "partial solution leaves some unassigned, partial solution\n",
        "\n",
        "map coloring, scheduling\n",
        "\n",
        "discrete, finite domains are simplest\n",
        "\n",
        "no algorithm exists for solving general nonlinear constraints on integer values - undecidable\n",
        "\n",
        "continuous domains are common in real world\n",
        "\n",
        "unary constraint - one variable\n",
        "binary 2\n",
        "global constraint - arbitrary number of variables\n",
        "\n",
        "constrained optimzation problem\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "\n",
        "Constraint propagation - use constraints to reduce legal values for a variable, which propagates for another variable, so on\n",
        "local consistency, each variable as a node in graph\n",
        "\n",
        "node consistent if unary constraints satisfied\n",
        "arc consistent if every binary constraint satisfied\n",
        "ac-3 enforces above\n",
        "O(cd^3)\n",
        "\n",
        "path consistent uses implicit constraints that are inferred by looking at triples\n",
        "two variable set path consistent with third variable if every assignment of a,b is consistent with their constraints, and there is an assignment to c that is\n",
        "consistent with b,c and a,c\n",
        "\n",
        "k-consistency is that but going on\n",
        "\n",
        "strongly k-consistent if also consistent for k, k-1, ... 1\n",
        "csp is np complete in general, n-consistency must take exponential time in worst case\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "backtracking search\n",
        "commutativity - order of actions doesn't matter, so leaves are just d^n\n",
        "minimum remain values heuristic - most constrained variable - fail first, so prune search tree and backtrack\n",
        "degree heuristic  - expand node with largest number of constraints\n",
        "least constraining variable - expand node that imposes least restrictions\n",
        "\n",
        "reduce domains with search and inference\n",
        "\n",
        "forward checking - chosen value should delete from domain those values inconsistent for x\n",
        "\n",
        "MAC detects inconsistencies, but only checks for arcs that are unassigned for neighbors of x\n",
        "then AC-3 does constraint propagation, if anyone is reduced to empty set, backtrack\n",
        "\n",
        "MAC is more powerful than forward checking because it doesn't recursively propagate \n",
        "\n",
        "\n",
        "conflict directed backjumping - reassign someone in the conflict set when empty\n",
        "\n",
        "Constraint learning records the conflicts as they are encountered during search in order\n",
        "to avoid the same conflict later in the search.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "local search is good for csps\n",
        "start with complete assignment (will probably violate constraints)\n",
        "min conflicts heuristic - reassign variables to value that results in minimum conflicts\n",
        "lots of plateaus for csps, should be able to move sideways to another state with the same score (plateau search)\n",
        "tabu search helps direct plateau search by forbidding to return to recently visited states\n",
        "constraint weighting, focus on important constraints, incrememnt weights of contraints that get violated by current assignment\n",
        "adds topography to the plateaus, adds learning\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "decompose real world into subproblems, try to find independent subproblems\n",
        "\n",
        "find the connected components of each graph\n",
        "completely independent subproblems are rare\n",
        "constraint graph is a tree when any two variables are connected by only one path\n",
        "any tree structured csp can be solved in linear time in the number of vars\n",
        "directional arc consistency DAC\n",
        "directional arc consistency if consistent in a line\n",
        "topological sort, each variable appears after its parent in the tree\n",
        "once you have directed arc consistent graph, just go down the list of variables and choose any remaining variable\n",
        "Since each edge from a parent to its child is arc-consistent, we know that for any value we choose \n",
        "for the parent, there will be a valid value left to choose for the child.\n",
        "\n",
        "cutset conditioning - reduce constraint graph to a tree - assign variables so remaining variables form a tree\n",
        "identify cycle cutset\n",
        "remove cycle cutset, attempt solution, solve tree\n",
        "if the cycle cutset has size c, total runtime is (d^c - (n-c)d^2)\n",
        "finding the smallest cycle cutset is np hard, but approximations are known, this is called cutset conditioning\n",
        "\n",
        "tree decomposition - group nodes into \"tree nodes\" so they become a tree you can solve very fast\n",
        "\n",
        "tree decomposition must satisfy:\n",
        "Every variable in the original problem appears in at least one of the tree nodes.\n",
        "If two variables are connected by a constraint in the original problem, they must appear\n",
        "together (along with the constraint) in at least one of the tree nodes.\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the\n",
        "path connecting those nodes.\n",
        "tree width = is one less than size of largest node\n",
        "O(nd^w+1)\n",
        "\n",
        "value symmetry, some solutions are same as others with permuation of values\n",
        "can introduce symmetry breaking constraint, arbitrary constraint that only one of the symmetric solutions is possible\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Not different from above \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "946ec5ee-e02a-4f18-e830-9e2755701c5c"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSP has X- set of variables\nD - set of domains\nC - set of constraints that allow combinations of values\n\nconstraint is scope (variables) and relation that defines what values those variables can take on\n\nconsistent = no constraints violated \n\nCSPS assign values\nsolution is a complete assignment, where every variable has an assignment\n\npartial solution leaves some unassigned, partial solution\n\nmap coloring, scheduling\n\ndiscrete, finite domains are simplest\n\nno algorithm exists for solving general nonlinear constraints on integer values - undecidable\n\ncontinuous domains are common in real world\n\nunary constraint - one variable\nbinary 2\nglobal constraint - arbitrary number of variables\n\nconstrained optimzation problem\n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n\nConstraint propagation - use constraints to reduce legal values for a variable, which propagates for another variable, so on\nlocal consistency, each variable as a node in graph\n\nnode consistent if unary constraints satisfied\narc consistent if every binary constraint satisfied\nac-3 enforces above\nO(cd^3)\n\npath consistent uses implicit constraints that are inferred by looking at triples\ntwo variable set path consistent with third variable if every assignment of a,b is consistent with their constraints, and there is an assignment to c that is\nconsistent with b,c and a,c\n\nk-consistency is that but going on\n\nstrongly k-consistent if also consistent for k, k-1, ... 1\ncsp is np complete in general, n-consistency must take exponential time in worst case\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nbacktracking search\ncommutativity - order of actions doesn't matter, so leaves are just d^n\nminimum remain values heuristic - most constrained variable - fail first, so prune search tree and backtrack\ndegree heuristic  - expand node with largest number of constraints\nleast constraining variable - expand node that imposes least restrictions\n\nreduce domains with search and inference\n\nforward checking - chosen value should delete from domain those values inconsistent for x\n\nMAC detects inconsistencies, but only checks for arcs that are unassigned for neighbors of x\nthen AC-3 does constraint propagation, if anyone is reduced to empty set, backtrack\n\nMAC is more powerful than forward checking because it doesn't recursively propagate \n\n\nconflict directed backjumping - reassign someone in the conflict set when empty\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nlocal search is good for csps\nstart with complete assignment (will probably violate constraints)\nmin conflicts heuristic - reassign variables to value that results in minimum conflicts\nlots of plateaus for csps, should be able to move sideways to another state with the same score (plateau search)\ntabu search helps direct plateau search by forbidding to return to recently visited states\nconstraint weighting, focus on important constraints, incrememnt weights of contraints that get violated by current assignment\nadds topography to the plateaus, adds learning\n\n\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\ndecompose real world into subproblems, try to find independent subproblems\n\nfind the connected components of each graph\ncompletely independent subproblems are rare\nconstraint graph is a tree when any two variables are connected by only one path\nany tree structured csp can be solved in linear time in the number of vars\ndirectional arc consistency DAC\ndirectional arc consistency if consistent in a line\ntopological sort, each variable appears after its parent in the tree\nonce you have directed arc consistent graph, just go down the list of variables and choose any remaining variable\nSince each edge from a parent to its child is arc-consistent, we know that for any value we choose \nfor the parent, there will be a valid value left to choose for the child.\n\ncutset conditioning - reduce constraint graph to a tree - assign variables so remaining variables form a tree\nidentify cycle cutset\nremove cycle cutset, attempt solution, solve tree\nif the cycle cutset has size c, total runtime is (d^c - (n-c)d^2)\nfinding the smallest cycle cutset is np hard, but approximations are known, this is called cutset conditioning\n\ntree decomposition must satisfy:\nEvery variable in the original problem appears in at least one of the tree nodes.\nIf two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\nIf a variable appears in two nodes in the tree, it must appear in every node along the\npath connecting those nodes.\n\n\n\n\n## Module 6 Lecture Notes\n Not different from above \n\n## Module 6 Definitions\n* **Concept** - definition\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",
        "knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\n",
        "knowledge base, kb\n",
        "knowledge base is set of sentences in a knowledge representation language\n",
        "givens are called axioms\n",
        "\n",
        "adding sentences through tell, query through ask\n",
        "e.g. if goal is go from point a to point b, and we know c is only path from a to b, the agent will take path c because it knows this sentence, regardless of implmentation\n",
        "declarative approach to system building - tell agent things until it knows how to work\n",
        "procedural approach - encode desired behaviors as program code\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "wumpus world\n",
        "performance measure - leave cave with gold\n",
        "-1000 for encountering wumpus or falling pit\n",
        "-1 for each action\n",
        "-10 for using the arrow\n",
        "enviornment 4x4 room of grids, always start at 1,1\n",
        "actuators - turn, forward, grab, shoot\n",
        "sensors - stench if wumpus is in adjacent square, breeze if directly adjacent to pit, glitter if in gold room, scream if wumpus killed, bump if in wall\n",
        "\n",
        "if information is correct, conclusions are guarenteed to be correct by logical reasoning\n",
        "\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "logic defines semantics of sentences\n",
        "semantics (meaning) defines the truth of a sentence with respect to each possible world (model)\n",
        "a model satisfies / is a model of a sentence if a sentence a is true under the model\n",
        "M(a) describes the set of all models of a\n",
        "logical entailment - sentence follows logically from another\n",
        "KB is a set of sentences that asserts all the individual sentences\n",
        "model checking - enumerates models to check that a is true in which kb is true\n",
        "inference algorithm that only derives entailed sentences is called sound or truth preserving\n",
        "completness - can derive any sentence that is entailed\n",
        "general rules are produced by sentence construction called learning, learning is fallible\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "propositional logic\n",
        "truth tables\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "rules of inference\n",
        "commutatativity of\n",
        "associativity of \n",
        "double negation elimination\n",
        "contraposition\n",
        "implication elimination\n",
        "biconditional elimination\n",
        "demorgan\n",
        "distributivity of _ over _\n",
        "\n",
        "validity - tautologies\n",
        "\n",
        "deduction theorem\n",
        "a is consistent with b iff a => b is valid\n",
        "\n",
        "satisfiability - some model satisfies a sentence\n",
        "SAT problem\n",
        "\n",
        "proof by contradiction (a and not b is unsatisfiable)\n",
        "modus ponens (a => b, a, thus b)\n",
        "and elimination (a and b, thus a)\n",
        "\n",
        "entailed sentences can only increase as infomration is added\n",
        "if KB |= a, then KB and B |= a\n",
        "\n",
        "resolution rule - you have a sentence that is a big disjunction, and you add a sentence that is a complement to that disjunction\n",
        "thus, an entailment is just the disjunction with one removed\n",
        "a or b or c, not a, thus b or c\n",
        "\n",
        "you cannot resolve on two literals at once\n",
        "a or not b or c, not a or b, NOT thus c\n",
        "only thus a or not a or c\n",
        "or thus not b or c or b\n",
        "\n",
        "factoring - remove multiple copies of literal (a or a is just a, a and a is just a)\n",
        "\n",
        "CNF, everything expressed as conjunction of clauses\n",
        "eliminate biconditionals\n",
        "eliminate conditionals\n",
        "move negation inwards with double negation and demorgan\n",
        "\n",
        "resolution algorithm - convert to cnf, then resolution applied to resulting clauses -> kb and not a is converted to cnf\n",
        "each pair that contains complementary literals is resolved to a new clause, which is added if not present\n",
        "keep going until:\n",
        "no new clauses are added -> kb does not entail a\n",
        "empty clause added -> kb entails a\n",
        "\n",
        "resolution inference is complete\n",
        "\n",
        "definite clause - exactly one is positive\n",
        "horn clause- at most one is positive, closed under resolution\n",
        "k-CNF, each cnf has at most k literals\n",
        "every definite clause can be written as implication of conjunction with conclusion as one positive\n",
        "horn form, premise = body, conclusion = head, single positive literal is called fact\n",
        "forward chaining -> keep modus ponensing until you conclude the query or stop adding \n",
        "(complete, sound)\n",
        "backward chaining - find implications in knowledge base that conclude q, and check if the implications can be proven true, and so on.\n",
        "backward chaining is goal-directed reasoning, cost is usually much less than linear because the process only touches relevant facts\n",
        "(complete, sound)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Not different from above\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "88854927-a314-40c6-dd1e-59f64a00a40d"
      },
      "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": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nknowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\nknowledge base, kb\nknowledge base is set of sentences in a knowledge representation language\ngivens are called axioms\n\nadding sentences through tell, query through ask\ne.g. if goal is go from point a to point b, and we know c is only path from a to b, the agent will take path c because it knows this sentence, regardless of implmentation\ndeclarative approach to system building - tell agent things until it knows how to work\nprocedural approach - encode desired behaviors as program code\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nwumpus world\nperformance measure - leave cave with gold\n-1000 for encountering wumpus or falling pit\n-1 for each action\n-10 for using the arrow\nenviornment 4x4 room of grids, always start at 1,1\nactuators - turn, forward, grab, shoot\nsensors - stench if wumpus is in adjacent square, breeze if directly adjacent to pit, glitter if in gold room, scream if wumpus killed, bump if in wall\n\nif information is correct, conclusions are guarenteed to be correct by logical reasoning\n\n\n\n## AIMA Chapter 7.3 Logic\n\nlogic defines semantics of sentences\nsemantics (meaning) defines the truth of a sentence with respect to each possible world (model)\na model satisfies / is a model of a sentence if a sentence a is true under the model\nM(a) describes the set of all models of a\nlogical entailment - sentence follows logically from another\nKB is a set of sentences that asserts all the individual sentences\nmodel checking - enumerates models to check that a is true in which kb is true\ninference algorithm that only derives entailed sentences is called sound or truth preserving\ncompletness - can derive any sentence that is entailed\ngeneral rules are produced by sentence construction called learning, learning is fallible\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\npropositional logic\ntruth tables\n\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nrules of inference\ncommutatativity of\nassociativity of \ndouble negation elimination\ncontraposition\nimplication elimination\nbiconditional elimination\ndemorgan\ndistributivity of _ over _\n\nvalidity - tautologies\n\ndeduction theorem\na is consistent with b iff a => b is valid\n\nsatisfiability - some model satisfies a sentence\nSAT problem\n\nproof by contradiction (a and not b is unsatisfiable)\nmodus ponens (a => b, a, thus b)\nand elimination (a and b, thus a)\n\nentailed sentences can only increase as infomration is added\nif KB |= a, then KB and B |= a\n\nresolution rule - you have a sentence that is a big disjunction, and you add a sentence that is a complement to that disjunction\nthus, an entailment is just the disjunction with one removed\na or b or c, not a, thus b or c\n\nyou cannot resolve on two literals at once\na or not b or c, not a or b, NOT thus c\nonly thus a or not a or c\nor thus not b or c or b\n\nfactoring - remove multiple copies of literal (a or a is just a, a and a is just a)\n\nCNF, everything expressed as conjunction of clauses\neliminate biconditionals\neliminate conditionals\nmove negation inwards with double negation and demorgan\n\nresolution algorithm - convert to cnf, then resolution applied to resulting clauses -> kb and not a is converted to cnf\neach pair that contains complementary literals is resolved to a new clause, which is added if not present\nkeep going until:\nno new clauses are added -> kb does not entail a\nempty clause added -> kb entails a\n\nresolution inference is complete\n\ndefinite clause - exactly one is positive\nhorn clause- at most one is positive, closed under resolution\nk-CNF, each cnf has at most k literals\nevery definite clause can be written as implication of conjunction with conclusion as one positive\nhorn form, premise = body, conclusion = head, single positive literal is called fact\nforward chaining -> keep modus ponensing until you conclude the query or stop adding \n(complete, sound)\nbackward chaining - find implications in knowledge base that conclude q, and check if the implications can be proven true, and so on.\nbackward chaining is goal-directed reasoning, cost is usually much less than linear because the process only touches relevant facts\n(complete, sound)\n\n\n\n\n## Module 7 Lecture Notes\nNot different from above\n\n## Module 7 Definitions\n* **Concept** - definition\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/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}