{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "12645d72-2d12-47d5-e1a7-7a32be43780a"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "21403c5d-9b58-4604-8a9b-340f4cf02811"
      },
      "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": 26,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 27,
      "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 = \"\"\" an abstract, formal definition of intelligence called rationality—loosely speaking, doing the “right thing.” The Turing test: \n",
        "A computer passes the test if a human interrogator, after posing some written questions, \n",
        "cannot tell whether the written responses come from a person or from a computer. \n",
        "natural language processing to communicate successfully in a human language;\n",
        "knowledge representation to store what it knows or hears;\n",
        "automated reasoning to answer questions and to draw new conclusions;\n",
        "machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n",
        "An agent is just something that acts. A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n",
        "\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking \n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Chinese room: computers generate no understanding. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n",
        "We use the term percept to refer to the content an agent’s sensors are perceiving. \n",
        "An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
        "Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action. \"\"\"\n",
        "chapter2_2 = \"\"\"consequentialism: we evaluate an agent’s behavior by its consequences.\n",
        "This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, \n",
        "given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly.\n",
        "Gather information and learn from it\n",
        "A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\"\"\"\n",
        "chapter2_3 = \"\"\" task environments, which are essentially the “problems” to which rational agents are the “solutions.”\n",
        "PEAS (Performance, Environment, Actuators, Sensors) description.\n",
        "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE\n",
        "If the agent has no sensors at all then the environment is unobservable.\n",
        "SINGLE-AGENT VS. MULTIAGENT\n",
        "Can be competitive or cooperative.\n",
        "Deterministic vs. nondeterministic.\n",
        "If the next state of the environment is completely determined by the current state and the action executed by the agent(s), \n",
        "then we say the environment is deterministic; otherwise, it is nondeterministic. \n",
        "EPISODIC VS. SEQUENTIAL\n",
        "sequential: current move will affect future moves.\n",
        "STATIC VS. DYNAMIC\n",
        "If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise, it is static.\n",
        "DISCRETE(chess) VS. CONTINUOUS(driving)\"\"\"\n",
        "chapter2_4 = \"\"\" agent program that implements the agent function—the mapping from percepts to actions. agent = architecture + program\n",
        "Agent program: take the current percept as input from the sensors and return an action to the actuators.\n",
        "simple reflex agent: select actions on the basis of the current percept, ignoring the rest of the percept history.\n",
        "model-based agent: combine sensor model and transition model to keep track of the world.\n",
        "Goal-based agents: reach or not, binary, straightforward\n",
        "Utility-based agents: use utility function to measure performance: maximize the expected utility\n",
        "Learning agents: penalty and reward\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Simple reflex agents respond directly to percepts, \n",
        "whereas model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept. \n",
        "Goal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.”\n",
        "All agents can improve their performance through learning\n",
        "Performance measure:\n",
        "• safe, fast, legal, comfortable, maximize profits\n",
        "Environment:\n",
        "• roads, other traffic, pedestrians, customers\n",
        "Actuators:\n",
        "• steering, accelerator, brake, signal, horn\n",
        "Sensors:\n",
        "• cameras, LiDAR, speedometer, GPS\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "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": 1082
        },
        "cellView": "form",
        "outputId": "26afd3a7-1796-4b4f-f510-2fe6dcf9a68b"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n an abstract, formal definition of intelligence called rationality—loosely speaking, doing the “right thing.” The Turing test: \nA computer passes the test if a human interrogator, after posing some written questions, \ncannot tell whether the written responses come from a person or from a computer. \nnatural language processing to communicate successfully in a human language;\nknowledge representation to store what it knows or hears;\nautomated reasoning to answer questions and to draw new conclusions;\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns.\nAn agent is just something that acts. A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking \n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room: computers generate no understanding. \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\nWe use the term percept to refer to the content an agent’s sensors are perceiving. \nAn agent’s percept sequence is the complete history of everything the agent has ever perceived.\nMathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nconsequentialism: we evaluate an agent’s behavior by its consequences.\nThis notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\nFor each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, \ngiven the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\nAn omniscient agent knows the actual outcome of its actions and can act accordingly.\nGather information and learn from it\nA rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\n\n## AIMA 2.3 The Nature of Environments\n task environments, which are essentially the “problems” to which rational agents are the “solutions.”\nPEAS (Performance, Environment, Actuators, Sensors) description.\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE\nIf the agent has no sensors at all then the environment is unobservable.\nSINGLE-AGENT VS. MULTIAGENT\nCan be competitive or cooperative.\nDeterministic vs. nondeterministic.\nIf the next state of the environment is completely determined by the current state and the action executed by the agent(s), \nthen we say the environment is deterministic; otherwise, it is nondeterministic. \nEPISODIC VS. SEQUENTIAL\nsequential: current move will affect future moves.\nSTATIC VS. DYNAMIC\nIf the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise, it is static.\nDISCRETE(chess) VS. CONTINUOUS(driving)\n\n## AIMA 2.4 The Structure of Agents\n agent program that implements the agent function—the mapping from percepts to actions. agent = architecture + program\nAgent program: take the current percept as input from the sensors and return an action to the actuators.\nsimple reflex agent: select actions on the basis of the current percept, ignoring the rest of the percept history.\nmodel-based agent: combine sensor model and transition model to keep track of the world.\nGoal-based agents: reach or not, binary, straightforward\nUtility-based agents: use utility function to measure performance: maximize the expected utility\nLearning agents: penalty and reward\n\n## Module 1 Lecture Notes\n Simple reflex agents respond directly to percepts, \nwhereas model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept. \nGoal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.”\nAll agents can improve their performance through learning\nPerformance measure:\n• safe, fast, legal, comfortable, maximize profits\nEnvironment:\n• roads, other traffic, pedestrians, customers\nActuators:\n• steering, accelerator, brake, signal, horn\nSensors:\n• cameras, LiDAR, speedometer, GPS\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Treat all data as objects and all objects have fixed type. Incompatible types are not allowed. \n",
        "Dynamic typing, automatically infer type.\n",
        "For functions,\n",
        "non-default argument should always precede default arguments.\n",
        "*args: accept non keyword arguments.\n",
        "Functions can be passed to other functions as inputs.\n",
        "A class can extend the definition of another class like this :class AI_Student(Student)\n",
        "Filtered List Comprehensions: li = [3, 6, 2, 7, 1, 9],[elem * 2 for elem in li if elem > 4],[12, 14, 18]\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"the ability of objects to change their values\",\n",
        "\"tuple\" : \"immutable ordered sequence of items, can be of mixed types\",\n",
        "\"string\": \"immutable\",\n",
        "\"list\" : \"Mutable ordered sequence of items of mixed types\",\n",
        "\"Dictionary\": \"unordered map by hashing, keys must be immutable\",\n",
        "\"Functions\" : \"can return multiple values as tuple, no overloading\",\n",
        "\"Magic Methods\" : \"allow user-defined classes to behave like built in types, similar to overloading\",\n",
        "\"iterator\" : \"Iterators are objects with a __next__() method\",\n",
        "\"generator\" : \"Functions that contain the yield keyword automatically return a generator when called\",\n",
        "}"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 396
        },
        "outputId": "7eb59280-c6ec-440e-9622-020821fb53ac"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Treat all data as objects and all objects have fixed type. Incompatible types are not allowed. \nDynamic typing, automatically infer type.\nFor functions,\nnon-default argument should always precede default arguments.\n*args: accept non keyword arguments.\nFunctions can be passed to other functions as inputs.\nA class can extend the definition of another class like this :class AI_Student(Student)\nFiltered List Comprehensions: li = [3, 6, 2, 7, 1, 9],[elem * 2 for elem in li if elem > 4],[12, 14, 18]\n\n\n## Module 2 Definitions\n* **Mutability** - the ability of objects to change their values\n* **Tuple** - immutable ordered sequence of items, can be of mixed types\n* **String** - immutable\n* **List** - Mutable ordered sequence of items of mixed types\n* **Dictionary** - unordered map by hashing, keys must be immutable\n* **Functions** - can return multiple values as tuple, no overloading\n* **Magic methods** - allow user-defined classes to behave like built in types, similar to overloading\n* **Iterator** - Iterators are objects with a __next__() method\n* **Generator** - Functions that contain the yield keyword automatically return a generator when called\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 = \"\"\" Form the problem and the goal, then search for solution. The agent can now execute the actions in the solution, one at a time.\n",
        "Search problem: state space, initial state, goal states, actions, transition model, action cost function and \n",
        "a solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions.\n",
        "Abstraction: The process of removing detail from a representation. \"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is intended to illustrate or exercise various problem-solving methods, \n",
        "A real-world problem, such as robot navigation, is one whose solutions people actually use \"\"\"\n",
        "chapter3_3 = \"\"\"  search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n",
        "Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. \n",
        "The root of the tree corresponds to the initial state of the problem.\n",
        "best-first search:On each iteration we choose a node on the frontier with minimum f(n) value.\n",
        "priority queue: irst pops the node with the minimum cost according to some evaluation function f, used in best-first search.\n",
        "FIFO queue: first pops the node that was added to the queue first, used in BFS.\n",
        "LIFO queue/ stack: pops first the most recently added node, used in DFS.\n",
        "COMPLETENESS: give a solution when there is one,  report failure when there is not.\n",
        "Cost be measured with space and time complexity.\n",
        "For implicit state space, performance can be measured by depth, maximum number of actions and the branching factor.\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" BFS: optimal and complete, uniform-cost search, spreads out in waves of uniform path-cost.\n",
        "DFS: not optimal, not guaranteed to return a solution.\n",
        "depth-limited search: set depth to be a constant value.\n",
        "Iterative deepening search: gradually increase the depth for searching.\n",
        "bidirectional search: go from initial state and goal state, hope they meet.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Uninformed search: All non-goal nodes in frontier look equally good\n",
        "Informed search: Some non-goal nodes can be ranked above others \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 712
        },
        "outputId": "5d4c0640-86f7-4f0a-8ef4-1a6fa21dbab4"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Form the problem and the goal, then search for solution. The agent can now execute the actions in the solution, one at a time.\nSearch problem: state space, initial state, goal states, actions, transition model, action cost function and \na solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions.\nAbstraction: The process of removing detail from a representation. \n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem-solving methods, \nA real-world problem, such as robot navigation, is one whose solutions people actually use \n\n## AIMA Chapter 3.3 Search Algorithms\n  search algorithm takes a search problem as input and returns a solution, or an indication of failure.\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem.\nbest-first search:On each iteration we choose a node on the frontier with minimum f(n) value.\npriority queue: irst pops the node with the minimum cost according to some evaluation function f, used in best-first search.\nFIFO queue: first pops the node that was added to the queue first, used in BFS.\nLIFO queue/ stack: pops first the most recently added node, used in DFS.\nCOMPLETENESS: give a solution when there is one,  report failure when there is not.\nCost be measured with space and time complexity.\nFor implicit state space, performance can be measured by depth, maximum number of actions and the branching factor.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: optimal and complete, uniform-cost search, spreads out in waves of uniform path-cost.\nDFS: not optimal, not guaranteed to return a solution.\ndepth-limited search: set depth to be a constant value.\nIterative deepening search: gradually increase the depth for searching.\nbidirectional search: go from initial state and goal state, hope they meet.\n\n## Module 3 Lecture Notes\n Uninformed search: All non-goal nodes in frontier look equally good\nInformed search: Some non-goal nodes can be ranked above others \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" informed search strategy—one that uses domain-specific hints about the location of goals,\n",
        "Greedy best-first search: expands first the node with the lowest h(n) value. f(n) = h(n)\n",
        "An admissible heuristic is one that never overestimates the cost to reach a goal. A* with a consistent heuristic is optimally efficient.\n",
        "If we allow inadmissible heuristic, we may miss the optimal solution.\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" One way to characterize the quality of a heuristic is the effective branching factor b*.\n",
        "A well-designed heuristic would have a value of b* close to 1. Another measurement:it reduces the effective depth by a constant \n",
        "k_h compared to the true depth. \n",
        "two heuristics that for any node n, h2(n) > h1(n), We thus say that h2 dominates h1.\n",
        "Admissible heuristic can be derived either from relaxed problems or sub problems\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Frontier: those states that are available for expanding (for applying legal actions to).\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "Best h*(n) = the true distance from the n to goal, dominates all other h(n).\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"estimate the cost from current state to a goal state.\", \n",
        "\"Greedy best-first search\" : \"f(n) = h(n)\",\n",
        "\"A* search\" : \"f(n) = g(n) + h(n)\",\n",
        "\"relaxed problem\": \"A problem that has fewer restrictions on the actions\",\n",
        "\"Beam Search\": \"the size of frontier has a limitation\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 528
        },
        "outputId": "7638b698-6347-4257-ca04-a1d51298c5f6"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n informed search strategy—one that uses domain-specific hints about the location of goals,\nGreedy best-first search: expands first the node with the lowest h(n) value. f(n) = h(n)\nAn admissible heuristic is one that never overestimates the cost to reach a goal. A* with a consistent heuristic is optimally efficient.\nIf we allow inadmissible heuristic, we may miss the optimal solution.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n One way to characterize the quality of a heuristic is the effective branching factor b*.\nA well-designed heuristic would have a value of b* close to 1. Another measurement:it reduces the effective depth by a constant \nk_h compared to the true depth. \ntwo heuristics that for any node n, h2(n) > h1(n), We thus say that h2 dominates h1.\nAdmissible heuristic can be derived either from relaxed problems or sub problems\n\n## Module 4 Lecture Notes\n Frontier: those states that are available for expanding (for applying legal actions to).\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nBest h*(n) = the true distance from the n to goal, dominates all other h(n).\n \n\n## Module 4 Definitions\n* **Heuristic function** - estimate the cost from current state to a goal state.\n* **Greedy best-first search** - f(n) = h(n)\n* **A* search** - f(n) = g(n) + h(n)\n* **Relaxed problem** - A problem that has fewer restrictions on the actions\n* **Beam search** - the size of frontier has a limitation\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 = \"\"\" eterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect information” is a synonym for “fully observable,”\n",
        "and “zero-sum” means that what is good for one player is just as bad for the other: there is no “win-win” outcome.\n",
        "state space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths.\n",
        "We define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" The minimax value is the utility (for max) of being in that state, \n",
        "assuming that both players play optimally from there to the end of the game.It is a recursive algorithm that proceeds all the way down to \n",
        "the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \n",
        "alpha-beta pruning: alpha : the value of the best (i.e., highest-value) choice we have found so far \n",
        "at any choice point along the path for max. Think: alpha “at least.\n",
        "Beta: the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. Think: Beta “at most.”\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \n",
        "Type A strategy considers all possible moves to a certain depth in the search tree, \n",
        "and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \n",
        "A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.”\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" A heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p. \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games: We don't know the outcome since it is random. we can only calculate the expected value of a position.\n",
        "For chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" The expected utility of an action given the evidence, \n",
        "is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n",
        "TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\n",
        "CONTINUITY, SUBSTITUTABILITY, MONOTONICITY, DECOMPOSABILITY\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions map from lotteries to real numbers, preference elicitation, \n",
        "involves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\n",
        "the agent exhibits a monotonic preference for more money\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Simpliest game environment: Multiagent, Static: No change while an agent is deliberating, Discrete: A finite set of percepts and actions, \n",
        "Fully observable: An agent's sensors give it the complete state of the environment,\n",
        "Strategic: The next state is determined by the current state and the action executed\n",
        "by the agent and the actions of one other agent. \n",
        "For a MAX node, the backed-up value is the maximum of the values of its\n",
        "children\n",
        "For a MIN node, the backed-up value is the minimum of the values of its children.\n",
        "MAX will never allow a move that could lead to a worse score (for MAX) than α\n",
        "MIN will never allow a move that could lead to a better score (for MAX) than β.\n",
        "A random variable represents an event whose outcome is unknown.\n",
        "A probability distribution is an assignment of weights to outcomes.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"minimax decision\" : \"Assume opponent play optimal step, and choose the step with max utility\", \n",
        "\"quiescent\" : \"position that all moves have been made\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 36,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "eaac6ba3-e9f0-4dc9-b57d-4b2fe4b738b6"
      },
      "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": 37,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n eterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect information” is a synonym for “fully observable,”\nand “zero-sum” means that what is good for one player is just as bad for the other: there is no “win-win” outcome.\nstate space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths.\nWe define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n The minimax value is the utility (for max) of being in that state, \nassuming that both players play optimally from there to the end of the game.It is a recursive algorithm that proceeds all the way down to \nthe leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \nalpha-beta pruning: alpha : the value of the best (i.e., highest-value) choice we have found so far \nat any choice point along the path for max. Think: alpha “at least.\nBeta: the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. Think: Beta “at most.”\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nType A strategy considers all possible moves to a certain depth in the search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \nA Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.”\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games: We don't know the outcome since it is random. we can only calculate the expected value of a position.\nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The expected utility of an action given the evidence, \nis just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\nTRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\nCONTINUITY, SUBSTITUTABILITY, MONOTONICITY, DECOMPOSABILITY\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers, preference elicitation, \ninvolves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\nthe agent exhibits a monotonic preference for more money\n\n\n## Module 5 Lecture Notes\n \nSimpliest game environment: Multiagent, Static: No change while an agent is deliberating, Discrete: A finite set of percepts and actions, \nFully observable: An agent's sensors give it the complete state of the environment,\nStrategic: The next state is determined by the current state and the action executed\nby the agent and the actions of one other agent. \nFor a MAX node, the backed-up value is the maximum of the values of its\nchildren\nFor a MIN node, the backed-up value is the minimum of the values of its children.\nMAX will never allow a move that could lead to a worse score (for MAX) than α\nMIN will never allow a move that could lead to a better score (for MAX) than β.\nA random variable represents an event whose outcome is unknown.\nA probability distribution is an assignment of weights to outcomes.\n\n\n\n## Module 5 Definitions\n* **Minimax decision** - Assume opponent play optimal step, and choose the step with max utility\n* **Quiescent** - position that all moves have been made\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 = \"\"\" A constraint satisfaction problem consists of X(a set of variables), D(a set of domains, one for each variable)\n",
        " and C(a set of constraints that specify allowable combinations of values). \n",
        " An assignment that does not violate any constraints is called a consistent or legal assignment.\n",
        " A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. \n",
        " A partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n",
        " It can be helpful to visualize a CSP as a constraint graph.\n",
        " The simplest kind of CSP involves variables that have discrete, finite domains.\n",
        " unary constraint: restricts the value of a single variable.\n",
        " A binary constraint relates two variables.\n",
        " global constraint: ex: all of the variables involved in the constraint must have different values.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" constraint propagation: using the constraints to reduce the number of legal values for a variable.\n",
        "A single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
        "arc-consistent1 if every value in its domain satisfies the variable’s binary constraints.\n",
        "enforcing arc consistency is called AC-3.\n",
        "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "A CSP is -consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \n",
        "a consistent value can always be assigned to any kth variable.\n",
        "A CSP is strongly -consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, ...all the way down to 1-consistent.\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" a crucial property of CSPs: commutativity.\n",
        "choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\n",
        "degree heuristic: selecting the variable that is involved in the largest number of constraints on other unassigned variables.\n",
        "least-constraining-value heuristic: it prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
        "forward checking. Whenever a variable is assigned, the forward-checking process establishes arc consistency for it.\n",
        "MAC: backtrack when AC-3 failed.\n",
        "chronological backtracking: back up to the preceding variable and try a different value for it.\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. \n",
        "This set of variables, along with their corresponding values, is called a no-good.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\n",
        "tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. \"\"\"\n",
        "chapter6_5 = \"\"\"tree decomposition of the constraint graph: a transformation of the original graph into a \n",
        "tree where each node in the tree consists of a set of variables, \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Constraint graph: nodes are variables, arcs are (binary) constraints\n",
        "Constraint graph simplifies search.\n",
        "Constraint propagation (inference):Eliminates possible values for a variable\n",
        "if the value would violate local consistency.\n",
        "Waltz/Mackworth Constraint Propagation Algorithm: 1. Assign every node in the constraint graph a set of all\n",
        "possible values 2. Repeat until there is no change in the set of values associated with any node.\n",
        "AC-3: worst case:If there are d values, checking arc (i,j) takes O(d2 ) time. \n",
        "Each arc (i,j) can only be inserted into the queue d times. Worst case complexity: O(n2d3).\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 38,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 932
        },
        "outputId": "8cfea3dc-f253-4945-90b2-42b10fe8c635"
      },
      "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": 39,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of X(a set of variables), D(a set of domains, one for each variable)\n and C(a set of constraints that specify allowable combinations of values). \n An assignment that does not violate any constraints is called a consistent or legal assignment.\n A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. \n A partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n It can be helpful to visualize a CSP as a constraint graph.\n The simplest kind of CSP involves variables that have discrete, finite domains.\n unary constraint: restricts the value of a single variable.\n A binary constraint relates two variables.\n global constraint: ex: all of the variables involved in the constraint must have different values.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a variable.\nA single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\narc-consistent1 if every value in its domain satisfies the variable’s binary constraints.\nenforcing arc consistency is called AC-3.\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\nA CSP is -consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \na consistent value can always be assigned to any kth variable.\nA CSP is strongly -consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, ...all the way down to 1-consistent.\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n a crucial property of CSPs: commutativity.\nchoosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\ndegree heuristic: selecting the variable that is involved in the largest number of constraints on other unassigned variables.\nleast-constraining-value heuristic: it prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\nforward checking. Whenever a variable is assigned, the forward-checking process establishes arc consistency for it.\nMAC: backtrack when AC-3 failed.\nchronological backtracking: back up to the preceding variable and try a different value for it.\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. \nThis set of variables, along with their corresponding values, is called a no-good.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\ntabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. \n\n## AIMA Chapter 6.5 The Structure of Problems\ntree decomposition of the constraint graph: a transformation of the original graph into a \ntree where each node in the tree consists of a set of variables, \n\n## Module 6 Lecture Notes\n Constraint graph: nodes are variables, arcs are (binary) constraints\nConstraint graph simplifies search.\nConstraint propagation (inference):Eliminates possible values for a variable\nif the value would violate local consistency.\nWaltz/Mackworth Constraint Propagation Algorithm: 1. Assign every node in the constraint graph a set of all\npossible values 2. Repeat until there is no change in the set of values associated with any node.\nAC-3: worst case:If there are d values, checking arc (i,j) takes O(d2 ) time. \nEach arc (i,j) can only be inserted into the queue d times. Worst case complexity: O(n2d3).\n\n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\n",
        "A knowledge base is a set of sentences. \n",
        "Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. \n",
        "When the sentence is taken as being given without being derived from other sentences, we call it an axiom.\n",
        "inference—that is, deriving new sentences from old.\n",
        "declarative approach: Starting with an empty knowledge base, \n",
        "the agent designer can Tell sentences one by one until the agent knows how to operate in its environment.\n",
        "procedural approach encodes desired behaviors directly as program code.\"\"\"\n",
        "chapter7_2 = \"\"\" A cautious agent will move only into a square that it knows to be OK.\n",
        "agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct.\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.\n",
        "A logic must also define the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world.\n",
        "If a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha. \n",
        "logical entailment between sentences— a sentence follows logically from another sentence. \n",
        "An inference algorithm that derives only entailed sentences is called sound or truth-preserving.\n",
        "The property of completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed.\"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\n",
        "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n",
        "a model simply sets the truth value—true or false—for every proposition symbol. \"\"\"\n",
        "chapter7_5 = \"\"\"theorem proving—applying rules of inference directly to the sentences in our knowledge base to \n",
        "construct a proof of the desired sentence without consulting models. \n",
        "Two sentences alpha and beta are logically equivalent if they are true in the same set of models.\n",
        "A sentence is valid if it is true in all models.Valid sentences are also known as tautologies.\n",
        "A sentence is satisfiable if it is true in, or satisfied by, some model.\n",
        "inference rules that can be applied to derive a proof.\n",
        "monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"If ℓi and m are complementary literals, which means that one is the negation of\n",
        "another, then we can eliminate them via unit resolution.\n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n",
        "Clauses are disjunctions of literals.\n",
        "1. Eliminate ⇔ by replacing alpha ⇔ β with (alpha ⟹ β) ⋀ (β ⟹alpha)\n",
        "2. Eliminate ⟹ by replacing alpha ⟹ β with ¬alpha ⋁ β\n",
        "3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\n",
        "distributivity law to distribute ⋁ over ⋀ wherever possible.\n",
        "Inference procedures based on resolution work using the principle of proof by\n",
        "contradiction.\n",
        "To show KB⊨alpha then we can show that KB ⋀ ¬alpha is unsatisfiable. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 40,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 980
        },
        "outputId": "efdf2b37-ede9-4c0f-acce-53f08fb55fb8"
      },
      "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": 41,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\nA knowledge base is a set of sentences. \nEach sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. \nWhen the sentence is taken as being given without being derived from other sentences, we call it an axiom.\ninference—that is, deriving new sentences from old.\ndeclarative approach: Starting with an empty knowledge base, \nthe agent designer can Tell sentences one by one until the agent knows how to operate in its environment.\nprocedural approach encodes desired behaviors directly as program code.\n\n## AIMA Chapter 7.2 The Wumpus World\n A cautious agent will move only into a square that it knows to be OK.\nagent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct.\n\n\n## AIMA Chapter 7.3 Logic\n sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.\nA logic must also define the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world.\nIf a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha. \nlogical entailment between sentences— a sentence follows logically from another sentence. \nAn inference algorithm that derives only entailed sentences is called sound or truth-preserving.\nThe property of completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\na model simply sets the truth value—true or false—for every proposition symbol. \n\n## AIMA 7.5 Propositional Theorem Proving\ntheorem proving—applying rules of inference directly to the sentences in our knowledge base to \nconstruct a proof of the desired sentence without consulting models. \nTwo sentences alpha and beta are logically equivalent if they are true in the same set of models.\nA sentence is valid if it is true in all models.Valid sentences are also known as tautologies.\nA sentence is satisfiable if it is true in, or satisfied by, some model.\ninference rules that can be applied to derive a proof.\nmonotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n\n## Module 7 Lecture Notes\nIf ℓi and m are complementary literals, which means that one is the negation of\nanother, then we can eliminate them via unit resolution.\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals.\n1. Eliminate ⇔ by replacing alpha ⇔ β with (alpha ⟹ β) ⋀ (β ⟹alpha)\n2. Eliminate ⟹ by replacing alpha ⟹ β with ¬alpha ⋁ β\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.\nInference procedures based on resolution work using the principle of proof by\ncontradiction.\nTo show KB⊨alpha then we can show that KB ⋀ ¬alpha is unsatisfiable. \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "d8b98932-b80e-442a-c72a-8a090419772d"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n an abstract, formal definition of intelligence called rationality—loosely speaking, doing the “right thing.” The Turing test: \nA computer passes the test if a human interrogator, after posing some written questions, \ncannot tell whether the written responses come from a person or from a computer. \nnatural language processing to communicate successfully in a human language;\nknowledge representation to store what it knows or hears;\nautomated reasoning to answer questions and to draw new conclusions;\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns.\nAn agent is just something that acts. A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking \n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room: computers generate no understanding. \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\nWe use the term percept to refer to the content an agent’s sensors are perceiving. \nAn agent’s percept sequence is the complete history of everything the agent has ever perceived.\nMathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nconsequentialism: we evaluate an agent’s behavior by its consequences.\nThis notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\nFor each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, \ngiven the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\nAn omniscient agent knows the actual outcome of its actions and can act accordingly.\nGather information and learn from it\nA rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\n\n## AIMA 2.3 The Nature of Environments\n task environments, which are essentially the “problems” to which rational agents are the “solutions.”\nPEAS (Performance, Environment, Actuators, Sensors) description.\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE\nIf the agent has no sensors at all then the environment is unobservable.\nSINGLE-AGENT VS. MULTIAGENT\nCan be competitive or cooperative.\nDeterministic vs. nondeterministic.\nIf the next state of the environment is completely determined by the current state and the action executed by the agent(s), \nthen we say the environment is deterministic; otherwise, it is nondeterministic. \nEPISODIC VS. SEQUENTIAL\nsequential: current move will affect future moves.\nSTATIC VS. DYNAMIC\nIf the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise, it is static.\nDISCRETE(chess) VS. CONTINUOUS(driving)\n\n## AIMA 2.4 The Structure of Agents\n agent program that implements the agent function—the mapping from percepts to actions. agent = architecture + program\nAgent program: take the current percept as input from the sensors and return an action to the actuators.\nsimple reflex agent: select actions on the basis of the current percept, ignoring the rest of the percept history.\nmodel-based agent: combine sensor model and transition model to keep track of the world.\nGoal-based agents: reach or not, binary, straightforward\nUtility-based agents: use utility function to measure performance: maximize the expected utility\nLearning agents: penalty and reward\n\n## Module 1 Lecture Notes\n Simple reflex agents respond directly to percepts, \nwhereas model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept. \nGoal-based agents act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.”\nAll agents can improve their performance through learning\nPerformance measure:\n• safe, fast, legal, comfortable, maximize profits\nEnvironment:\n• roads, other traffic, pedestrians, customers\nActuators:\n• steering, accelerator, brake, signal, horn\nSensors:\n• cameras, LiDAR, speedometer, GPS\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Treat all data as objects and all objects have fixed type. Incompatible types are not allowed. \nDynamic typing, automatically infer type.\nFor functions,\nnon-default argument should always precede default arguments.\n*args: accept non keyword arguments.\nFunctions can be passed to other functions as inputs.\nA class can extend the definition of another class like this :class AI_Student(Student)\nFiltered List Comprehensions: li = [3, 6, 2, 7, 1, 9],[elem * 2 for elem in li if elem > 4],[12, 14, 18]\n\n\n## Module 2 Definitions\n* **Mutability** - the ability of objects to change their values\n* **Tuple** - immutable ordered sequence of items, can be of mixed types\n* **String** - immutable\n* **List** - Mutable ordered sequence of items of mixed types\n* **Dictionary** - unordered map by hashing, keys must be immutable\n* **Functions** - can return multiple values as tuple, no overloading\n* **Magic methods** - allow user-defined classes to behave like built in types, similar to overloading\n* **Iterator** - Iterators are objects with a __next__() method\n* **Generator** - Functions that contain the yield keyword automatically return a generator when called\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Form the problem and the goal, then search for solution. The agent can now execute the actions in the solution, one at a time.\nSearch problem: state space, initial state, goal states, actions, transition model, action cost function and \na solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions.\nAbstraction: The process of removing detail from a representation. \n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem-solving methods, \nA real-world problem, such as robot navigation, is one whose solutions people actually use \n\n## AIMA Chapter 3.3 Search Algorithms\n  search algorithm takes a search problem as input and returns a solution, or an indication of failure.\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. \nThe root of the tree corresponds to the initial state of the problem.\nbest-first search:On each iteration we choose a node on the frontier with minimum f(n) value.\npriority queue: irst pops the node with the minimum cost according to some evaluation function f, used in best-first search.\nFIFO queue: first pops the node that was added to the queue first, used in BFS.\nLIFO queue/ stack: pops first the most recently added node, used in DFS.\nCOMPLETENESS: give a solution when there is one,  report failure when there is not.\nCost be measured with space and time complexity.\nFor implicit state space, performance can be measured by depth, maximum number of actions and the branching factor.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: optimal and complete, uniform-cost search, spreads out in waves of uniform path-cost.\nDFS: not optimal, not guaranteed to return a solution.\ndepth-limited search: set depth to be a constant value.\nIterative deepening search: gradually increase the depth for searching.\nbidirectional search: go from initial state and goal state, hope they meet.\n\n## Module 3 Lecture Notes\n Uninformed search: All non-goal nodes in frontier look equally good\nInformed search: Some non-goal nodes can be ranked above others \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n informed search strategy—one that uses domain-specific hints about the location of goals,\nGreedy best-first search: expands first the node with the lowest h(n) value. f(n) = h(n)\nAn admissible heuristic is one that never overestimates the cost to reach a goal. A* with a consistent heuristic is optimally efficient.\nIf we allow inadmissible heuristic, we may miss the optimal solution.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n One way to characterize the quality of a heuristic is the effective branching factor b*.\nA well-designed heuristic would have a value of b* close to 1. Another measurement:it reduces the effective depth by a constant \nk_h compared to the true depth. \ntwo heuristics that for any node n, h2(n) > h1(n), We thus say that h2 dominates h1.\nAdmissible heuristic can be derived either from relaxed problems or sub problems\n\n## Module 4 Lecture Notes\n Frontier: those states that are available for expanding (for applying legal actions to).\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nBest h*(n) = the true distance from the n to goal, dominates all other h(n).\n \n\n## Module 4 Definitions\n* **Heuristic function** - estimate the cost from current state to a goal state.\n* **Greedy best-first search** - f(n) = h(n)\n* **A* search** - f(n) = g(n) + h(n)\n* **Relaxed problem** - A problem that has fewer restrictions on the actions\n* **Beam search** - the size of frontier has a limitation\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n eterministic, two-player, turn-taking, perfect information, zero-sum games. “Perfect information” is a synonym for “fully observable,”\nand “zero-sum” means that what is good for one player is just as bad for the other: there is no “win-win” outcome.\nstate space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths.\nWe define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n The minimax value is the utility (for max) of being in that state, \nassuming that both players play optimally from there to the end of the game.It is a recursive algorithm that proceeds all the way down to \nthe leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \nalpha-beta pruning: alpha : the value of the best (i.e., highest-value) choice we have found so far \nat any choice point along the path for max. Think: alpha “at least.\nBeta: the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for min. Think: Beta “at most.”\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nType A strategy considers all possible moves to a certain depth in the search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \nA Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.”\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function Eval(s,p) returns an estimate of the expected utility of state s to player p. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games: We don't know the outcome since it is random. we can only calculate the expected value of a position.\nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The expected utility of an action given the evidence, \nis just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\nTRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\nCONTINUITY, SUBSTITUTABILITY, MONOTONICITY, DECOMPOSABILITY\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers, preference elicitation, \ninvolves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\nthe agent exhibits a monotonic preference for more money\n\n\n## Module 5 Lecture Notes\n \nSimpliest game environment: Multiagent, Static: No change while an agent is deliberating, Discrete: A finite set of percepts and actions, \nFully observable: An agent's sensors give it the complete state of the environment,\nStrategic: The next state is determined by the current state and the action executed\nby the agent and the actions of one other agent. \nFor a MAX node, the backed-up value is the maximum of the values of its\nchildren\nFor a MIN node, the backed-up value is the minimum of the values of its children.\nMAX will never allow a move that could lead to a worse score (for MAX) than α\nMIN will never allow a move that could lead to a better score (for MAX) than β.\nA random variable represents an event whose outcome is unknown.\nA probability distribution is an assignment of weights to outcomes.\n\n\n\n## Module 5 Definitions\n* **Minimax decision** - Assume opponent play optimal step, and choose the step with max utility\n* **Quiescent** - position that all moves have been made\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of X(a set of variables), D(a set of domains, one for each variable)\n and C(a set of constraints that specify allowable combinations of values). \n An assignment that does not violate any constraints is called a consistent or legal assignment.\n A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. \n A partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n It can be helpful to visualize a CSP as a constraint graph.\n The simplest kind of CSP involves variables that have discrete, finite domains.\n unary constraint: restricts the value of a single variable.\n A binary constraint relates two variables.\n global constraint: ex: all of the variables involved in the constraint must have different values.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a variable.\nA single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\narc-consistent1 if every value in its domain satisfies the variable’s binary constraints.\nenforcing arc consistency is called AC-3.\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\nA CSP is -consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \na consistent value can always be assigned to any kth variable.\nA CSP is strongly -consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, ...all the way down to 1-consistent.\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n a crucial property of CSPs: commutativity.\nchoosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\ndegree heuristic: selecting the variable that is involved in the largest number of constraints on other unassigned variables.\nleast-constraining-value heuristic: it prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\nforward checking. Whenever a variable is assigned, the forward-checking process establishes arc consistency for it.\nMAC: backtrack when AC-3 failed.\nchronological backtracking: back up to the preceding variable and try a different value for it.\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. \nThis set of variables, along with their corresponding values, is called a no-good.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\ntabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. \n\n## AIMA Chapter 6.5 The Structure of Problems\ntree decomposition of the constraint graph: a transformation of the original graph into a \ntree where each node in the tree consists of a set of variables, \n\n## Module 6 Lecture Notes\n Constraint graph: nodes are variables, arcs are (binary) constraints\nConstraint graph simplifies search.\nConstraint propagation (inference):Eliminates possible values for a variable\nif the value would violate local consistency.\nWaltz/Mackworth Constraint Propagation Algorithm: 1. Assign every node in the constraint graph a set of all\npossible values 2. Repeat until there is no change in the set of values associated with any node.\nAC-3: worst case:If there are d values, checking arc (i,j) takes O(d2 ) time. \nEach arc (i,j) can only be inserted into the queue d times. Worst case complexity: O(n2d3).\n\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\nA knowledge base is a set of sentences. \nEach sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. \nWhen the sentence is taken as being given without being derived from other sentences, we call it an axiom.\ninference—that is, deriving new sentences from old.\ndeclarative approach: Starting with an empty knowledge base, \nthe agent designer can Tell sentences one by one until the agent knows how to operate in its environment.\nprocedural approach encodes desired behaviors directly as program code.\n\n## AIMA Chapter 7.2 The Wumpus World\n A cautious agent will move only into a square that it knows to be OK.\nagent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct.\n\n\n## AIMA Chapter 7.3 Logic\n sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.\nA logic must also define the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world.\nIf a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha. \nlogical entailment between sentences— a sentence follows logically from another sentence. \nAn inference algorithm that derives only entailed sentences is called sound or truth-preserving.\nThe property of completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\na model simply sets the truth value—true or false—for every proposition symbol. \n\n## AIMA 7.5 Propositional Theorem Proving\ntheorem proving—applying rules of inference directly to the sentences in our knowledge base to \nconstruct a proof of the desired sentence without consulting models. \nTwo sentences alpha and beta are logically equivalent if they are true in the same set of models.\nA sentence is valid if it is true in all models.Valid sentences are also known as tautologies.\nA sentence is satisfiable if it is true in, or satisfied by, some model.\ninference rules that can be applied to derive a proof.\nmonotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n\n## Module 7 Lecture Notes\nIf ℓi and m are complementary literals, which means that one is the negation of\nanother, then we can eliminate them via unit resolution.\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nClauses are disjunctions of literals.\n1. Eliminate ⇔ by replacing alpha ⇔ β with (alpha ⟹ β) ⋀ (β ⟹alpha)\n2. Eliminate ⟹ by replacing alpha ⟹ β with ¬alpha ⋁ β\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.\nInference procedures based on resolution work using the principle of proof by\ncontradiction.\nTo show KB⊨alpha then we can show that KB ⋀ ¬alpha is unsatisfiable. \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}