{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4dc396fd-e9f4-4029-96ed-74a02e02b53f"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "deec3ea0-eb92-4233-ae36-c5ab6ab46b8c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent’s decisions can be determined based on its current senses and also its percept sequence, just not anything that it hasn’t sensed yet. \"\"\"\n",
        "chapter2_2 = \"\"\" Rationality is measured by performance measure, knowledge of the area, available actions, and percept sequence.  \"\"\"\n",
        "chapter2_3 = \"\"\" There are competitive (game) multiagent environments compared to cooperative (taxi-drivers) multi-agent environments. \"\"\"\n",
        "chapter2_4 = \"\"\" The agent program takes the current precent, while the agent function uses the whole percept sequence. Randomization is typically not rational in a single agent environment. Learning agent has a critic (the performance standard), which gives feedback from information it gets from the sensors to the learning element, which provides changes to the performance element and learning goals to the problem generator. The performance element then gives the actuators the action to do and provides knowledge back  to the learning element. The problem generator also interfaces with the performance element, since it suggests actions. Problem generator explores a bit, while the performance element would stay with what it knows otherwise. Structured representations are usually the most expressive, followed by factored representation, followed by atomic. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"rationally\" : \"selecting the correct and logical action. Includes math, engineering, stats, etc.\",\n",
        "\"Turing Test\" : \"passes if a human can’t determine if replies are human or machine\",\n",
        "\"Natural language processing\" : \"computer communicating well in English\",\n",
        "\"Knowledge representation\" : \"save the information it learns\", \n",
        "\"Automated reasoning\" : \"use reasoning to inform decisions/respond to queries\", \n",
        "\"Machine learning\" : \"predict and change to situations based on previous patterns\",\n",
        "\"total Turing test\" : \"like the turing test but with irl manipulation\",\n",
        "\"computer vision\" : \"helps know the area around the machine\",\n",
        "\"robotics\" : \"used to interact with the world\",\n",
        "\"agent\" : \"an actor who sees and acts upon an environment\",\n",
        "\"rational agent\" : \"actor to get an optimal solution, or at least expected optimal\",\n",
        "\"standard model\" : \"where an agent performs optimally (minimizes cost or maximizes gain)\",\n",
        "\"limited rationality\" : \"doing the best you can with information you have, computations are too long\",\n",
        "\"value alignment problem\" : \"goals must be same as people. Make sure computer doesn’t misbehave\",\n",
        "\"weak AI\" : \"Computers aren’t actually thinking\",\n",
        "\"strong AI\" : \"Computers making their own thoughts\",\n",
        "\"embodied cognition\" : \"include the whole body, not just brain. Everything in the environment\",\n",
        "\"qualia\" : \"experiencing the world, awareness, consciousness\",\n",
        "\"actuators\" : \"what an agent uses to operate on the environment\",\n",
        "\"percept\" : \"what an agent is sensing\",\n",
        "\"percept sequence\" : \"all things that the agent sensed, currently and in the past\",\n",
        "\"agent function\" : \"the action that is performed based on the percept sequence; agent behavior; abstract\",\n",
        "\"agent program\" : \"implementation of the agent function\",\n",
        "\"consequentialism\" : \"what outcome comes out of action and how good of an outcome\",\n",
        "\"information gathering\" : \"done before performing to change percepts\",\n",
        "\"autonomy\" : \"learn to balance previous knowledge\",\n",
        "\"task environments\" : \"encompasses all of PEAS\",\n",
        "\"PEAS\" : \"performance measure, environment, actuators, sensors\",\n",
        "\"software agent\" : \"performs in a virtual environment\", \n",
        "\"fully observable\" : \"Total relevant environment is seen. No internal state is needed\",\n",
        "\"deterministic\" : \"no uncertainty in a fully observable area\",\n",
        "\"stochastic\" : \"uses probabilities compared to nondeterministic which doesn’t\",\n",
        "\"known\" : \"outcomes for each action is known; like rules in a game\",\n",
        "\"agent architecture\" : \"physical form of the agent\",\n",
        "\"simple reflex agent\" : \"makes their decisions and acts based on the current environment and precept\",\n",
        "\"condition-action rule\" : \"if something do something\",\n",
        "\"internal state\" : \"uses precept sequence and history to keep track of unobservable parts of the environment that it previously learned about\",\n",
        "\"transition model\" : \"agent’s actions affecting the environment and how else the environment changes regardless of the agent\",\n",
        "\"model-based agent\" : \"combines transition model and sensor model to keep track of the environment\",\n",
        "\"utility function\" : \"measuring performance and trying to maximize utility\",\n",
        "\"model-free agent\" : \"determining best action without knowing how it alters the environment\",\n",
        "\"learning element\" : \"in a learning agent, makes the changes for the better\",\n",
        "\"performance element\" : \"learning agent, makes the actions\",\n",
        "\"atomic representation\" : \"indivisible states; different states are distinct and unrelated\",\n",
        "\"factored representation\" : \"use multiple pieces of information. Different states can share some properties while differing on others\",\n",
        "\"structured representation\" : \"different objects can be described together using relationships\",\n",
        "\"localist representation\" : \"everything can be represented in a memory location\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f83a2484-2804-4396-fd9b-f84202e7f56f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent’s decisions can be determined based on its current senses and also its percept sequence, just not anything that it hasn’t sensed yet. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rationality is measured by performance measure, knowledge of the area, available actions, and percept sequence.  \n\n## AIMA 2.3 The Nature of Environments\n There are competitive (game) multiagent environments compared to cooperative (taxi-drivers) multi-agent environments. \n\n## AIMA 2.4 The Structure of Agents\n The agent program takes the current precent, while the agent function uses the whole percept sequence. Randomization is typically not rational in a single agent environment. Learning agent has a critic (the performance standard), which gives feedback from information it gets from the sensors to the learning element, which provides changes to the performance element and learning goals to the problem generator. The performance element then gives the actuators the action to do and provides knowledge back  to the learning element. The problem generator also interfaces with the performance element, since it suggests actions. Problem generator explores a bit, while the performance element would stay with what it knows otherwise. Structured representations are usually the most expressive, followed by factored representation, followed by atomic. \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationally** - selecting the correct and logical action. Includes math, engineering, stats, etc.\n* **Turing test** - passes if a human can’t determine if replies are human or machine\n* **Natural language processing** - computer communicating well in English\n* **Knowledge representation** - save the information it learns\n* **Automated reasoning** - use reasoning to inform decisions/respond to queries\n* **Machine learning** - predict and change to situations based on previous patterns\n* **Total turing test** - like the turing test but with irl manipulation\n* **Computer vision** - helps know the area around the machine\n* **Robotics** - used to interact with the world\n* **Agent** - an actor who sees and acts upon an environment\n* **Rational agent** - actor to get an optimal solution, or at least expected optimal\n* **Standard model** - where an agent performs optimally (minimizes cost or maximizes gain)\n* **Limited rationality** - doing the best you can with information you have, computations are too long\n* **Value alignment problem** - goals must be same as people. Make sure computer doesn’t misbehave\n* **Weak ai** - Computers aren’t actually thinking\n* **Strong ai** - Computers making their own thoughts\n* **Embodied cognition** - include the whole body, not just brain. Everything in the environment\n* **Qualia** - experiencing the world, awareness, consciousness\n* **Actuators** - what an agent uses to operate on the environment\n* **Percept** - what an agent is sensing\n* **Percept sequence** - all things that the agent sensed, currently and in the past\n* **Agent function** - the action that is performed based on the percept sequence; agent behavior; abstract\n* **Agent program** - implementation of the agent function\n* **Consequentialism** - what outcome comes out of action and how good of an outcome\n* **Information gathering** - done before performing to change percepts\n* **Autonomy** - learn to balance previous knowledge\n* **Task environments** - encompasses all of PEAS\n* **Peas** - performance measure, environment, actuators, sensors\n* **Software agent** - performs in a virtual environment\n* **Fully observable** - Total relevant environment is seen. No internal state is needed\n* **Deterministic** - no uncertainty in a fully observable area\n* **Stochastic** - uses probabilities compared to nondeterministic which doesn’t\n* **Known** - outcomes for each action is known; like rules in a game\n* **Agent architecture** - physical form of the agent\n* **Simple reflex agent** - makes their decisions and acts based on the current environment and precept\n* **Condition-action rule** - if something do something\n* **Internal state** - uses precept sequence and history to keep track of unobservable parts of the environment that it previously learned about\n* **Transition model** - agent’s actions affecting the environment and how else the environment changes regardless of the agent\n* **Model-based agent** - combines transition model and sensor model to keep track of the environment\n* **Utility function** - measuring performance and trying to maximize utility\n* **Model-free agent** - determining best action without knowing how it alters the environment\n* **Learning element** - in a learning agent, makes the changes for the better\n* **Performance element** - learning agent, makes the actions\n* **Atomic representation** - indivisible states; different states are distinct and unrelated\n* **Factored representation** - use multiple pieces of information. Different states can share some properties while differing on others\n* **Structured representation** - different objects can be described together using relationships\n* **Localist representation** - everything can be represented in a memory location\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 212
        },
        "outputId": "8adc2ea7-ee9c-45ec-8f0c-faeb54079c4b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Four steps to solve a problem. 1. Goal formulation – understand the goal. 2. Problem formulation – states and actions to reach the goal. 3. Search – looking for the goal. Creates a sequence that can represent the solution when the goal is found. 4. Execute. \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Search trees represent the state space, with each node as one state and edges are actions. Redundant path solutions: remember all previously reached states, not worry about repeating states (assembly problems), or check for cycles but not redundant paths. We can check if performance is complete, cost optimal, low time complexity and space complexity. Complexity can be measured by depth, maximum number of actions, or branching factor.\"\"\"\n",
        "chapter3_4 = \"\"\" IDDFS is O(bd) on space when there’s a solution or O(bm) if not. For time, O(b^d) if solution, O(b^m) if not. D is depth. B is branching. M is max tree depth. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"Problem-solving agent\" : \"plan a sequence to find the goal; solved with atomic states\",\n",
        "\"Search\" : \"process to find the goal for problem-solving agents\",\n",
        "\"planning agents\" : \"agents that take into account factored or structured data instead\",\n",
        "\"informed\" :  \"agent knows where the goal is and how close it is\",\n",
        "\"open-loop\" : \"full observable, deterministic, known, leads to a set sequence. You don’t need percepts\",\n",
        "\"closed-loop\" : \"uses the percepts, in nondeterminstic or potentially incorrect models\",\n",
        "\"state space\" : \"all potential states\",\n",
        "\"problem\" : \"state space, initial state, goal states, available actions, transition model, action cost function\",\n",
        "\"transition model\" : \"how an action affects the environment and state moving forward\",\n",
        "\"action cost function\" : \"calculates the cost of doing an action at a given state\",\n",
        "\"path\" : \"a sequence of states together from valid actions\",\n",
        "\"optimal solution\" : \"minimum cost path from initial state to goal\",\n",
        "\"standardized problem\" : \"common problem solving methods that can easily be compared\", \n",
        "\"real-world problem\" : \"non-standard with more useful solutions\",\n",
        "\"grid world\" : \"standardized problem where the agent can move to neighboring cells\",\n",
        "\"egocentric actions\" :  \"actions from the robot’s point of view, rather than absolute directions\",\n",
        "\"route-finding problem\" : \"an example of a real-world problem\",\n",
        "\"VLSI layout\" : \"positions components on a chip for ideal cell layout and channel routing\",\n",
        "\"frontier\" : \"nodes that have been found but not explored, boundary between where states have been expanded and exterior nodes that haven’t\",\n",
        "\"best-first search\" : \"choose node with minimum value and expand that one\",\n",
        "\"nodes\" : \"have states, parents, actions, and cost\",\n",
        "\"priority queue\" : \"node with minimum cost first, used in best-first\",\n",
        "\"FIFO queue\" :  \"used in BFS\",\n",
        "\"LIFO queue\" : \"used in DFS\",\n",
        "\"graph search\" : \"checks for redundant paths and tree-like searches do not\",\n",
        "\"complete\" : \"guaranteed to find a solution, algorithm is systematic\",\n",
        "\"branching factor\" : \"b. number of successors a node has that would need to be expanded\",\n",
        "\"depth\" : \"d. deepness, number in optimal path\",\n",
        "\"breadth-first search\" : \"complete in infinite spaces. Always produces path with minimum actions. O(b^d) time and space\",\n",
        "\"early goal test\" : \"if a node is a solution when discovered instead of popped\",\n",
        "\"late goal test\" : \"used by best-first, solution is determined after node is popped from frontier\",\n",
        "\"uniform-cost search\" : \"Dijkstra’s. Expands lowest-cost path next. Can be worse than O(b^d). Complete and cost-optimal.\",\n",
        "\"Depth-first search\" : \"Expands deepest. Not cost-optimal. Incomplete. Smaller memory compared to bfs or best-first. O(bm)\",\n",
        "\"backtracking search\" : \"DFS alternate. Only one successor at a time instead of generating all successors. Successor changes current state.\",\n",
        "\"depth-limited search\" : \"DFS with a limit; pretend all nodes at limit are leaves. O(b^l) time and O(bl) space\",\n",
        "\"diameter\" : \"the furthest chain/farthest nodes apart, the number of steps between\",\n",
        "\"Iterative deepening search\" : \"depth-limited search but increases l form 0 until a solution or max l\",\n",
        "\"bidirectional search\" : \"searches forward but also backwards from goal states\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8cf278ea-e65b-4647-db67-7493bdaf5fbd"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Four steps to solve a problem. 1. Goal formulation – understand the goal. 2. Problem formulation – states and actions to reach the goal. 3. Search – looking for the goal. Creates a sequence that can represent the solution when the goal is found. 4. Execute. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Search trees represent the state space, with each node as one state and edges are actions. Redundant path solutions: remember all previously reached states, not worry about repeating states (assembly problems), or check for cycles but not redundant paths. We can check if performance is complete, cost optimal, low time complexity and space complexity. Complexity can be measured by depth, maximum number of actions, or branching factor.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n IDDFS is O(bd) on space when there’s a solution or O(bm) if not. For time, O(b^d) if solution, O(b^m) if not. D is depth. B is branching. M is max tree depth. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - plan a sequence to find the goal; solved with atomic states\n* **Search** - process to find the goal for problem-solving agents\n* **Planning agents** - agents that take into account factored or structured data instead\n* **Informed** - agent knows where the goal is and how close it is\n* **Open-loop** - full observable, deterministic, known, leads to a set sequence. You don’t need percepts\n* **Closed-loop** - uses the percepts, in nondeterminstic or potentially incorrect models\n* **State space** - all potential states\n* **Problem** - state space, initial state, goal states, available actions, transition model, action cost function\n* **Transition model** - how an action affects the environment and state moving forward\n* **Action cost function** - calculates the cost of doing an action at a given state\n* **Path** - a sequence of states together from valid actions\n* **Optimal solution** - minimum cost path from initial state to goal\n* **Standardized problem** - common problem solving methods that can easily be compared\n* **Real-world problem** - non-standard with more useful solutions\n* **Grid world** - standardized problem where the agent can move to neighboring cells\n* **Egocentric actions** - actions from the robot’s point of view, rather than absolute directions\n* **Route-finding problem** - an example of a real-world problem\n* **Vlsi layout** - positions components on a chip for ideal cell layout and channel routing\n* **Frontier** - nodes that have been found but not explored, boundary between where states have been expanded and exterior nodes that haven’t\n* **Best-first search** - choose node with minimum value and expand that one\n* **Nodes** - have states, parents, actions, and cost\n* **Priority queue** - node with minimum cost first, used in best-first\n* **Fifo queue** - used in BFS\n* **Lifo queue** - used in DFS\n* **Graph search** - checks for redundant paths and tree-like searches do not\n* **Complete** - guaranteed to find a solution, algorithm is systematic\n* **Branching factor** - b. number of successors a node has that would need to be expanded\n* **Depth** - d. deepness, number in optimal path\n* **Breadth-first search** - complete in infinite spaces. Always produces path with minimum actions. O(b^d) time and space\n* **Early goal test** - if a node is a solution when discovered instead of popped\n* **Late goal test** - used by best-first, solution is determined after node is popped from frontier\n* **Uniform-cost search** - Dijkstra’s. Expands lowest-cost path next. Can be worse than O(b^d). Complete and cost-optimal.\n* **Depth-first search** - Expands deepest. Not cost-optimal. Incomplete. Smaller memory compared to bfs or best-first. O(bm)\n* **Backtracking search** - DFS alternate. Only one successor at a time instead of generating all successors. Successor changes current state.\n* **Depth-limited search** - DFS with a limit; pretend all nodes at limit are leaves. O(b^l) time and O(bl) space\n* **Diameter** - the furthest chain/farthest nodes apart, the number of steps between\n* **Iterative deepening search** - depth-limited search but increases l form 0 until a solution or max l\n* **Bidirectional search** - searches forward but also backwards from goal states\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" A* expands no nodes with f(n) > C*, where C* is the optimal solution path cost. Biggest issue with A* is lots of memory use. Some solutions: only store state information on frontier or reached states, not both. Or remove states from the reached table when they aren’t needed (involves separation property and not allowing u-turns). Or keep reference counts and remove nodes from the table when there are no other ways to reach it. IDA* and RBFS use too little memory sometimes. IDA * only maintains the current cost limit and RBFS only keeps the alternate path and keeps linear space. They probably will reexamine same states multiple times.\"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search\" : \"uses goal information to target solutions for efficiency:\",\n",
        "\"Heuristic function\" : \"estimated cost from a node to a goal\",\n",
        "\"Greedy best-first search\" : \"f(n) = h(n). Picks lowest node based on heuristic only. Complete in finite spaces only. O(|V|) or O(bm) if good\",\n",
        "\"A* search\" : \"best-first with f(n) = g(n) + h(n). Complete and potentially cost-optimal if heuristic is admissible\",\n",
        "\"admissible\" : \"optimistic, underestimates or exactly estimates distance to goal\",\n",
        "\"consistency\" : \"h(n) $\\leq$ c(n,a,n’) + h(n’). follows triangle inequality\",\n",
        "\"contours\" : \"topographical map like lines\",\n",
        "\"monotonic\" : \"cost always increases, each step has a positive value associated so as you go cost will increase\",\n",
        "\"surely expanded nodes\" : \"all nodes where cost is less than the cost of the optimal solution path\",\n",
        "\"optimally efficient\" : \"A* with consistent heuristic\",\n",
        "\"pruning\" : \"eliminating nodes based on cost or other factors without having to expand/examine them\",\n",
        "\"satisficing\" : \"not optimal/admissible but do well enough\",\n",
        "\"inadmissible heuristic\" : \"may overestimate costs in which case A* solution may not be optimal\",\n",
        "\"weighted A* search\" : \"value heuristic more and multiply it by a factor > 1\",\n",
        "\"bounded suboptimal search\" : \"solution within a factor of the optimal\",\n",
        "\"bounded-cost search\" : \"any solution where the cost is less than the boundary\",\n",
        "\"unbounded-cost search\" : \"want to find solution ASAP, doesn’t matter the cost\",\n",
        "\"reference counts\" : \"number of times a node has been found\",\n",
        "\"beam search\" : \"only keep certain amount of nodes with best costs. Incomplete, suboptimal. Limits frontier size\",\n",
        "\"iterative-deepening A* search\" : \"like iddfs without needing to keep everything in memory\",\n",
        "\"recursive best-first search\" : \"linear space, uses a limit variable to track best alternative path, if limit is hit, go to alternate\",\n",
        "\"MA*\" : \"memory bounded A*\",\n",
        "\"SMA *\" : \"simplified MA*. Does A* until memory is full, removes the worst leaf. Complete if goal depth < memory size\",\n",
        "\"effective branching factor b*\" : \"N + 1 = 1 + b* + b*^2 + b*^d\",\n",
        "\"effective depth\" : \"O(b^(d-k))\",\n",
        "\"dominates\" : \"h2 >= h1 in all cases h2 dominates. H2 won’t expand more than h1\",\n",
        "\"relaxed problem\" : \"has fewer restrictions. All optimal solutions to og are also optimal to relaxed\",\n",
        "\"subproblem\" : \"also admissible heuristic. Working with fewer parts compared to the whole problem\",\n",
        "\"pattern databases\" : \"store costs for all states and use to find heuristics\",\n",
        "\"disjoint pattern databases\" : \"using two completely separate subproblems for pattern databases and adding them\",\n",
        "\"precomputation\" : \"helps with map searches and stuff. Calculations take long but only done once\",\n",
        "\"metalevel state space\" : \"learn to search better and minimize the balance of computational expense and path cost\",\n",
        "  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "85cb3d1d-4ade-4e78-b963-70bdabd2010f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A* expands no nodes with f(n) > C*, where C* is the optimal solution path cost. Biggest issue with A* is lots of memory use. Some solutions: only store state information on frontier or reached states, not both. Or remove states from the reached table when they aren’t needed (involves separation property and not allowing u-turns). Or keep reference counts and remove nodes from the table when there are no other ways to reach it. IDA* and RBFS use too little memory sometimes. IDA * only maintains the current cost limit and RBFS only keeps the alternate path and keeps linear space. They probably will reexamine same states multiple times.\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - uses goal information to target solutions for efficiency:\n* **Heuristic function** - estimated cost from a node to a goal\n* **Greedy best-first search** - f(n) = h(n). Picks lowest node based on heuristic only. Complete in finite spaces only. O(|V|) or O(bm) if good\n* **A* search** - best-first with f(n) = g(n) + h(n). Complete and potentially cost-optimal if heuristic is admissible\n* **Admissible** - optimistic, underestimates or exactly estimates distance to goal\n* **Consistency** - h(n) $\\leq$ c(n,a,n’) + h(n’). follows triangle inequality\n* **Contours** - topographical map like lines\n* **Monotonic** - cost always increases, each step has a positive value associated so as you go cost will increase\n* **Surely expanded nodes** - all nodes where cost is less than the cost of the optimal solution path\n* **Optimally efficient** - A* with consistent heuristic\n* **Pruning** - eliminating nodes based on cost or other factors without having to expand/examine them\n* **Satisficing** - not optimal/admissible but do well enough\n* **Inadmissible heuristic** - may overestimate costs in which case A* solution may not be optimal\n* **Weighted a* search** - value heuristic more and multiply it by a factor > 1\n* **Bounded suboptimal search** - solution within a factor of the optimal\n* **Bounded-cost search** - any solution where the cost is less than the boundary\n* **Unbounded-cost search** - want to find solution ASAP, doesn’t matter the cost\n* **Reference counts** - number of times a node has been found\n* **Beam search** - only keep certain amount of nodes with best costs. Incomplete, suboptimal. Limits frontier size\n* **Iterative-deepening a* search** - like iddfs without needing to keep everything in memory\n* **Recursive best-first search** - linear space, uses a limit variable to track best alternative path, if limit is hit, go to alternate\n* **Ma*** - memory bounded A*\n* **Sma *** - simplified MA*. Does A* until memory is full, removes the worst leaf. Complete if goal depth < memory size\n* **Effective branching factor b*** - N + 1 = 1 + b* + b*^2 + b*^d\n* **Effective depth** - O(b^(d-k))\n* **Dominates** - h2 >= h1 in all cases h2 dominates. H2 won’t expand more than h1\n* **Relaxed problem** - has fewer restrictions. All optimal solutions to og are also optimal to relaxed\n* **Subproblem** - also admissible heuristic. Working with fewer parts compared to the whole problem\n* **Pattern databases** - store costs for all states and use to find heuristics\n* **Disjoint pattern databases** - using two completely separate subproblems for pattern databases and adding them\n* **Precomputation** - helps with map searches and stuff. Calculations take long but only done once\n* **Metalevel state space** - learn to search better and minimize the balance of computational expense and path cost\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Max moves to a state of maximum, min moves to state of minimum value. Minimax algo is DFS complete O(b^m) time and O(bm) space if all actions are generated at once or O(m)) if actions are one at a time. For more than 2 player games, use a vector for each player's node/score.  \"\"\"\n",
        "chapter5_3 = \"\"\" Alpha is max (starts at - inf) and beta is min (starts at inf). With idea alpha beta pruning, effective branching becomes sqrt b instead with O(b^(m/2)). Randomly this is about O(b^(3m/4)). Good evaluation functions are fast (not too much of a computation) with high chances of actually winning. Forward pruning is type b, eliminates moves to save computation time but not necessarily optimal/does not look at everything. Probcut prunes moves that are probably outside the alpha beta window. \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" If an agent violates orderability, transitivity, continuity, substitutability, monotonicity, or decomposability, then it will act irrationally. \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"evaluation function\" : \"guess of who is winning in an adversarial game\",\n",
        "\"imperfect information\" : \"has randomness involved so not all info is available\",\n",
        "\"perfect information\" : \"all info is available and fully observable\",\n",
        "\"zero-sum\" : \"if it’s good for someone, it’s bad for someone else\",\n",
        "\"terminal test\" : \"tells you if the game is over\",\n",
        "\"utility function\" : \"a value to the player at the end of a game\",\n",
        "\"game tree\" : \"search tree that goes to the end of each game down the branches\",\n",
        "\"minimax search\" : \"max trying to win, increase score, min trying to win, decrease max’s score\",\n",
        "\"minimax values\" : \"the value at a state where both players play optimally until terminal game end\",\n",
        "\"minimax decision\" : \"the choice that a player makes to either maximize or minimize the utility score\",\n",
        "\"alpha-beta pruning\" : \"not checking branches if the min is lower than another branch's min when optimizing max\",\n",
        "\"type a strategy\" : \"looks at all moves up to a given depth\",\n",
        "\"type b strategy\" : \"follows good looking moves all the way through and doesn't pick moves that currently look bad\",\n",
        "\"cutoff test\" : \"assesses if at a terminal end or at a limit\",\n",
        "\"features\" : \"describe the state and its categories\",\n",
        "\"quiescent\" : \"positions where a big change in points or position will NOT occur\",\n",
        "\"horizon effect\" : \"an opponent's move that you can't avoid but will do harm and lower your standing but in longer times\",\n",
        "\"singular extensions\" : \"the best move choice clearly for a state\",\n",
        "\"forward pruning\" : \"eliminates moves that do not seem to be good but may be okay\",\n",
        "\"beam search\" : \"evaluated and look at only the n best moves. Might miss out on future best moves\",\n",
        "\"late move reduction\" : \"assumes that worse moves appear later so reduce depth when we search the later ones\",\n",
        "\"stochasitic games\" : \"games with randomness\",\n",
        "\"chance nodes\" : \"look at potential states based on randomness\",\n",
        "\"expected value\" : \"instead of minmax in stochastic games. Look at average outcome\",\n",
        "\"expectiminimax value\" : \"combine minimax and expected value to make best prediction move\",\n",
        "\"orderability\" : \"you have preferences\",\n",
        "\"transitivity\" : \"a > b and b > c then a > c\",\n",
        "\"continuity\" : \"if b is in the middle, then there is a probablility of A and C that yields B\",\n",
        "\"substitutability\" : \"if two are equal they can be interchanged\",\n",
        "\"monotonicity\" : \"agent has a preference for the one with a higher chance\",\n",
        "\"decomposability\" : \"combine two together\",\n",
        "\"preference elicitation\" : \"determining preferences based on what people select\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "10944f90-bfcb-4725-ce8c-ef75b3038db9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Max moves to a state of maximum, min moves to state of minimum value. Minimax algo is DFS complete O(b^m) time and O(bm) space if all actions are generated at once or O(m)) if actions are one at a time. For more than 2 player games, use a vector for each player's node/score.  \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Alpha is max (starts at - inf) and beta is min (starts at inf). With idea alpha beta pruning, effective branching becomes sqrt b instead with O(b^(m/2)). Randomly this is about O(b^(3m/4)). Good evaluation functions are fast (not too much of a computation) with high chances of actually winning. Forward pruning is type b, eliminates moves to save computation time but not necessarily optimal/does not look at everything. Probcut prunes moves that are probably outside the alpha beta window. \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n If an agent violates orderability, transitivity, continuity, substitutability, monotonicity, or decomposability, then it will act irrationally. \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Evaluation function** - guess of who is winning in an adversarial game\n* **Imperfect information** - has randomness involved so not all info is available\n* **Perfect information** - all info is available and fully observable\n* **Zero-sum** - if it’s good for someone, it’s bad for someone else\n* **Terminal test** - tells you if the game is over\n* **Utility function** - a value to the player at the end of a game\n* **Game tree** - search tree that goes to the end of each game down the branches\n* **Minimax search** - max trying to win, increase score, min trying to win, decrease max’s score\n* **Minimax values** - the value at a state where both players play optimally until terminal game end\n* **Minimax decision** - the choice that a player makes to either maximize or minimize the utility score\n* **Alpha-beta pruning** - not checking branches if the min is lower than another branch's min when optimizing max\n* **Type a strategy** - looks at all moves up to a given depth\n* **Type b strategy** - follows good looking moves all the way through and doesn't pick moves that currently look bad\n* **Cutoff test** - assesses if at a terminal end or at a limit\n* **Features** - describe the state and its categories\n* **Quiescent** - positions where a big change in points or position will NOT occur\n* **Horizon effect** - an opponent's move that you can't avoid but will do harm and lower your standing but in longer times\n* **Singular extensions** - the best move choice clearly for a state\n* **Forward pruning** - eliminates moves that do not seem to be good but may be okay\n* **Beam search** - evaluated and look at only the n best moves. Might miss out on future best moves\n* **Late move reduction** - assumes that worse moves appear later so reduce depth when we search the later ones\n* **Stochasitic games** - games with randomness\n* **Chance nodes** - look at potential states based on randomness\n* **Expected value** - instead of minmax in stochastic games. Look at average outcome\n* **Expectiminimax value** - combine minimax and expected value to make best prediction move\n* **Orderability** - you have preferences\n* **Transitivity** - a > b and b > c then a > c\n* **Continuity** - if b is in the middle, then there is a probablility of A and C that yields B\n* **Substitutability** - if two are equal they can be interchanged\n* **Monotonicity** - agent has a preference for the one with a higher chance\n* **Decomposability** - combine two together\n* **Preference elicitation** - determining preferences based on what people select\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Constraint satisfaction problems consist of a set of variables, a set of domains, and a set of constraints that allow combinations of values.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" AC-3 maintains a frontier of arcs where it hasall of the arcs. For each arc (x,y) it moves through, it makes x arc-consistent in regards to y. If a chance is made, we re-add to the queue all nodes (z,x) where z neighbors x (when x was changed). \"\"\"\n",
        "chapter6_3 = \"\"\" Variable selection fail first and value selection fail last. \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Tree CSP solved in linear time. To solve, pick a node to be the root and order such that each variable appears after its parent. Tree decompositions must have every variable from the og problem in a tree node. If two variables have a constraint, they need to be together in a tree node. If a variable is in two nodes in the tree, it must be in every node in the path between the two. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"relation\" : \"sets how variables can relate to each other, what values something can have based on rules\",\n",
        "\"assignments\"  : \"set values to the variables\",\n",
        "\"consistent\" : \"if all assignments are allowed and within the bounds of the rules\",\n",
        "\"complete assignment\" : \"every variable has something assigned to it\",\n",
        "\"solution\" : \"complete and consistent\", \n",
        "\"partial solution\" : \"consistent but not every variable has been assigned\",\n",
        "\"constraint graph\" : \"each node is a variable and each edge acts as a constraint between the nodes\",\n",
        "\"unary constraint\" : \"restains one variable with a value restriction\",\n",
        "\"binary constraint\" : \"two variables constrain each other\",\n",
        "\"binary CSP\" : \"binary and unary constraints only\",\n",
        "\"global constraint\" : \"any number of variables can fall under the constraint, does not have to be all\",\n",
        "\"constraint propagation\" : \"uses current restraints to reduce other options for other variables\",\n",
        "\"local consistency\" : \"remove inconsistent values through the neighbors in the graph\",\n",
        "\"node-consistent\" : \"a node meets the unary constraints\",\n",
        "\"arc-consistent\" : \"a node meets all the binary constraints\",\n",
        "\"path consistency\" : \"looks at triples of variables to further ensure binary constraints\",\n",
        "\"k-consistency\" : \"when a consistent value can be assigned to the kth variable if k-1 previous variables are consistent\",\n",
        "\"resource constraint\" : \"limits available resources that can be determined across part of the problem\",\n",
        "\"commutativity\" : \"sequence and order of actions does not matter\",\n",
        "\"minimum remaining value\" : \"heuristic where you pick the option with the fewest options left; fail first; most constrained variable\",\n",
        "\"degree heuristic\" : \"reducing branching by pickinig the variable with the most constraints on other unassigned nodes\",\n",
        "\"least-constraining value\" : \"heuristic that eliminates the fewest choices for its neighbors; most flexibility for others\",\n",
        "\"forward checking\" : \"checks with the neighbors after a variable is assigned for consistency; makes all of its neighbors arc consistent\",\n",
        "\"chronological backtracking\" : \"most recent backtracking point where a decision was made is redone\",\n",
        "\"conflict set\" : \"keep track of assignments that do not work for a node\",\n",
        "\"backjumping\" : \"goes back past the most recent assignment in the conflict set; already pruned by forward checking\",\n",
        "\"conflict-directed backjumping\" : \"the set with no consistent solution because it was caused with other subsequent variables\",\n",
        "\"constraint learning\" : \"find the variable in the conflict set that are most troublesome\",\n",
        "\"min-conflicts\" : \"heuristic where you pick the choice that gives the fewest conflicts with other variables\",\n",
        "\"tabu search\" : \"keep some recent states and do not go back to them; helps with plateaus with nodes of same constraint levels\",\n",
        "\"constraint weighting\" : \"search based on most important constraints first; helps with plateaus\",\n",
        "\"independent subproblems\" : \"Tasmania. Basically a separate connected component\",\n",
        "\"directional arc consistency\" : \"all arcs are consistent for xi xj when j > i\",\n",
        "\"cycle cutset\" : \"a subset where, once removed, the remaining constraint graph is a tree\",\n",
        "\"tree decomposition\" : \"each node is a set of variables\",\n",
        "\"tree width\" : \"the size of the largest node - 1; tree decomposition\", \n",
        "\"value symmetry\" : \"different ways to meet the same constraints for a group that all affects each other\",\n",
        "\"symmetry-breaking constraint\" : \"adding another constraint to break the symmetry\"\n",
        "   \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4f1c91ed-e4e3-49fe-a59f-1e3c3f936350"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Constraint satisfaction problems consist of a set of variables, a set of domains, and a set of constraints that allow combinations of values.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n AC-3 maintains a frontier of arcs where it hasall of the arcs. For each arc (x,y) it moves through, it makes x arc-consistent in regards to y. If a chance is made, we re-add to the queue all nodes (z,x) where z neighbors x (when x was changed). \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Variable selection fail first and value selection fail last. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Tree CSP solved in linear time. To solve, pick a node to be the root and order such that each variable appears after its parent. Tree decompositions must have every variable from the og problem in a tree node. If two variables have a constraint, they need to be together in a tree node. If a variable is in two nodes in the tree, it must be in every node in the path between the two. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Relation** - sets how variables can relate to each other, what values something can have based on rules\n* **Assignments** - set values to the variables\n* **Consistent** - if all assignments are allowed and within the bounds of the rules\n* **Complete assignment** - every variable has something assigned to it\n* **Solution** - complete and consistent\n* **Partial solution** - consistent but not every variable has been assigned\n* **Constraint graph** - each node is a variable and each edge acts as a constraint between the nodes\n* **Unary constraint** - restains one variable with a value restriction\n* **Binary constraint** - two variables constrain each other\n* **Binary csp** - binary and unary constraints only\n* **Global constraint** - any number of variables can fall under the constraint, does not have to be all\n* **Constraint propagation** - uses current restraints to reduce other options for other variables\n* **Local consistency** - remove inconsistent values through the neighbors in the graph\n* **Node-consistent** - a node meets the unary constraints\n* **Arc-consistent** - a node meets all the binary constraints\n* **Path consistency** - looks at triples of variables to further ensure binary constraints\n* **K-consistency** - when a consistent value can be assigned to the kth variable if k-1 previous variables are consistent\n* **Resource constraint** - limits available resources that can be determined across part of the problem\n* **Commutativity** - sequence and order of actions does not matter\n* **Minimum remaining value** - heuristic where you pick the option with the fewest options left; fail first; most constrained variable\n* **Degree heuristic** - reducing branching by pickinig the variable with the most constraints on other unassigned nodes\n* **Least-constraining value** - heuristic that eliminates the fewest choices for its neighbors; most flexibility for others\n* **Forward checking** - checks with the neighbors after a variable is assigned for consistency; makes all of its neighbors arc consistent\n* **Chronological backtracking** - most recent backtracking point where a decision was made is redone\n* **Conflict set** - keep track of assignments that do not work for a node\n* **Backjumping** - goes back past the most recent assignment in the conflict set; already pruned by forward checking\n* **Conflict-directed backjumping** - the set with no consistent solution because it was caused with other subsequent variables\n* **Constraint learning** - find the variable in the conflict set that are most troublesome\n* **Min-conflicts** - heuristic where you pick the choice that gives the fewest conflicts with other variables\n* **Tabu search** - keep some recent states and do not go back to them; helps with plateaus with nodes of same constraint levels\n* **Constraint weighting** - search based on most important constraints first; helps with plateaus\n* **Independent subproblems** - Tasmania. Basically a separate connected component\n* **Directional arc consistency** - all arcs are consistent for xi xj when j > i\n* **Cycle cutset** - a subset where, once removed, the remaining constraint graph is a tree\n* **Tree decomposition** - each node is a set of variables\n* **Tree width** - the size of the largest node - 1; tree decomposition\n* **Value symmetry** - different ways to meet the same constraints for a group that all affects each other\n* **Symmetry-breaking constraint** - adding another constraint to break the symmetry\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Agent tells the KB what it is perceiving and asks what to do. From this ask, reasoning about the world can be performed and what the outcomes of actions will be. Finally, program tells KB which action was done. \"\"\"\n",
        "chapter7_2 = \"\"\" We look for performance measures (points for gettign gold, losing points for falling or being eaten, minus one point for each action), environemnt (available area for the agent to act), actuators (what the agent can actually do), sensors (what the agent perceives). \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" 5 logical connectives. Not, And, Or, Implies, If and only if. Not operator has highest precedence. Not P is T iff P is F. P ^ Q is T iff both P and Q are T. P V Q is T iff EITHER P or Q is T. P -> Q is T unless P is T and Q is F. P <-> is T iff P and Q are both T or F.  \"\"\"\n",
        "chapter7_5 = \"\"\" 1. Eliminate <-> , then ->, then nots moved inwards, then distributivity law. Forward chaining is sound and complete. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning processes to determine their actions\",\n",
        "\"knowledge base\" : \"set of sentences that the agent knows\",\n",
        "\"knowledge representation language\" : \"how the sentence is actually expressed to the agent\",\n",
        "\"axiom\" : \"setnence that is given not derived\",\n",
        "\"inference\" : \"add to the KB by deriving information from already given sentences\",\n",
        "\"knowledge level\" : \"agents goals and what is knows/perceives\",\n",
        "\"declarative\" : \"tell the agent things one by one until it knows how to operate\",\n",
        "\"procedural\" : \"makes the desired behaviors by coding it into the agent\",\n",
        "\"entailment\" : \"logically follows based on another sentence; a entails b iff every model where a is true b is true\",\n",
        "\"logical inference\" : \"using entailment to make conclusions\",\n",
        "\"sound\" : \"aka truth preserving, when an inference only determines entailed sentences\",\n",
        "\"propositional logic\" : \"allowable sentences and rules for determining if a sentence is true for a model\",\n",
        "\"atomic sentence\" : \"has only one proposition symbol\",\n",
        "\"unit resolution\" : \"takes a literal and a clause to make a new clause; only resolve one pair at a time\",\n",
        "\"definite clause\" : \"disjunction of literals where one (exactly) is positive\",\n",
        "\"horn clause\" : \"disjunction of literals where no more than one is positive\",\n",
        "\"goal clauses\" : \"no positive literals\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 908
        },
        "outputId": "80ea25bb-7814-4248-bf4a-cb2fef977ada"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Agent tells the KB what it is perceiving and asks what to do. From this ask, reasoning about the world can be performed and what the outcomes of actions will be. Finally, program tells KB which action was done. \n\n## AIMA Chapter 7.2 The Wumpus World\n We look for performance measures (points for gettign gold, losing points for falling or being eaten, minus one point for each action), environemnt (available area for the agent to act), actuators (what the agent can actually do), sensors (what the agent perceives). \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 5 logical connectives. Not, And, Or, Implies, If and only if. Not operator has highest precedence. Not P is T iff P is F. P ^ Q is T iff both P and Q are T. P V Q is T iff EITHER P or Q is T. P -> Q is T unless P is T and Q is F. P <-> is T iff P and Q are both T or F.  \n\n## AIMA 7.5 Propositional Theorem Proving\n 1. Eliminate <-> , then ->, then nots moved inwards, then distributivity law. Forward chaining is sound and complete. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning processes to determine their actions\n* **Knowledge base** - set of sentences that the agent knows\n* **Knowledge representation language** - how the sentence is actually expressed to the agent\n* **Axiom** - setnence that is given not derived\n* **Inference** - add to the KB by deriving information from already given sentences\n* **Knowledge level** - agents goals and what is knows/perceives\n* **Declarative** - tell the agent things one by one until it knows how to operate\n* **Procedural** - makes the desired behaviors by coding it into the agent\n* **Entailment** - logically follows based on another sentence; a entails b iff every model where a is true b is true\n* **Logical inference** - using entailment to make conclusions\n* **Sound** - aka truth preserving, when an inference only determines entailed sentences\n* **Propositional logic** - allowable sentences and rules for determining if a sentence is true for a model\n* **Atomic sentence** - has only one proposition symbol\n* **Unit resolution** - takes a literal and a clause to make a new clause; only resolve one pair at a time\n* **Definite clause** - disjunction of literals where one (exactly) is positive\n* **Horn clause** - disjunction of literals where no more than one is positive\n* **Goal clauses** - no positive literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "8f2ca8be-45fc-4c77-8209-902b32fba478"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent’s decisions can be determined based on its current senses and also its percept sequence, just not anything that it hasn’t sensed yet. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rationality is measured by performance measure, knowledge of the area, available actions, and percept sequence.  \n\n## AIMA 2.3 The Nature of Environments\n There are competitive (game) multiagent environments compared to cooperative (taxi-drivers) multi-agent environments. \n\n## AIMA 2.4 The Structure of Agents\n The agent program takes the current precent, while the agent function uses the whole percept sequence. Randomization is typically not rational in a single agent environment. Learning agent has a critic (the performance standard), which gives feedback from information it gets from the sensors to the learning element, which provides changes to the performance element and learning goals to the problem generator. The performance element then gives the actuators the action to do and provides knowledge back  to the learning element. The problem generator also interfaces with the performance element, since it suggests actions. Problem generator explores a bit, while the performance element would stay with what it knows otherwise. Structured representations are usually the most expressive, followed by factored representation, followed by atomic. \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationally** - selecting the correct and logical action. Includes math, engineering, stats, etc.\n* **Turing test** - passes if a human can’t determine if replies are human or machine\n* **Natural language processing** - computer communicating well in English\n* **Knowledge representation** - save the information it learns\n* **Automated reasoning** - use reasoning to inform decisions/respond to queries\n* **Machine learning** - predict and change to situations based on previous patterns\n* **Total turing test** - like the turing test but with irl manipulation\n* **Computer vision** - helps know the area around the machine\n* **Robotics** - used to interact with the world\n* **Agent** - an actor who sees and acts upon an environment\n* **Rational agent** - actor to get an optimal solution, or at least expected optimal\n* **Standard model** - where an agent performs optimally (minimizes cost or maximizes gain)\n* **Limited rationality** - doing the best you can with information you have, computations are too long\n* **Value alignment problem** - goals must be same as people. Make sure computer doesn’t misbehave\n* **Weak ai** - Computers aren’t actually thinking\n* **Strong ai** - Computers making their own thoughts\n* **Embodied cognition** - include the whole body, not just brain. Everything in the environment\n* **Qualia** - experiencing the world, awareness, consciousness\n* **Actuators** - what an agent uses to operate on the environment\n* **Percept** - what an agent is sensing\n* **Percept sequence** - all things that the agent sensed, currently and in the past\n* **Agent function** - the action that is performed based on the percept sequence; agent behavior; abstract\n* **Agent program** - implementation of the agent function\n* **Consequentialism** - what outcome comes out of action and how good of an outcome\n* **Information gathering** - done before performing to change percepts\n* **Autonomy** - learn to balance previous knowledge\n* **Task environments** - encompasses all of PEAS\n* **Peas** - performance measure, environment, actuators, sensors\n* **Software agent** - performs in a virtual environment\n* **Fully observable** - Total relevant environment is seen. No internal state is needed\n* **Deterministic** - no uncertainty in a fully observable area\n* **Stochastic** - uses probabilities compared to nondeterministic which doesn’t\n* **Known** - outcomes for each action is known; like rules in a game\n* **Agent architecture** - physical form of the agent\n* **Simple reflex agent** - makes their decisions and acts based on the current environment and precept\n* **Condition-action rule** - if something do something\n* **Internal state** - uses precept sequence and history to keep track of unobservable parts of the environment that it previously learned about\n* **Transition model** - agent’s actions affecting the environment and how else the environment changes regardless of the agent\n* **Model-based agent** - combines transition model and sensor model to keep track of the environment\n* **Utility function** - measuring performance and trying to maximize utility\n* **Model-free agent** - determining best action without knowing how it alters the environment\n* **Learning element** - in a learning agent, makes the changes for the better\n* **Performance element** - learning agent, makes the actions\n* **Atomic representation** - indivisible states; different states are distinct and unrelated\n* **Factored representation** - use multiple pieces of information. Different states can share some properties while differing on others\n* **Structured representation** - different objects can be described together using relationships\n* **Localist representation** - everything can be represented in a memory location\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Four steps to solve a problem. 1. Goal formulation – understand the goal. 2. Problem formulation – states and actions to reach the goal. 3. Search – looking for the goal. Creates a sequence that can represent the solution when the goal is found. 4. Execute. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Search trees represent the state space, with each node as one state and edges are actions. Redundant path solutions: remember all previously reached states, not worry about repeating states (assembly problems), or check for cycles but not redundant paths. We can check if performance is complete, cost optimal, low time complexity and space complexity. Complexity can be measured by depth, maximum number of actions, or branching factor.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n IDDFS is O(bd) on space when there’s a solution or O(bm) if not. For time, O(b^d) if solution, O(b^m) if not. D is depth. B is branching. M is max tree depth. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - plan a sequence to find the goal; solved with atomic states\n* **Search** - process to find the goal for problem-solving agents\n* **Planning agents** - agents that take into account factored or structured data instead\n* **Informed** - agent knows where the goal is and how close it is\n* **Open-loop** - full observable, deterministic, known, leads to a set sequence. You don’t need percepts\n* **Closed-loop** - uses the percepts, in nondeterminstic or potentially incorrect models\n* **State space** - all potential states\n* **Problem** - state space, initial state, goal states, available actions, transition model, action cost function\n* **Transition model** - how an action affects the environment and state moving forward\n* **Action cost function** - calculates the cost of doing an action at a given state\n* **Path** - a sequence of states together from valid actions\n* **Optimal solution** - minimum cost path from initial state to goal\n* **Standardized problem** - common problem solving methods that can easily be compared\n* **Real-world problem** - non-standard with more useful solutions\n* **Grid world** - standardized problem where the agent can move to neighboring cells\n* **Egocentric actions** - actions from the robot’s point of view, rather than absolute directions\n* **Route-finding problem** - an example of a real-world problem\n* **Vlsi layout** - positions components on a chip for ideal cell layout and channel routing\n* **Frontier** - nodes that have been found but not explored, boundary between where states have been expanded and exterior nodes that haven’t\n* **Best-first search** - choose node with minimum value and expand that one\n* **Nodes** - have states, parents, actions, and cost\n* **Priority queue** - node with minimum cost first, used in best-first\n* **Fifo queue** - used in BFS\n* **Lifo queue** - used in DFS\n* **Graph search** - checks for redundant paths and tree-like searches do not\n* **Complete** - guaranteed to find a solution, algorithm is systematic\n* **Branching factor** - b. number of successors a node has that would need to be expanded\n* **Depth** - d. deepness, number in optimal path\n* **Breadth-first search** - complete in infinite spaces. Always produces path with minimum actions. O(b^d) time and space\n* **Early goal test** - if a node is a solution when discovered instead of popped\n* **Late goal test** - used by best-first, solution is determined after node is popped from frontier\n* **Uniform-cost search** - Dijkstra’s. Expands lowest-cost path next. Can be worse than O(b^d). Complete and cost-optimal.\n* **Depth-first search** - Expands deepest. Not cost-optimal. Incomplete. Smaller memory compared to bfs or best-first. O(bm)\n* **Backtracking search** - DFS alternate. Only one successor at a time instead of generating all successors. Successor changes current state.\n* **Depth-limited search** - DFS with a limit; pretend all nodes at limit are leaves. O(b^l) time and O(bl) space\n* **Diameter** - the furthest chain/farthest nodes apart, the number of steps between\n* **Iterative deepening search** - depth-limited search but increases l form 0 until a solution or max l\n* **Bidirectional search** - searches forward but also backwards from goal states\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A* expands no nodes with f(n) > C*, where C* is the optimal solution path cost. Biggest issue with A* is lots of memory use. Some solutions: only store state information on frontier or reached states, not both. Or remove states from the reached table when they aren’t needed (involves separation property and not allowing u-turns). Or keep reference counts and remove nodes from the table when there are no other ways to reach it. IDA* and RBFS use too little memory sometimes. IDA * only maintains the current cost limit and RBFS only keeps the alternate path and keeps linear space. They probably will reexamine same states multiple times.\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - uses goal information to target solutions for efficiency:\n* **Heuristic function** - estimated cost from a node to a goal\n* **Greedy best-first search** - f(n) = h(n). Picks lowest node based on heuristic only. Complete in finite spaces only. O(|V|) or O(bm) if good\n* **A* search** - best-first with f(n) = g(n) + h(n). Complete and potentially cost-optimal if heuristic is admissible\n* **Admissible** - optimistic, underestimates or exactly estimates distance to goal\n* **Consistency** - h(n) $\\leq$ c(n,a,n’) + h(n’). follows triangle inequality\n* **Contours** - topographical map like lines\n* **Monotonic** - cost always increases, each step has a positive value associated so as you go cost will increase\n* **Surely expanded nodes** - all nodes where cost is less than the cost of the optimal solution path\n* **Optimally efficient** - A* with consistent heuristic\n* **Pruning** - eliminating nodes based on cost or other factors without having to expand/examine them\n* **Satisficing** - not optimal/admissible but do well enough\n* **Inadmissible heuristic** - may overestimate costs in which case A* solution may not be optimal\n* **Weighted a* search** - value heuristic more and multiply it by a factor > 1\n* **Bounded suboptimal search** - solution within a factor of the optimal\n* **Bounded-cost search** - any solution where the cost is less than the boundary\n* **Unbounded-cost search** - want to find solution ASAP, doesn’t matter the cost\n* **Reference counts** - number of times a node has been found\n* **Beam search** - only keep certain amount of nodes with best costs. Incomplete, suboptimal. Limits frontier size\n* **Iterative-deepening a* search** - like iddfs without needing to keep everything in memory\n* **Recursive best-first search** - linear space, uses a limit variable to track best alternative path, if limit is hit, go to alternate\n* **Ma*** - memory bounded A*\n* **Sma *** - simplified MA*. Does A* until memory is full, removes the worst leaf. Complete if goal depth < memory size\n* **Effective branching factor b*** - N + 1 = 1 + b* + b*^2 + b*^d\n* **Effective depth** - O(b^(d-k))\n* **Dominates** - h2 >= h1 in all cases h2 dominates. H2 won’t expand more than h1\n* **Relaxed problem** - has fewer restrictions. All optimal solutions to og are also optimal to relaxed\n* **Subproblem** - also admissible heuristic. Working with fewer parts compared to the whole problem\n* **Pattern databases** - store costs for all states and use to find heuristics\n* **Disjoint pattern databases** - using two completely separate subproblems for pattern databases and adding them\n* **Precomputation** - helps with map searches and stuff. Calculations take long but only done once\n* **Metalevel state space** - learn to search better and minimize the balance of computational expense and path cost\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Max moves to a state of maximum, min moves to state of minimum value. Minimax algo is DFS complete O(b^m) time and O(bm) space if all actions are generated at once or O(m)) if actions are one at a time. For more than 2 player games, use a vector for each player's node/score.  \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Alpha is max (starts at - inf) and beta is min (starts at inf). With idea alpha beta pruning, effective branching becomes sqrt b instead with O(b^(m/2)). Randomly this is about O(b^(3m/4)). Good evaluation functions are fast (not too much of a computation) with high chances of actually winning. Forward pruning is type b, eliminates moves to save computation time but not necessarily optimal/does not look at everything. Probcut prunes moves that are probably outside the alpha beta window. \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n If an agent violates orderability, transitivity, continuity, substitutability, monotonicity, or decomposability, then it will act irrationally. \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Evaluation function** - guess of who is winning in an adversarial game\n* **Imperfect information** - has randomness involved so not all info is available\n* **Perfect information** - all info is available and fully observable\n* **Zero-sum** - if it’s good for someone, it’s bad for someone else\n* **Terminal test** - tells you if the game is over\n* **Utility function** - a value to the player at the end of a game\n* **Game tree** - search tree that goes to the end of each game down the branches\n* **Minimax search** - max trying to win, increase score, min trying to win, decrease max’s score\n* **Minimax values** - the value at a state where both players play optimally until terminal game end\n* **Minimax decision** - the choice that a player makes to either maximize or minimize the utility score\n* **Alpha-beta pruning** - not checking branches if the min is lower than another branch's min when optimizing max\n* **Type a strategy** - looks at all moves up to a given depth\n* **Type b strategy** - follows good looking moves all the way through and doesn't pick moves that currently look bad\n* **Cutoff test** - assesses if at a terminal end or at a limit\n* **Features** - describe the state and its categories\n* **Quiescent** - positions where a big change in points or position will NOT occur\n* **Horizon effect** - an opponent's move that you can't avoid but will do harm and lower your standing but in longer times\n* **Singular extensions** - the best move choice clearly for a state\n* **Forward pruning** - eliminates moves that do not seem to be good but may be okay\n* **Beam search** - evaluated and look at only the n best moves. Might miss out on future best moves\n* **Late move reduction** - assumes that worse moves appear later so reduce depth when we search the later ones\n* **Stochasitic games** - games with randomness\n* **Chance nodes** - look at potential states based on randomness\n* **Expected value** - instead of minmax in stochastic games. Look at average outcome\n* **Expectiminimax value** - combine minimax and expected value to make best prediction move\n* **Orderability** - you have preferences\n* **Transitivity** - a > b and b > c then a > c\n* **Continuity** - if b is in the middle, then there is a probablility of A and C that yields B\n* **Substitutability** - if two are equal they can be interchanged\n* **Monotonicity** - agent has a preference for the one with a higher chance\n* **Decomposability** - combine two together\n* **Preference elicitation** - determining preferences based on what people select\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Constraint satisfaction problems consist of a set of variables, a set of domains, and a set of constraints that allow combinations of values.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n AC-3 maintains a frontier of arcs where it hasall of the arcs. For each arc (x,y) it moves through, it makes x arc-consistent in regards to y. If a chance is made, we re-add to the queue all nodes (z,x) where z neighbors x (when x was changed). \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Variable selection fail first and value selection fail last. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Tree CSP solved in linear time. To solve, pick a node to be the root and order such that each variable appears after its parent. Tree decompositions must have every variable from the og problem in a tree node. If two variables have a constraint, they need to be together in a tree node. If a variable is in two nodes in the tree, it must be in every node in the path between the two. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Relation** - sets how variables can relate to each other, what values something can have based on rules\n* **Assignments** - set values to the variables\n* **Consistent** - if all assignments are allowed and within the bounds of the rules\n* **Complete assignment** - every variable has something assigned to it\n* **Solution** - complete and consistent\n* **Partial solution** - consistent but not every variable has been assigned\n* **Constraint graph** - each node is a variable and each edge acts as a constraint between the nodes\n* **Unary constraint** - restains one variable with a value restriction\n* **Binary constraint** - two variables constrain each other\n* **Binary csp** - binary and unary constraints only\n* **Global constraint** - any number of variables can fall under the constraint, does not have to be all\n* **Constraint propagation** - uses current restraints to reduce other options for other variables\n* **Local consistency** - remove inconsistent values through the neighbors in the graph\n* **Node-consistent** - a node meets the unary constraints\n* **Arc-consistent** - a node meets all the binary constraints\n* **Path consistency** - looks at triples of variables to further ensure binary constraints\n* **K-consistency** - when a consistent value can be assigned to the kth variable if k-1 previous variables are consistent\n* **Resource constraint** - limits available resources that can be determined across part of the problem\n* **Commutativity** - sequence and order of actions does not matter\n* **Minimum remaining value** - heuristic where you pick the option with the fewest options left; fail first; most constrained variable\n* **Degree heuristic** - reducing branching by pickinig the variable with the most constraints on other unassigned nodes\n* **Least-constraining value** - heuristic that eliminates the fewest choices for its neighbors; most flexibility for others\n* **Forward checking** - checks with the neighbors after a variable is assigned for consistency; makes all of its neighbors arc consistent\n* **Chronological backtracking** - most recent backtracking point where a decision was made is redone\n* **Conflict set** - keep track of assignments that do not work for a node\n* **Backjumping** - goes back past the most recent assignment in the conflict set; already pruned by forward checking\n* **Conflict-directed backjumping** - the set with no consistent solution because it was caused with other subsequent variables\n* **Constraint learning** - find the variable in the conflict set that are most troublesome\n* **Min-conflicts** - heuristic where you pick the choice that gives the fewest conflicts with other variables\n* **Tabu search** - keep some recent states and do not go back to them; helps with plateaus with nodes of same constraint levels\n* **Constraint weighting** - search based on most important constraints first; helps with plateaus\n* **Independent subproblems** - Tasmania. Basically a separate connected component\n* **Directional arc consistency** - all arcs are consistent for xi xj when j > i\n* **Cycle cutset** - a subset where, once removed, the remaining constraint graph is a tree\n* **Tree decomposition** - each node is a set of variables\n* **Tree width** - the size of the largest node - 1; tree decomposition\n* **Value symmetry** - different ways to meet the same constraints for a group that all affects each other\n* **Symmetry-breaking constraint** - adding another constraint to break the symmetry\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Agent tells the KB what it is perceiving and asks what to do. From this ask, reasoning about the world can be performed and what the outcomes of actions will be. Finally, program tells KB which action was done. \n\n## AIMA Chapter 7.2 The Wumpus World\n We look for performance measures (points for gettign gold, losing points for falling or being eaten, minus one point for each action), environemnt (available area for the agent to act), actuators (what the agent can actually do), sensors (what the agent perceives). \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 5 logical connectives. Not, And, Or, Implies, If and only if. Not operator has highest precedence. Not P is T iff P is F. P ^ Q is T iff both P and Q are T. P V Q is T iff EITHER P or Q is T. P -> Q is T unless P is T and Q is F. P <-> is T iff P and Q are both T or F.  \n\n## AIMA 7.5 Propositional Theorem Proving\n 1. Eliminate <-> , then ->, then nots moved inwards, then distributivity law. Forward chaining is sound and complete. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning processes to determine their actions\n* **Knowledge base** - set of sentences that the agent knows\n* **Knowledge representation language** - how the sentence is actually expressed to the agent\n* **Axiom** - setnence that is given not derived\n* **Inference** - add to the KB by deriving information from already given sentences\n* **Knowledge level** - agents goals and what is knows/perceives\n* **Declarative** - tell the agent things one by one until it knows how to operate\n* **Procedural** - makes the desired behaviors by coding it into the agent\n* **Entailment** - logically follows based on another sentence; a entails b iff every model where a is true b is true\n* **Logical inference** - using entailment to make conclusions\n* **Sound** - aka truth preserving, when an inference only determines entailed sentences\n* **Propositional logic** - allowable sentences and rules for determining if a sentence is true for a model\n* **Atomic sentence** - has only one proposition symbol\n* **Unit resolution** - takes a literal and a clause to make a new clause; only resolve one pair at a time\n* **Definite clause** - disjunction of literals where one (exactly) is positive\n* **Horn clause** - disjunction of literals where no more than one is positive\n* **Goal clauses** - no positive literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}