{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0f73caac-370a-4e83-ab18-1775e016022b"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "99f97f7c-07d0-423a-d953-9c1e0e44085b"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"rationality. Can think humanly. Rationaly agent. An agent is just something that acts (agent comes from the Latin agere, to do).\\\n",
        "A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\\\n",
        "Acting humanly: The Turing test approach. Thinking humanly: The cognitive modeling approach. introspection, psychological experiments, brain imaging\\\n",
        "Think like people, think rationally, act like people, act rationally\\\n",
        "An agent is anything that perceives its environment through sensors and can act on its environment through actuators.\\\n",
        "A percept is the agent’s perceptual inputs at any given instance.\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 = \"\"\" Vision is a perceptual channel that accepts a stimulus and reports some representation of the world. \\\n",
        "Most agents that use vision use passive sensing—they do not need to send out light to see. \\\n",
        "In contrast, active sensing involves sending out a signal such as radar or ultrasound, and sensing a reflection.\\\n",
        "A feature is a number obtained by applying simple computations to an image. Very use- ful information can be obtained directly from features.\\\n",
        "This feature extraction approach emphasizes simple, direct computations applied to sensor responses.\\\n",
        "The model-based approach to vision uses two kinds of models.\\\n",
        "An object model could be the kind of precise geometric model produced by computer aided design systems. \n",
        "The two core problems of computer vision are reconstruction, where an agent builds a model of the world from\\\n",
        "an image or a set of images, and recognition, where an agent draws distinctions among the objects it encounters\n",
        "based on visual and other information.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" This effect is known as foreshortening (Figure 27.1). Models of these effects are essential for building competent object recognition systems and also yield powerful cues for reconstructing geometry.\\\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract,\\\n",
        "and so on for actuators. A robotic agent might have cameras and infrared range finders for sensors and various\\\n",
        "motors for actuators. A software agent receives file contents, network packets, and human input as sensory inputs and acts on the\\\n",
        "environment by writing files, sending network packets, and displaying information or generating sounds.\\\n",
        "We use the term percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequence\\\n",
        "is the complete history of everything the agent has ever perceived.\\\n",
        "Mathematically speak- ing, we say that an agent’s behavior is described by the agent function that maps any\\\n",
        "given percept sequence to an action.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"A rational agent is one that does the right thing. Obviously, doing the right thing is better\\\n",
        "than doing the wrong thing, but what does it mean to do the right thing.\\\n",
        "Moral philosophy has developed several different notions of the “right thing,”\\\n",
        "but AI has generally stuck to one notion called consequentialism.\\\n",
        "This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\n",
        "This leads to a definition of a rational agent:\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to\\\n",
        "maximize its performance measure, given the evidence provided by the percept sequence\\\n",
        "and whatever built-in knowledge the agent has.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"An omniscient agent knows the actual outcome of its actions and can act\\\n",
        "accordingly; but omniscience is impossible in reality\\\n",
        "First, however, we must think about task environments, which are essentially the “problems”\\\n",
        "to which rational agents are the “solutions.” We begin by showing how to specify a task environment,\\\n",
        "illustrating the process with a number of examples.\"\"\"\n",
        "chapter2_4 = \"\"\"The job of AI is to design an agent program that implements the agent function the mapping\\\n",
        "from percepts to actions. We assume this program will run on some sort of computing device with physical sensors\\\n",
        "and actuators—we call this the agent architecture:\n",
        "agent = architecture + program .\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"A rational agent is an agent that perceives its environment and and behaves rationally\\\n",
        "AI is usually concerned with Consequentialism.\\\n",
        "Informally, we expect that it will do the right thing in all circumstances.\\\n",
        "An objective criterion for success of an agent's behavior\\\n",
        "given the evidence provided by the percept sequence.\\\n",
        "It is better to design performance measures according to what you want to be\\\n",
        "achieved in the environment, rather than how you think the agent should behave\\\n",
        "For each possible percept sequence P\\\n",
        "a rational agent selects an action\\\n",
        "to maximize its performance measure\\\n",
        "Caveat: computational limitations make complete rationality unachievable\\\n",
        "For each possible percept sequence P,\\\n",
        "a rational agent selects an action a\\\n",
        "that maximizes the expected value of its performance measure\\\n",
        "To design a rational agent we need to specify a task environment\\\n",
        "a problem specification for which the agent is a solution\\\n",
        "For instance, a telephone pole is part of the environment, but a car might be another agent\\\n",
        "When something behavior can best be described as having its own performance\\\n",
        "measure, then we should consider it to be an agent.\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",
        "\"states\" : \"configurations of the puzzle (9! configurations)\",\n",
        "\"actions\" : \"Move one of the movable pieces\",\n",
        "\"Performance measure\" : \"minimize total moves\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "33db1a0a-7f55-40ee-8b75-b16a689c3fc0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nrationality. Can think humanly. Rationaly agent. An agent is just something that acts (agent comes from the Latin agere, to do).A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.Acting humanly: The Turing test approach. Thinking humanly: The cognitive modeling approach. introspection, psychological experiments, brain imagingThink like people, think rationally, act like people, act rationallyAn agent is anything that perceives its environment through sensors and can act on its environment through actuators.A percept is the agent’s perceptual inputs at any given instance.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Vision is a perceptual channel that accepts a stimulus and reports some representation of the world. Most agents that use vision use passive sensing—they do not need to send out light to see. In contrast, active sensing involves sending out a signal such as radar or ultrasound, and sensing a reflection.A feature is a number obtained by applying simple computations to an image. Very use- ful information can be obtained directly from features.This feature extraction approach emphasizes simple, direct computations applied to sensor responses.The model-based approach to vision uses two kinds of models.An object model could be the kind of precise geometric model produced by computer aided design systems. \nThe two core problems of computer vision are reconstruction, where an agent builds a model of the world froman image or a set of images, and recognition, where an agent draws distinctions among the objects it encounters\nbased on visual and other information.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n This effect is known as foreshortening (Figure 27.1). Models of these effects are essential for building competent object recognition systems and also yield powerful cues for reconstructing geometry.\n\n## AIMA 2.1 Agents and Environments\nA human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract,and so on for actuators. A robotic agent might have cameras and infrared range finders for sensors and variousmotors for actuators. A software agent receives file contents, network packets, and human input as sensory inputs and acts on theenvironment by writing files, sending network packets, and displaying information or generating sounds.We use the term percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequenceis the complete history of everything the agent has ever perceived.Mathematically speak- ing, we say that an agent’s behavior is described by the agent function that maps anygiven percept sequence to an action.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nA rational agent is one that does the right thing. Obviously, doing the right thing is betterthan doing the wrong thing, but what does it mean to do the right thing.Moral philosophy has developed several different notions of the “right thing,”but AI has generally stuck to one notion called consequentialism.This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\nThis leads to a definition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected tomaximize its performance measure, given the evidence provided by the percept sequenceand whatever built-in knowledge the agent has.\n\n\n## AIMA 2.3 The Nature of Environments\nAn omniscient agent knows the actual outcome of its actions and can actaccordingly; but omniscience is impossible in realityFirst, however, we must think about task environments, which are essentially the “problems”to which rational agents are the “solutions.” We begin by showing how to specify a task environment,illustrating the process with a number of examples.\n\n## AIMA 2.4 The Structure of Agents\nThe job of AI is to design an agent program that implements the agent function the mappingfrom percepts to actions. We assume this program will run on some sort of computing device with physical sensorsand actuators—we call this the agent architecture:\nagent = architecture + program .\n\n## Module 1 Lecture Notes\nA rational agent is an agent that perceives its environment and and behaves rationallyAI is usually concerned with Consequentialism.Informally, we expect that it will do the right thing in all circumstances.An objective criterion for success of an agent's behaviorgiven the evidence provided by the percept sequence.It is better to design performance measures according to what you want to beachieved in the environment, rather than how you think the agent should behaveFor each possible percept sequence Pa rational agent selects an actionto maximize its performance measureCaveat: computational limitations make complete rationality unachievableFor each possible percept sequence P,a rational agent selects an action athat maximizes the expected value of its performance measureTo design a rational agent we need to specify a task environmenta problem specification for which the agent is a solutionFor instance, a telephone pole is part of the environment, but a car might be another agentWhen something behavior can best be described as having its own performancemeasure, then we should consider it to be an agent.\n\n\n## Module 1 Definitions\n* **States** - configurations of the puzzle (9! configurations)\n* **Actions** - Move one of the movable pieces\n* **Performance measure** - minimize total moves\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 = \"\"\" yield\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        },
        "outputId": "4bf424c2-a7b3-4fa8-c9fa-457afd1a2638"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n yield\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"When the correct action to take is not immediately obvious, an agent may need to plan ahead\\\n",
        "to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving\\\n",
        "agent, and the computational process it undertakes is called search.\\\n",
        "We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal,\\\n",
        "and uninformed algorithms\\\n",
        "A search problem can be defined formally as follows:\\\n",
        "A set of possible states that the environment can be in. We call this the state space\\\n",
        "The initial state that the agent starts in. For example: Arad.\\\n",
        "\n",
        "Search problem definition\n",
        "A set of one or more goal states. Sometimes there is one goal state (e.g., Bucharest),\\\n",
        "sometimes there is a small set of alternative goal states, and sometimes the goal is defined\\\n",
        "by a property that applies to many states (potentially an infinite number). For example, in a\\\n",
        "vacuum-cleaner world, the goal might be to have no dirt in any location, regardless of any other\\\n",
        "facts about the state. We can account for all three of these possibilities by specifying an\\\n",
        "IS-GOAL method for a problem. In this chapter we will sometimes say “the goal” for simplicity,\\\n",
        "but what we say also applies to “any one of the possible goal states\\\n",
        "The actions available to the agent. Given a state s, ACTIONS(s) returns a finite \\\n",
        "set of actions that can be executed in s. We say that each of these actions is\\\n",
        "applicable in s. An example: ACTIONS(Arad) = {ToSibiu,ToTimisoara,ToZerind}.\\\n",
        "A transition model, which describes what each action does. RESULT(s,a) returns the\\\n",
        "state that results from doing action a in state s. For example, RESULT(Arad,ToZerind)=Zerind.\\\n",
        "An action cost function\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"The problem-solving approach has been applied to a vast array of task environments.\\\n",
        "We list some of the best known here, distinguishing between standardized and real-world problems.\\\n",
        "A standardized problem is intended to illustrate or exercise various problem-solving methods.\\\n",
        "It can be given a concise, exact description and hence is suitable as a benchmark for researchers\\\n",
        "to compare the performance of algorithms. A real-world problem, such as robot navigation, is one\\\n",
        "whose solutions people actually use, and whose formulation is idiosyn- cratic, not standardized,\\\n",
        "because, for example, each robot has different sensors that produce different data.\"\"\"\n",
        "chapter3_3 = \"\"\"A search algorithm takes a search problem as input and returns a solution, or an indication\\\n",
        "of failure. In this chapter we consider algorithms that superimpose a search tree over the state- space graph\\\n",
        "forming various paths from the initial state, trying to find a path that reaches a goal state. Each node in\\\n",
        "the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.\"\"\"\n",
        "chapter3_4 = \"\"\"When all actions have the same cost, an appropriate strategy is breadth-first search, in which\\\n",
        "the root node is expanded first, then all the successors of the root node are expanded next,\\\n",
        "then their successors.\\\n",
        "That also means we can do an early goal test, checking whether a node is a solution as soon as it is generated,\\\n",
        "rather than the late goal test that best-first search uses, waiting until a node is popped off the queue.\\\n",
        "This is called Di- jkstra’s algorithm by the theoretical computer science community,\\\n",
        "and uniform-cost search by the AI community.\\\n",
        "Depth-first search always expands the deepest node in the frontier first. It could be imple- mented as a call to\\\n",
        "BEST-FIRST-SEARCH where the evaluation function f is the negative of the depth\\\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"A simple reflex agent is one that selects an action based only on the current percept.\\\n",
        "A problem-solving agent must plan ahead.\\\n",
        "Uninformed search: All non-goal nodes in frontier look equally good\\\n",
        "Informed search: Some non-goal nodes can be ranked above others. \\\n",
        "Completeness- always find the solution?\\\n",
        "Optimality - finds a least cost solution (lowest path cost) first?\\\n",
        "Time complexity - # of nodes generated (worst case)\\\n",
        "Space complexity - # of nodes simultaneously in memory (worst case)\\\n",
        "b, maximum branching factor of search tree\\\n",
        "d, depth of the shallowest goal node\\\n",
        "m, maximum length of any path in the state space (potentially ∞)\\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"DFS\" : \"Space restricted, There are many possible solutions with long paths and wrong paths are usually terminated quickly.Search can be fine-tuned quickly\",\n",
        "\"BFS\" : \"Possible infinite paths. Some solutions have short paths. Can quickly discard unlikely paths\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 914
        },
        "outputId": "d0440fbe-4d80-46b1-e5b9-8fd3e34233bc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'DFS' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nWhen the correct action to take is not immediately obvious, an agent may need to plan aheadto consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solvingagent, and the computational process it undertakes is called search.We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal,and uninformed algorithmsA search problem can be defined formally as follows:A set of possible states that the environment can be in. We call this the state spaceThe initial state that the agent starts in. For example: Arad.\nSearch problem definition\nA set of one or more goal states. Sometimes there is one goal state (e.g., Bucharest),sometimes there is a small set of alternative goal states, and sometimes the goal is definedby a property that applies to many states (potentially an infinite number). For example, in avacuum-cleaner world, the goal might be to have no dirt in any location, regardless of any otherfacts about the state. We can account for all three of these possibilities by specifying anIS-GOAL method for a problem. In this chapter we will sometimes say “the goal” for simplicity,but what we say also applies to “any one of the possible goal statesThe actions available to the agent. Given a state s, ACTIONS(s) returns a finite set of actions that can be executed in s. We say that each of these actions isapplicable in s. An example: ACTIONS(Arad) = {ToSibiu,ToTimisoara,ToZerind}.A transition model, which describes what each action does. RESULT(s,a) returns thestate that results from doing action a in state s. For example, RESULT(Arad,ToZerind)=Zerind.An action cost function\n\n\n## AIMA Chapter 3.2 Example Problems\nThe problem-solving approach has been applied to a vast array of task environments.We list some of the best known here, distinguishing between standardized and real-world problems.A standardized problem is intended to illustrate or exercise various problem-solving methods.It can be given a concise, exact description and hence is suitable as a benchmark for researchersto compare the performance of algorithms. A real-world problem, such as robot navigation, is onewhose solutions people actually use, and whose formulation is idiosyn- cratic, not standardized,because, for example, each robot has different sensors that produce different data.\n\n## AIMA Chapter 3.3 Search Algorithms\nA search algorithm takes a search problem as input and returns a solution, or an indicationof failure. In this chapter we consider algorithms that superimpose a search tree over the state- space graphforming various paths from the initial state, trying to find a path that reaches a goal state. Each node inthe search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nWhen all actions have the same cost, an appropriate strategy is breadth-first search, in whichthe root node is expanded first, then all the successors of the root node are expanded next,then their successors.That also means we can do an early goal test, checking whether a node is a solution as soon as it is generated,rather than the late goal test that best-first search uses, waiting until a node is popped off the queue.This is called Di- jkstra’s algorithm by the theoretical computer science community,and uniform-cost search by the AI community.Depth-first search always expands the deepest node in the frontier first. It could be imple- mented as a call toBEST-FIRST-SEARCH where the evaluation function f is the negative of the depth\n\n## Module 3 Lecture Notes\nA simple reflex agent is one that selects an action based only on the current percept.A problem-solving agent must plan ahead.Uninformed search: All non-goal nodes in frontier look equally goodInformed search: Some non-goal nodes can be ranked above others. Completeness- always find the solution?Optimality - finds a least cost solution (lowest path cost) first?Time complexity - # of nodes generated (worst case)Space complexity - # of nodes simultaneously in memory (worst case)b, maximum branching factor of search treed, depth of the shallowest goal nodem, maximum length of any path in the state space (potentially ∞)\n\n## Module 3 Definitions\n* **Dfs** - Space restricted, There are many possible solutions with long paths and wrong paths are usually terminated quickly.Search can be fine-tuned quickly\n* **Bfs** - Possible infinite paths. Some solutions have short paths. Can quickly discard unlikely paths\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 = \"\"\"This section shows how an informed search strategy—one that uses domain-specific hints\\\n",
        "about the location of goals—can find solutions more efficiently than an uninformed strategy. The hints\\\n",
        "come in the form of a heuristic function, denoted h(n)\\\n",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state.\\\n",
        "Greedy best-first search is a form of best-first search that expands first the node with the\\\n",
        "lowest h(n) value—the node that appears to be closest to the goal—on the grounds that this is\\\n",
        "likely to lead to a solution quickly. So the evaluation function f (n) = h(n).\\\n",
        "We say that A∗ with a consistent heuristic is optimally efficient in the sense that\\\n",
        "any algorithm that extends search paths from the initial state.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"One way to characterize the quality of a heuristic is the effective branching factor b.\\\n",
        "If the total number of nodes generated by A∗ for a particular problem is N and the solution depth is d,\\\n",
        "then b∗ is the branching factor that a uniform tree of depth d would have to have in order to contain N + 1 nodes\\\n",
        "given heuristic h is that it reduces the effective depth by a constant kh compared to the true depth.\\\n",
        "We thus say that h2 dominates h1. Domination translates directly into efficiency: A∗ using h2 will never expand more nodes than A∗ using h1\\\n",
        "A problem with fewer restrictions on the actions is called a relaxed problem.\\\n",
        "Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.\\\n",
        "A problem consists of five parts: the initial state, a set of actions, a transition model\n",
        "describing the results of those actions, a set of goal states, and an action cost function.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "State space: the set of all states reachable from the initial state by any sequence of actions\\\n",
        "Path: a sequence of actions leading from one state sj to another state sk\\\n",
        "Frontier: those states that are available for expanding (for applying legal actions to)\\\n",
        "Solution: a path from the initial state si to a state sg that satisfies the goal test\\\n",
        "Uniform-cost search: Expand node with lowest path cost\\\n",
        "Subtle but significant difference from BFS:\n",
        "Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.\\\n",
        "Updates a node on the frontier if a better path to the same state is found.\\\n",
        "So always enqueues a node before checking whether it is a goal.\\\n",
        "\n",
        "Greedy best-first\\\n",
        "Expands the node that is estimated to be closest to goal \\\n",
        "Completely ignores g(n): the cost to get to n\\\n",
        "\n",
        "A*\\\n",
        "A heuristic h(n) is admissible if it never overestimates the cost to reach the goal;\\\n",
        "If h(n) is admissible, A* using Tree Search is optimal\\\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Best-first search\" : \"selects nodes for expansion using an evaluation function\",\n",
        "\"Breadth-first search\":\"expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity\",\n",
        "\"Uniform-cost search\":\"expands the node with lowest path cost, g(n), and is optimal for general action costs\",\n",
        "\"Depth-first search\":\"expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity\",\n",
        "\"Bidirectional search\":\"expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 669
        },
        "outputId": "aa284ffc-fd24-4b23-9225-35438068ce01"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nThis section shows how an informed search strategy—one that uses domain-specific hintsabout the location of goals—can find solutions more efficiently than an uninformed strategy. The hintscome in the form of a heuristic function, denoted h(n)h(n) = estimated cost of the cheapest path from the state at node n to a goal state.Greedy best-first search is a form of best-first search that expands first the node with thelowest h(n) value—the node that appears to be closest to the goal—on the grounds that this islikely to lead to a solution quickly. So the evaluation function f (n) = h(n).We say that A∗ with a consistent heuristic is optimally efficient in the sense thatany algorithm that extends search paths from the initial state.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\nOne way to characterize the quality of a heuristic is the effective branching factor b.If the total number of nodes generated by A∗ for a particular problem is N and the solution depth is d,then b∗ is the branching factor that a uniform tree of depth d would have to have in order to contain N + 1 nodesgiven heuristic h is that it reduces the effective depth by a constant kh compared to the true depth.We thus say that h2 dominates h1. Domination translates directly into efficiency: A∗ using h2 will never expand more nodes than A∗ using h1A problem with fewer restrictions on the actions is called a relaxed problem.Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.A problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n\n## Module 4 Lecture Notes\n\nState space: the set of all states reachable from the initial state by any sequence of actionsPath: a sequence of actions leading from one state sj to another state skFrontier: those states that are available for expanding (for applying legal actions to)Solution: a path from the initial state si to a state sg that satisfies the goal testUniform-cost search: Expand node with lowest path costSubtle but significant difference from BFS:\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.Updates a node on the frontier if a better path to the same state is found.So always enqueues a node before checking whether it is a goal.\nGreedy best-firstExpands the node that is estimated to be closest to goal Completely ignores g(n): the cost to get to n\nA*A heuristic h(n) is admissible if it never overestimates the cost to reach the goal;If h(n) is admissible, A* using Tree Search is optimalThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\n## Module 4 Definitions\n* **Best-first search** - selects nodes for expansion using an evaluation function\n* **Breadth-first search** - expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity\n* **Uniform-cost search** - expands the node with lowest path cost, g(n), and is optimal for general action costs\n* **Depth-first search** - expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity\n* **Bidirectional search** - expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\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 = \"\"\"\n",
        "pruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.\\\n",
        "we can apply a heuristic evaluation function to estimate who is winning based on features of the state\\\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "For games with multiple outcome scores, we need a slightly more general algorithm called minimax search.\\\n",
        "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state\\\n",
        "in the tree, which we write as MINIMAX(s). 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.\\\n",
        "We can also identify the minimax decision at the root: action a1 is the optimal choice for MAX because\\\n",
        "it leads to the state with the highest minimax value.\\\n",
        "It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up\\\n",
        "the minimax values through the tree as the recursion unwinds.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "α = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.\\\n",
        "Think: α = “at least.”\\\n",
        "β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN\\\n",
        "Think: β = “at most.\"\\\n",
        "To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function\\\n",
        "to states, effectively treating nonterminal nodes as if they were terminal.\\\n",
        "Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes\\\n",
        "moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk\\\n",
        "of making an error. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do this, considering\\\n",
        "only a few moves from each position (at least consciously).\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games bring us a little closer to the unpredictability of real life by including a random element, such as the\\\n",
        "throwing of dice.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"The agent’s prefer- ences are captured by a utility function, which assigns a single number to express\\\n",
        "the desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utility\\\n",
        "value of the outcomes, weighted by the probability that the outcome occurs: P(RESULT(a)=s′) = ∑P(s)P(s′ |s,a)\"\"\"\n",
        "chapter16_2 = \"\"\"Orderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability\"\"\"\n",
        "chapter16_3 = \"\"\"This process, often called preference elicitation, involves presenting choices to the human and using\\\n",
        "the observed preferences to pin down the underlying utility function. Normalized utilities use a scale with u⊥ = 0 and u⊤ = 1.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"1. Two players alternate moves\\\n",
        "2. Zero-sum: one player’s loss is another’s gain\\\n",
        "3. Clear set of legal moves\\\n",
        "4. Well-defined outcomes (e.g. win, lose, draw)\\\n",
        "Nodes represent ‘board positions’; edges represent legal moves. Root node is the first position in which a decision must be made.\\\n",
        "The Minimax Rule: “Don’t play hope chess\". Make the best move for MAX assuming that MIN always replies with the best move for MIN\\\n",
        "Compute each node’s minimax value: the best achievable utility against a rational (optimal) adversary\\\n",
        "α: MAX’s best already explored option on path to root\\\n",
        "β: MIN’s best already explored option on path to root\\\n",
        "Expectimax search: compute the average score under optimal play\\\n",
        "Calculate their expected utilities\\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Expectimax\" : \"Let’s say you know that your opponent is actually running a depth 2 minimax, using the result 80% of the time, and moving randomly otherwise\",    \n",
        "\"Expectiminimax\": \"Environment is an extra “random agent” player that moves after each min/max agent Each node computes the appropriate combination of its children\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b1f37fb3-58db-4e95-8d43-6da14211a10b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Expectimax' is too long!\nWARNING: Your definition of 'Expectiminimax' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\npruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.we can apply a heuristic evaluation function to estimate who is winning based on features of the state\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nFor games with multiple outcome scores, we need a slightly more general algorithm called minimax search.Given a game tree, the optimal strategy can be determined by working out the minimax value of each statein the tree, which we write as MINIMAX(s). The minimax value is the utility (for MAX) of being in that state,assuming that both players play optimally from there to the end of the game.We can also identify the minimax decision at the root: action a1 is the optimal choice for MAX becauseit leads to the state with the highest minimax value.It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs upthe minimax values through the tree as the recursion unwinds.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nα = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.Think: α = “at least.”β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MINThink: β = “at most.\"To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation functionto states, effectively treating nonterminal nodes as if they were terminal.Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunesmoves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the riskof making an error. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do this, consideringonly a few moves from each position (at least consciously).\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games bring us a little closer to the unpredictability of real life by including a random element, such as thethrowing of dice.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe agent’s prefer- ences are captured by a utility function, which assigns a single number to expressthe desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utilityvalue of the outcomes, weighted by the probability that the outcome occurs: P(RESULT(a)=s′) = ∑P(s)P(s′ |s,a)\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nOrderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability\n\n## AIMA Chapter 16.3 Utility Functions\nThis process, often called preference elicitation, involves presenting choices to the human and usingthe observed preferences to pin down the underlying utility function. Normalized utilities use a scale with u⊥ = 0 and u⊤ = 1.\n\n## Module 5 Lecture Notes\n1. Two players alternate moves2. Zero-sum: one player’s loss is another’s gain3. Clear set of legal moves4. Well-defined outcomes (e.g. win, lose, draw)Nodes represent ‘board positions’; edges represent legal moves. Root node is the first position in which a decision must be made.The Minimax Rule: “Don’t play hope chess\". Make the best move for MAX assuming that MIN always replies with the best move for MINCompute each node’s minimax value: the best achievable utility against a rational (optimal) adversaryα: MAX’s best already explored option on path to rootβ: MIN’s best already explored option on path to rootExpectimax search: compute the average score under optimal playCalculate their expected utilities\n\n\n## Module 5 Definitions\n* **Expectimax** - Let’s say you know that your opponent is actually running a depth 2 minimax, using the result 80% of the time, and moving randomly otherwise\n* **Expectiminimax** - Environment is an extra “random agent” player that moves after each min/max agent Each node computes the appropriate combination of its children\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 = \"\"\"CSPs deal with assignments of values to variables, {Xi = vi , X j = v j , . . .}. An assignment that\\\n",
        "does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which\\\n",
        "every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. A partial assignment\\\n",
        "is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\\\n",
        "Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can be\\\n",
        "solved very efficiently.\"\"\"\n",
        "chapter6_2 = \"\"\"constraint propagation: using the constraints to reduce the number of legal values for a variable,\\\n",
        "which a single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s\\\n",
        "domain satisfy the variable’s unary constraints.\"\"\"\n",
        "chapter6_3 = \"\"\"commutativity. A problem is commutative if the order of application of any given set of actions does not matter. \"\"\"\n",
        "chapter6_4 = \"\"\"the most obvious approach is to select the value that results in the minimum number of conflicts with other\\\n",
        "variables—the min-conflicts heuristic. Constraint weighting aims to concentrate the search on the important constraints\"\"\"\n",
        "chapter6_5 = \"\"\"Independence can be ascertained simply by finding connected components of the con- straint graph.\\\n",
        "The key is a new notion of consistency, called directional arc consistency\\\n",
        "Constraint satisfaction problems (CSPs) represent a state with a set of variable/value pairs\\\n",
        "and represent the conditions for a solution by a set of constraints on the variables. Many\\\n",
        "important real-world problems can be described as CSPs.\\\n",
        "A number of inference techniques use the constraints to rule out certain variable assignments.\\\n",
        "These include node, arc, path, and k-consistency.\\\n",
        "Backtracking search, a form of depth-first search, is commonly used for solving CSPs.\\\n",
        "Inference can be interwoven with search.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "An assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment.\\\n",
        "Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.\\\n",
        "Beyond our scope: CSPs that require a solution that maximizes an objective function.\\\n",
        "Depth-first search for CSPs with single-variable assignments is called backtracking search\\\n",
        "Q: Which variable should be assigned next?\\\n",
        "1. Most constrained variable\\\n",
        "2. (if ties:) Most constraining variable\\\n",
        "Q: In what order should that variable’s values be tried?\\\n",
        "3. Least constraining value\\\n",
        "Q: Can we detect inevitable failure early?\\\n",
        "4. Forward checking\\\n",
        "AC-3: Worst Case Complexity Analysis\\\n",
        "o All nodes can be connected to every other node,\\\n",
        "so each of n nodes must be compared against n-1 other nodes,\\\n",
        "so total # of arcs is 2*n*(n-1), i.e. O(n2)\\\n",
        "o If there are d values, checking arc (i,j) takes O(d2) time\\\n",
        "o Each arc (i,j) can only be inserted into the queue d times\\\n",
        "o Worst case complexity: O(n2d3)\\\n",
        "(For planar constraint graphs, the number of arcs can only be linear in N and the\\\n",
        "time complexity is only O(nd3))\\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 798
        },
        "outputId": "1872cfb3-dc4a-488e-a3fb-7eae7f0a0a6e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSPs deal with assignments of values to variables, {Xi = vi , X j = v j , . . .}. An assignment thatdoes not violate any constraints is called a consistent or legal assignment. A complete assignment is one in whichevery variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. A partial assignmentis one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can besolved very efficiently.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nconstraint propagation: using the constraints to reduce the number of legal values for a variable,which a single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’sdomain satisfy the variable’s unary constraints.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\ncommutativity. A problem is commutative if the order of application of any given set of actions does not matter. \n\n## AIMA Chapter 6.4 Local Search for CSPs\nthe most obvious approach is to select the value that results in the minimum number of conflicts with othervariables—the min-conflicts heuristic. Constraint weighting aims to concentrate the search on the important constraints\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependence can be ascertained simply by finding connected components of the con- straint graph.The key is a new notion of consistency, called directional arc consistencyConstraint satisfaction problems (CSPs) represent a state with a set of variable/value pairsand represent the conditions for a solution by a set of constraints on the variables. Manyimportant real-world problems can be described as CSPs.A number of inference techniques use the constraints to rule out certain variable assignments.These include node, arc, path, and k-consistency.Backtracking search, a form of depth-first search, is commonly used for solving CSPs.Inference can be interwoven with search.\n\n\n## Module 6 Lecture Notes\n\nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment.Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.Beyond our scope: CSPs that require a solution that maximizes an objective function.Depth-first search for CSPs with single-variable assignments is called backtracking searchQ: Which variable should be assigned next?1. Most constrained variable2. (if ties:) Most constraining variableQ: In what order should that variable’s values be tried?3. Least constraining valueQ: Can we detect inevitable failure early?4. Forward checkingAC-3: Worst Case Complexity Analysiso All nodes can be connected to every other node,so each of n nodes must be compared against n-1 other nodes,so total # of arcs is 2*n*(n-1), i.e. O(n2)o If there are d values, checking arc (i,j) takes O(d2) timeo Each arc (i,j) can only be inserted into the queue d timeso Worst case complexity: O(n2d3)(For planar constraint graphs, the number of arcs can only be linear in N and thetime complexity is only O(nd3))\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 = \"\"\"The agent maintains a knowledge base, KB, which may initially contain some background knowledge.\\\n",
        "A knowl- edge base is a set of sentences. Each sentence is expressed in a language called a knowledge representation\\\n",
        "language and represents some assertion about the world. inference—that is, deriving new sentences from old.\"\"\"\n",
        "chapter7_2 = \"\"\"Performance measure, Environment, Actuators, Sensors\"\"\"\n",
        "chapter7_3 = \"\"\"A logic must also define the semantics, or meaning, of sentences. The semantics defines the truth\\\n",
        "of each sentence with respect to each possible world.\\\n",
        "entailment between sentences—the idea that a sentence follows logically from another sentence.\"\"\"\n",
        "chapter7_4 = \"\"\"The syntax of propositional logic defines the allowable sentences. The atomic sentences\\\n",
        "consist of a single proposition symbol. Complex sentences are constructed from simpler sentences, using\\\n",
        "parentheses and operators called logical connectives\"\"\"\n",
        "chapter7_5 = \"\"\"theorem proving—applying rules of inference directly to the sentences in our knowledge\\\n",
        "base to construct a proof of the desired sentence without consulting models. The first concept is logical equivalence:\\\n",
        "two sentences α and β are logically equivalent if they are true in the same set of models. The second concept we will\\\n",
        "need is validity.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Sound – the inference algorithm should only derive entailed sentences.\\\n",
        "Complete – an inference algorithm is complete if it can derive all sentences that are entailed\\\n",
        "(a ⋀ b) ≡ (b ⋀ a) Commutativity of ⋀\\\n",
        "(a ⋁ b) ≡ (b ⋁ a) Commutativity of ⋁\\\n",
        "((a ⋀ b) ⋀ r) ≡ (a ⋀ (b ⋀ r)) Associativity of ⋀\\\n",
        "((a ⋁ b) ⋁ r) ≡ (a ⋁ (b ⋁ r)) Associativity of ⋁\\\n",
        "¬(¬ a) ≡ a Double-negation elimination\\\n",
        "(a ⟹ β) ≡ (¬β ⟹ ¬a) Contraposition\\\n",
        "(a ⟹ β) ≡ (¬a ⋁ β) Implication elimination\\\n",
        "(a ⇔ β) ≡ ((a ⟹ β) ⋀ (β ⟹a)) Biconditional elimination\\\n",
        "¬(a ⋀ β) ≡ (¬a ⋁ ¬b) De Morgan\\\n",
        "¬(a ⋁ β) ≡ (¬a ⋀ ¬β) De Morgan\\\n",
        "((a ⋀ β) ⋁ r) ≡ ((a ⋀ β) ⋁ (a ⋀ r))) Distributivity of ⋀ over ⋁\\\n",
        "((a ⋁ β) ⋀ r) ≡ ((a ⋁ β) ⋀ (a ⋁ r))) Distributivity of ⋁ over ⋀\\\n",
        "If l and m are complementary literals, which means that one is the negation of another, then we can eliminate\\\n",
        "them via unit resolution.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Forward Chaining\" : \"Forward Chaining is a kind of data-driven reasoning. An agent can start with known data,\\\n",
        "adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive\\\n",
        "new conclusions. It doesn’t have to have a specific query in mind to do so\",\n",
        "\"Forward Chaining\":\"Backward chaining works backwards from a query. If the query is known to be true, then no\\\n",
        "work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all\\\n",
        "the premises of one of those can be proved to be true (via backward chaining), then the query is true.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 806
        },
        "outputId": "bd86ee49-b642-4f4f-c34d-f3a033c2adc9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Forward Chaining' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nThe agent maintains a knowledge base, KB, which may initially contain some background knowledge.A knowl- edge base is a set of sentences. Each sentence is expressed in a language called a knowledge representationlanguage and represents some assertion about the world. inference—that is, deriving new sentences from old.\n\n## AIMA Chapter 7.2 The Wumpus World\nPerformance measure, Environment, Actuators, Sensors\n\n## AIMA Chapter 7.3 Logic\nA logic must also define the semantics, or meaning, of sentences. The semantics defines the truthof each sentence with respect to each possible world.entailment between sentences—the idea that a sentence follows logically from another sentence.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nThe syntax of propositional logic defines the allowable sentences. The atomic sentencesconsist of a single proposition symbol. Complex sentences are constructed from simpler sentences, usingparentheses and operators called logical connectives\n\n## AIMA 7.5 Propositional Theorem Proving\ntheorem proving—applying rules of inference directly to the sentences in our knowledgebase to construct a proof of the desired sentence without consulting models. The first concept is logical equivalence:two sentences α and β are logically equivalent if they are true in the same set of models. The second concept we willneed is validity.\n\n## Module 7 Lecture Notes\n\nSound – the inference algorithm should only derive entailed sentences.Complete – an inference algorithm is complete if it can derive all sentences that are entailed(a ⋀ b) ≡ (b ⋀ a) Commutativity of ⋀(a ⋁ b) ≡ (b ⋁ a) Commutativity of ⋁((a ⋀ b) ⋀ r) ≡ (a ⋀ (b ⋀ r)) Associativity of ⋀((a ⋁ b) ⋁ r) ≡ (a ⋁ (b ⋁ r)) Associativity of ⋁¬(¬ a) ≡ a Double-negation elimination(a ⟹ β) ≡ (¬β ⟹ ¬a) Contraposition(a ⟹ β) ≡ (¬a ⋁ β) Implication elimination(a ⇔ β) ≡ ((a ⟹ β) ⋀ (β ⟹a)) Biconditional elimination¬(a ⋀ β) ≡ (¬a ⋁ ¬b) De Morgan¬(a ⋁ β) ≡ (¬a ⋀ ¬β) De Morgan((a ⋀ β) ⋁ r) ≡ ((a ⋀ β) ⋁ (a ⋀ r))) Distributivity of ⋀ over ⋁((a ⋁ β) ⋀ r) ≡ ((a ⋁ β) ⋀ (a ⋁ r))) Distributivity of ⋁ over ⋀If l and m are complementary literals, which means that one is the negation of another, then we can eliminatethem via unit resolution.\n\n\n## Module 7 Definitions\n* **Forward chaining** - Backward chaining works backwards from a query. If the query is known to be true, then nowork is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If allthe premises of one of those can be proved to be true (via backward chaining), then the query is true.\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": "97e07d40-cbe8-472c-e498-673ba4832b37"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nrationality. Can think humanly. Rationaly agent. An agent is just something that acts (agent comes from the Latin agere, to do).A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.Acting humanly: The Turing test approach. Thinking humanly: The cognitive modeling approach. introspection, psychological experiments, brain imagingThink like people, think rationally, act like people, act rationallyAn agent is anything that perceives its environment through sensors and can act on its environment through actuators.A percept is the agent’s perceptual inputs at any given instance.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Vision is a perceptual channel that accepts a stimulus and reports some representation of the world. Most agents that use vision use passive sensing—they do not need to send out light to see. In contrast, active sensing involves sending out a signal such as radar or ultrasound, and sensing a reflection.A feature is a number obtained by applying simple computations to an image. Very use- ful information can be obtained directly from features.This feature extraction approach emphasizes simple, direct computations applied to sensor responses.The model-based approach to vision uses two kinds of models.An object model could be the kind of precise geometric model produced by computer aided design systems. \nThe two core problems of computer vision are reconstruction, where an agent builds a model of the world froman image or a set of images, and recognition, where an agent draws distinctions among the objects it encounters\nbased on visual and other information.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n This effect is known as foreshortening (Figure 27.1). Models of these effects are essential for building competent object recognition systems and also yield powerful cues for reconstructing geometry.\n\n## AIMA 2.1 Agents and Environments\nA human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract,and so on for actuators. A robotic agent might have cameras and infrared range finders for sensors and variousmotors for actuators. A software agent receives file contents, network packets, and human input as sensory inputs and acts on theenvironment by writing files, sending network packets, and displaying information or generating sounds.We use the term percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequenceis the complete history of everything the agent has ever perceived.Mathematically speak- ing, we say that an agent’s behavior is described by the agent function that maps anygiven percept sequence to an action.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nA rational agent is one that does the right thing. Obviously, doing the right thing is betterthan doing the wrong thing, but what does it mean to do the right thing.Moral philosophy has developed several different notions of the “right thing,”but AI has generally stuck to one notion called consequentialism.This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.\nThis leads to a definition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected tomaximize its performance measure, given the evidence provided by the percept sequenceand whatever built-in knowledge the agent has.\n\n\n## AIMA 2.3 The Nature of Environments\nAn omniscient agent knows the actual outcome of its actions and can actaccordingly; but omniscience is impossible in realityFirst, however, we must think about task environments, which are essentially the “problems”to which rational agents are the “solutions.” We begin by showing how to specify a task environment,illustrating the process with a number of examples.\n\n## AIMA 2.4 The Structure of Agents\nThe job of AI is to design an agent program that implements the agent function the mappingfrom percepts to actions. We assume this program will run on some sort of computing device with physical sensorsand actuators—we call this the agent architecture:\nagent = architecture + program .\n\n## Module 1 Lecture Notes\nA rational agent is an agent that perceives its environment and and behaves rationallyAI is usually concerned with Consequentialism.Informally, we expect that it will do the right thing in all circumstances.An objective criterion for success of an agent's behaviorgiven the evidence provided by the percept sequence.It is better to design performance measures according to what you want to beachieved in the environment, rather than how you think the agent should behaveFor each possible percept sequence Pa rational agent selects an actionto maximize its performance measureCaveat: computational limitations make complete rationality unachievableFor each possible percept sequence P,a rational agent selects an action athat maximizes the expected value of its performance measureTo design a rational agent we need to specify a task environmenta problem specification for which the agent is a solutionFor instance, a telephone pole is part of the environment, but a car might be another agentWhen something behavior can best be described as having its own performancemeasure, then we should consider it to be an agent.\n\n\n## Module 1 Definitions\n* **States** - configurations of the puzzle (9! configurations)\n* **Actions** - Move one of the movable pieces\n* **Performance measure** - minimize total moves\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n yield\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n## WARNING: Your definition of 'DFS' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nWhen the correct action to take is not immediately obvious, an agent may need to plan aheadto consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solvingagent, and the computational process it undertakes is called search.We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal,and uninformed algorithmsA search problem can be defined formally as follows:A set of possible states that the environment can be in. We call this the state spaceThe initial state that the agent starts in. For example: Arad.\nSearch problem definition\nA set of one or more goal states. Sometimes there is one goal state (e.g., Bucharest),sometimes there is a small set of alternative goal states, and sometimes the goal is definedby a property that applies to many states (potentially an infinite number). For example, in avacuum-cleaner world, the goal might be to have no dirt in any location, regardless of any otherfacts about the state. We can account for all three of these possibilities by specifying anIS-GOAL method for a problem. In this chapter we will sometimes say “the goal” for simplicity,but what we say also applies to “any one of the possible goal statesThe actions available to the agent. Given a state s, ACTIONS(s) returns a finite set of actions that can be executed in s. We say that each of these actions isapplicable in s. An example: ACTIONS(Arad) = {ToSibiu,ToTimisoara,ToZerind}.A transition model, which describes what each action does. RESULT(s,a) returns thestate that results from doing action a in state s. For example, RESULT(Arad,ToZerind)=Zerind.An action cost function\n\n\n## AIMA Chapter 3.2 Example Problems\nThe problem-solving approach has been applied to a vast array of task environments.We list some of the best known here, distinguishing between standardized and real-world problems.A standardized problem is intended to illustrate or exercise various problem-solving methods.It can be given a concise, exact description and hence is suitable as a benchmark for researchersto compare the performance of algorithms. A real-world problem, such as robot navigation, is onewhose solutions people actually use, and whose formulation is idiosyn- cratic, not standardized,because, for example, each robot has different sensors that produce different data.\n\n## AIMA Chapter 3.3 Search Algorithms\nA search algorithm takes a search problem as input and returns a solution, or an indicationof failure. In this chapter we consider algorithms that superimpose a search tree over the state- space graphforming various paths from the initial state, trying to find a path that reaches a goal state. Each node inthe search tree corresponds to a state in the state space and the edges in the search tree correspond to actions.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nWhen all actions have the same cost, an appropriate strategy is breadth-first search, in whichthe root node is expanded first, then all the successors of the root node are expanded next,then their successors.That also means we can do an early goal test, checking whether a node is a solution as soon as it is generated,rather than the late goal test that best-first search uses, waiting until a node is popped off the queue.This is called Di- jkstra’s algorithm by the theoretical computer science community,and uniform-cost search by the AI community.Depth-first search always expands the deepest node in the frontier first. It could be imple- mented as a call toBEST-FIRST-SEARCH where the evaluation function f is the negative of the depth\n\n## Module 3 Lecture Notes\nA simple reflex agent is one that selects an action based only on the current percept.A problem-solving agent must plan ahead.Uninformed search: All non-goal nodes in frontier look equally goodInformed search: Some non-goal nodes can be ranked above others. Completeness- always find the solution?Optimality - finds a least cost solution (lowest path cost) first?Time complexity - # of nodes generated (worst case)Space complexity - # of nodes simultaneously in memory (worst case)b, maximum branching factor of search treed, depth of the shallowest goal nodem, maximum length of any path in the state space (potentially ∞)\n\n## Module 3 Definitions\n* **Dfs** - Space restricted, There are many possible solutions with long paths and wrong paths are usually terminated quickly.Search can be fine-tuned quickly\n* **Bfs** - Possible infinite paths. Some solutions have short paths. Can quickly discard unlikely paths\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nThis section shows how an informed search strategy—one that uses domain-specific hintsabout the location of goals—can find solutions more efficiently than an uninformed strategy. The hintscome in the form of a heuristic function, denoted h(n)h(n) = estimated cost of the cheapest path from the state at node n to a goal state.Greedy best-first search is a form of best-first search that expands first the node with thelowest h(n) value—the node that appears to be closest to the goal—on the grounds that this islikely to lead to a solution quickly. So the evaluation function f (n) = h(n).We say that A∗ with a consistent heuristic is optimally efficient in the sense thatany algorithm that extends search paths from the initial state.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\nOne way to characterize the quality of a heuristic is the effective branching factor b.If the total number of nodes generated by A∗ for a particular problem is N and the solution depth is d,then b∗ is the branching factor that a uniform tree of depth d would have to have in order to contain N + 1 nodesgiven heuristic h is that it reduces the effective depth by a constant kh compared to the true depth.We thus say that h2 dominates h1. Domination translates directly into efficiency: A∗ using h2 will never expand more nodes than A∗ using h1A problem with fewer restrictions on the actions is called a relaxed problem.Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.A problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n\n## Module 4 Lecture Notes\n\nState space: the set of all states reachable from the initial state by any sequence of actionsPath: a sequence of actions leading from one state sj to another state skFrontier: those states that are available for expanding (for applying legal actions to)Solution: a path from the initial state si to a state sg that satisfies the goal testUniform-cost search: Expand node with lowest path costSubtle but significant difference from BFS:\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.Updates a node on the frontier if a better path to the same state is found.So always enqueues a node before checking whether it is a goal.\nGreedy best-firstExpands the node that is estimated to be closest to goal Completely ignores g(n): the cost to get to n\nA*A heuristic h(n) is admissible if it never overestimates the cost to reach the goal;If h(n) is admissible, A* using Tree Search is optimalThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\n## Module 4 Definitions\n* **Best-first search** - selects nodes for expansion using an evaluation function\n* **Breadth-first search** - expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity\n* **Uniform-cost search** - expands the node with lowest path cost, g(n), and is optimal for general action costs\n* **Depth-first search** - expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity\n* **Bidirectional search** - expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n\n\n## WARNING: Your definition of 'Expectimax' is too long!\nWARNING: Your definition of 'Expectiminimax' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\npruning makes the search more efficient by ignoring portions of the search tree that make no difference to the optimal move.we can apply a heuristic evaluation function to estimate who is winning based on features of the state\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nFor games with multiple outcome scores, we need a slightly more general algorithm called minimax search.Given a game tree, the optimal strategy can be determined by working out the minimax value of each statein the tree, which we write as MINIMAX(s). The minimax value is the utility (for MAX) of being in that state,assuming that both players play optimally from there to the end of the game.We can also identify the minimax decision at the root: action a1 is the optimal choice for MAX becauseit leads to the state with the highest minimax value.It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs upthe minimax values through the tree as the recursion unwinds.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nα = the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX.Think: α = “at least.”β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MINThink: β = “at most.\"To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation functionto states, effectively treating nonterminal nodes as if they were terminal.Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunesmoves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the riskof making an error. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do this, consideringonly a few moves from each position (at least consciously).\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games bring us a little closer to the unpredictability of real life by including a random element, such as thethrowing of dice.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe agent’s prefer- ences are captured by a utility function, which assigns a single number to expressthe desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utilityvalue of the outcomes, weighted by the probability that the outcome occurs: P(RESULT(a)=s′) = ∑P(s)P(s′ |s,a)\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nOrderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability\n\n## AIMA Chapter 16.3 Utility Functions\nThis process, often called preference elicitation, involves presenting choices to the human and usingthe observed preferences to pin down the underlying utility function. Normalized utilities use a scale with u⊥ = 0 and u⊤ = 1.\n\n## Module 5 Lecture Notes\n1. Two players alternate moves2. Zero-sum: one player’s loss is another’s gain3. Clear set of legal moves4. Well-defined outcomes (e.g. win, lose, draw)Nodes represent ‘board positions’; edges represent legal moves. Root node is the first position in which a decision must be made.The Minimax Rule: “Don’t play hope chess\". Make the best move for MAX assuming that MIN always replies with the best move for MINCompute each node’s minimax value: the best achievable utility against a rational (optimal) adversaryα: MAX’s best already explored option on path to rootβ: MIN’s best already explored option on path to rootExpectimax search: compute the average score under optimal playCalculate their expected utilities\n\n\n## Module 5 Definitions\n* **Expectimax** - Let’s say you know that your opponent is actually running a depth 2 minimax, using the result 80% of the time, and moving randomly otherwise\n* **Expectiminimax** - Environment is an extra “random agent” player that moves after each min/max agent Each node computes the appropriate combination of its children\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSPs deal with assignments of values to variables, {Xi = vi , X j = v j , . . .}. An assignment thatdoes not violate any constraints is called a consistent or legal assignment. A complete assignment is one in whichevery variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. A partial assignmentis one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can besolved very efficiently.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nconstraint propagation: using the constraints to reduce the number of legal values for a variable,which a single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’sdomain satisfy the variable’s unary constraints.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\ncommutativity. A problem is commutative if the order of application of any given set of actions does not matter. \n\n## AIMA Chapter 6.4 Local Search for CSPs\nthe most obvious approach is to select the value that results in the minimum number of conflicts with othervariables—the min-conflicts heuristic. Constraint weighting aims to concentrate the search on the important constraints\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependence can be ascertained simply by finding connected components of the con- straint graph.The key is a new notion of consistency, called directional arc consistencyConstraint satisfaction problems (CSPs) represent a state with a set of variable/value pairsand represent the conditions for a solution by a set of constraints on the variables. Manyimportant real-world problems can be described as CSPs.A number of inference techniques use the constraints to rule out certain variable assignments.These include node, arc, path, and k-consistency.Backtracking search, a form of depth-first search, is commonly used for solving CSPs.Inference can be interwoven with search.\n\n\n## Module 6 Lecture Notes\n\nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment.Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.Beyond our scope: CSPs that require a solution that maximizes an objective function.Depth-first search for CSPs with single-variable assignments is called backtracking searchQ: Which variable should be assigned next?1. Most constrained variable2. (if ties:) Most constraining variableQ: In what order should that variable’s values be tried?3. Least constraining valueQ: Can we detect inevitable failure early?4. Forward checkingAC-3: Worst Case Complexity Analysiso All nodes can be connected to every other node,so each of n nodes must be compared against n-1 other nodes,so total # of arcs is 2*n*(n-1), i.e. O(n2)o If there are d values, checking arc (i,j) takes O(d2) timeo Each arc (i,j) can only be inserted into the queue d timeso Worst case complexity: O(n2d3)(For planar constraint graphs, the number of arcs can only be linear in N and thetime complexity is only O(nd3))\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n## WARNING: Your definition of 'Forward Chaining' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nThe agent maintains a knowledge base, KB, which may initially contain some background knowledge.A knowl- edge base is a set of sentences. Each sentence is expressed in a language called a knowledge representationlanguage and represents some assertion about the world. inference—that is, deriving new sentences from old.\n\n## AIMA Chapter 7.2 The Wumpus World\nPerformance measure, Environment, Actuators, Sensors\n\n## AIMA Chapter 7.3 Logic\nA logic must also define the semantics, or meaning, of sentences. The semantics defines the truthof each sentence with respect to each possible world.entailment between sentences—the idea that a sentence follows logically from another sentence.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nThe syntax of propositional logic defines the allowable sentences. The atomic sentencesconsist of a single proposition symbol. Complex sentences are constructed from simpler sentences, usingparentheses and operators called logical connectives\n\n## AIMA 7.5 Propositional Theorem Proving\ntheorem proving—applying rules of inference directly to the sentences in our knowledgebase to construct a proof of the desired sentence without consulting models. The first concept is logical equivalence:two sentences α and β are logically equivalent if they are true in the same set of models. The second concept we willneed is validity.\n\n## Module 7 Lecture Notes\n\nSound – the inference algorithm should only derive entailed sentences.Complete – an inference algorithm is complete if it can derive all sentences that are entailed(a ⋀ b) ≡ (b ⋀ a) Commutativity of ⋀(a ⋁ b) ≡ (b ⋁ a) Commutativity of ⋁((a ⋀ b) ⋀ r) ≡ (a ⋀ (b ⋀ r)) Associativity of ⋀((a ⋁ b) ⋁ r) ≡ (a ⋁ (b ⋁ r)) Associativity of ⋁¬(¬ a) ≡ a Double-negation elimination(a ⟹ β) ≡ (¬β ⟹ ¬a) Contraposition(a ⟹ β) ≡ (¬a ⋁ β) Implication elimination(a ⇔ β) ≡ ((a ⟹ β) ⋀ (β ⟹a)) Biconditional elimination¬(a ⋀ β) ≡ (¬a ⋁ ¬b) De Morgan¬(a ⋁ β) ≡ (¬a ⋀ ¬β) De Morgan((a ⋀ β) ⋁ r) ≡ ((a ⋀ β) ⋁ (a ⋀ r))) Distributivity of ⋀ over ⋁((a ⋁ β) ⋀ r) ≡ ((a ⋁ β) ⋀ (a ⋁ r))) Distributivity of ⋁ over ⋀If l and m are complementary literals, which means that one is the negation of another, then we can eliminatethem via unit resolution.\n\n\n## Module 7 Definitions\n* **Forward chaining** - Backward chaining works backwards from a query. If the query is known to be true, then nowork is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If allthe premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}