{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "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": {
        "colab": {
          "background_save": true,
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "71277598-38e5-438c-e72c-de5c67cc7eed"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "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": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "7ccc0360-2ff9-440e-8438-40a686d0c907"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "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": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "Turing Test: designed to figure out if a machine can think, a computer passes \n",
        "this test if a human interrogator asks it questions and can't tell if the \n",
        "response came from the computer or a human.\n",
        "\n",
        "To pass the Turing test the computer needs:\n",
        "- natural language processing (communicate in human language)\n",
        "- knowledge representation (store what it knows / hears)\n",
        "- automated reasoning (answer questions, draw conclusions)\n",
        "- machine learning (adapt to new circumstances and detect patterns)\n",
        "\n",
        "Total Turing Test: requires interaction with objects and people in the real world\n",
        "- computer vision and speech recognition (perceive the world)\n",
        "- robotics (manipulate objects and move about)\n",
        "\n",
        "Agent: something that acts\n",
        "\n",
        "Computer Agents: expected to operate autonomously, perceive their environment,\n",
        "persist over a prolonged time period, adapt to change, and create and pursue goals\n",
        "\n",
        "Rational Agent: one that acts so as to achieve the best outcome, or the best\n",
        "expected outcome\n",
        "\n",
        "Standard Model: focus on the construction of agents that do the right thing\n",
        "as defined by the objective provided to the agent\n",
        "\n",
        "Value Alignment Problem: problem of achieving agreement between our true preferences\n",
        "and the objective we put into the machine\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "Argument from informality of behavior: human behavior is far too complex to be \n",
        "captured by any formal set of rules, humans use informal guidelines\n",
        "\n",
        "Embodied Cognition: don't consider the brain separately, cognition takes places \n",
        "within a body, need to study the system as a whole\"\"\"\n",
        "chapter27_2 = \"\"\"It is irrelevant to ask whether or not machines can think.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "Agent: anything that can be viewed as perceiving its environment through sensors \n",
        "and acting upon that environment through actuators\n",
        "\n",
        "In general, an agent's choice of action at any given instant can depend on its built-in\n",
        "knowledge and on the entire percept sequence so far observed.\n",
        "\n",
        "Agent function is an abstract mathematical description, agent program is a concrete\n",
        "implementation that runs on some physical system. The agent function is implemented\n",
        "by an agent program.\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "Consequentialism: we evaluate an agent's behavior by its consequences\n",
        "\n",
        "Rationality depends on:\n",
        "- performance measure that defines success\n",
        "- agent's prior knowledge of the environment\n",
        "- actions the agent can perform\n",
        "- agent's percept sequence to date\n",
        "\n",
        "Omniscient Agent: knows the actual outcome of its actions and can act accordingly, \n",
        "impossible in reality\n",
        "\n",
        "Rationality maximizes expected performance; perfection maximizes actual performance.\n",
        "\n",
        "Rational agents should be autonomous: they should learn what they can to compensate\n",
        "for partial or incorrect prior knowledge.\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "Task Environment is defined by: performance, environment, actuators, and sensors\n",
        "\n",
        "Fully Observable: the agent has access to the complete state at every point in time\n",
        "- agent does not need to maintain an internal state to keep track of the world\n",
        "\n",
        "Unobservable: agent has no sensors at all\n",
        "\n",
        "Multiagent: if an object is best described as maximizing a performance measure \n",
        "whose value depends on another agent's behavior\n",
        "- environments can be competitive or cooperative\n",
        "\n",
        "Deterministic: the next state of the environment can be completely determined by\n",
        "the current state and an action executed by the agent\n",
        "- most real situations are very complex and should be treated as nondeterministic\n",
        "\n",
        "Episodic: the agent's next episode does not depend on the actions taken in\n",
        "previous episodes\n",
        "- othwerise, sequential, the current decision could affect all future decisions\n",
        "\n",
        "Dynamic: if the environment can change while an agent is deliberating\n",
        "- otherwise environment is static\n",
        "- semidynamic if the environment doesn't change but the agent's performance score does\n",
        "\n",
        "Discrete: finite number of distinct states\n",
        "- otherwise, environment is continuous\n",
        "\n",
        "Known: outcomes for all actions are given\n",
        "- otherwise, environment is unknown\n",
        "- known environment can still be partially observable, can know the rules of a game \n",
        "but be unable to see the cards that have not been flipped\n",
        "- unknown environment can be fully observable, screen could show a video game but\n",
        "could not know what the buttons will do\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "Agent Program: takes the current percept as input from the sensors and returns an action\n",
        "to the actuators\n",
        "\n",
        "Simple Reflex Agent: selects actions based on the current percept, ignoring the \n",
        "percept history\n",
        "- escape from infinite loops is possible if the agent can randomize its actions\n",
        "\n",
        "Model-Based Reflex Agent: agent maintains some internal state depending on the\n",
        "percept history that keeps track of some of the unobserved aspects of the current state\n",
        "- transition model and sensor model keep track of the state of the world\n",
        "\n",
        "Goal-Based Agent: agent needs information on what its desirable / goal states are\n",
        "- takes actions based on what is predicts will achieve its goal\n",
        "\n",
        "Utility-Based Agent: agents makes decisions based on a utility function that acts \n",
        "as a performance measure to find most desirable way to reach goal\n",
        "\n",
        "A rational utility-based agent chooses the action that maximizes the expected \n",
        "utility of the action outcomes, this is the utility the agent expects to derive, \n",
        "on average, given the probabilities and utilities of each outcome.\n",
        "\n",
        "Model-Free Agent: can learn what action is best in a situation without learning\n",
        "how it changes the environment\n",
        "\n",
        "Learning agent has four components:\n",
        "- learning elements (responsible for making improvements)\n",
        "- performance element (responsible for selecting external actions)\n",
        "- critic (provides feedback on how the performance element could do better)\n",
        "- problem generator (suggests actions that lead to new and informative experiences)\n",
        "\n",
        "Atomic Representation: each state of the world has no internal structure\n",
        "\n",
        "Factored Representation: splits each state into a fixed set of variables or attributes,\n",
        "each of which can have a value\n",
        "\n",
        "Structured Representation: explicitly describes objects and their relationships\n",
        "\n",
        "A more expressive representation can capture at least and more of what a less expressive\n",
        "representation can capture.\n",
        "\n",
        "Localist Representation: a one-to-one mapping between concepts and memory locations\n",
        "\n",
        "Distributed Representation: spread over many memory locations and each memory \n",
        "location is part of the representation of multiple different concepts\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "Strong AI vs. Weak AI: actually thinking vs. simulating thinking\"\"\"\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\" : \"the content an agent's senros are perceiving\",\n",
        "\"percept sequence\" : \"complete history of everything the agent has ever perceived\",\n",
        "\"agent function\": \"maps any given percept sequence to an action, describes an agent's behavior\",\n",
        "\"rational agent\": \"selects an action expected to maximize performance measure, given percept sequence and agent's built-in knowledge\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "200a6a08-2d9f-43c6-bde4-2f9564bb8746"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nTuring Test: designed to figure out if a machine can think, a computer passes \nthis test if a human interrogator asks it questions and can't tell if the \nresponse came from the computer or a human.\n\nTo pass the Turing test the computer needs:\n- natural language processing (communicate in human language)\n- knowledge representation (store what it knows / hears)\n- automated reasoning (answer questions, draw conclusions)\n- machine learning (adapt to new circumstances and detect patterns)\n\nTotal Turing Test: requires interaction with objects and people in the real world\n- computer vision and speech recognition (perceive the world)\n- robotics (manipulate objects and move about)\n\nAgent: something that acts\n\nComputer Agents: expected to operate autonomously, perceive their environment,\npersist over a prolonged time period, adapt to change, and create and pursue goals\n\nRational Agent: one that acts so as to achieve the best outcome, or the best\nexpected outcome\n\nStandard Model: focus on the construction of agents that do the right thing\nas defined by the objective provided to the agent\n\nValue Alignment Problem: problem of achieving agreement between our true preferences\nand the objective we put into the machine\n\n## AIMA Chapter 27.1 The Limits of AI\n\nArgument from informality of behavior: human behavior is far too complex to be \ncaptured by any formal set of rules, humans use informal guidelines\n\nEmbodied Cognition: don't consider the brain separately, cognition takes places \nwithin a body, need to study the system as a whole\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nIt is irrelevant to ask whether or not machines can think.\n\n## AIMA 2.1 Agents and Environments\n\nAgent: anything that can be viewed as perceiving its environment through sensors \nand acting upon that environment through actuators\n\nIn general, an agent's choice of action at any given instant can depend on its built-in\nknowledge and on the entire percept sequence so far observed.\n\nAgent function is an abstract mathematical description, agent program is a concrete\nimplementation that runs on some physical system. The agent function is implemented\nby an agent program.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nConsequentialism: we evaluate an agent's behavior by its consequences\n\nRationality depends on:\n- performance measure that defines success\n- agent's prior knowledge of the environment\n- actions the agent can perform\n- agent's percept sequence to date\n\nOmniscient Agent: knows the actual outcome of its actions and can act accordingly, \nimpossible in reality\n\nRationality maximizes expected performance; perfection maximizes actual performance.\n\nRational agents should be autonomous: they should learn what they can to compensate\nfor partial or incorrect prior knowledge.\n\n## AIMA 2.3 The Nature of Environments\n\nTask Environment is defined by: performance, environment, actuators, and sensors\n\nFully Observable: the agent has access to the complete state at every point in time\n- agent does not need to maintain an internal state to keep track of the world\n\nUnobservable: agent has no sensors at all\n\nMultiagent: if an object is best described as maximizing a performance measure \nwhose value depends on another agent's behavior\n- environments can be competitive or cooperative\n\nDeterministic: the next state of the environment can be completely determined by\nthe current state and an action executed by the agent\n- most real situations are very complex and should be treated as nondeterministic\n\nEpisodic: the agent's next episode does not depend on the actions taken in\nprevious episodes\n- othwerise, sequential, the current decision could affect all future decisions\n\nDynamic: if the environment can change while an agent is deliberating\n- otherwise environment is static\n- semidynamic if the environment doesn't change but the agent's performance score does\n\nDiscrete: finite number of distinct states\n- otherwise, environment is continuous\n\nKnown: outcomes for all actions are given\n- otherwise, environment is unknown\n- known environment can still be partially observable, can know the rules of a game \nbut be unable to see the cards that have not been flipped\n- unknown environment can be fully observable, screen could show a video game but\ncould not know what the buttons will do\n\n## AIMA 2.4 The Structure of Agents\n\nAgent Program: takes the current percept as input from the sensors and returns an action\nto the actuators\n\nSimple Reflex Agent: selects actions based on the current percept, ignoring the \npercept history\n- escape from infinite loops is possible if the agent can randomize its actions\n\nModel-Based Reflex Agent: agent maintains some internal state depending on the\npercept history that keeps track of some of the unobserved aspects of the current state\n- transition model and sensor model keep track of the state of the world\n\nGoal-Based Agent: agent needs information on what its desirable / goal states are\n- takes actions based on what is predicts will achieve its goal\n\nUtility-Based Agent: agents makes decisions based on a utility function that acts \nas a performance measure to find most desirable way to reach goal\n\nA rational utility-based agent chooses the action that maximizes the expected \nutility of the action outcomes, this is the utility the agent expects to derive, \non average, given the probabilities and utilities of each outcome.\n\nModel-Free Agent: can learn what action is best in a situation without learning\nhow it changes the environment\n\nLearning agent has four components:\n- learning elements (responsible for making improvements)\n- performance element (responsible for selecting external actions)\n- critic (provides feedback on how the performance element could do better)\n- problem generator (suggests actions that lead to new and informative experiences)\n\nAtomic Representation: each state of the world has no internal structure\n\nFactored Representation: splits each state into a fixed set of variables or attributes,\neach of which can have a value\n\nStructured Representation: explicitly describes objects and their relationships\n\nA more expressive representation can capture at least and more of what a less expressive\nrepresentation can capture.\n\nLocalist Representation: a one-to-one mapping between concepts and memory locations\n\nDistributed Representation: spread over many memory locations and each memory \nlocation is part of the representation of multiple different concepts\n\n## Module 1 Lecture Notes\n\nStrong AI vs. Weak AI: actually thinking vs. simulating thinking\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content an agent's senros are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function** - maps any given percept sequence to an action, describes an agent's behavior\n* **Rational agent** - selects an action expected to maximize performance measure, given percept sequence and agent's built-in knowledge\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Python uses dynamic typing - variables come into existence when first assigned.\n",
        "- type errors are only caught at runtime\n",
        "\n",
        "Strings: immutable\n",
        "\n",
        "Lists: mutable, can have mixed types\n",
        "\n",
        "Tuple: immutable, can have mixed types\n",
        "\n",
        "Dictionaries: unordered, work by hashing, keys must be immutable\n",
        "\n",
        "Python does not allow function overloading but does allow operator overloading.\n",
        "\n",
        "Keyword Arguments: can be used after all other arguments\n",
        "- *args comes before **kwargs\n",
        "- *args : variable number of args\n",
        "- **kwargs : variable number of keyword args\n",
        "\n",
        "Python uses dynamic scope - function sees the most current value of variables.\n",
        "\n",
        "First Class Object: can be dynamically created, destroyed, passed to a function, \n",
        "returned as a value, and have all the rights as other variables have\n",
        "- functions are first class objects\n",
        "\n",
        "Subclass: a class can extend the definition of another class\n",
        "- allows use or extensions of methods and attributes already created\n",
        "- to define a subclass, name of superclass goes in parenthesis on the first line of \n",
        "the class definition\n",
        "- multiple inheritance is supported\n",
        "- can redefine methods (similar to over-riding in Java), new definition using same\n",
        "name of method\n",
        "- only ever pass self as an argument when calling a method of an ancestor\n",
        "\n",
        "Class:\n",
        "- every method begins with the variable self\n",
        "- the __init__ method (constructor) must be done explicitly\n",
        "\n",
        "Magic Methods: built-in methods for classes\n",
        "- includes __init__, __len__, __copy__, etc.\n",
        "\n",
        "Duck Typing: call a python function on any class that implements that method, determines\n",
        "whether the method is present by 'does it swim like a duck and quack like a duck'\n",
        "\n",
        "Python iterators do not have a hasnext() method, they catch the StopIteration exception.\n",
        "- iterators use memory efficiently\n",
        "\n",
        "Generators: a type of iterator\n",
        "- functions containing the yield keyword automatically return a generator\n",
        "- whenever next() is called, method runs until it encounters a yield statement, then \n",
        "resumes where it left off\n",
        "- avoids storing the entire sequence in memory\n",
        "- crucial for infinite sequences\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"can be changed\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 919
        },
        "id": "ydOK__lwWgdp",
        "outputId": "1854ab84-0b3e-41c3-e60b-597c34098048"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython uses dynamic typing - variables come into existence when first assigned.\n- type errors are only caught at runtime\n\nStrings: immutable\n\nLists: mutable, can have mixed types\n\nTuple: immutable, can have mixed types\n\nDictionaries: unordered, work by hashing, keys must be immutable\n\nPython does not allow function overloading but does allow operator overloading.\n\nKeyword Arguments: can be used after all other arguments\n- *args comes before **kwargs\n- *args : variable number of args\n- **kwargs : variable number of keyword args\n\nPython uses dynamic scope - function sees the most current value of variables.\n\nFirst Class Object: can be dynamically created, destroyed, passed to a function, \nreturned as a value, and have all the rights as other variables have\n- functions are first class objects\n\nSubclass: a class can extend the definition of another class\n- allows use or extensions of methods and attributes already created\n- to define a subclass, name of superclass goes in parenthesis on the first line of \nthe class definition\n- multiple inheritance is supported\n- can redefine methods (similar to over-riding in Java), new definition using same\nname of method\n- only ever pass self as an argument when calling a method of an ancestor\n\nClass:\n- every method begins with the variable self\n- the __init__ method (constructor) must be done explicitly\n\nMagic Methods: built-in methods for classes\n- includes __init__, __len__, __copy__, etc.\n\nDuck Typing: call a python function on any class that implements that method, determines\nwhether the method is present by 'does it swim like a duck and quack like a duck'\n\nPython iterators do not have a hasnext() method, they catch the StopIteration exception.\n- iterators use memory efficiently\n\nGenerators: a type of iterator\n- functions containing the yield keyword automatically return a generator\n- whenever next() is called, method runs until it encounters a yield statement, then \nresumes where it left off\n- avoids storing the entire sequence in memory\n- crucial for infinite sequences\n\n## Module 2 Definitions\n* **Mutability** - can be changed\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "Problem-Solving Agents:\n",
        "- use atomic representations\n",
        "- agents that use factored or structured representations are called planning agents\n",
        "\n",
        "In informed algorithms, agents can estimate how far they are from the goal, in\n",
        "uninformed they can't.\n",
        "\n",
        "Search: before taking an action, agent simulates sequences of actions in its model\n",
        "- each sequence is called a solution\n",
        "\n",
        "Open-Loop System: once an agent has found a solution, it can ignore the percepts\n",
        "while executing the actions because the solution is guaranteed to lead to the goal\n",
        "- ignoring the percepts breaks the loop between agent and environment\n",
        "- if the model could be incorrect or the environment could be nondeterministic, \n",
        "it is safer to use a closed-loop approach that monitors the percepts\n",
        "\n",
        "Search problem includes:\n",
        "- problem\n",
        "- states (state space, initial state)\n",
        "- goal states\n",
        "- actions (available to the agent)\n",
        "- transition model (describes what each action does)\n",
        "- action cost function\n",
        "\n",
        "Solution: a path (sequence of actions) from the initial state to a goal state\n",
        "- total cost of a path is the sum of the inidivial action costs\n",
        "- optimal solution has the lowest path cost\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Touring Problems: describes a set of loctions that must be visited\n",
        "rether than a single goal destination\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Search Algorithm: takes a search problem as input and returns a solution or an \n",
        "indication of failure\n",
        "- use a search tree over the state-space graph\n",
        "- each node corresponds to a state space\n",
        "- each edge corresponds to an action\n",
        "- expand a node by considering its available actions, generate child (successor) \n",
        "nodes for each resulting state\n",
        "- frontier: nodes that have not been expanded\n",
        "- all states with nodes generated have been reached\n",
        "\n",
        "Best-First Search: choosse a node with minimum value of some evaluation \n",
        "function f(n), on each iteration expand node with minimum f(n)\n",
        "\n",
        "Queues used in search algorithms:\n",
        "- priority queue\n",
        "- fifo queue (first in first out)\n",
        "- lifo queue (last in first out)\n",
        "\n",
        "Graph Search: checks for redundant paths\n",
        "\n",
        "Tree Search: does NOT check for redundant paths\n",
        "\n",
        "Completeness: algorithm is guaranteed to find a solution when there is one and\n",
        "reports failure when there isn't\n",
        "- complete search algorithms must be systematic in the way they explore infinite\n",
        "state spaces\n",
        "\n",
        "Complexity:\n",
        "- d: depth, the number of actions in an optimal solution\n",
        "- m: maxmimum number of actions in any path\n",
        "- b: braching factor, number of successors of a node that need to be considered\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Breadth-First Search (BFS):\n",
        "- best when all actions have the same cost\n",
        "- complete on infinite spaces\n",
        "- FIFO queue is faster than a priority queue\n",
        "- early goal test: checks whether a node is a solution as soon as it is generated \n",
        "(best-first search uses the late goal test, waiting until a node is popped off \n",
        "the queue)\n",
        "- time complexity: O(b^d)\n",
        "- space complexity: O(b^d)\n",
        "- memory requirements are a bigger problem than execution time\n",
        "\n",
        "Uniform-Cost Search: aka Dijkstra's algorithm, uses BFS\n",
        "- complete\n",
        "- has optimal cost\n",
        "\n",
        "Depth-First Search (DFS):\n",
        "- not cost-optimal (returns first solution it finds)\n",
        "- efficient and complete for finite state spaces that are trees\n",
        "- for acyclic state spaces, may expand the same state multiple times but will \n",
        "eventually explore the entire space\n",
        "- not systematic for infinite state spaces\n",
        "- DFS uses less memory when a tree-like search is feasible\n",
        "- space complexitiy for finite tree-like search: O(bm), m is maximum depth of\n",
        "the tree\n",
        "\n",
        "Backtracking Search: usees DFS, only one successor generated at a time, uses\n",
        "little memory\n",
        "- space complexity: O(m)\n",
        "\n",
        "Depth-Limited Search: treat nodes at depth limit l as if they have no successors\n",
        "- time complexity: O(b^l)\n",
        "- space complexity: O(bl)\n",
        "- incomplete\n",
        "\n",
        "Iterative Deepening: repeatedly applies depth-limited search with increasing limits\n",
        "- space complexity: O(bd) if there is a solution, O(bm) for finite spaces with no solution\n",
        "- optimal for problems where all actions have the same cost\n",
        "- complete on finitie acyclic spaces, or finite spaces where we check for cycles \n",
        "up the path\n",
        "- time complexity: O(b^d) if there is a solution, O(b^m) if not\n",
        "- generally the best uninformed search method when the search state space can't fit in\n",
        "memory and the depth of the solution is unknown\n",
        "- complete\n",
        "- has optimal cost\n",
        "\n",
        "Bidirectional Search: simultaneously searches forward from the initial state and backwards \n",
        "from the goal state(s), waiting until the frontiners collide\n",
        "- complete\n",
        "- has optimal cost\n",
        "- time complexity: O(b^(d/2))\n",
        "- space complexity: O(b^(d/2))\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"State space must be abstracted for problem solving \n",
        "in the real world because it is very complex.\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "f65e115d-2cf5-41f6-80e7-72a64c6554e7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nProblem-Solving Agents:\n- use atomic representations\n- agents that use factored or structured representations are called planning agents\n\nIn informed algorithms, agents can estimate how far they are from the goal, in\nuninformed they can't.\n\nSearch: before taking an action, agent simulates sequences of actions in its model\n- each sequence is called a solution\n\nOpen-Loop System: once an agent has found a solution, it can ignore the percepts\nwhile executing the actions because the solution is guaranteed to lead to the goal\n- ignoring the percepts breaks the loop between agent and environment\n- if the model could be incorrect or the environment could be nondeterministic, \nit is safer to use a closed-loop approach that monitors the percepts\n\nSearch problem includes:\n- problem\n- states (state space, initial state)\n- goal states\n- actions (available to the agent)\n- transition model (describes what each action does)\n- action cost function\n\nSolution: a path (sequence of actions) from the initial state to a goal state\n- total cost of a path is the sum of the inidivial action costs\n- optimal solution has the lowest path cost\n\n## AIMA Chapter 3.2 Example Problems\n\nTouring Problems: describes a set of loctions that must be visited\nrether than a single goal destination\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch Algorithm: takes a search problem as input and returns a solution or an \nindication of failure\n- use a search tree over the state-space graph\n- each node corresponds to a state space\n- each edge corresponds to an action\n- expand a node by considering its available actions, generate child (successor) \nnodes for each resulting state\n- frontier: nodes that have not been expanded\n- all states with nodes generated have been reached\n\nBest-First Search: choosse a node with minimum value of some evaluation \nfunction f(n), on each iteration expand node with minimum f(n)\n\nQueues used in search algorithms:\n- priority queue\n- fifo queue (first in first out)\n- lifo queue (last in first out)\n\nGraph Search: checks for redundant paths\n\nTree Search: does NOT check for redundant paths\n\nCompleteness: algorithm is guaranteed to find a solution when there is one and\nreports failure when there isn't\n- complete search algorithms must be systematic in the way they explore infinite\nstate spaces\n\nComplexity:\n- d: depth, the number of actions in an optimal solution\n- m: maxmimum number of actions in any path\n- b: braching factor, number of successors of a node that need to be considered\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth-First Search (BFS):\n- best when all actions have the same cost\n- complete on infinite spaces\n- FIFO queue is faster than a priority queue\n- early goal test: checks whether a node is a solution as soon as it is generated \n(best-first search uses the late goal test, waiting until a node is popped off \nthe queue)\n- time complexity: O(b^d)\n- space complexity: O(b^d)\n- memory requirements are a bigger problem than execution time\n\nUniform-Cost Search: aka Dijkstra's algorithm, uses BFS\n- complete\n- has optimal cost\n\nDepth-First Search (DFS):\n- not cost-optimal (returns first solution it finds)\n- efficient and complete for finite state spaces that are trees\n- for acyclic state spaces, may expand the same state multiple times but will \neventually explore the entire space\n- not systematic for infinite state spaces\n- DFS uses less memory when a tree-like search is feasible\n- space complexitiy for finite tree-like search: O(bm), m is maximum depth of\nthe tree\n\nBacktracking Search: usees DFS, only one successor generated at a time, uses\nlittle memory\n- space complexity: O(m)\n\nDepth-Limited Search: treat nodes at depth limit l as if they have no successors\n- time complexity: O(b^l)\n- space complexity: O(bl)\n- incomplete\n\nIterative Deepening: repeatedly applies depth-limited search with increasing limits\n- space complexity: O(bd) if there is a solution, O(bm) for finite spaces with no solution\n- optimal for problems where all actions have the same cost\n- complete on finitie acyclic spaces, or finite spaces where we check for cycles \nup the path\n- time complexity: O(b^d) if there is a solution, O(b^m) if not\n- generally the best uninformed search method when the search state space can't fit in\nmemory and the depth of the solution is unknown\n- complete\n- has optimal cost\n\nBidirectional Search: simultaneously searches forward from the initial state and backwards \nfrom the goal state(s), waiting until the frontiners collide\n- complete\n- has optimal cost\n- time complexity: O(b^(d/2))\n- space complexity: O(b^(d/2))\n\n## Module 3 Lecture Notes\nState space must be abstracted for problem solving \nin the real world because it is very complex.\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": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Informed Search: uses a heuristic function, h(n), about the location of goals\n",
        "\n",
        "Greedy Best-First Search: expands first the node with the lowest h(n) value\n",
        "- evaluation function: f(n) = h(n)\n",
        "\n",
        "A* Search: search using the evaluation function f(n) = g(n) + h(n)\n",
        "- g(n): path cost from the initial state to node n\n",
        "- h(n): estimated cost of the shortest path from n to a goal state\n",
        "- f(n): estimated cost of the best path from n to a goal\n",
        "- complete\n",
        "- cost optimal if there is an admissible heuristic\n",
        "- prunes away nodes that are not necessary for finding an optimal solution\n",
        "\n",
        "Every consistent heuristic is admissible (but not vice versa).\n",
        "\n",
        "Weighted A* Search: focuses the search towards a goal, expanding fewer nodes, but\n",
        "sacrificing optimality\n",
        "\n",
        "Bounded Suboptimal Search: look for a solution guaranteed to be within a constant \n",
        "factor W of the optimal cost\n",
        "\n",
        "Bounded-Cost Search: look for a solution whose cost is less than some constant C\n",
        "\n",
        "Unbounded-Cost Search: accept a solution of any cost that's found quickly\n",
        "\n",
        "Beam Search: limits the size of the frontier, keeps only the k nodes with the \n",
        "best f-scores\n",
        "\n",
        "Iterative-Deepening A* Search: does not keep all reached states in memory\n",
        "- can visit some states multiple times\n",
        "\n",
        "Recursive Best-First Search (RBFS): a recursive depth-first search, but keeps \n",
        "track of the f-value of the best alternative path available from any ancestor of \n",
        "the current node, then unwinds back to that node if the current node exceeds \n",
        "the limit, replacing the value at each node with the backed-up value\n",
        "\n",
        "MA* : memory bounded A*\n",
        "\n",
        "SMA* : simplified MA*\n",
        "\n",
        "Bidirectional Heuristic Search: uses ff(n) = gf(n) + hf(n) for nodes going \n",
        "forwards, and fb(n) = gb(n) + hb(n) for nodes going backwards\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Effective Branching Factor: b*\n",
        "- N: total number of nodes generated by A*\n",
        "- N + 1 = 1 + b* + (b* )^2 + ... + (b* )^d\n",
        "\n",
        "Any optimal solution for the original problem is a solution in the \n",
        "relaxed problem, but the relaxed problem might have better solutions if the\n",
        "added edges provide shortcuts.\n",
        "- Relaxed Problem: has fewer restrictions on the actions\n",
        "- the cost of an optimal solution to a relaxed problem is an admissible \n",
        "heuristic for the original problem\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Dominance: if h2(n) >= h1(n) for all n (both admissible), then h2 dominates h1\n",
        "- h2 is optiministic, but more accurate than h1\n",
        "- h2 is better for search\n",
        "\n",
        "Uniform-Cost expands equally in all directions, while A* mainly expands towards \n",
        "the goal.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"estimated cost of the cheapest path from the state at node n to a goal state\", \n",
        "\"admissible heuristic\" : \"never overestimates cost to reach a goal\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "8a44b4d8-7bfc-4d91-92ed-4df77d9d3d95"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed Search: uses a heuristic function, h(n), about the location of goals\n\nGreedy Best-First Search: expands first the node with the lowest h(n) value\n- evaluation function: f(n) = h(n)\n\nA* Search: search using the evaluation function f(n) = g(n) + h(n)\n- g(n): path cost from the initial state to node n\n- h(n): estimated cost of the shortest path from n to a goal state\n- f(n): estimated cost of the best path from n to a goal\n- complete\n- cost optimal if there is an admissible heuristic\n- prunes away nodes that are not necessary for finding an optimal solution\n\nEvery consistent heuristic is admissible (but not vice versa).\n\nWeighted A* Search: focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality\n\nBounded Suboptimal Search: look for a solution guaranteed to be within a constant \nfactor W of the optimal cost\n\nBounded-Cost Search: look for a solution whose cost is less than some constant C\n\nUnbounded-Cost Search: accept a solution of any cost that's found quickly\n\nBeam Search: limits the size of the frontier, keeps only the k nodes with the \nbest f-scores\n\nIterative-Deepening A* Search: does not keep all reached states in memory\n- can visit some states multiple times\n\nRecursive Best-First Search (RBFS): a recursive depth-first search, but keeps \ntrack of the f-value of the best alternative path available from any ancestor of \nthe current node, then unwinds back to that node if the current node exceeds \nthe limit, replacing the value at each node with the backed-up value\n\nMA* : memory bounded A*\n\nSMA* : simplified MA*\n\nBidirectional Heuristic Search: uses ff(n) = gf(n) + hf(n) for nodes going \nforwards, and fb(n) = gb(n) + hb(n) for nodes going backwards\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nEffective Branching Factor: b*\n- N: total number of nodes generated by A*\n- N + 1 = 1 + b* + (b* )^2 + ... + (b* )^d\n\nAny optimal solution for the original problem is a solution in the \nrelaxed problem, but the relaxed problem might have better solutions if the\nadded edges provide shortcuts.\n- Relaxed Problem: has fewer restrictions on the actions\n- the cost of an optimal solution to a relaxed problem is an admissible \nheuristic for the original problem\n\n## Module 4 Lecture Notes\n\nDominance: if h2(n) >= h1(n) for all n (both admissible), then h2 dominates h1\n- h2 is optiministic, but more accurate than h1\n- h2 is better for search\n\nUniform-Cost expands equally in all directions, while A* mainly expands towards \nthe goal.\n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Admissible heuristic** - never overestimates cost to reach a goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Two Player Zero-Sum Game Elements:\n",
        "- initial state\n",
        "- the player whose turn it is to move\n",
        "- actions\n",
        "- transition model\n",
        "- terminal test\n",
        "- terminal states\n",
        "- utility function (defines the final numeric value to a player when the game ends)\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax Search: forms strategy assuming that both players play optimally\n",
        "- minimax value of a terminal state is its utility\n",
        "- max moves to max value of result for min\n",
        "- min moves to min value of result for max\n",
        "- backs up the minimax values through the tree during recursion\n",
        "\n",
        "Alpha-Beta Pruning:\n",
        "- alpha: the value of the best (highest-value) choice for max\n",
        "- beta: the value of the best (lowest-value) choice for min\n",
        "- prune the values below the alpha and above the beta\n",
        "- better move ordering can lead to better runtime\n",
        "\n",
        "Transposition Table: can cache the heuristic value of states to avoid transpositions,\n",
        "different permutations of moves that end up in the same position\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "Heuristic Evaluation Function: estimates the utility of a state, used to cut off \n",
        "the search\n",
        "\n",
        "Monte Carlo Tree Search (MCTS): evaluates states by playing out the game and seeing \n",
        "who won, then repeating multiple times and averaging the results\n",
        "\n",
        "Many game programs precompute tables of best moves in the opening and endgame so that\n",
        "they can look up a move rather than search.\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Expectiminimax: evaluates a chance node by taking the average utility of all its children, \n",
        "weighed by the probability of each child\n",
        "- handles games of chance\n",
        "\n",
        "In games of imperfect information, optimal play requires reasoning about the current \n",
        "and future belief states of each player. Can obtain an approximation by averaging \n",
        "the value of an action over eah possible configuration of missing information.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Probability Theory: describes what an agent should believe on the basis of evidence.\n",
        "\n",
        "Utility Theory: describes what an agent wants\n",
        "\n",
        "Decision Theory: puts probability and utility theory together to describe what \n",
        "an agent should do\n",
        "- use decision theory to build a rational agent\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Utility theory shows that an agent whose preference between lotteries are consistent \n",
        "with a set of simple axioms can be described as possessing a utility function, and \n",
        "that agent selects actions as if maximizing its expected utility.\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Decision theory is a normative theory, it describes how rational agents should act. \n",
        "Descriptive theory describes how actual agents (ex: humans) act.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"zero-sum game\" : \"what is good for one player is just as bad for the other\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "0f85371b-f5ee-404e-97e2-75fa724c7141"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nTwo Player Zero-Sum Game Elements:\n- initial state\n- the player whose turn it is to move\n- actions\n- transition model\n- terminal test\n- terminal states\n- utility function (defines the final numeric value to a player when the game ends)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax Search: forms strategy assuming that both players play optimally\n- minimax value of a terminal state is its utility\n- max moves to max value of result for min\n- min moves to min value of result for max\n- backs up the minimax values through the tree during recursion\n\nAlpha-Beta Pruning:\n- alpha: the value of the best (highest-value) choice for max\n- beta: the value of the best (lowest-value) choice for min\n- prune the values below the alpha and above the beta\n- better move ordering can lead to better runtime\n\nTransposition Table: can cache the heuristic value of states to avoid transpositions,\ndifferent permutations of moves that end up in the same position\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nHeuristic Evaluation Function: estimates the utility of a state, used to cut off \nthe search\n\nMonte Carlo Tree Search (MCTS): evaluates states by playing out the game and seeing \nwho won, then repeating multiple times and averaging the results\n\nMany game programs precompute tables of best moves in the opening and endgame so that\nthey can look up a move rather than search.\n\n## AIMA Chapter 5.5 Stochastic Games\n\nExpectiminimax: evaluates a chance node by taking the average utility of all its children, \nweighed by the probability of each child\n- handles games of chance\n\nIn games of imperfect information, optimal play requires reasoning about the current \nand future belief states of each player. Can obtain an approximation by averaging \nthe value of an action over eah possible configuration of missing information.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nProbability Theory: describes what an agent should believe on the basis of evidence.\n\nUtility Theory: describes what an agent wants\n\nDecision Theory: puts probability and utility theory together to describe what \nan agent should do\n- use decision theory to build a rational agent\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nUtility theory shows that an agent whose preference between lotteries are consistent \nwith a set of simple axioms can be described as possessing a utility function, and \nthat agent selects actions as if maximizing its expected utility.\n\n## AIMA Chapter 16.3 Utility Functions\n\nDecision theory is a normative theory, it describes how rational agents should act. \nDescriptive theory describes how actual agents (ex: humans) act.\n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum game** - what is good for one player is just as bad for the other\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "Constraint Satisfaction Problems (CSPs): represent a state with a variable/value \n",
        "pairs and represent the conditions for a solution by a set of constraints on the \n",
        "variables\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "Inference techniques that use the constraints to rule out certain value assignments:\n",
        "- node\n",
        "- arc\n",
        "- path\n",
        "- k-consistency\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Minimum-Remaining Values and Degree heuristics are domain-independent methods for \n",
        "deciding which variable to choose next in a backtracking search.\n",
        "\n",
        "Least-Constraining-Value Heuristic: helps decide which value to try first for a variable\n",
        "\n",
        "Backtracking Search: DFS for CSPs\n",
        "- chooses values for one variable at a time\n",
        "- backtracking occurs when no legal assignment can be found for a variable\n",
        "- basic uninformed algorithm for CSPs\n",
        "\n",
        "Conflict-Directed Backjumping: backtracks directly to the source of the problem\n",
        "\n",
        "Contraint Learning: records the conflicts as they are encountered during search in \n",
        "order to avoid the same conflict later in the search\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Local Search: uses the min-conflicts heuristic\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Tree-structured problems can be solved in linear time.\n",
        "\n",
        "Cutset Conditioning: can reduce a general CSP to a tree-structured one and is efficient\n",
        "if a small cutset can be found\n",
        "- requires linear memory if a small cutset can be found\n",
        "\n",
        "Tree Decomposition: transform the CSP into a tree of subproblems\n",
        "- efficient if the tree width of the constraint graph is small\n",
        "- need memory exponential in the tree width of the constraint graph\n",
        "\n",
        "Combining cutset conditioning with tree decomposition can allow a better tradeoff of \n",
        "memory versus time.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "CSP: \n",
        "- represent the coontraints that solutions must satisfy in a uniform declarative language\n",
        "- find solutions by general purpose search algorithms with no changes from problem to \n",
        "problem\n",
        "\n",
        "CSP consists of:\n",
        "- finite set of variables\n",
        "- nonempty domain of possible values for each variable\n",
        "- finite set of constraints\n",
        "\n",
        "A consistent assignment does not violate the constraints.\n",
        "- assignment is complete when every variable is assigned a value\n",
        "- solution to a CSP is a complete, consistent assignment\n",
        "\n",
        "CSPs automatically prune off all branches that violate constraints.\n",
        "\n",
        "Varities of CSPs:\n",
        "- discrete variables\n",
        "- continuous variables\n",
        "\n",
        "Varieties of Constraints:\n",
        "- unary (single variable)\n",
        "- binary (pairs of variables)\n",
        "- higher-order (3 or more variables)\n",
        "- preference (soft constraints, represented by a cost for each variable assignment)\n",
        "\n",
        "General-purpose methods & general-purpose heuristics can give huge gains in speed\n",
        "on average for backtracking search algorithms.\n",
        "- assign next the most constrained variable\n",
        "- if ties, assign next the most constraining variable\n",
        "- try the variable's values in least constraining value order\n",
        "- can detect failure early through forward checking\n",
        "\n",
        "Forward Checking: keep track of remaining legal values for unassigned variables, \n",
        "terminate search when any unassigned variables has no remaining legal values\n",
        "- constraint propagation: goes further and repeatedly enforces constraints locally\n",
        "\n",
        "CSP solvers combine search and inference.\n",
        "- search: assigning a value to a variable\n",
        "- constraint propagation (inference): eliminates possible values for a variable \n",
        "if the value would violate local consistency\n",
        "\n",
        "Local Consistency:\n",
        "- node consistency: satifies unary constraints; trivial\n",
        "- arc consistency: satisfies binary constraints (constraints between nodes)\n",
        "\n",
        "AC-3:\n",
        "- at each iteration, only need to examine nodes where at least one neighbor lost \n",
        "a value in the previous iteration\n",
        "- if Xi loses a value only because of arc inconsistencies with Yj, we don't need \n",
        "to check Yj on the next iteration\n",
        "- worst case: O(n^2d^3), with d values\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constrained optimization problems\" : \"optimize by preference\",\n",
        "\"arc consistent\" : \"iff every value v on Xi is consistent with some label on Yj\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "84577f61-d2de-4a48-97a5-70332100aaaf"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Satisfaction Problems (CSPs): represent a state with a variable/value \npairs and represent the conditions for a solution by a set of constraints on the \nvariables\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nInference techniques that use the constraints to rule out certain value assignments:\n- node\n- arc\n- path\n- k-consistency\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nMinimum-Remaining Values and Degree heuristics are domain-independent methods for \ndeciding which variable to choose next in a backtracking search.\n\nLeast-Constraining-Value Heuristic: helps decide which value to try first for a variable\n\nBacktracking Search: DFS for CSPs\n- chooses values for one variable at a time\n- backtracking occurs when no legal assignment can be found for a variable\n- basic uninformed algorithm for CSPs\n\nConflict-Directed Backjumping: backtracks directly to the source of the problem\n\nContraint Learning: records the conflicts as they are encountered during search in \norder to avoid the same conflict later in the search\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal Search: uses the min-conflicts heuristic\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nTree-structured problems can be solved in linear time.\n\nCutset Conditioning: can reduce a general CSP to a tree-structured one and is efficient\nif a small cutset can be found\n- requires linear memory if a small cutset can be found\n\nTree Decomposition: transform the CSP into a tree of subproblems\n- efficient if the tree width of the constraint graph is small\n- need memory exponential in the tree width of the constraint graph\n\nCombining cutset conditioning with tree decomposition can allow a better tradeoff of \nmemory versus time.\n\n## Module 6 Lecture Notes\n\nCSP: \n- represent the coontraints that solutions must satisfy in a uniform declarative language\n- find solutions by general purpose search algorithms with no changes from problem to \nproblem\n\nCSP consists of:\n- finite set of variables\n- nonempty domain of possible values for each variable\n- finite set of constraints\n\nA consistent assignment does not violate the constraints.\n- assignment is complete when every variable is assigned a value\n- solution to a CSP is a complete, consistent assignment\n\nCSPs automatically prune off all branches that violate constraints.\n\nVarities of CSPs:\n- discrete variables\n- continuous variables\n\nVarieties of Constraints:\n- unary (single variable)\n- binary (pairs of variables)\n- higher-order (3 or more variables)\n- preference (soft constraints, represented by a cost for each variable assignment)\n\nGeneral-purpose methods & general-purpose heuristics can give huge gains in speed\non average for backtracking search algorithms.\n- assign next the most constrained variable\n- if ties, assign next the most constraining variable\n- try the variable's values in least constraining value order\n- can detect failure early through forward checking\n\nForward Checking: keep track of remaining legal values for unassigned variables, \nterminate search when any unassigned variables has no remaining legal values\n- constraint propagation: goes further and repeatedly enforces constraints locally\n\nCSP solvers combine search and inference.\n- search: assigning a value to a variable\n- constraint propagation (inference): eliminates possible values for a variable \nif the value would violate local consistency\n\nLocal Consistency:\n- node consistency: satifies unary constraints; trivial\n- arc consistency: satisfies binary constraints (constraints between nodes)\n\nAC-3:\n- at each iteration, only need to examine nodes where at least one neighbor lost \na value in the previous iteration\n- if Xi loses a value only because of arc inconsistencies with Yj, we don't need \nto check Yj on the next iteration\n- worst case: O(n^2d^3), with d values\n\n## Module 6 Definitions\n* **Constrained optimization problems** - optimize by preference\n* **Arc consistent** - iff every value v on Xi is consistent with some label on Yj\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "Knowledge-Based Agents\n",
        "Knowledge Base: stores agent knowledge in sentences in a knowledge representation \n",
        "language\n",
        "\n",
        "Knowledge-Based Agent:\n",
        "- composed of a knowledge base and an inference mechanism\n",
        "- operates by storing sentences about the world in its knowledge base\n",
        "- uses the inference mechanism to infer new sentences\n",
        "- uses the sentences to decide what action to take\n",
        "\n",
        "Representation Language is defined by:\n",
        "- syntax (specifies structure of sentences)\n",
        "- semantics (defines the truth of each sentence in each possible world or model)\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "The Wumpus World\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "Entailment: a sentence x entails another sentence y if y is true in all worlds \n",
        "where x is true\n",
        "- equivalently, validity of the sentence x -> y\n",
        "- equivalently, unsatisfiability of the sentence x ^ !y\n",
        "\n",
        "Inference: deriving new sentences from old ones\n",
        "\n",
        "Sound Inference Algorithms: derive only sentences that are entailed\n",
        "\n",
        "Complete Algorithms: derive all sentences that are entailed\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Propositional Logic: a simple language consisting of proposition symbols and \n",
        "logical connectives\n",
        "- can handle propositions known to be true, false, or completely unknown\n",
        "\n",
        "The set of possible models, given a fixed propositional vocabulary, is finite, so\n",
        "entailment can be checked by enumerating models.\n",
        "\n",
        "Efficient model-checking inference algorithms for propositional logic include backtracking\n",
        "and local search methods and can often solve large problems quickly.\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Inference Rules: patterns of sound inference that can be used to find proofs\n",
        "\n",
        "Resolution Rule: yields a complete inference algorithm for knowledge bases that are \n",
        "expressed in conjunctive normal form\n",
        "- when coupled with any complete search algorithm\n",
        "\n",
        "Forward chaining and backward chaining are very natural reasoning algorithms for knowledge \n",
        "bases in Horn form.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Two kinds of sentences:\n",
        "- axioms: a sentence that is given\n",
        "- derived sentences: a new sentence that is derived from other sentences\n",
        "\n",
        "Inference: the process of deriving new sentences from old sentences\n",
        "\n",
        "Rules:\n",
        "- a entails b iff M(a) is a subset of M(b)\n",
        "\n",
        "Atomic Sentences: represented with a single propositional symbol\n",
        "- propositional symbols: stand for a statement that can be true or false\n",
        "\n",
        "Models: mathematical abstractions that have a fixed set of truth values which \n",
        "are {true, false} for each sentence\n",
        "- if sentence a is true in model m, then m satisfies a, or m is a model of a\n",
        "- M(a): the set of all models of a\n",
        "\n",
        "Logical Inference: process of applying entailment to derive conclusions\n",
        "\n",
        "Inference Algorithm: enumerates sentences in a KB\n",
        "\n",
        "Logically Equivalent: they are true in the same set of model; they entail each other\n",
        "\n",
        "Monotonicity: the set of entailed sentences can only increase as information is added \n",
        "to the KB\n",
        "- monotonicity implies soundness\n",
        "- adding information to the KB will not invalidate any other info that's already been \n",
        "inferred\n",
        "- it is sound, will only derive entailed sentences\n",
        "\n",
        "If two values are complementary literals (one is the negation of the other), we can \n",
        "eliminate them via unit resolution.\n",
        "\n",
        "Conjunction Normal Form (CNF): every sentence of propositional logic is logically \n",
        "equivalent to a conjunction of clauses\n",
        "- clauses are disjunctions of literals\n",
        "\n",
        "Resolution Algorithm: inference procedures based on resolution work using the principle \n",
        "of proof by contradiction\n",
        "- complete\n",
        "\n",
        "Definite Clause: disjunction of literals where exactly one is positive\n",
        "\n",
        "Horn Clause: disjunction of literals where at most one is positive\n",
        "- includes definite clauses and clauses with no positive literals\n",
        "- closed under resolution (if you apply resolution to a horn clause, you get \n",
        "back a horn clause)\n",
        "- inference with Horn clauses can be done through the forward-chaining and \n",
        "backward-chaining algorithms\n",
        "- deciding entailment with Horn clauses can be done in linear time with respect to the\n",
        "size of the KB\n",
        "\n",
        "Forward Chaining: agent can start with known data, adding premises as new percepts come in, \n",
        "then incrementally apply the forward chaining algorithm to derive new conclusions\n",
        "- a kind of data-driven reasoning\n",
        "\n",
        "Backward Chaining: works backwards from a query\n",
        "- if the query is known to be true, no work is needed\n",
        "- otherwise the algorithm finds implications in the KB whose conclusion is in the query\n",
        "- if all the premises of one of those can be proved to be true, then the query is true\n",
        "- a form of goal-directed reasoning\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning over an internal representation of knowledge to decide what to do\",\n",
        "\"entailment\" : \"a sentence follows logically from another sentence\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "56d809dc-6bfa-498e-809c-acd3b904de16"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-Based Agents\nKnowledge Base: stores agent knowledge in sentences in a knowledge representation \nlanguage\n\nKnowledge-Based Agent:\n- composed of a knowledge base and an inference mechanism\n- operates by storing sentences about the world in its knowledge base\n- uses the inference mechanism to infer new sentences\n- uses the sentences to decide what action to take\n\nRepresentation Language is defined by:\n- syntax (specifies structure of sentences)\n- semantics (defines the truth of each sentence in each possible world or model)\n\n## AIMA Chapter 7.2 The Wumpus World\n\nThe Wumpus World\n\n## AIMA Chapter 7.3 Logic\n\nEntailment: a sentence x entails another sentence y if y is true in all worlds \nwhere x is true\n- equivalently, validity of the sentence x -> y\n- equivalently, unsatisfiability of the sentence x ^ !y\n\nInference: deriving new sentences from old ones\n\nSound Inference Algorithms: derive only sentences that are entailed\n\nComplete Algorithms: derive all sentences that are entailed\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nPropositional Logic: a simple language consisting of proposition symbols and \nlogical connectives\n- can handle propositions known to be true, false, or completely unknown\n\nThe set of possible models, given a fixed propositional vocabulary, is finite, so\nentailment can be checked by enumerating models.\n\nEfficient model-checking inference algorithms for propositional logic include backtracking\nand local search methods and can often solve large problems quickly.\n\n## AIMA 7.5 Propositional Theorem Proving\n\nInference Rules: patterns of sound inference that can be used to find proofs\n\nResolution Rule: yields a complete inference algorithm for knowledge bases that are \nexpressed in conjunctive normal form\n- when coupled with any complete search algorithm\n\nForward chaining and backward chaining are very natural reasoning algorithms for knowledge \nbases in Horn form.\n\n## Module 7 Lecture Notes\n\nTwo kinds of sentences:\n- axioms: a sentence that is given\n- derived sentences: a new sentence that is derived from other sentences\n\nInference: the process of deriving new sentences from old sentences\n\nRules:\n- a entails b iff M(a) is a subset of M(b)\n\nAtomic Sentences: represented with a single propositional symbol\n- propositional symbols: stand for a statement that can be true or false\n\nModels: mathematical abstractions that have a fixed set of truth values which \nare {true, false} for each sentence\n- if sentence a is true in model m, then m satisfies a, or m is a model of a\n- M(a): the set of all models of a\n\nLogical Inference: process of applying entailment to derive conclusions\n\nInference Algorithm: enumerates sentences in a KB\n\nLogically Equivalent: they are true in the same set of model; they entail each other\n\nMonotonicity: the set of entailed sentences can only increase as information is added \nto the KB\n- monotonicity implies soundness\n- adding information to the KB will not invalidate any other info that's already been \ninferred\n- it is sound, will only derive entailed sentences\n\nIf two values are complementary literals (one is the negation of the other), we can \neliminate them via unit resolution.\n\nConjunction Normal Form (CNF): every sentence of propositional logic is logically \nequivalent to a conjunction of clauses\n- clauses are disjunctions of literals\n\nResolution Algorithm: inference procedures based on resolution work using the principle \nof proof by contradiction\n- complete\n\nDefinite Clause: disjunction of literals where exactly one is positive\n\nHorn Clause: disjunction of literals where at most one is positive\n- includes definite clauses and clauses with no positive literals\n- closed under resolution (if you apply resolution to a horn clause, you get \nback a horn clause)\n- inference with Horn clauses can be done through the forward-chaining and \nbackward-chaining algorithms\n- deciding entailment with Horn clauses can be done in linear time with respect to the\nsize of the KB\n\nForward Chaining: agent can start with known data, adding premises as new percepts come in, \nthen incrementally apply the forward chaining algorithm to derive new conclusions\n- a kind of data-driven reasoning\n\nBackward Chaining: works backwards from a query\n- if the query is known to be true, no work is needed\n- otherwise the algorithm finds implications in the KB whose conclusion is in the query\n- if all the premises of one of those can be proved to be true, then the query is true\n- a form of goal-directed reasoning\n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over an internal representation of knowledge to decide what to do\n* **Entailment** - a sentence follows logically from another sentence\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "bfd653d7-4f93-4818-a7c1-2531d3756c5c"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nTuring Test: designed to figure out if a machine can think, a computer passes \nthis test if a human interrogator asks it questions and can't tell if the \nresponse came from the computer or a human.\n\nTo pass the Turing test the computer needs:\n- natural language processing (communicate in human language)\n- knowledge representation (store what it knows / hears)\n- automated reasoning (answer questions, draw conclusions)\n- machine learning (adapt to new circumstances and detect patterns)\n\nTotal Turing Test: requires interaction with objects and people in the real world\n- computer vision and speech recognition (perceive the world)\n- robotics (manipulate objects and move about)\n\nAgent: something that acts\n\nComputer Agents: expected to operate autonomously, perceive their environment,\npersist over a prolonged time period, adapt to change, and create and pursue goals\n\nRational Agent: one that acts so as to achieve the best outcome, or the best\nexpected outcome\n\nStandard Model: focus on the construction of agents that do the right thing\nas defined by the objective provided to the agent\n\nValue Alignment Problem: problem of achieving agreement between our true preferences\nand the objective we put into the machine\n\n## AIMA Chapter 27.1 The Limits of AI\n\nArgument from informality of behavior: human behavior is far too complex to be \ncaptured by any formal set of rules, humans use informal guidelines\n\nEmbodied Cognition: don't consider the brain separately, cognition takes places \nwithin a body, need to study the system as a whole\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nIt is irrelevant to ask whether or not machines can think.\n\n## AIMA 2.1 Agents and Environments\n\nAgent: anything that can be viewed as perceiving its environment through sensors \nand acting upon that environment through actuators\n\nIn general, an agent's choice of action at any given instant can depend on its built-in\nknowledge and on the entire percept sequence so far observed.\n\nAgent function is an abstract mathematical description, agent program is a concrete\nimplementation that runs on some physical system. The agent function is implemented\nby an agent program.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nConsequentialism: we evaluate an agent's behavior by its consequences\n\nRationality depends on:\n- performance measure that defines success\n- agent's prior knowledge of the environment\n- actions the agent can perform\n- agent's percept sequence to date\n\nOmniscient Agent: knows the actual outcome of its actions and can act accordingly, \nimpossible in reality\n\nRationality maximizes expected performance; perfection maximizes actual performance.\n\nRational agents should be autonomous: they should learn what they can to compensate\nfor partial or incorrect prior knowledge.\n\n## AIMA 2.3 The Nature of Environments\n\nTask Environment is defined by: performance, environment, actuators, and sensors\n\nFully Observable: the agent has access to the complete state at every point in time\n- agent does not need to maintain an internal state to keep track of the world\n\nUnobservable: agent has no sensors at all\n\nMultiagent: if an object is best described as maximizing a performance measure \nwhose value depends on another agent's behavior\n- environments can be competitive or cooperative\n\nDeterministic: the next state of the environment can be completely determined by\nthe current state and an action executed by the agent\n- most real situations are very complex and should be treated as nondeterministic\n\nEpisodic: the agent's next episode does not depend on the actions taken in\nprevious episodes\n- othwerise, sequential, the current decision could affect all future decisions\n\nDynamic: if the environment can change while an agent is deliberating\n- otherwise environment is static\n- semidynamic if the environment doesn't change but the agent's performance score does\n\nDiscrete: finite number of distinct states\n- otherwise, environment is continuous\n\nKnown: outcomes for all actions are given\n- otherwise, environment is unknown\n- known environment can still be partially observable, can know the rules of a game \nbut be unable to see the cards that have not been flipped\n- unknown environment can be fully observable, screen could show a video game but\ncould not know what the buttons will do\n\n## AIMA 2.4 The Structure of Agents\n\nAgent Program: takes the current percept as input from the sensors and returns an action\nto the actuators\n\nSimple Reflex Agent: selects actions based on the current percept, ignoring the \npercept history\n- escape from infinite loops is possible if the agent can randomize its actions\n\nModel-Based Reflex Agent: agent maintains some internal state depending on the\npercept history that keeps track of some of the unobserved aspects of the current state\n- transition model and sensor model keep track of the state of the world\n\nGoal-Based Agent: agent needs information on what its desirable / goal states are\n- takes actions based on what is predicts will achieve its goal\n\nUtility-Based Agent: agents makes decisions based on a utility function that acts \nas a performance measure to find most desirable way to reach goal\n\nA rational utility-based agent chooses the action that maximizes the expected \nutility of the action outcomes, this is the utility the agent expects to derive, \non average, given the probabilities and utilities of each outcome.\n\nModel-Free Agent: can learn what action is best in a situation without learning\nhow it changes the environment\n\nLearning agent has four components:\n- learning elements (responsible for making improvements)\n- performance element (responsible for selecting external actions)\n- critic (provides feedback on how the performance element could do better)\n- problem generator (suggests actions that lead to new and informative experiences)\n\nAtomic Representation: each state of the world has no internal structure\n\nFactored Representation: splits each state into a fixed set of variables or attributes,\neach of which can have a value\n\nStructured Representation: explicitly describes objects and their relationships\n\nA more expressive representation can capture at least and more of what a less expressive\nrepresentation can capture.\n\nLocalist Representation: a one-to-one mapping between concepts and memory locations\n\nDistributed Representation: spread over many memory locations and each memory \nlocation is part of the representation of multiple different concepts\n\n## Module 1 Lecture Notes\n\nStrong AI vs. Weak AI: actually thinking vs. simulating thinking\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content an agent's senros are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function** - maps any given percept sequence to an action, describes an agent's behavior\n* **Rational agent** - selects an action expected to maximize performance measure, given percept sequence and agent's built-in knowledge\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nPython uses dynamic typing - variables come into existence when first assigned.\n- type errors are only caught at runtime\n\nStrings: immutable\n\nLists: mutable, can have mixed types\n\nTuple: immutable, can have mixed types\n\nDictionaries: unordered, work by hashing, keys must be immutable\n\nPython does not allow function overloading but does allow operator overloading.\n\nKeyword Arguments: can be used after all other arguments\n- *args comes before **kwargs\n- *args : variable number of args\n- **kwargs : variable number of keyword args\n\nPython uses dynamic scope - function sees the most current value of variables.\n\nFirst Class Object: can be dynamically created, destroyed, passed to a function, \nreturned as a value, and have all the rights as other variables have\n- functions are first class objects\n\nSubclass: a class can extend the definition of another class\n- allows use or extensions of methods and attributes already created\n- to define a subclass, name of superclass goes in parenthesis on the first line of \nthe class definition\n- multiple inheritance is supported\n- can redefine methods (similar to over-riding in Java), new definition using same\nname of method\n- only ever pass self as an argument when calling a method of an ancestor\n\nClass:\n- every method begins with the variable self\n- the __init__ method (constructor) must be done explicitly\n\nMagic Methods: built-in methods for classes\n- includes __init__, __len__, __copy__, etc.\n\nDuck Typing: call a python function on any class that implements that method, determines\nwhether the method is present by 'does it swim like a duck and quack like a duck'\n\nPython iterators do not have a hasnext() method, they catch the StopIteration exception.\n- iterators use memory efficiently\n\nGenerators: a type of iterator\n- functions containing the yield keyword automatically return a generator\n- whenever next() is called, method runs until it encounters a yield statement, then \nresumes where it left off\n- avoids storing the entire sequence in memory\n- crucial for infinite sequences\n\n## Module 2 Definitions\n* **Mutability** - can be changed\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nProblem-Solving Agents:\n- use atomic representations\n- agents that use factored or structured representations are called planning agents\n\nIn informed algorithms, agents can estimate how far they are from the goal, in\nuninformed they can't.\n\nSearch: before taking an action, agent simulates sequences of actions in its model\n- each sequence is called a solution\n\nOpen-Loop System: once an agent has found a solution, it can ignore the percepts\nwhile executing the actions because the solution is guaranteed to lead to the goal\n- ignoring the percepts breaks the loop between agent and environment\n- if the model could be incorrect or the environment could be nondeterministic, \nit is safer to use a closed-loop approach that monitors the percepts\n\nSearch problem includes:\n- problem\n- states (state space, initial state)\n- goal states\n- actions (available to the agent)\n- transition model (describes what each action does)\n- action cost function\n\nSolution: a path (sequence of actions) from the initial state to a goal state\n- total cost of a path is the sum of the inidivial action costs\n- optimal solution has the lowest path cost\n\n## AIMA Chapter 3.2 Example Problems\n\nTouring Problems: describes a set of loctions that must be visited\nrether than a single goal destination\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch Algorithm: takes a search problem as input and returns a solution or an \nindication of failure\n- use a search tree over the state-space graph\n- each node corresponds to a state space\n- each edge corresponds to an action\n- expand a node by considering its available actions, generate child (successor) \nnodes for each resulting state\n- frontier: nodes that have not been expanded\n- all states with nodes generated have been reached\n\nBest-First Search: choosse a node with minimum value of some evaluation \nfunction f(n), on each iteration expand node with minimum f(n)\n\nQueues used in search algorithms:\n- priority queue\n- fifo queue (first in first out)\n- lifo queue (last in first out)\n\nGraph Search: checks for redundant paths\n\nTree Search: does NOT check for redundant paths\n\nCompleteness: algorithm is guaranteed to find a solution when there is one and\nreports failure when there isn't\n- complete search algorithms must be systematic in the way they explore infinite\nstate spaces\n\nComplexity:\n- d: depth, the number of actions in an optimal solution\n- m: maxmimum number of actions in any path\n- b: braching factor, number of successors of a node that need to be considered\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth-First Search (BFS):\n- best when all actions have the same cost\n- complete on infinite spaces\n- FIFO queue is faster than a priority queue\n- early goal test: checks whether a node is a solution as soon as it is generated \n(best-first search uses the late goal test, waiting until a node is popped off \nthe queue)\n- time complexity: O(b^d)\n- space complexity: O(b^d)\n- memory requirements are a bigger problem than execution time\n\nUniform-Cost Search: aka Dijkstra's algorithm, uses BFS\n- complete\n- has optimal cost\n\nDepth-First Search (DFS):\n- not cost-optimal (returns first solution it finds)\n- efficient and complete for finite state spaces that are trees\n- for acyclic state spaces, may expand the same state multiple times but will \neventually explore the entire space\n- not systematic for infinite state spaces\n- DFS uses less memory when a tree-like search is feasible\n- space complexitiy for finite tree-like search: O(bm), m is maximum depth of\nthe tree\n\nBacktracking Search: usees DFS, only one successor generated at a time, uses\nlittle memory\n- space complexity: O(m)\n\nDepth-Limited Search: treat nodes at depth limit l as if they have no successors\n- time complexity: O(b^l)\n- space complexity: O(bl)\n- incomplete\n\nIterative Deepening: repeatedly applies depth-limited search with increasing limits\n- space complexity: O(bd) if there is a solution, O(bm) for finite spaces with no solution\n- optimal for problems where all actions have the same cost\n- complete on finitie acyclic spaces, or finite spaces where we check for cycles \nup the path\n- time complexity: O(b^d) if there is a solution, O(b^m) if not\n- generally the best uninformed search method when the search state space can't fit in\nmemory and the depth of the solution is unknown\n- complete\n- has optimal cost\n\nBidirectional Search: simultaneously searches forward from the initial state and backwards \nfrom the goal state(s), waiting until the frontiners collide\n- complete\n- has optimal cost\n- time complexity: O(b^(d/2))\n- space complexity: O(b^(d/2))\n\n## Module 3 Lecture Notes\nState space must be abstracted for problem solving \nin the real world because it is very complex.\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed Search: uses a heuristic function, h(n), about the location of goals\n\nGreedy Best-First Search: expands first the node with the lowest h(n) value\n- evaluation function: f(n) = h(n)\n\nA* Search: search using the evaluation function f(n) = g(n) + h(n)\n- g(n): path cost from the initial state to node n\n- h(n): estimated cost of the shortest path from n to a goal state\n- f(n): estimated cost of the best path from n to a goal\n- complete\n- cost optimal if there is an admissible heuristic\n- prunes away nodes that are not necessary for finding an optimal solution\n\nEvery consistent heuristic is admissible (but not vice versa).\n\nWeighted A* Search: focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality\n\nBounded Suboptimal Search: look for a solution guaranteed to be within a constant \nfactor W of the optimal cost\n\nBounded-Cost Search: look for a solution whose cost is less than some constant C\n\nUnbounded-Cost Search: accept a solution of any cost that's found quickly\n\nBeam Search: limits the size of the frontier, keeps only the k nodes with the \nbest f-scores\n\nIterative-Deepening A* Search: does not keep all reached states in memory\n- can visit some states multiple times\n\nRecursive Best-First Search (RBFS): a recursive depth-first search, but keeps \ntrack of the f-value of the best alternative path available from any ancestor of \nthe current node, then unwinds back to that node if the current node exceeds \nthe limit, replacing the value at each node with the backed-up value\n\nMA* : memory bounded A*\n\nSMA* : simplified MA*\n\nBidirectional Heuristic Search: uses ff(n) = gf(n) + hf(n) for nodes going \nforwards, and fb(n) = gb(n) + hb(n) for nodes going backwards\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nEffective Branching Factor: b*\n- N: total number of nodes generated by A*\n- N + 1 = 1 + b* + (b* )^2 + ... + (b* )^d\n\nAny optimal solution for the original problem is a solution in the \nrelaxed problem, but the relaxed problem might have better solutions if the\nadded edges provide shortcuts.\n- Relaxed Problem: has fewer restrictions on the actions\n- the cost of an optimal solution to a relaxed problem is an admissible \nheuristic for the original problem\n\n## Module 4 Lecture Notes\n\nDominance: if h2(n) >= h1(n) for all n (both admissible), then h2 dominates h1\n- h2 is optiministic, but more accurate than h1\n- h2 is better for search\n\nUniform-Cost expands equally in all directions, while A* mainly expands towards \nthe goal.\n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Admissible heuristic** - never overestimates cost to reach a goal\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nTwo Player Zero-Sum Game Elements:\n- initial state\n- the player whose turn it is to move\n- actions\n- transition model\n- terminal test\n- terminal states\n- utility function (defines the final numeric value to a player when the game ends)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax Search: forms strategy assuming that both players play optimally\n- minimax value of a terminal state is its utility\n- max moves to max value of result for min\n- min moves to min value of result for max\n- backs up the minimax values through the tree during recursion\n\nAlpha-Beta Pruning:\n- alpha: the value of the best (highest-value) choice for max\n- beta: the value of the best (lowest-value) choice for min\n- prune the values below the alpha and above the beta\n- better move ordering can lead to better runtime\n\nTransposition Table: can cache the heuristic value of states to avoid transpositions,\ndifferent permutations of moves that end up in the same position\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nHeuristic Evaluation Function: estimates the utility of a state, used to cut off \nthe search\n\nMonte Carlo Tree Search (MCTS): evaluates states by playing out the game and seeing \nwho won, then repeating multiple times and averaging the results\n\nMany game programs precompute tables of best moves in the opening and endgame so that\nthey can look up a move rather than search.\n\n## AIMA Chapter 5.5 Stochastic Games\n\nExpectiminimax: evaluates a chance node by taking the average utility of all its children, \nweighed by the probability of each child\n- handles games of chance\n\nIn games of imperfect information, optimal play requires reasoning about the current \nand future belief states of each player. Can obtain an approximation by averaging \nthe value of an action over eah possible configuration of missing information.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nProbability Theory: describes what an agent should believe on the basis of evidence.\n\nUtility Theory: describes what an agent wants\n\nDecision Theory: puts probability and utility theory together to describe what \nan agent should do\n- use decision theory to build a rational agent\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nUtility theory shows that an agent whose preference between lotteries are consistent \nwith a set of simple axioms can be described as possessing a utility function, and \nthat agent selects actions as if maximizing its expected utility.\n\n## AIMA Chapter 16.3 Utility Functions\n\nDecision theory is a normative theory, it describes how rational agents should act. \nDescriptive theory describes how actual agents (ex: humans) act.\n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum game** - what is good for one player is just as bad for the other\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Satisfaction Problems (CSPs): represent a state with a variable/value \npairs and represent the conditions for a solution by a set of constraints on the \nvariables\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nInference techniques that use the constraints to rule out certain value assignments:\n- node\n- arc\n- path\n- k-consistency\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nMinimum-Remaining Values and Degree heuristics are domain-independent methods for \ndeciding which variable to choose next in a backtracking search.\n\nLeast-Constraining-Value Heuristic: helps decide which value to try first for a variable\n\nBacktracking Search: DFS for CSPs\n- chooses values for one variable at a time\n- backtracking occurs when no legal assignment can be found for a variable\n- basic uninformed algorithm for CSPs\n\nConflict-Directed Backjumping: backtracks directly to the source of the problem\n\nContraint Learning: records the conflicts as they are encountered during search in \norder to avoid the same conflict later in the search\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal Search: uses the min-conflicts heuristic\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nTree-structured problems can be solved in linear time.\n\nCutset Conditioning: can reduce a general CSP to a tree-structured one and is efficient\nif a small cutset can be found\n- requires linear memory if a small cutset can be found\n\nTree Decomposition: transform the CSP into a tree of subproblems\n- efficient if the tree width of the constraint graph is small\n- need memory exponential in the tree width of the constraint graph\n\nCombining cutset conditioning with tree decomposition can allow a better tradeoff of \nmemory versus time.\n\n## Module 6 Lecture Notes\n\nCSP: \n- represent the coontraints that solutions must satisfy in a uniform declarative language\n- find solutions by general purpose search algorithms with no changes from problem to \nproblem\n\nCSP consists of:\n- finite set of variables\n- nonempty domain of possible values for each variable\n- finite set of constraints\n\nA consistent assignment does not violate the constraints.\n- assignment is complete when every variable is assigned a value\n- solution to a CSP is a complete, consistent assignment\n\nCSPs automatically prune off all branches that violate constraints.\n\nVarities of CSPs:\n- discrete variables\n- continuous variables\n\nVarieties of Constraints:\n- unary (single variable)\n- binary (pairs of variables)\n- higher-order (3 or more variables)\n- preference (soft constraints, represented by a cost for each variable assignment)\n\nGeneral-purpose methods & general-purpose heuristics can give huge gains in speed\non average for backtracking search algorithms.\n- assign next the most constrained variable\n- if ties, assign next the most constraining variable\n- try the variable's values in least constraining value order\n- can detect failure early through forward checking\n\nForward Checking: keep track of remaining legal values for unassigned variables, \nterminate search when any unassigned variables has no remaining legal values\n- constraint propagation: goes further and repeatedly enforces constraints locally\n\nCSP solvers combine search and inference.\n- search: assigning a value to a variable\n- constraint propagation (inference): eliminates possible values for a variable \nif the value would violate local consistency\n\nLocal Consistency:\n- node consistency: satifies unary constraints; trivial\n- arc consistency: satisfies binary constraints (constraints between nodes)\n\nAC-3:\n- at each iteration, only need to examine nodes where at least one neighbor lost \na value in the previous iteration\n- if Xi loses a value only because of arc inconsistencies with Yj, we don't need \nto check Yj on the next iteration\n- worst case: O(n^2d^3), with d values\n\n## Module 6 Definitions\n* **Constrained optimization problems** - optimize by preference\n* **Arc consistent** - iff every value v on Xi is consistent with some label on Yj\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-Based Agents\nKnowledge Base: stores agent knowledge in sentences in a knowledge representation \nlanguage\n\nKnowledge-Based Agent:\n- composed of a knowledge base and an inference mechanism\n- operates by storing sentences about the world in its knowledge base\n- uses the inference mechanism to infer new sentences\n- uses the sentences to decide what action to take\n\nRepresentation Language is defined by:\n- syntax (specifies structure of sentences)\n- semantics (defines the truth of each sentence in each possible world or model)\n\n## AIMA Chapter 7.2 The Wumpus World\n\nThe Wumpus World\n\n## AIMA Chapter 7.3 Logic\n\nEntailment: a sentence x entails another sentence y if y is true in all worlds \nwhere x is true\n- equivalently, validity of the sentence x -> y\n- equivalently, unsatisfiability of the sentence x ^ !y\n\nInference: deriving new sentences from old ones\n\nSound Inference Algorithms: derive only sentences that are entailed\n\nComplete Algorithms: derive all sentences that are entailed\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nPropositional Logic: a simple language consisting of proposition symbols and \nlogical connectives\n- can handle propositions known to be true, false, or completely unknown\n\nThe set of possible models, given a fixed propositional vocabulary, is finite, so\nentailment can be checked by enumerating models.\n\nEfficient model-checking inference algorithms for propositional logic include backtracking\nand local search methods and can often solve large problems quickly.\n\n## AIMA 7.5 Propositional Theorem Proving\n\nInference Rules: patterns of sound inference that can be used to find proofs\n\nResolution Rule: yields a complete inference algorithm for knowledge bases that are \nexpressed in conjunctive normal form\n- when coupled with any complete search algorithm\n\nForward chaining and backward chaining are very natural reasoning algorithms for knowledge \nbases in Horn form.\n\n## Module 7 Lecture Notes\n\nTwo kinds of sentences:\n- axioms: a sentence that is given\n- derived sentences: a new sentence that is derived from other sentences\n\nInference: the process of deriving new sentences from old sentences\n\nRules:\n- a entails b iff M(a) is a subset of M(b)\n\nAtomic Sentences: represented with a single propositional symbol\n- propositional symbols: stand for a statement that can be true or false\n\nModels: mathematical abstractions that have a fixed set of truth values which \nare {true, false} for each sentence\n- if sentence a is true in model m, then m satisfies a, or m is a model of a\n- M(a): the set of all models of a\n\nLogical Inference: process of applying entailment to derive conclusions\n\nInference Algorithm: enumerates sentences in a KB\n\nLogically Equivalent: they are true in the same set of model; they entail each other\n\nMonotonicity: the set of entailed sentences can only increase as information is added \nto the KB\n- monotonicity implies soundness\n- adding information to the KB will not invalidate any other info that's already been \ninferred\n- it is sound, will only derive entailed sentences\n\nIf two values are complementary literals (one is the negation of the other), we can \neliminate them via unit resolution.\n\nConjunction Normal Form (CNF): every sentence of propositional logic is logically \nequivalent to a conjunction of clauses\n- clauses are disjunctions of literals\n\nResolution Algorithm: inference procedures based on resolution work using the principle \nof proof by contradiction\n- complete\n\nDefinite Clause: disjunction of literals where exactly one is positive\n\nHorn Clause: disjunction of literals where at most one is positive\n- includes definite clauses and clauses with no positive literals\n- closed under resolution (if you apply resolution to a horn clause, you get \nback a horn clause)\n- inference with Horn clauses can be done through the forward-chaining and \nbackward-chaining algorithms\n- deciding entailment with Horn clauses can be done in linear time with respect to the\nsize of the KB\n\nForward Chaining: agent can start with known data, adding premises as new percepts come in, \nthen incrementally apply the forward chaining algorithm to derive new conclusions\n- a kind of data-driven reasoning\n\nBackward Chaining: works backwards from a query\n- if the query is known to be true, no work is needed\n- otherwise the algorithm finds implications in the KB whose conclusion is in the query\n- if all the premises of one of those can be proved to be true, then the query is true\n- a form of goal-directed reasoning\n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over an internal representation of knowledge to decide what to do\n* **Entailment** - a sentence follows logically from another sentence\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ]
    }
  ]
}