{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of 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/",
          "height": 0
        },
        "outputId": "aaf98fd0-8d9b-4f46-a5da-2e11cfe309ee"
      },
      "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": 40,
      "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/",
          "height": 0
        },
        "outputId": "6c595974-cd73-4fc7-b0d9-93a79b75da02"
      },
      "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": 41,
      "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 = True"
      ],
      "execution_count": 42,
      "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 = \"\"\" AI = make machines think and act rational \\\n",
        "rationality = doing the right thing \\\n",
        "introspection—trying to catch our own thoughts as they go by \\\n",
        "psychological experiments—observing a person in action \\\n",
        "brain imaging—observing the brain in action \\\n",
        "An agent is just something that acts (Latin) \\\n",
        "A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome. \\\n",
        "AI has focused on the study Do the right thing and construction of agents that do the right thing \\\n",
        "The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem\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 = \"\"\" Good Old-Fashioned AI (GOFAI). \\\n",
        "qualification problem: difficult to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules \\\n",
        "The embodied cognition approach claims that it makes no sense to consider the brain Embodied cognition \\\n",
        "separately: cognition takes place within a body, which is embedded in an environment. We need to study the system as a whole \\\n",
        "Turing test. The test requires a program to have a conversation (via typed messages) with an interrogator for five minutes\\\n",
        "To Turing, the key point was not the exact details of the test, but instead the idea of measuring intelligence by performance on \\\n",
        "some kind of open-ended behavioral task, rather than by philosophical speculation.\\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" The Chinese room: computers generate no understanding \\\n",
        "Searle, a proponent of biological naturalism, according to which mental states \\\n",
        "are high-level emergent features that are caused by low-level physical processes in the neurons, \\\n",
        "and it is the (unspecified) properties of the neurons that matter: according to Searle’s biases, neurons have “it” and transistors do not. \\\n",
        "consciousness: awareness of the outside world, and of the self, and the subjective experience of living \\\n",
        "The technical term for the intrinsic nature of experiences is qualia. Can machine have qualia? Similar to animals, debatable\\\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 acting upon that environment through actuators. \\\n",
        "percept = the content an agent’s sensors are perceiving \\\n",
        "percept sequence = complete history of everything the agent has ever perceived \\\n",
        "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 implemented by an agent program. \\\n",
        "The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \\\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "A rational agent is one that does the right thing. \\ \n",
        "consequentialism: we evaluate an agent’s behavior by its consequences. \\\n",
        "performance measure evaluates any given sequence of environment states \\\n",
        "For each possible percept sequence, a rational agent should select an action that is expected \\\n",
        "to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. \\\n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly \\\n",
        "but omniscience is impossible in reality \\ \n",
        "Rationality maximizes expected performance, while perfection maximizes actual performance \\\n",
        "Doing actions in order to modify future percepts—sometimes called information gathering\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "task environment: performance measure, the environment, and the agent’s actuators and sensors \\\n",
        "PEAS (Performance, Environment, Actuators, Sensors) \\\n",
        "fully observable = If an agent’s sensors give it access to the Fully observable complete state of the environment at each point in time \\\n",
        "A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action \\\n",
        "unobservable: If the agent has no sensors at all \\\n",
        "chess is a competitive multiagent environment \\\n",
        "Deterministic the next state of the environment is completely determined by the current state and the action executed by the agents \\\n",
        "episodic task environment, the agent’s experience is divided into atomic episodes \\\n",
        "In each episode the agent receives a percept and then performs a single action. next episode does not depend on the actions taken in previous episodes \\\n",
        "known environment can be partially observable (solitaire). Unknown environment can be fully observable \\\n",
        "episodic vs sequential, static vs dynamic, discrete vs continuous, known vs unknown\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" simple reflex agent: select actions on the basis of current percept, ignoring the rest of the percept history \\\n",
        "Simple reflex agents respond directly to percepts, whereas model-based reflex agents \\\n",
        "maintain internal state to track aspects of the world that are not evident in the current percept \\\n",
        "Goal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness. \\\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",
        "\n"
      ],
      "execution_count": 43,
      "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": 1167
        },
        "cellView": "form",
        "outputId": "fd0f63aa-bfab-4555-f78c-32f72fdeef09"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n AI = make machines think and act rational rationality = doing the right thing introspection—trying to catch our own thoughts as they go by psychological experiments—observing a person in action brain imaging—observing the brain in action An agent is just something that acts (Latin) A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome. AI has focused on the study Do the right thing and construction of agents that do the right thing The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Good Old-Fashioned AI (GOFAI). qualification problem: difficult to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules The embodied cognition approach claims that it makes no sense to consider the brain Embodied cognition separately: cognition takes place within a body, which is embedded in an environment. We need to study the system as a whole Turing test. The test requires a program to have a conversation (via typed messages) with an interrogator for five minutesTo Turing, the key point was not the exact details of the test, but instead the idea of measuring intelligence by performance on some kind of open-ended behavioral task, rather than by philosophical speculation.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n The Chinese room: computers generate no understanding Searle, a proponent of biological naturalism, according to which mental states are high-level emergent features that are caused by low-level physical processes in the neurons, and it is the (unspecified) properties of the neurons that matter: according to Searle’s biases, neurons have “it” and transistors do not. consciousness: awareness of the outside world, and of the self, and the subjective experience of living The technical term for the intrinsic nature of experiences is qualia. Can machine have qualia? Similar to animals, debatable\n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. percept = the content an agent’s sensors are perceiving percept sequence = complete history of everything the agent has ever perceived agent’s behavior is described by the agent function that maps any given percept sequence to an action. Internally, the agent function for an artificial agent will be implemented by an agent program. The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nA rational agent is one that does the right thing. \\ \nconsequentialism: we evaluate an agent’s behavior by its consequences. performance measure evaluates any given sequence of environment states For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. An omniscient agent knows the actual outcome of its actions and can act accordingly but omniscience is impossible in reality \\ \nRationality maximizes expected performance, while perfection maximizes actual performance Doing actions in order to modify future percepts—sometimes called information gathering\n\n\n## AIMA 2.3 The Nature of Environments\n \ntask environment: performance measure, the environment, and the agent’s actuators and sensors PEAS (Performance, Environment, Actuators, Sensors) fully observable = If an agent’s sensors give it access to the Fully observable complete state of the environment at each point in time A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action unobservable: If the agent has no sensors at all chess is a competitive multiagent environment Deterministic the next state of the environment is completely determined by the current state and the action executed by the agents episodic task environment, the agent’s experience is divided into atomic episodes In each episode the agent receives a percept and then performs a single action. next episode does not depend on the actions taken in previous episodes known environment can be partially observable (solitaire). Unknown environment can be fully observable episodic vs sequential, static vs dynamic, discrete vs continuous, known vs unknown\n\n\n## AIMA 2.4 The Structure of Agents\n simple reflex agent: select actions on the basis of current percept, ignoring the rest of the percept history Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept Goal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.  \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": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "c50957a2-b811-4d49-b50c-e610e91a3171"
      },
      "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": 46,
      "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 = \"\"\" search problem = state space + initial state + goal states + actions + transition model + action cost function \\\n",
        "abstraction. = remove detail from a presentation\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problems: grid world (vacuum world, sokoban puzzle) \\\n",
        "real world problems: route-finding problem (robot navigation), touring problems (traveling salesperson problem) \\\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" best-first search = choose node with minimum value of some evaluation function \\\n",
        "A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search \\\n",
        "FIFO queue: used in bfs. LIFO queue in DFS \\\n",
        "A cycle is a special case of a redundant path \\\n",
        "We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check \\\n",
        "best-first search is graph search \\\n",
        "evaluate an algorithm's performance in four ways: completeness, cost optimality, time complexity and space complexity \\\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" Properties of BFS. Complete yes (if b is finite). Optimal yes if cost = 1 per step (not optimal in general) \\\n",
        "time complexity = O(b^d). space complexity = O(b^d) keeps every node in memory \\\n",
        "Properties of DFS. Complete no unless m is bounded, optimal no \\\n",
        "time complexity = O(b^m), bad if m >>d, space complexity = O(b*m)\n",
        "use dfs if space is restricted, search can be fine-tuned quickly, There are many possible solutions with long paths and wrong paths are usually terminated quickly \\\n",
        "use bfs if possible infinite paths, some solutions have short paths or can quickly discard unlikely paths \\\n",
        "depth-limited search: dfs but with depth limit l (no infinite path problem). if l = d then optimal. if l < d incomplete, l > d not optimal \\\n",
        "time complexity O(b^l), space complexity O(bl) \\\n",
        "iterative deepening search: general strate to find best depth limit l \\\n",
        "idea: use depth-limited search as subroutine with increasing l \\\n",
        "complete and optimal: goal is always found at depth d (depth of shallowest goal-node) \\\n",
        "id search properties: complete yes, optimal yes if step cost = 1 \\\n",
        "time complexity = O(b^d) (as efficient as bfs). space = O(bd) \\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" A problem solving agent must plan ahead. The computational process that it undertakes is called search \\\n",
        "It will consider a sequence of actions that form a path to a goal state. Such a sequence is called a solution \\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 661
        },
        "outputId": "a012add4-7fd3-4f29-aad8-9da3a286c8e4"
      },
      "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": 48,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n search problem = state space + initial state + goal states + actions + transition model + action cost function abstraction. = remove detail from a presentation\n \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems: grid world (vacuum world, sokoban puzzle) real world problems: route-finding problem (robot navigation), touring problems (traveling salesperson problem)  \n\n## AIMA Chapter 3.3 Search Algorithms\n best-first search = choose node with minimum value of some evaluation function A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search FIFO queue: used in bfs. LIFO queue in DFS A cycle is a special case of a redundant path We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check best-first search is graph search evaluate an algorithm's performance in four ways: completeness, cost optimality, time complexity and space complexity  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Properties of BFS. Complete yes (if b is finite). Optimal yes if cost = 1 per step (not optimal in general) time complexity = O(b^d). space complexity = O(b^d) keeps every node in memory Properties of DFS. Complete no unless m is bounded, optimal no time complexity = O(b^m), bad if m >>d, space complexity = O(b*m)\nuse dfs if space is restricted, search can be fine-tuned quickly, There are many possible solutions with long paths and wrong paths are usually terminated quickly use bfs if possible infinite paths, some solutions have short paths or can quickly discard unlikely paths depth-limited search: dfs but with depth limit l (no infinite path problem). if l = d then optimal. if l < d incomplete, l > d not optimal time complexity O(b^l), space complexity O(bl) iterative deepening search: general strate to find best depth limit l idea: use depth-limited search as subroutine with increasing l complete and optimal: goal is always found at depth d (depth of shallowest goal-node) id search properties: complete yes, optimal yes if step cost = 1 time complexity = O(b^d) (as efficient as bfs). space = O(bd) \n\n## Module 3 Lecture Notes\n A problem solving agent must plan ahead. The computational process that it undertakes is called search It will consider a sequence of actions that form a path to a goal state. Such a sequence is called a solution \n \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",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state \\\n",
        "g(N) = path cost function\\\n",
        "uniform cost search = favor lower cost paths \\\n",
        "greedy best-first search = form of best-first search that expand node with lowest h(n) \\ \n",
        "route-finding problem use straight-line distance heuristic \\\n",
        "A* search: a best-first search that uses evaluation function f(n) = g(n) + h(n) \\ \n",
        "admissible heuristic is one that never overestimates the cost to reach a goal \\\n",
        "A* expand the frontier node of lowest f-cost. \\\n",
        "With uniform-cost search, we also have contours, but of g-cost, not g+h \\\n",
        "contour spread out equally in all directions \\\n",
        "A* with good heuristic the g+h bands stretch toward a goal state and become narrowly focused around an optimal path \\\n",
        "as extend a path, the g costs are monotonic: the path cost always increases as go along a path, b/c action costs are always positive \\\n",
        "A*  with a consistent heuristic is optimally efficient in the sense that any algorithm \\\n",
        "that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A* \\\n",
        "A*  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. \\\n",
        "Weighted A* has bounded suboptimal search \\\n",
        "Memory-bounded search: e.g. beam search limits the size of the frontier \\\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" effective branching factor b*.  \\\n",
        "N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d with d is the solution depth, N number of nodes \\\n",
        "h2 dominates h1 for a more efficient\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Greedy best-first search: f(n) = h(n). Optimal no, complete no \\\n",
        "A* search is optimal. Manhattan distance is admissible\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"satisficing\" : \"accept suboptimal solutions (good enough) for less time and space\",\n",
        "'weighted A* search': 'weight heuristic value more heavily f (n) = g(n)+W  h(n), for someW > 1',\n",
        "'bounded suboptimal search' : 'look for a solution that is guaranteed to be within a constant factor W of the optimal cost',\n",
        "'bounded-cost search' : 'look for a solution whose cost is less than some constant C',\n",
        "'unbounded-cost search' : 'accept solution of any cost as long as find it quickly',\n",
        "'speedy search' : 'example of unbounded-cost search, uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions',\n",
        "'Iterative-deepening A*  search (IDA*)': 'is to A* what iterative-deepening search is to depth-first',\n",
        "'Recursive best-first search (RBFS)' : 'mimic the operation of standard best-first search, but only use linear space',\n",
        "'relaxed problem' : 'problem with fewer restrictions on the actions'\n",
        "}\n",
        "\n"
      ],
      "execution_count": 49,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 674
        },
        "cellView": "form",
        "outputId": "b3e3cf38-b3c8-433c-c82c-a254fa35839b"
      },
      "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": 50,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'speedy search' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nh(n) = estimated cost of the cheapest path from the state at node n to a goal state g(N) = path cost functionuniform cost search = favor lower cost paths greedy best-first search = form of best-first search that expand node with lowest h(n) \\ \nroute-finding problem use straight-line distance heuristic A* search: a best-first search that uses evaluation function f(n) = g(n) + h(n) \\ \nadmissible heuristic is one that never overestimates the cost to reach a goal A* expand the frontier node of lowest f-cost. With uniform-cost search, we also have contours, but of g-cost, not g+h contour spread out equally in all directions A* with good heuristic the g+h bands stretch toward a goal state and become narrowly focused around an optimal path as extend a path, the g costs are monotonic: the path cost always increases as go along a path, b/c action costs are always positive A*  with a consistent heuristic is optimally efficient in the sense that any algorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A* A*  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. Weighted A* has bounded suboptimal search Memory-bounded search: e.g. beam search limits the size of the frontier  \n\n## AIMA Chapter 3.6 Heuristic Functions\n effective branching factor b*.  N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d with d is the solution depth, N number of nodes h2 dominates h1 for a more efficient\n\n\n## Module 4 Lecture Notes\n \nGreedy best-first search: f(n) = h(n). Optimal no, complete no A* search is optimal. Manhattan distance is admissible\n\n\n\n## Module 4 Definitions\n* **Satisficing** - accept suboptimal solutions (good enough) for less time and space\n* **Weighted a* search** - weight heuristic value more heavily f (n) = g(n)+W  h(n), for someW > 1\n* **Bounded suboptimal search** - look for a solution that is guaranteed to be within a constant factor W of the optimal cost\n* **Bounded-cost search** - look for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accept solution of any cost as long as find it quickly\n* **Speedy search** - example of unbounded-cost search, uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions\n* **Iterative-deepening a*  search (ida*)** - is to A* what iterative-deepening search is to depth-first\n* **Recursive best-first search (rbfs)** - mimic the operation of standard best-first search, but only use linear space\n* **Relaxed problem** - problem with fewer restrictions on the actions\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 = \"\"\" deterministic, two-player, turn-taking, perfect information, zero-sum games \\\n",
        "A game needs: so initial state, to-move (the player whose turn it is to move in state s)\\\n",
        "actions: set of legal moves, result (transition model), terminal test, utility function \\\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" minimax search, assuming both players play optimally \\\n",
        "alpha beta pruning effectiveness dependent on the order in which the states are examined \\\n",
        "repeated states can occur b/c of transpositions different permutations of the move sequence that end up in the same position \\\n",
        "type A strat consider all possible moves to a certain depth, use heuristic eval function to estimate the utility of states that that depth \\\n",
        "type A explore wide but shallow portion \\\n",
        "type B strat ignores moves that look bad and follow promising lines as far as possible \\\n",
        "type b explore deep but narrow portion \\\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" weighted linear function in chess: each position might worth some material value\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" stochastic games: include random elements, expected minimax value\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \\\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" 6 constrains that require any reasonable preference relation to obey:\n",
        "orderability: must prefer one or else rate equally. Cannot avoid deciding \\\n",
        "transitivity: prefer A to B, prefer B to C -> prefer A to C\n",
        "continuity: if B is between A and C in preference, there is some prob p that agent will be indifferent between getting B \\\n",
        "for sure, and yield A with prob p and C with prob 1-p \\\n",
        "substitutability: A ~ B => [p;A; 1 - p;C] ~ [p;B;1 - p;C] \\\n",
        "monotonicity: if 2 lotteries have same 2 possible outcomes A and B, if agent prefers A to B then agents must prefer lottery that has a higher prob for A \\\n",
        "decomposability: [p;A; 1- p; [q;B; 1-q;C]] ~ [p;A; (1-p)q;B; (1-p)(1-q);C] \\\n",
        "value function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states \\\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" preference elicitation = involves presenting choices to the human and using the observed preferences to pin down the underlying utility function \\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" backed-up value of each node is determined by the values of its children \\\n",
        "for max node the backed-up value is the max of the values of its children \\\n",
        "for min node the backed-up value is the min of the values of its children \\\n",
        "apha beta pruning: alpha = MAX's current lower bound on MAX's outcome \\\n",
        "beta = MIN's current upper bound on MIN's outcome \\\n",
        "when eval MAX node: if v >= beta, backed-up v b/c min will never select that max node \\\n",
        "when eval MIN node: if v <= alpha, backed-up v b/c max will never select that min node \\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"imperfect information\" : \"e.g. poker, not all info are visible to all players\",\n",
        "'zero sum' : 'what is good for one is bad for other, no win-win',\n",
        "'beam search': 'a type of forward pruning, on each ply consider only a beam of n best moves',\n",
        "'policy' : 'mapping from every possible state to the best move in that state',\n",
        "'expected utility' : 'average utility value of the outcomes, weighted by the probability of the outcome',\n",
        "'normative theory': 'describe how a rational agent should act',\n",
        "'descriptive theory' : 'describes how actual agents really do act',\n",
        "'certainty effect': 'people are strongly attracted to gains that are certain',\n",
        "'framing effect': 'wording can have big impact on the agent choice',\n",
        "'anchoring effect': 'offer something high in value to skew estimate'\n",
        "}\n",
        "\n"
      ],
      "execution_count": 51,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1014
        },
        "outputId": "f1ad6871-e2c0-4897-a99c-29a2bc06628a"
      },
      "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": 52,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games A game needs: so initial state, to-move (the player whose turn it is to move in state s)actions: set of legal moves, result (transition model), terminal test, utility function \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n minimax search, assuming both players play optimally alpha beta pruning effectiveness dependent on the order in which the states are examined repeated states can occur b/c of transpositions different permutations of the move sequence that end up in the same position type A strat consider all possible moves to a certain depth, use heuristic eval function to estimate the utility of states that that depth type A explore wide but shallow portion type B strat ignores moves that look bad and follow promising lines as far as possible type b explore deep but narrow portion \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n weighted linear function in chess: each position might worth some material value\n \n\n## AIMA Chapter 5.5 Stochastic Games\n stochastic games: include random elements, expected minimax value\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n 6 constrains that require any reasonable preference relation to obey:\norderability: must prefer one or else rate equally. Cannot avoid deciding transitivity: prefer A to B, prefer B to C -> prefer A to C\ncontinuity: if B is between A and C in preference, there is some prob p that agent will be indifferent between getting B for sure, and yield A with prob p and C with prob 1-p substitutability: A ~ B => [p;A; 1 - p;C] ~ [p;B;1 - p;C] monotonicity: if 2 lotteries have same 2 possible outcomes A and B, if agent prefers A to B then agents must prefer lottery that has a higher prob for A decomposability: [p;A; 1- p; [q;B; 1-q;C]] ~ [p;A; (1-p)q;B; (1-p)(1-q);C] value function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states  \n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation = involves presenting choices to the human and using the observed preferences to pin down the underlying utility function \n\n\n## Module 5 Lecture Notes\n backed-up value of each node is determined by the values of its children for max node the backed-up value is the max of the values of its children for min node the backed-up value is the min of the values of its children apha beta pruning: alpha = MAX's current lower bound on MAX's outcome beta = MIN's current upper bound on MIN's outcome when eval MAX node: if v >= beta, backed-up v b/c min will never select that max node when eval MIN node: if v <= alpha, backed-up v b/c max will never select that min node \n\n## Module 5 Definitions\n* **Imperfect information** - e.g. poker, not all info are visible to all players\n* **Zero sum** - what is good for one is bad for other, no win-win\n* **Beam search** - a type of forward pruning, on each ply consider only a beam of n best moves\n* **Policy** - mapping from every possible state to the best move in that state\n* **Expected utility** - average utility value of the outcomes, weighted by the probability of the outcome\n* **Normative theory** - describe how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Framing effect** - wording can have big impact on the agent choice\n* **Anchoring effect** - offer something high in value to skew estimate\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 = \"\"\" CSP consist of finite set of variables, nonempty domain of possible values for each variable \\\n",
        "and finite set of constraints. A state is defined as an assignment of values to some or all variables \\\n",
        "a consistent assignment does not violate the constraints \\\n",
        "simplest kind of CSP involves variables that have discrete, finite domain. \\\n",
        "with infinite we use implicit constraints like T1 + d1 <= T2\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" node consistency k = 1, arc consistency k = 2, path consistency k = 3 \\\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" minimum-remaining-values (MRV) heuristic: choosing the variable with the fewest legal moves \\\n",
        "least-constraining-value heuristic prefers the value that rules out the fewest choices for the neighboring variables in the constraint \\\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" local search. min-conflicts heuristic: select the value that results in the minimum number of conflicts with other variables \\\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" Cutset condition: reduce constraint graph to a tree, assign values to some variables so the remaining variables form a tree \\\n",
        "tree decomposition: a transformation of the original graph into a tree where each node in the tree consists of a set of variables \\\n",
        "3 requirements: every variable in the original problem appears in at least 1 tree nodes \\\n",
        "If two variables are connected by a constraint in the original problem, they must appear together in one of tree nodes \\\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes \\\n",
        "the tree width of the graph itself is the minimum width among all its tree decompositions \\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "An assignment is complete when every variable is assigned a value. \\\n",
        "A solution to a CSP is a complete, consistent assignment. \\\n",
        "Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP. \\\n",
        "eg: map coloring, scheduling problems, floor planning, sudoku, etc. \\\n",
        "in constraint graph, nodes are variables, arcs are binary constraints. Constraint graph simplifies search \\\n",
        "CSP can be expresed as a search problem: initial state, successor function, goal test, and path cost \\\n",
        "backtracking search = depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign \\\n",
        "backtracking is the basic uninformed algo for CSPs\\\n",
        "4 type of heuristic: most constrained variable (fewest legal values), most constraining variable (most constrains on remaining variables), \\\n",
        "least constraining value, and forward checking \\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"backtracking\" : \"dfs for CSPs with single-variable assignments\",\n",
        "'commutativity' : 'the order of application of any given set of actions does not matter',\n",
        "'MAC': 'Maintaining Arc Consistency'\n",
        "\n",
        "}\n"
      ],
      "execution_count": 53,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 779
        },
        "outputId": "e507e268-c371-43e3-a2f6-170cbb85df3d"
      },
      "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": 54,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP consist of finite set of variables, nonempty domain of possible values for each variable and finite set of constraints. A state is defined as an assignment of values to some or all variables a consistent assignment does not violate the constraints simplest kind of CSP involves variables that have discrete, finite domain. with infinite we use implicit constraints like T1 + d1 <= T2\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n node consistency k = 1, arc consistency k = 2, path consistency k = 3 \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n minimum-remaining-values (MRV) heuristic: choosing the variable with the fewest legal moves least-constraining-value heuristic prefers the value that rules out the fewest choices for the neighboring variables in the constraint  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n local search. min-conflicts heuristic: select the value that results in the minimum number of conflicts with other variables \n\n## AIMA Chapter 6.5 The Structure of Problems\n Cutset condition: reduce constraint graph to a tree, assign values to some variables so the remaining variables form a tree tree decomposition: a transformation of the original graph into a tree where each node in the tree consists of a set of variables 3 requirements: every variable in the original problem appears in at least 1 tree nodes If two variables are connected by a constraint in the original problem, they must appear together in one of tree nodes If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes the tree width of the graph itself is the minimum width among all its tree decompositions \n\n## Module 6 Lecture Notes\n \nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment. Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP. eg: map coloring, scheduling problems, floor planning, sudoku, etc. in constraint graph, nodes are variables, arcs are binary constraints. Constraint graph simplifies search CSP can be expresed as a search problem: initial state, successor function, goal test, and path cost backtracking search = depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign backtracking is the basic uninformed algo for CSPs4 type of heuristic: most constrained variable (fewest legal values), most constraining variable (most constrains on remaining variables), least constraining value, and forward checking \n \n\n## Module 6 Definitions\n* **Backtracking** - dfs for CSPs with single-variable assignments\n* **Commutativity** - the order of application of any given set of actions does not matter\n* **Mac** - Maintaining Arc Consistency\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_2 = \"\"\" task environment = PEAS \\ \n",
        "Performance measure + Environment + actuators + sensors\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" logical inference = apply entailment to derive conclusions \\\n",
        "model checking = enumerates all possible models to check that alpha is true in all models \\\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines the allowable sentences. The atomic sentences \\\n",
        "consist of a single proposition symbol. Each such symbol stands for a proposition that can symbol be true or false \\\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" theorem proving = applying rules of inference directly to the sentences to construct proof of the desired sentence \"\"\"\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "# Lecture notes \n",
        "\n",
        "module7_lecture_notes = \"\"\" Propositional logic \\\n",
        "kb consists of sentences in the representation language. representation language has syntax that specifies sentences that are well-formed \\\n",
        "a logic defined the semantics of the sentences' meaning. The semantics defines the truth of each sentence wrt a possible world or model \\\n",
        "knowledge base: logical equivalence (table), inference rules (table) \\\n",
        "search for a proof: need initial state, acitons, result, goal \\\n",
        "A KB can initially contain some background information about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world \\\n",
        "models have a fixed set of truth values which are T/F. If sentence alpha is true then model m satisfies alpha. M(alpha) mean set of all models of alpha \\\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agent\" : \"use process of reasoning over an internal representation of knowledge to decide on actions, more complex\",    \n",
        "\"knowledge base (KB)\" : \"contains set of sentences that are written in knowledge representation language that has some assertion about the world\",\n",
        "\"type1, axiom\" : \"given sentence\",\n",
        "\"type2, derived sentences\" : \"new sentences derived from other setences (by a process called inference)\",\n",
        "'semantics' : 'meaning of sentences',\n",
        "\"logical reasoning\" : \"involves entailment relation between sentences\",\n",
        "\"entailment\" : \" a sentences follows logical from another sentences\",\n",
        "\"Inference Algorithm\" : \"find which sentences are entailed by KB based on search\",\n",
        "\"sound\" : \"the inference algorithm should only derive entailed sentences\",\n",
        "\"complete\" : \"can derive all sentences that are entailed\",\n",
        "'grounding' : 'the connection between logical reasoning processes and the real env which agent exists',\n",
        "'tautologies' : 'valid sentences, they are necessarily true',\n",
        "\"logical equivalence\" : \"two sentneces logically equivalent if they are true and in same set of models\",\n",
        "\"monotonicity\" : \"set of entailed setneces can only increase as information is added to KB, implies soundness\",\n",
        "\"Proof by Resolution\" : \"single inference rule that yields a complete inference algoirthm when coupled with any complete search algorithm implies Complete\",\n",
        "\"Conjunctive Normal Form (CNF)\" : \"every sentence of propositional logic is logically equivalent to a conjunction of clauses\",\n",
        "\"Clause\" : \"disjunctions of literals\",\n",
        "\"Definite Clause\" : \"disjunction (OR) where exactly one is positive\",\n",
        "\"Horn Clause\" : \"disjunction (OR) where at most one is positive\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 932
        },
        "outputId": "cf581387-753e-467a-ff68-685baaa93c7d"
      },
      "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": 56,
      "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 task environment = PEAS \\ \nPerformance measure + Environment + actuators + sensors\n\n\n## AIMA Chapter 7.3 Logic\n logical inference = apply entailment to derive conclusions model checking = enumerates all possible models to check that alpha is true in all models \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. Each such symbol stands for a proposition that can symbol be true or false \n\n\n## AIMA 7.5 Propositional Theorem Proving\n theorem proving = applying rules of inference directly to the sentences to construct proof of the desired sentence \n\n## Module 7 Lecture Notes\n Propositional logic kb consists of sentences in the representation language. representation language has syntax that specifies sentences that are well-formed a logic defined the semantics of the sentences' meaning. The semantics defines the truth of each sentence wrt a possible world or model knowledge base: logical equivalence (table), inference rules (table) search for a proof: need initial state, acitons, result, goal A KB can initially contain some background information about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world models have a fixed set of truth values which are T/F. If sentence alpha is true then model m satisfies alpha. M(alpha) mean set of all models of alpha \n\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agent** - use process of reasoning over an internal representation of knowledge to decide on actions, more complex\n* **Knowledge base (kb)** - contains set of sentences that are written in knowledge representation language that has some assertion about the world\n* **Type1, axiom** - given sentence\n* **Type2, derived sentences** - new sentences derived from other setences (by a process called inference)\n* **Semantics** - meaning of sentences\n* **Logical reasoning** - involves entailment relation between sentences\n* **Entailment** -  a sentences follows logical from another sentences\n* **Inference algorithm** - find which sentences are entailed by KB based on search\n* **Sound** - the inference algorithm should only derive entailed sentences\n* **Complete** - can derive all sentences that are entailed\n* **Grounding** - the connection between logical reasoning processes and the real env which agent exists\n* **Tautologies** - valid sentences, they are necessarily true\n* **Logical equivalence** - two sentneces logically equivalent if they are true and in same set of models\n* **Monotonicity** - set of entailed setneces can only increase as information is added to KB, implies soundness\n* **Proof by resolution** - single inference rule that yields a complete inference algoirthm when coupled with any complete search algorithm implies Complete\n* **Conjunctive normal form (cnf)** - every sentence of propositional logic is logically equivalent to a conjunction of clauses\n* **Clause** - disjunctions of literals\n* **Definite clause** - disjunction (OR) where exactly one is positive\n* **Horn clause** - disjunction (OR) where at most one is positive\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": 5296
        },
        "id": "T3cm1WV542_a",
        "outputId": "1410baae-3af4-4521-cda9-a3c451cc1a1e"
      },
      "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": 57,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n AI = make machines think and act rational rationality = doing the right thing introspection—trying to catch our own thoughts as they go by psychological experiments—observing a person in action brain imaging—observing the brain in action An agent is just something that acts (Latin) A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome. AI has focused on the study Do the right thing and construction of agents that do the right thing The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Good Old-Fashioned AI (GOFAI). qualification problem: difficult to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules The embodied cognition approach claims that it makes no sense to consider the brain Embodied cognition separately: cognition takes place within a body, which is embedded in an environment. We need to study the system as a whole Turing test. The test requires a program to have a conversation (via typed messages) with an interrogator for five minutesTo Turing, the key point was not the exact details of the test, but instead the idea of measuring intelligence by performance on some kind of open-ended behavioral task, rather than by philosophical speculation.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n The Chinese room: computers generate no understanding Searle, a proponent of biological naturalism, according to which mental states are high-level emergent features that are caused by low-level physical processes in the neurons, and it is the (unspecified) properties of the neurons that matter: according to Searle’s biases, neurons have “it” and transistors do not. consciousness: awareness of the outside world, and of the self, and the subjective experience of living The technical term for the intrinsic nature of experiences is qualia. Can machine have qualia? Similar to animals, debatable\n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. percept = the content an agent’s sensors are perceiving percept sequence = complete history of everything the agent has ever perceived agent’s behavior is described by the agent function that maps any given percept sequence to an action. Internally, the agent function for an artificial agent will be implemented by an agent program. The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nA rational agent is one that does the right thing. \\ \nconsequentialism: we evaluate an agent’s behavior by its consequences. performance measure evaluates any given sequence of environment states For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. An omniscient agent knows the actual outcome of its actions and can act accordingly but omniscience is impossible in reality \\ \nRationality maximizes expected performance, while perfection maximizes actual performance Doing actions in order to modify future percepts—sometimes called information gathering\n\n\n## AIMA 2.3 The Nature of Environments\n \ntask environment: performance measure, the environment, and the agent’s actuators and sensors PEAS (Performance, Environment, Actuators, Sensors) fully observable = If an agent’s sensors give it access to the Fully observable complete state of the environment at each point in time A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action unobservable: If the agent has no sensors at all chess is a competitive multiagent environment Deterministic the next state of the environment is completely determined by the current state and the action executed by the agents episodic task environment, the agent’s experience is divided into atomic episodes In each episode the agent receives a percept and then performs a single action. next episode does not depend on the actions taken in previous episodes known environment can be partially observable (solitaire). Unknown environment can be fully observable episodic vs sequential, static vs dynamic, discrete vs continuous, known vs unknown\n\n\n## AIMA 2.4 The Structure of Agents\n simple reflex agent: select actions on the basis of current percept, ignoring the rest of the percept history Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept Goal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.  \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 search problem = state space + initial state + goal states + actions + transition model + action cost function abstraction. = remove detail from a presentation\n \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems: grid world (vacuum world, sokoban puzzle) real world problems: route-finding problem (robot navigation), touring problems (traveling salesperson problem)  \n\n## AIMA Chapter 3.3 Search Algorithms\n best-first search = choose node with minimum value of some evaluation function A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search FIFO queue: used in bfs. LIFO queue in DFS A cycle is a special case of a redundant path We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check best-first search is graph search evaluate an algorithm's performance in four ways: completeness, cost optimality, time complexity and space complexity  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Properties of BFS. Complete yes (if b is finite). Optimal yes if cost = 1 per step (not optimal in general) time complexity = O(b^d). space complexity = O(b^d) keeps every node in memory Properties of DFS. Complete no unless m is bounded, optimal no time complexity = O(b^m), bad if m >>d, space complexity = O(b*m)\nuse dfs if space is restricted, search can be fine-tuned quickly, There are many possible solutions with long paths and wrong paths are usually terminated quickly use bfs if possible infinite paths, some solutions have short paths or can quickly discard unlikely paths depth-limited search: dfs but with depth limit l (no infinite path problem). if l = d then optimal. if l < d incomplete, l > d not optimal time complexity O(b^l), space complexity O(bl) iterative deepening search: general strate to find best depth limit l idea: use depth-limited search as subroutine with increasing l complete and optimal: goal is always found at depth d (depth of shallowest goal-node) id search properties: complete yes, optimal yes if step cost = 1 time complexity = O(b^d) (as efficient as bfs). space = O(bd) \n\n## Module 3 Lecture Notes\n A problem solving agent must plan ahead. The computational process that it undertakes is called search It will consider a sequence of actions that form a path to a goal state. Such a sequence is called a solution \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n## WARNING: Your definition of 'speedy search' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nh(n) = estimated cost of the cheapest path from the state at node n to a goal state g(N) = path cost functionuniform cost search = favor lower cost paths greedy best-first search = form of best-first search that expand node with lowest h(n) \\ \nroute-finding problem use straight-line distance heuristic A* search: a best-first search that uses evaluation function f(n) = g(n) + h(n) \\ \nadmissible heuristic is one that never overestimates the cost to reach a goal A* expand the frontier node of lowest f-cost. With uniform-cost search, we also have contours, but of g-cost, not g+h contour spread out equally in all directions A* with good heuristic the g+h bands stretch toward a goal state and become narrowly focused around an optimal path as extend a path, the g costs are monotonic: the path cost always increases as go along a path, b/c action costs are always positive A*  with a consistent heuristic is optimally efficient in the sense that any algorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A* A*  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. Weighted A* has bounded suboptimal search Memory-bounded search: e.g. beam search limits the size of the frontier  \n\n## AIMA Chapter 3.6 Heuristic Functions\n effective branching factor b*.  N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d with d is the solution depth, N number of nodes h2 dominates h1 for a more efficient\n\n\n## Module 4 Lecture Notes\n \nGreedy best-first search: f(n) = h(n). Optimal no, complete no A* search is optimal. Manhattan distance is admissible\n\n\n\n## Module 4 Definitions\n* **Satisficing** - accept suboptimal solutions (good enough) for less time and space\n* **Weighted a* search** - weight heuristic value more heavily f (n) = g(n)+W  h(n), for someW > 1\n* **Bounded suboptimal search** - look for a solution that is guaranteed to be within a constant factor W of the optimal cost\n* **Bounded-cost search** - look for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accept solution of any cost as long as find it quickly\n* **Speedy search** - example of unbounded-cost search, uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions\n* **Iterative-deepening a*  search (ida*)** - is to A* what iterative-deepening search is to depth-first\n* **Recursive best-first search (rbfs)** - mimic the operation of standard best-first search, but only use linear space\n* **Relaxed problem** - problem with fewer restrictions on the actions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games A game needs: so initial state, to-move (the player whose turn it is to move in state s)actions: set of legal moves, result (transition model), terminal test, utility function \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n minimax search, assuming both players play optimally alpha beta pruning effectiveness dependent on the order in which the states are examined repeated states can occur b/c of transpositions different permutations of the move sequence that end up in the same position type A strat consider all possible moves to a certain depth, use heuristic eval function to estimate the utility of states that that depth type A explore wide but shallow portion type B strat ignores moves that look bad and follow promising lines as far as possible type b explore deep but narrow portion \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n weighted linear function in chess: each position might worth some material value\n \n\n## AIMA Chapter 5.5 Stochastic Games\n stochastic games: include random elements, expected minimax value\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n 6 constrains that require any reasonable preference relation to obey:\norderability: must prefer one or else rate equally. Cannot avoid deciding transitivity: prefer A to B, prefer B to C -> prefer A to C\ncontinuity: if B is between A and C in preference, there is some prob p that agent will be indifferent between getting B for sure, and yield A with prob p and C with prob 1-p substitutability: A ~ B => [p;A; 1 - p;C] ~ [p;B;1 - p;C] monotonicity: if 2 lotteries have same 2 possible outcomes A and B, if agent prefers A to B then agents must prefer lottery that has a higher prob for A decomposability: [p;A; 1- p; [q;B; 1-q;C]] ~ [p;A; (1-p)q;B; (1-p)(1-q);C] value function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states  \n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation = involves presenting choices to the human and using the observed preferences to pin down the underlying utility function \n\n\n## Module 5 Lecture Notes\n backed-up value of each node is determined by the values of its children for max node the backed-up value is the max of the values of its children for min node the backed-up value is the min of the values of its children apha beta pruning: alpha = MAX's current lower bound on MAX's outcome beta = MIN's current upper bound on MIN's outcome when eval MAX node: if v >= beta, backed-up v b/c min will never select that max node when eval MIN node: if v <= alpha, backed-up v b/c max will never select that min node \n\n## Module 5 Definitions\n* **Imperfect information** - e.g. poker, not all info are visible to all players\n* **Zero sum** - what is good for one is bad for other, no win-win\n* **Beam search** - a type of forward pruning, on each ply consider only a beam of n best moves\n* **Policy** - mapping from every possible state to the best move in that state\n* **Expected utility** - average utility value of the outcomes, weighted by the probability of the outcome\n* **Normative theory** - describe how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Framing effect** - wording can have big impact on the agent choice\n* **Anchoring effect** - offer something high in value to skew estimate\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP consist of finite set of variables, nonempty domain of possible values for each variable and finite set of constraints. A state is defined as an assignment of values to some or all variables a consistent assignment does not violate the constraints simplest kind of CSP involves variables that have discrete, finite domain. with infinite we use implicit constraints like T1 + d1 <= T2\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n node consistency k = 1, arc consistency k = 2, path consistency k = 3 \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n minimum-remaining-values (MRV) heuristic: choosing the variable with the fewest legal moves least-constraining-value heuristic prefers the value that rules out the fewest choices for the neighboring variables in the constraint  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n local search. min-conflicts heuristic: select the value that results in the minimum number of conflicts with other variables \n\n## AIMA Chapter 6.5 The Structure of Problems\n Cutset condition: reduce constraint graph to a tree, assign values to some variables so the remaining variables form a tree tree decomposition: a transformation of the original graph into a tree where each node in the tree consists of a set of variables 3 requirements: every variable in the original problem appears in at least 1 tree nodes If two variables are connected by a constraint in the original problem, they must appear together in one of tree nodes If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes the tree width of the graph itself is the minimum width among all its tree decompositions \n\n## Module 6 Lecture Notes\n \nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment. Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP. eg: map coloring, scheduling problems, floor planning, sudoku, etc. in constraint graph, nodes are variables, arcs are binary constraints. Constraint graph simplifies search CSP can be expresed as a search problem: initial state, successor function, goal test, and path cost backtracking search = depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign backtracking is the basic uninformed algo for CSPs4 type of heuristic: most constrained variable (fewest legal values), most constraining variable (most constrains on remaining variables), least constraining value, and forward checking \n \n\n## Module 6 Definitions\n* **Backtracking** - dfs for CSPs with single-variable assignments\n* **Commutativity** - the order of application of any given set of actions does not matter\n* **Mac** - Maintaining Arc Consistency\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 task environment = PEAS \\ \nPerformance measure + Environment + actuators + sensors\n\n\n## AIMA Chapter 7.3 Logic\n logical inference = apply entailment to derive conclusions model checking = enumerates all possible models to check that alpha is true in all models \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. Each such symbol stands for a proposition that can symbol be true or false \n\n\n## AIMA 7.5 Propositional Theorem Proving\n theorem proving = applying rules of inference directly to the sentences to construct proof of the desired sentence \n\n## Module 7 Lecture Notes\n Propositional logic kb consists of sentences in the representation language. representation language has syntax that specifies sentences that are well-formed a logic defined the semantics of the sentences' meaning. The semantics defines the truth of each sentence wrt a possible world or model knowledge base: logical equivalence (table), inference rules (table) search for a proof: need initial state, acitons, result, goal A KB can initially contain some background information about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world models have a fixed set of truth values which are T/F. If sentence alpha is true then model m satisfies alpha. M(alpha) mean set of all models of alpha \n\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agent** - use process of reasoning over an internal representation of knowledge to decide on actions, more complex\n* **Knowledge base (kb)** - contains set of sentences that are written in knowledge representation language that has some assertion about the world\n* **Type1, axiom** - given sentence\n* **Type2, derived sentences** - new sentences derived from other setences (by a process called inference)\n* **Semantics** - meaning of sentences\n* **Logical reasoning** - involves entailment relation between sentences\n* **Entailment** -  a sentences follows logical from another sentences\n* **Inference algorithm** - find which sentences are entailed by KB based on search\n* **Sound** - the inference algorithm should only derive entailed sentences\n* **Complete** - can derive all sentences that are entailed\n* **Grounding** - the connection between logical reasoning processes and the real env which agent exists\n* **Tautologies** - valid sentences, they are necessarily true\n* **Logical equivalence** - two sentneces logically equivalent if they are true and in same set of models\n* **Monotonicity** - set of entailed setneces can only increase as information is added to KB, implies soundness\n* **Proof by resolution** - single inference rule that yields a complete inference algoirthm when coupled with any complete search algorithm implies Complete\n* **Conjunctive normal form (cnf)** - every sentence of propositional logic is logically equivalent to a conjunction of clauses\n* **Clause** - disjunctions of literals\n* **Definite clause** - disjunction (OR) where exactly one is positive\n* **Horn clause** - disjunction (OR) where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}