{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Michael FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4ec2d640-497a-4e5e-f2b9-0ca42ec2993d"
      },
      "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": "dd900627-01c2-497a-97ab-5edf1da6c1af"
      },
      "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-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5a51c410-ba19-4fb4-ad81-5851426697f0"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "-intelligence = fidelity to human performance, rationality (doing the right thing?), property of internal thought processes and reasoning, behavior?\n",
        "-turing test: thought experiment -- computer passes if human cannot tell whether response is from human or computer\n",
        "  -needded capabilities: NLP, knowledge representation, automated reasoning, machine learning\n",
        "  -total turing test: requires interaction wiht objects and people in the physical world (requires computer vision, robotics)\n",
        "-human thinking: cognitive modelling\n",
        "  -can be examined through introspection, psychological experiments, brain imaging\n",
        "-rational thinking: laws of thought -- \n",
        "  -right thinking = irrefutable reasoning processes (correct premises must yield correct conclusions)\n",
        "  -utilizes logic and probability\n",
        "-rational agent: one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n",
        "  -this has dominated the other approaches to AI because:\n",
        "    -more general (more possible mechanisms for achieving rationality)\n",
        "    -more amenable to scientific development\n",
        "-AI focuses on the study and construction of agents that DO THE RIGHT THING (standard model)\n",
        "  -but not the best in the long run because it assumes we wll supply a fully specified (complete and correct) objective to the machine\n",
        "  -value alignment problem: how to achieve agreement between our true preferences and the objective we put into the machine\n",
        "  -thus the ultimate aim should be beneficial machines (provably beneficial to humans)\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",
        "strong ai: machines are consciously thinking vs weak ai: machines could act as if they were intelligent\n",
        "argument from informality: human behavior is far too complex (using informal guidelines) to be captured by any formal set of rules\n",
        "qualification problem: capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules (this is difficult)\n",
        "embodied cognition approach: it makes no sense to consider the brain separately\n",
        "-study system as a whole (robots become 'central')\n",
        "argument from disability: a machine can never do things such as be kind, fall in love, do something really new...\n",
        "-machine can never be exactly human\n",
        "mathematical objection: certain mathematical questions are not answerable by formal systems (eg. godel's incompleteness theorem)\n",
        "turing test: a measure of intelligence by performance on open-ended task, not by philosophical speculation\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "chinese room argument: fluent, intelligent responses in Chinese can be transferred even with the individual not \"understanding\" it\n",
        "-asserts that a digital computer executing a program cannot have a \"mind\", \"understanding\" or \"consciousness\", regardless of how intelligently or human-like the program may make the computer behave.\n",
        "-biological naturalism: mental states are high-level emergent features caused by low-level physical processes in the neurons\n",
        "-consciousness: awareness of outside world, self, subjective experience of living\n",
        "  -required for behaving intelligently/interacting with humans\n",
        "-qualia: intrinsic nature of experiences\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "-agent: anything that can be viewed as perceiving its environment through sensors, and acting upon that environment through actuators\n",
        "-percept: the content an agent's sensors are perceiving (percept sequence: complete history)\n",
        "  -an agent's choice of action must depend on percept sequence and/or built-in knwowledge\n",
        "-agent function: maps percept sequence to action (could then be tabulated)\n",
        "-agent program: concrete implementation of an agent function\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "-consequentialism: evaluate an agent's behavior by its consequences (evaluated using performance measure, desirable from the designer's view)\n",
        "-rational agent: select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knwoledge the agent has\n",
        "-rationality depends on: performance measure, prior knowledge, possible actions, percept sequence \n",
        "-omniscience: knowing the actual outcome of its actions and can act accordingly\n",
        "-information gathering: doing actions in order to modify future percepts (eg. through exploration)\n",
        "-rational agent should be autonomous (learn in order to compensate for partial/incorrect prior knowledge)\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "-task environment: the problems to which rational agents are the solutions\n",
        "  -components: PEAS (performance, environment, actuators, sensors)\n",
        "  -properties: \n",
        "    -fully observable (sensors provide access to complete state of environment at each point in time) or partially observable\n",
        "    -single agent or multiagent (cooperative or competitive)\n",
        "      -key distinction between agent and merely object: whether its behavior is best described as maximizing a performance measure whose value depends on another agent's behavior\n",
        "    -deterministic (next state of environment is completely determined by current state and action executed) vs non-deterministic (similar to stochastic, but probabilities are listed without being quantified)\n",
        "      -if deterministic then no uncertainty\n",
        "    -episodic (divide agent's experience into atomic episodes -- discrete, actions in one does not depend on another) or sequential (Current decision could affect all future decisions)\n",
        "    -static or dynamic (environment can change when agent is deliberating, agent is continuously being asked what to do) or semidynamic (environment does not change, but agent's performance score does)\n",
        "    -discrete or continuous (states, time, percepts/actions)\n",
        "    -known or unknown (environment, outcomes for all actions are given)\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "-agent architecture: program runs on computing device with physical sensors and actuators\n",
        "-types of agent programs:\n",
        "1. simple reflex agents\n",
        "-select actions only based on current percept, ignoring past percept history\n",
        "-eg. vacuum \n",
        "-condition action rule: condition connects to some action\n",
        "-unobservability can cause trouble\n",
        "2. model-based reflex agents\n",
        "-maintain an internal state based on percept history to keep track of the world that it cannot see (model-based agent)\n",
        "-components:\n",
        "  -transition model: knowledge of how the world works\n",
        "  -sensor model: how the state of the world is reflected in the agent’s percepts\n",
        "-still may have uncertainty\n",
        "3. goal-based agents\n",
        "-goal = desirable situations\n",
        "-find action sequences that reach goal states through search and planning (consideration of the future)\n",
        "-less efficient but more flexible (decisions are explicitly represented so can be modified easily)\n",
        "4. utility-based agents\n",
        "-utility function: internalization of performance measure (how desirable each way of getting to destination is)\n",
        "-expected utility (due to partial observability and nondeterminism in the real world): utility based on probabilities/utilities of each outcome\n",
        "-An agent that possesses an explicit utility function can make rational de- cisions with a general-purpose algorithm that does not depend on the specific utility function being maximized.\n",
        "5. model-free agent: learn best action in a situation without learning how that action changes the environment specifically\n",
        "-learning agents: what any type of agent can be built as\n",
        "  -advantage: allows the agent to operate in initially unknown environments and to become more competent than its initial knowledge alone might allow\n",
        "  -four conceptual components:\n",
        "  a. learning element: making improvements\n",
        "  b. performance element: selecting external actions \n",
        "  c. critic: informs learning element how well agent is doing wrt fixed performance standard\n",
        "  d. problem generator: suggest actions that will lead to new and informative experiences\n",
        "  -human choices can provide information about human preferences\n",
        "-components of agent programs work along axis of increasing complexity, expressive power (often precision as well)\n",
        "-types of representations:\n",
        "  -atomic: each state of the world is indivisible (no internal structure)\n",
        "    -eg. markov \n",
        "  -factored: each state is split up into a fixed set of variables/attributes (each having a value)\n",
        "    -states may share attributes (easy to see how to move from one to another\n",
        "    -eg. constraint satisfaction\n",
        "  -structured: explicit declaration of objects and their relationships\n",
        "    -eg. NLP\n",
        "-alternate axis: mapping of concepts to memory locations in physical memory\n",
        "  -one-to-one mapping: localist representation\n",
        "  -one-to-many, many-to-one mapping: distributed representation (more robust against memory loss, noise)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"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"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "405"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "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": "bec1c5f7-c5c2-4450-b3c9-721c05d0820d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n-intelligence = fidelity to human performance, rationality (doing the right thing?), property of internal thought processes and reasoning, behavior?\n-turing test: thought experiment -- computer passes if human cannot tell whether response is from human or computer\n  -needded capabilities: NLP, knowledge representation, automated reasoning, machine learning\n  -total turing test: requires interaction wiht objects and people in the physical world (requires computer vision, robotics)\n-human thinking: cognitive modelling\n  -can be examined through introspection, psychological experiments, brain imaging\n-rational thinking: laws of thought -- \n  -right thinking = irrefutable reasoning processes (correct premises must yield correct conclusions)\n  -utilizes logic and probability\n-rational agent: one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n  -this has dominated the other approaches to AI because:\n    -more general (more possible mechanisms for achieving rationality)\n    -more amenable to scientific development\n-AI focuses on the study and construction of agents that DO THE RIGHT THING (standard model)\n  -but not the best in the long run because it assumes we wll supply a fully specified (complete and correct) objective to the machine\n  -value alignment problem: how to achieve agreement between our true preferences and the objective we put into the machine\n  -thus the ultimate aim should be beneficial machines (provably beneficial to humans)\n\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 \n-agent: anything that can be viewed as perceiving its environment through sensors, and acting upon that environment through actuators\n-percept: the content an agent's sensors are perceiving (percept sequence: complete history)\n  -an agent's choice of action must depend on percept sequence and/or built-in knwowledge\n-agent function: maps percept sequence to action (could then be tabulated)\n-agent program: concrete implementation of an agent function\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n-consequentialism: evaluate an agent's behavior by its consequences (evaluated using performance measure, desirable from the designer's view)\n-rational agent: select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knwoledge the agent has\n-rationality depends on: performance measure, prior knowledge, possible actions, percept sequence \n-omniscience: knowing the actual outcome of its actions and can act accordingly\n-information gathering: doing actions in order to modify future percepts (eg. through exploration)\n-rational agent should be autonomous (learn in order to compensate for partial/incorrect prior knowledge)\n\n\n## AIMA 2.3 The Nature of Environments\n \n-task environment: the problems to which rational agents are the solutions\n  -components: PEAS (performance, environment, actuators, sensors)\n  -properties: \n    -fully observable (sensors provide access to complete state of environment at each point in time) or partially observable\n    -single agent or multiagent (cooperative or competitive)\n      -key distinction between agent and merely object: whether its behavior is best described as maximizing a performance measure whose value depends on another agent's behavior\n    -deterministic (next state of environment is completely determined by current state and action executed) vs non-deterministic (similar to stochastic, but probabilities are listed without being quantified)\n      -if deterministic then no uncertainty\n    -episodic (divide agent's experience into atomic episodes -- discrete, actions in one does not depend on another) or sequential (Current decision could affect all future decisions)\n    -static or dynamic (environment can change when agent is deliberating, agent is continuously being asked what to do) or semidynamic (environment does not change, but agent's performance score does)\n    -discrete or continuous (states, time, percepts/actions)\n    -known or unknown (environment, outcomes for all actions are given)\n\n\n\n## AIMA 2.4 The Structure of Agents\n \n-agent architecture: program runs on computing device with physical sensors and actuators\n-types of agent programs:\n1. simple reflex agents\n-select actions only based on current percept, ignoring past percept history\n-eg. vacuum \n-condition action rule: condition connects to some action\n-unobservability can cause trouble\n2. model-based reflex agents\n-maintain an internal state based on percept history to keep track of the world that it cannot see (model-based agent)\n-components:\n  -transition model: knowledge of how the world works\n  -sensor model: how the state of the world is reflected in the agent’s percepts\n-still may have uncertainty\n3. goal-based agents\n-goal = desirable situations\n-find action sequences that reach goal states through search and planning (consideration of the future)\n-less efficient but more flexible (decisions are explicitly represented so can be modified easily)\n4. utility-based agents\n-utility function: internalization of performance measure (how desirable each way of getting to destination is)\n-expected utility (due to partial observability and nondeterminism in the real world): utility based on probabilities/utilities of each outcome\n-An agent that possesses an explicit utility function can make rational de- cisions with a general-purpose algorithm that does not depend on the specific utility function being maximized.\n5. model-free agent: learn best action in a situation without learning how that action changes the environment specifically\n-learning agents: what any type of agent can be built as\n  -advantage: allows the agent to operate in initially unknown environments and to become more competent than its initial knowledge alone might allow\n  -four conceptual components:\n  a. learning element: making improvements\n  b. performance element: selecting external actions \n  c. critic: informs learning element how well agent is doing wrt fixed performance standard\n  d. problem generator: suggest actions that will lead to new and informative experiences\n  -human choices can provide information about human preferences\n-components of agent programs work along axis of increasing complexity, expressive power (often precision as well)\n-types of representations:\n  -atomic: each state of the world is indivisible (no internal structure)\n    -eg. markov \n  -factored: each state is split up into a fixed set of variables/attributes (each having a value)\n    -states may share attributes (easy to see how to move from one to another\n    -eg. constraint satisfaction\n  -structured: explicit declaration of objects and their relationships\n    -eg. NLP\n-alternate axis: mapping of concepts to memory locations in physical memory\n  -one-to-one mapping: localist representation\n  -one-to-many, many-to-one mapping: distributed representation (more robust against memory loss, noise)\n\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",
            "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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "52525bc0-2eae-48ab-d49d-79320e34666c"
      },
      "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",
        "four phase problem solving process (environment known)\n",
        "1. Goal formulation: what are the objectives, goal states\n",
        "2. Problem formulation: The agent devises a description of the states and actions necessary to reach the goal; what changes at each action (transition model)?\n",
        "3. Search: Before taking any action in the real world, the agent simulates sequences of actions in its model, searching until it finds a sequence of \n",
        "actions that reaches goal (solution)\n",
        "4. Execution: The agent can now execute each action in the solution\n",
        "fully observable, deterministic, known environment: solution to any problem is a fixed sequence of actions\n",
        "partially observable or nondeterministic environment: solution would be a branching strategy that recommends different future actions depending on percepts that arrive.\n",
        "after solution: open loop(no need to monitor percepts if model is 100%) vs closed loop (keep monitoring percepts as model could be wrong)\n",
        "search problem components: state space, initial space, 1+ goal states, actions at each state, transition model, action cost function\n",
        "Path: sequence of actions (solution: path that reaches goal state from initial state; optimal: lowest path cost)\n",
        "abstraction: removing detail to get a better model (valid if same state, same action, same result state)\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"  \n",
        "grid world problem: two-dimensional rectangular array of square cells in which agents can move from cell to cell\n",
        "TSP: visit n nodes on a journey with or without min cost (optimal or non-optimal)\n",
        "touring problem: set of locations that must be visited\n",
        "\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" \n",
        "search algorithm: takes a search problem as input and returns a solution, or an indication of failure\n",
        "decision tree implementation:\n",
        "-nodes are expanded by calling the result function to see where that applicable action leads and then generating a new successor/child node\n",
        "-frontier: set of unexpanded nodes \n",
        "  -separates interior and exterior areas\n",
        "    -interior: region where every state has been expanded\n",
        "    -exterior: region where states are not expanded\n",
        "state space: not search tree\n",
        "-describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. \n",
        "-describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state\n",
        "-each node in the tree has a unique path back to the root\n",
        "state is reached: has had a node generated for it in search tree (expanded or unexpanded)\n",
        "components of nodes: state, parent, action , path cost\n",
        "frontier operations:\n",
        "- IS-EMPTY(frontier) returns true only if there are no nodes in the frontier. \n",
        "- POP(frontier) removes the top node from the frontier and returns it. \n",
        "- TOP(frontier) returns (but does not remove) the top node of the frontier. \n",
        "- ADD(node, frontier) inserts node into its proper place in the queue.\n",
        "greedy bfs:\n",
        "-choose a node with minimum value of some evaluation function\n",
        "-return it if its state is a goal state, or apply EXPAND to generate its child nodes\n",
        "-add child node to frontier if unvisited/update if it now has lower path cost\n",
        "-return any path\n",
        "even if state space is not infinite, possible to infinitely traverse a tree\n",
        "because you can go in loops with node expansion\n",
        "\n",
        "Graph search will check for redundancies by storing what nodes have already\n",
        "been reached, preventing loops etc. This is faster but takes more storage.\n",
        "- Or we can only check for cycles and get in between a tree and a graph search\n",
        "Performance measures: completeness (will it find solution or return failure if none), cost optimality (find a solution with the lowest path cost), time/space complexity\n",
        "Complexity: depth (number of actions in an optimal solution), branching factor (how many succesors need to be considered at each node)\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS: always finds a solution with a minimal number of actions, because when it is generating nodes at depth it has already generated all the nodes at depth\n",
        "-cost optimal and complete\n",
        "-time and space complexity : O(B^d)\n",
        "DFS: always expands the deepest node in the frontier first\n",
        "-could be implemented as a call to best first search (evaluation function is the negative of the depth\n",
        "-usually implemented as a tree-like search (no table of reached states).\n",
        "-returns first solution it finds (not cost-optimal)\n",
        "Backtracking search:\n",
        "-variant of dfs using less memory \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 474
        },
        "outputId": "ce136b1f-cc7f-462c-e4a2-9cec13a31205"
      },
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "search problem: states, initial state, actions, transition model, path cost, goal test\n",
        "State space: set of all reacble states from the initial state\n",
        "Path: a sequence of actions leading from one state to another\n",
        "Frontier: states available for expanding \n",
        "Solution: a path from the initial state to a goal state\n",
        "ucs vs bfs: tests if node is goal before adding to frontier\n",
        "greedy bfs: ucs with f(n), can get stuck in loops\n",
        "relaxed problem: fewer restrictions on the actions than the original (optimal solution cost for this can be an admissible heuristic for original problem)\n",
        "h2(n) >= h1(n) (both admissible): h2 dominates, more accurate and optimistic \n",
        "hmd dominates hoop\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 341
        },
        "cellView": "form",
        "outputId": "4aa6a665-fe0d-4f78-fab8-f3b1b52b1992"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n 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",
            "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 = \"\"\"Multi-agent environments. We show that pruning makes the search \n",
        "more efficient by ignoring portions of the search tree that make no difference \n",
        "to the optimal move. For nontrivial games, we will usually not have enough time \n",
        "to be sure of finding the optimal move (even with pruning); we will have to cut \n",
        "off the search at some point.\"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "simple game environment: multiagent, static (no change while agent deliberates), discrete set of percepts/actions, fully observable, strategic\n",
        "Zero-sum: one player’s loss is another’s gain\n",
        "stochastic games: not deterministic, not fully observable, lacking in perfect information\n",
        "game as search: initial state, successor function, terminal test, utility function\n",
        "Evaluation function f assigns real-number scores to `board positions’ \n",
        "-no reference to path (static features)\n",
        "alpha: MAX’s current lower bound on MAX’s outcome (can terminate if score <= alpha)\n",
        "beta: MIN’s current upper bound on MIN’s outcome (can terminate if score >= alpha)\n",
        "expectimax: compute average score (EU) under optimal play\n",
        "-chance node for eveyr outcome out of our control, plus a probabilistic distribution model\n",
        "-obtaining probabilistic distributions:\n",
        "  -objectivist: take averages of repeated experiments (new evidence changes reference class)\n",
        "  -subjectivist: degrees of belief about unobserved variables (new evidence updates beliefs)\n",
        "-as depth increases, probability of reaching a given search node shrinks\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 708
        },
        "outputId": "0cbc7b56-52d7-45d3-8457-b4df7c1768a7"
      },
      "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\nMulti-agent environments. We show that pruning makes the search \nmore efficient by ignoring portions of the search tree that make no difference \nto the optimal move. For nontrivial games, we will usually not have enough time \nto be sure of finding the optimal move (even with pruning); we will have to cut \noff the search at some point.\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "approaches to search planning (sequence of actions/path matters), identification (goal is important, all paths have same depth)\n",
        "constraint satisfaction: find solutions by general purpose search algos, problem (and constraints) represented in uniform declaritive language\n",
        "csp components: \n",
        "-finite set of variables\n",
        "  -discrete (finite/infinite domains) or continuous\n",
        "-nonempty domain of possible values per variable\n",
        "-finite set of constraints (limit values per variable)\n",
        "  -consistent assignment: no violation of constraints\n",
        "  -complete assignment: every variable is assigned a value\n",
        "  -types of constraints: unary (single variable), binary (pairs of variables), higher-order (3+ variables), preference/soft constraints (eg. better than)\n",
        "benefits of csp\n",
        "-clean specification\n",
        "-csp knows which variables violate a constraint\n",
        "-automatically prunes off branches that violate constraints\n",
        "-solution is always found at depth n for n variables\n",
        "csp as search problem: initial state, successor function, goal test, path cost\n",
        "branching factor: (n-x)^*d, x=depth, d=domain size\n",
        "tree has n!*d^n leaves\n",
        "is a tree search, since variable assignments are commutative\n",
        "backtracking search: dfs that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign\n",
        "-for csps with single-variable assignments\n",
        "-can be sped up with heuristics \n",
        "  -most constrained value: variable with fewest legal values (minimum remaining values, mrv)\n",
        "  -most constraining variable: variable with most constraints on remaining values\n",
        "  -least constraining value: value that rules out the fewest values amongst remaining variables\n",
        "  -forward checking: keep track of values of unassigned variables, terminate when any has no remaining legal values\n",
        "    -does not detect all failures (eg. constrained values having the same assignment)\n",
        "constraint propagation/inference in csps: eliminate possible values if it would violate local consistency\n",
        "arc consistency: for each x, there is some valid value in y\n",
        "-checking is O(d^2) worst case\n",
        "waltz/mackworth constraint propagation algorithm: assign all values to all nodes, repeat until no change in set of values\n",
        "AC3: only examine nodes whose neighbor(s) have lost a value in the previous iteration\n",
        "-runtime: O(n^2d^3) -- n^2 arcs, d^2 checking arcs, d times each arc can be inserted into queue\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 232
        },
        "outputId": "d0c2e760-7ad9-420f-f475-346ce96d7a1c"
      },
      "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": 3,
      "outputs": [
        {
          "output_type": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-3-e3a3471e8838>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     10\u001b[0m ]\n\u001b[1;32m     11\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n\u001b[0m\u001b[1;32m     13\u001b[0m                          \u001b[0mmodule6_sections\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m                          module6_definitions)\n",
            "\u001b[0;31mNameError\u001b[0m: name 'format_module' is not defined"
          ]
        }
      ]
    },
    {
      "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: reasoning rather than internal representation of knowledge\n",
        "-central component is knowledge base (set of sentences about the world, expressed using knowledge representation language)\n",
        "  -axiom: sentence taken as given, not derived from other sentences\n",
        "  -TELL, ASK: add to KB (could involve inference)\n",
        "  -could contain some background knowledge initially\n",
        "  -process when program is called:\n",
        "  1. TELL KB what it perceives\n",
        "  2. ASK KB what it should perform (extensive reasoning, outcomes of possible actions)\n",
        "  3. TELL KB what action was chosen, return that action for execution\n",
        "-approaches: declarative (TELL sentences one by one) vs procedural (encode desired behaviors directly as program code\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "Wumpus world\n",
        "-21% of environments are unfair (gold in/surrounded by pits)\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "logic semantics = truth of each sentence wrt each possible world (model)\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "propositional logic\n",
        "-factored representation\n",
        "-less expressive than first order logic but comes with well-developed inference technologies\n",
        "-sound/truth-preserving inference algorithm: entailed sentences only\n",
        "-complete algorithm: can derive all entailed sentences\n",
        "-grounding: connection between logical reasoning processes and real world\n",
        "-theorem proving: applying rules of inference directly to KB to prove desired sentence without consulting models\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "inference rules\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "entailment (a |= b): sentence follows logically from another sentence\n",
        "logical inference: applying entailments to derive conclusions\n",
        "logical equivalence: two statements are true in the same set of models\n",
        "resolution: inference rule that yields a complete inference algorithm when coupled with any complete search algorithm\n",
        "-unit resolution: elminate both l and m if they are complementary literals (one negates the other)\n",
        "-only applies to clauses (disjunctions of literals)\n",
        "CNF steps: a <=> b TO (a => b) and (b => a) TO (not a) or B\n",
        "-demorgan's laws: not (p or q) TO (not p) and (not q); not (p and q) TO (not p) or (not q)\n",
        "-distribute or over and: p or (q and r) TO (p or q) and (p or r)\n",
        "resolution algorithm (show KB entails A)\n",
        "-compute cnf of KB entails not A\n",
        "-Then apply the resolution rule to the resulting clauses (Resolve every pair of complementary literals to produce a new clause)\n",
        "-If that new clause isn’t already present, then add it to the set.\n",
        "-Continue the process until one of two things happens:\n",
        "1. There are no new clauses that can be added. In this case, the KB does not entail A\n",
        "2. Two clauses resolve to yield the empty clause, in which case the KB does entail A\n",
        "definite clause: disjunction of clauses, exactly one is positive\n",
        "-can be written as implication: promise is conjunction of positive literals, conclusion is positive literal\n",
        "horn clause: disjunction of clauses, at most one is positive\n",
        "forward chaining (data-driven): adding premises as it runs, then incrementally apply fc algo to derive new conclusions\n",
        "backward chaining (goal-directed): work backwards from query (if it's false, then find implications in KB whose conclusions are in query, prove one of these to be true to prove query is true)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "23cc6f2a-0fea-4bb3-bbac-dbc26f008223"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n 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": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "a49abd6a-db2c-4b45-c601-f7e4c48204c5"
      },
      "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 \n-intelligence = fidelity to human performance, rationality (doing the right thing?), property of internal thought processes and reasoning, behavior?\n-turing test: thought experiment -- computer passes if human cannot tell whether response is from human or computer\n  -needded capabilities: NLP, knowledge representation, automated reasoning, machine learning\n  -total turing test: requires interaction wiht objects and people in the physical world (requires computer vision, robotics)\n-human thinking: cognitive modelling\n  -can be examined through introspection, psychological experiments, brain imaging\n-rational thinking: laws of thought -- \n  -right thinking = irrefutable reasoning processes (correct premises must yield correct conclusions)\n  -utilizes logic and probability\n-rational agent: one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n  -this has dominated the other approaches to AI because:\n    -more general (more possible mechanisms for achieving rationality)\n    -more amenable to scientific development\n-AI focuses on the study and construction of agents that DO THE RIGHT THING (standard model)\n  -but not the best in the long run because it assumes we wll supply a fully specified (complete and correct) objective to the machine\n  -value alignment problem: how to achieve agreement between our true preferences and the objective we put into the machine\n  -thus the ultimate aim should be beneficial machines (provably beneficial to humans)\n\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 \n-agent: anything that can be viewed as perceiving its environment through sensors, and acting upon that environment through actuators\n-percept: the content an agent's sensors are perceiving (percept sequence: complete history)\n  -an agent's choice of action must depend on percept sequence and/or built-in knwowledge\n-agent function: maps percept sequence to action (could then be tabulated)\n-agent program: concrete implementation of an agent function\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n-consequentialism: evaluate an agent's behavior by its consequences (evaluated using performance measure, desirable from the designer's view)\n-rational agent: select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knwoledge the agent has\n-rationality depends on: performance measure, prior knowledge, possible actions, percept sequence \n-omniscience: knowing the actual outcome of its actions and can act accordingly\n-information gathering: doing actions in order to modify future percepts (eg. through exploration)\n-rational agent should be autonomous (learn in order to compensate for partial/incorrect prior knowledge)\n\n\n## AIMA 2.3 The Nature of Environments\n \n-task environment: the problems to which rational agents are the solutions\n  -components: PEAS (performance, environment, actuators, sensors)\n  -properties: \n    -fully observable (sensors provide access to complete state of environment at each point in time) or partially observable\n    -single agent or multiagent (cooperative or competitive)\n      -key distinction between agent and merely object: whether its behavior is best described as maximizing a performance measure whose value depends on another agent's behavior\n    -deterministic (next state of environment is completely determined by current state and action executed) vs non-deterministic (similar to stochastic, but probabilities are listed without being quantified)\n      -if deterministic then no uncertainty\n    -episodic (divide agent's experience into atomic episodes -- discrete, actions in one does not depend on another) or sequential (Current decision could affect all future decisions)\n    -static or dynamic (environment can change when agent is deliberating, agent is continuously being asked what to do) or semidynamic (environment does not change, but agent's performance score does)\n    -discrete or continuous (states, time, percepts/actions)\n    -known or unknown (environment, outcomes for all actions are given)\n\n\n\n## AIMA 2.4 The Structure of Agents\n \n-agent architecture: program runs on computing device with physical sensors and actuators\n-types of agent programs:\n1. simple reflex agents\n-select actions only based on current percept, ignoring past percept history\n-eg. vacuum \n-condition action rule: condition connects to some action\n-unobservability can cause trouble\n2. model-based reflex agents\n-maintain an internal state based on percept history to keep track of the world that it cannot see (model-based agent)\n-components:\n  -transition model: knowledge of how the world works\n  -sensor model: how the state of the world is reflected in the agent’s percepts\n-still may have uncertainty\n3. goal-based agents\n-goal = desirable situations\n-find action sequences that reach goal states through search and planning (consideration of the future)\n-less efficient but more flexible (decisions are explicitly represented so can be modified easily)\n4. utility-based agents\n-utility function: internalization of performance measure (how desirable each way of getting to destination is)\n-expected utility (due to partial observability and nondeterminism in the real world): utility based on probabilities/utilities of each outcome\n-An agent that possesses an explicit utility function can make rational de- cisions with a general-purpose algorithm that does not depend on the specific utility function being maximized.\n5. model-free agent: learn best action in a situation without learning how that action changes the environment specifically\n-learning agents: what any type of agent can be built as\n  -advantage: allows the agent to operate in initially unknown environments and to become more competent than its initial knowledge alone might allow\n  -four conceptual components:\n  a. learning element: making improvements\n  b. performance element: selecting external actions \n  c. critic: informs learning element how well agent is doing wrt fixed performance standard\n  d. problem generator: suggest actions that will lead to new and informative experiences\n  -human choices can provide information about human preferences\n-components of agent programs work along axis of increasing complexity, expressive power (often precision as well)\n-types of representations:\n  -atomic: each state of the world is indivisible (no internal structure)\n    -eg. markov \n  -factored: each state is split up into a fixed set of variables/attributes (each having a value)\n    -states may share attributes (easy to see how to move from one to another\n    -eg. constraint satisfaction\n  -structured: explicit declaration of objects and their relationships\n    -eg. NLP\n-alternate axis: mapping of concepts to memory locations in physical memory\n  -one-to-one mapping: localist representation\n  -one-to-many, many-to-one mapping: distributed representation (more robust against memory loss, noise)\n\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\nMulti-agent environments. We show that pruning makes the search \nmore efficient by ignoring portions of the search tree that make no difference \nto the optimal move. For nontrivial games, we will usually not have enough time \nto be sure of finding the optimal move (even with pruning); we will have to cut \noff the search at some point.\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": {}
        }
      ]
    }
  ]
}