{
  "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",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "lzaavW96tcxM",
        "outputId": "36f5c692-4de9-4628-9acb-fae432d13a19"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "8DvZ57A-djo1",
        "outputId": "3d8a3bc2-ee18-4df4-e8dd-c029defdfdc2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 5,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "An agent perceives through sensors and acts through actuators.\n",
        "\n",
        "Percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
        "\n",
        "Agent’s behavior when percept sequence leads to an action. The agent function for an artificial agent will be implemented by an agent program.  The agent function is an abstract mathematical description; the agent program is an implementation. \n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" Rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure.\n",
        "\n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly; but omniscience is impossible in reality.\n",
        "\n",
        "Rational agent maximizes expected performance. \n",
        "Information gathering – doing actions to modify future percepts. \n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "Task environment. PEAS (Performance, Environment, Actuators, Sensors) description:\n",
        "\n",
        "Properties: \n",
        "\n",
        "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: Fully observable if an agent’s sensors give it access to the complete state of the environment at each point in time.\n",
        "\n",
        "SINGLE-AGENT VS. MULTIAGENT: How many parties are involved.\n",
        "\n",
        "COMPETITIVE VS COOPERATIVE: Self described\n",
        "\n",
        "Deterministic vs. nondeterministic. If the next state of the environment is completely determined by the current state and the action executed by the agent, the environment is deterministic, otherwise nondeterministic. Stochastic if it deals with probabilities. \n",
        "\n",
        "EPISODIC VS. SEQUENTIAL: In episodic the agent receives a percept and then performs a single action. The next episode does not depend on the actions taken in previous episodes. Many classification tasks are episodic. Chess and taxi driving are sequential. Episodic is simpler because you don’t need to think ahead. \n",
        "\n",
        "STATIC VS. DYNAMIC: If the environment can change while an agent is figuring out solution, environment is dynamic, otherwise it’s static. If the environment itself does not change with the passage of time but the agent’s performance score does, the environment is semi dynamic. Taxi dynamic, chess with clock semi dynamic, crossword static. \n",
        "\n",
        "DISCRETE VS. CONTINUOUS: Applies to the way time is handled in the environment. Chess is discrete, taxi is continuous.\n",
        "\n",
        "KNOWN VS. UNKNOWN: Does agent know “laws of physics” of the environment. An unknown environment can be fully observable (videogame visible, what buttons do is not known). \n",
        "\n",
        "The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. Taxi driving is hard in all these senses\n",
        "AI aims to design an agent that implements the agent function,  the mapping from percepts to actions. The architecture will be the device with sensors and actuators. \n",
        "agent = architecture + program .\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" AGENTS\n",
        "Simple reflex agent. These agents act on current percept, and ignore the rest of the percept history. It may randomize to escape infinite loop. And it can do better than other agents. \n",
        "\n",
        "When there is partial observability, agent should maintain some internal state that depends on history and reflects some of the unobserved aspects of the current state. \n",
        "\n",
        "“how the world works” is a transition model of the world.  How info of the world is reflected in percepts is called sensor model. \n",
        "\n",
        "Agent uses the transition model and sensor model to keep track of the state of the world, this makes it a  model-based agent.\n",
        "\n",
        "Goal based agent = self explanatory \n",
        "\n",
        "Utility-based agents behave ‘well’ in most environments. There is a utility function that is an internalization of the performance measure. The agent will try to maximize its expected utility. \n",
        "\n",
        "Model-free agent learns what action is best in a particular situation without ever learning exactly how that action changes the environment.\n",
        "\n",
        "Learning Agents\n",
        "Learning element, is responsible for making improvements, and the performance element selects external actions.\n",
        "The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to improve it in the future.\n",
        "Problem generator. It is responsible for suggesting actions that will lead to new and informative experiences\n",
        "Feedback comes in the form of reward or penalty. \n",
        "\n",
        "How do they work? \n",
        "In an atomic representation each state of the world is indivisible—it has no internal structure\n",
        "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. \n",
        "A structured representation, in which objects like cars and dogs and their relationships can be described explicitly. \n",
        "The axis along which atomic, factored, and structured representations lie is the axis of increasing expressiveness.\n",
        "The mapping between concepts and memory locations is the localist representation. If the representation of a concept is spread over many locations (memory) , it’s a  distributed representation.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "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",
      "execution_count": 7,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1537
        },
        "id": "gYYeNcdM_maE",
        "outputId": "db8633dc-b409-465a-dd1e-c0ae8a1ed2a2"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " \n",
              "An agent perceives through sensors and acts through actuators.\n",
              "\n",
              "Percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
              "\n",
              "Agent’s behavior when percept sequence leads to an action. The agent function for an artificial agent will be implemented by an agent program.  The agent function is an abstract mathematical description; the agent program is an implementation. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure.\n",
              "\n",
              "An omniscient agent knows the actual outcome of its actions and can act accordingly; but omniscience is impossible in reality.\n",
              "\n",
              "Rational agent maximizes expected performance. \n",
              "Information gathering – doing actions to modify future percepts. \n",
              " \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " \n",
              "Task environment. PEAS (Performance, Environment, Actuators, Sensors) description:\n",
              "\n",
              "Properties: \n",
              "\n",
              "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: Fully observable if an agent’s sensors give it access to the complete state of the environment at each point in time.\n",
              "\n",
              "SINGLE-AGENT VS. MULTIAGENT: How many parties are involved.\n",
              "\n",
              "COMPETITIVE VS COOPERATIVE: Self described\n",
              "\n",
              "Deterministic vs. nondeterministic. If the next state of the environment is completely determined by the current state and the action executed by the agent, the environment is deterministic, otherwise nondeterministic. Stochastic if it deals with probabilities. \n",
              "\n",
              "EPISODIC VS. SEQUENTIAL: In episodic the agent receives a percept and then performs a single action. The next episode does not depend on the actions taken in previous episodes. Many classification tasks are episodic. Chess and taxi driving are sequential. Episodic is simpler because you don’t need to think ahead. \n",
              "\n",
              "STATIC VS. DYNAMIC: If the environment can change while an agent is figuring out solution, environment is dynamic, otherwise it’s static. If the environment itself does not change with the passage of time but the agent’s performance score does, the environment is semi dynamic. Taxi dynamic, chess with clock semi dynamic, crossword static. \n",
              "\n",
              "DISCRETE VS. CONTINUOUS: Applies to the way time is handled in the environment. Chess is discrete, taxi is continuous.\n",
              "\n",
              "KNOWN VS. UNKNOWN: Does agent know “laws of physics” of the environment. An unknown environment can be fully observable (videogame visible, what buttons do is not known). \n",
              "\n",
              "The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. Taxi driving is hard in all these senses\n",
              "AI aims to design an agent that implements the agent function,  the mapping from percepts to actions. The architecture will be the device with sensors and actuators. \n",
              "agent = architecture + program .\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " AGENTS\n",
              "Simple reflex agent. These agents act on current percept, and ignore the rest of the percept history. It may randomize to escape infinite loop. And it can do better than other agents. \n",
              "\n",
              "When there is partial observability, agent should maintain some internal state that depends on history and reflects some of the unobserved aspects of the current state. \n",
              "\n",
              "“how the world works” is a transition model of the world.  How info of the world is reflected in percepts is called sensor model. \n",
              "\n",
              "Agent uses the transition model and sensor model to keep track of the state of the world, this makes it a  model-based agent.\n",
              "\n",
              "Goal based agent = self explanatory \n",
              "\n",
              "Utility-based agents behave ‘well’ in most environments. There is a utility function that is an internalization of the performance measure. The agent will try to maximize its expected utility. \n",
              "\n",
              "Model-free agent learns what action is best in a particular situation without ever learning exactly how that action changes the environment.\n",
              "\n",
              "Learning Agents\n",
              "Learning element, is responsible for making improvements, and the performance element selects external actions.\n",
              "The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to improve it in the future.\n",
              "Problem generator. It is responsible for suggesting actions that will lead to new and informative experiences\n",
              "Feedback comes in the form of reward or penalty. \n",
              "\n",
              "How do they work? \n",
              "In an atomic representation each state of the world is indivisible—it has no internal structure\n",
              "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. \n",
              "A structured representation, in which objects like cars and dogs and their relationships can be described explicitly. \n",
              "The axis along which atomic, factored, and structured representations lie is the axis of increasing expressiveness.\n",
              "The mapping between concepts and memory locations is the localist representation. If the representation of a concept is spread over many locations (memory) , it’s a  distributed representation.\n",
              "\n",
              " \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "id": "ydOK__lwWgdp",
        "outputId": "7fc48bac-abcf-4b6d-942c-fa397f72281a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" There are four-phase problem-solving process:\n",
        "1.\tGOAL FORMULATION\n",
        "2.\tPROBLEM FORMULATION: An abstraction of the relevant part of the world. Agent describes states and the actions necessary to reach the goal. \n",
        "3.\tSEARCH: Agent simulates actions in its model and searches until it reaches the goal. This is a solution. \n",
        "4.\tEXECUTION – Takes the actual steps. \n",
        "\n",
        "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions\n",
        "\n",
        "The removal of detail from a representation is called abstraction.\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is used to show other problem solving methods \"\"\"\n",
        "chapter3_3 = \"\"\" A search algorithm takes a search problem as input and returns a solution. Creates a tree in which each node corresponds to a state in the state space. The state space is the possibly infinite set of states. \n",
        "Search tree describes the path between these states. \n",
        "\n",
        "Best-first search (Dijktra’s, goes with the min cost first and expands from there). \n",
        "\n",
        "Three kinds of queues are used in search algorithms: \n",
        "1.\tA priority queue first pops the node with the minimum cost( used in best-first search)\n",
        "2.\t FIFO queue pops the node that was added to the queue first(BFS)\n",
        "3.\tLIFO queue (stack) pops first the most recently added node(DFS) \n",
        "Graph search checks redundant paths, tree-like does not. \n",
        "To be complete, a search algorithm must be systematic in the way it explores an infinite state space\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" If all actions have same cost, BFS is best. BFS finds solution with min num of actions because it has generated all the nodes at d-1 depth. It does however have high space complexity. \n",
        "If actions have different costs, Best-first is the way to go (Dijkstra’s aka uniform cost search). \n",
        "A variant of DFS  called backtracking search uses even less memory.\n",
        "To avoid infinite loop in DFS you can apply a depth limit and treat that limit like there are no successors at that point. Furthermore you can do iterative deepening which tries depth values increasing every time. \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Reflex Agent – ignores percept history, just reacts to current percept \n",
        "Problem-Solving Agent – Needs to do search, process of finding a solution\n",
        "Task Environment:\n",
        "If Fully observable, deterministic, known => fixed sequence of actions\n",
        "If partially observable, non deterministic => branching strategy\n",
        "\n",
        "Process: State goal, formulate search problem, find solution\n",
        "\n",
        "Formal Definition\n",
        "1)\tState: set S\n",
        "2)\tInitial state\n",
        "3)\tActions\n",
        "4)\tTransition model (successors)\n",
        "5)\tPath Cost (performance measure)\n",
        "6)\tGoal test\n",
        "State Space = all states\n",
        "Path = sequence of actions\n",
        "Frontier = states available for expanding \n",
        "Solution = Path of states that satisfy the goal test\n",
        "\n",
        "World is complex and you need to do an abstraction to be able to approach it. \n",
        "Graph vs Tree = Graph uses queue avoids infinite loops\n",
        "Uninformed Search = all nodes look equally good \n",
        "Informed Search = Some nodes can be ranked above others \n",
        "\n",
        "How we evaluate:\n",
        "Completeness = Does it find the Solution\n",
        "Optimality  = Does it find the optimal (lowest cost) solution\n",
        "Time Complexity = # of nodes it visit \n",
        "Space = # of nodes in memory\n",
        "\n",
        "BFS \n",
        "Expand to shallowest node \n",
        "Uses FIFO queue\n",
        "It is complete and optimal\n",
        "Time O(b^d)\n",
        "Space O(b^d)\n",
        "\n",
        "DFS\n",
        "Expand deepest \n",
        "LIFO queue – successors go to the front \n",
        "It’s not complete if there are loops \n",
        "Not optimal \n",
        "Time O(b^m)\n",
        "Space 0(b *m) linear! \n",
        "\n",
        "DFS vs BFS: \n",
        "DFS if it’s space-restricted and long paths terminate quickly. Search can be fine-tuned\n",
        "BFS if possible infinite paths, some solutions are short and can discard unlikely paths. \n",
        "\n",
        "Depth limit and Iterative … look at table. \n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1075
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "5eb771d0-4f6f-4905-ee1b-17648f012504"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " There are four-phase problem-solving process:\n",
              "1.\tGOAL FORMULATION\n",
              "2.\tPROBLEM FORMULATION: An abstraction of the relevant part of the world. Agent describes states and the actions necessary to reach the goal. \n",
              "3.\tSEARCH: Agent simulates actions in its model and searches until it reaches the goal. This is a solution. \n",
              "4.\tEXECUTION – Takes the actual steps. \n",
              "\n",
              "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions\n",
              "\n",
              "The removal of detail from a representation is called abstraction.\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " A standardized problem is used to show other problem solving methods \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " A search algorithm takes a search problem as input and returns a solution. Creates a tree in which each node corresponds to a state in the state space. The state space is the possibly infinite set of states. \n",
              "Search tree describes the path between these states. \n",
              "\n",
              "Best-first search (Dijktra’s, goes with the min cost first and expands from there). \n",
              "\n",
              "Three kinds of queues are used in search algorithms: \n",
              "1.\tA priority queue first pops the node with the minimum cost( used in best-first search)\n",
              "2.\t FIFO queue pops the node that was added to the queue first(BFS)\n",
              "3.\tLIFO queue (stack) pops first the most recently added node(DFS) \n",
              "Graph search checks redundant paths, tree-like does not. \n",
              "To be complete, a search algorithm must be systematic in the way it explores an infinite state space\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " If all actions have same cost, BFS is best. BFS finds solution with min num of actions because it has generated all the nodes at d-1 depth. It does however have high space complexity. \n",
              "If actions have different costs, Best-first is the way to go (Dijkstra’s aka uniform cost search). \n",
              "A variant of DFS  called backtracking search uses even less memory.\n",
              "To avoid infinite loop in DFS you can apply a depth limit and treat that limit like there are no successors at that point. Furthermore you can do iterative deepening which tries depth values increasing every time. \n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Reflex Agent – ignores percept history, just reacts to current percept \n",
              "Problem-Solving Agent – Needs to do search, process of finding a solution\n",
              "Task Environment:\n",
              "If Fully observable, deterministic, known => fixed sequence of actions\n",
              "If partially observable, non deterministic => branching strategy\n",
              "\n",
              "Process: State goal, formulate search problem, find solution\n",
              "\n",
              "Formal Definition\n",
              "1)\tState: set S\n",
              "2)\tInitial state\n",
              "3)\tActions\n",
              "4)\tTransition model (successors)\n",
              "5)\tPath Cost (performance measure)\n",
              "6)\tGoal test\n",
              "State Space = all states\n",
              "Path = sequence of actions\n",
              "Frontier = states available for expanding \n",
              "Solution = Path of states that satisfy the goal test\n",
              "\n",
              "World is complex and you need to do an abstraction to be able to approach it. \n",
              "Graph vs Tree = Graph uses queue avoids infinite loops\n",
              "Uninformed Search = all nodes look equally good \n",
              "Informed Search = Some nodes can be ranked above others \n",
              "\n",
              "How we evaluate:\n",
              "Completeness = Does it find the Solution\n",
              "Optimality  = Does it find the optimal (lowest cost) solution\n",
              "Time Complexity = # of nodes it visit \n",
              "Space = # of nodes in memory\n",
              "\n",
              "BFS \n",
              "Expand to shallowest node \n",
              "Uses FIFO queue\n",
              "It is complete and optimal\n",
              "Time O(b^d)\n",
              "Space O(b^d)\n",
              "\n",
              "DFS\n",
              "Expand deepest \n",
              "LIFO queue – successors go to the front \n",
              "It’s not complete if there are loops \n",
              "Not optimal \n",
              "Time O(b^m)\n",
              "Space 0(b *m) linear! \n",
              "\n",
              "DFS vs BFS: \n",
              "DFS if it’s space-restricted and long paths terminate quickly. Search can be fine-tuned\n",
              "BFS if possible infinite paths, some solutions are short and can discard unlikely paths. \n",
              "\n",
              "Depth limit and Iterative … look at table. \n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Greedy best-first search is a form of best-first search that expands first the node with the lowest value—the node that appears to be closest to the goal\n",
        "f(n) = h(n).\n",
        "\n",
        "A* search\n",
        "a best-first search that uses the evaluation function f(n) = g(n) + h(n)\n",
        "it’s complete – cost optimality depends on properties of the heuristic (admissibility). If heuristic is admissible, it’s cost optimal. \n",
        "It has consistency which is a form of the triangle equality – no two sides can be shorter than one. \n",
        "It’s efficient because it prunes nodes that are not necessary. \n",
        "\n",
        "Other search algorithms\n",
        "Bounded suboptimal – within a constant factor\n",
        "Bounded cost -  as long as cost is below certain C\n",
        "Unbounded cost = any cost as long as it’s done quickly \n",
        "\n",
        "Issue with A* is its use of memory (visited, to visit etc)\n",
        "There is terative deepening search = won’t keep all reached states (risk visiting them many times). \n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" Heuristics: \n",
        "A typical is manhattan distance, \n",
        "Effective branching factor  - closest to 1 is best. \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform Cost = Moves away from unit cost. Used in weighted graphs. Similar to BFS but uses priority queue with next node being the lowest cost. Another difference is that it tests goal when selected for expansion, not when added to frontier. \n",
        "\n",
        "Heuristic is an educated guess that reduces the space of possible solutions. \n",
        "\n",
        "Greedy Best-First Search – Uses priority queue based on the h(n)  - the heuristic, not the lowest cost. \n",
        "It’s NOT optimal  - it does not find the shorter, it might not make it to the queue\n",
        "It’s NOT complete because it can get stuck in loops. \n",
        "\n",
        "A* - Expands to most promising node first with the lowest f(n) where:\n",
        " F(n) = g(n) + h(n) where g(n) is cost so far and h(n) is heuristic cost. \n",
        "\n",
        "Heuristic has to be admissible. Whether a heuristic is better is called dominance. A dominant heuristic will have a higher heuristic cost at every node. It still has to be less than the actual distance. \n",
        "\n",
        "A heuristic is admissible is greater than zero and less than true cost. \n",
        "\n",
        "Properties of A* - expand in different order by including cost so far. That will avoid going in the wrong direction and being optimal and complete. \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 650
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "5eff854c-ee8a-4460-a5f8-f039631d82e7"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Greedy best-first search is a form of best-first search that expands first the node with the lowest value—the node that appears to be closest to the goal\n",
              "f(n) = h(n).\n",
              "\n",
              "A* search\n",
              "a best-first search that uses the evaluation function f(n) = g(n) + h(n)\n",
              "it’s complete – cost optimality depends on properties of the heuristic (admissibility). If heuristic is admissible, it’s cost optimal. \n",
              "It has consistency which is a form of the triangle equality – no two sides can be shorter than one. \n",
              "It’s efficient because it prunes nodes that are not necessary. \n",
              "\n",
              "Other search algorithms\n",
              "Bounded suboptimal – within a constant factor\n",
              "Bounded cost -  as long as cost is below certain C\n",
              "Unbounded cost = any cost as long as it’s done quickly \n",
              "\n",
              "Issue with A* is its use of memory (visited, to visit etc)\n",
              "There is terative deepening search = won’t keep all reached states (risk visiting them many times). \n",
              " \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Heuristics: \n",
              "A typical is manhattan distance, \n",
              "Effective branching factor  - closest to 1 is best. \n",
              " \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform Cost = Moves away from unit cost. Used in weighted graphs. Similar to BFS but uses priority queue with next node being the lowest cost. Another difference is that it tests goal when selected for expansion, not when added to frontier. \n",
              "\n",
              "Heuristic is an educated guess that reduces the space of possible solutions. \n",
              "\n",
              "Greedy Best-First Search – Uses priority queue based on the h(n)  - the heuristic, not the lowest cost. \n",
              "It’s NOT optimal  - it does not find the shorter, it might not make it to the queue\n",
              "It’s NOT complete because it can get stuck in loops. \n",
              "\n",
              "A* - Expands to most promising node first with the lowest f(n) where:\n",
              " F(n) = g(n) + h(n) where g(n) is cost so far and h(n) is heuristic cost. \n",
              "\n",
              "Heuristic has to be admissible. Whether a heuristic is better is called dominance. A dominant heuristic will have a higher heuristic cost at every node. It still has to be less than the actual distance. \n",
              "\n",
              "A heuristic is admissible is greater than zero and less than true cost. \n",
              "\n",
              "Properties of A* - expand in different order by including cost so far. That will avoid going in the wrong direction and being optimal and complete. \n",
              " \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games. \"\"\"\n",
        "chapter5_2 = \"\"\" Minimax calculates the minimax value of each state in the tree. The value is the utility of being in that space. Minimax performs a complete depth first exploration of the game tree. \n",
        "Time complexity is o(b^m) and space O(bm). Not practical for very large games. \n",
        "\n",
        "Best way to think of alpha-beta\n",
        "Alpha: value of best choice we have found so far for MAX (“at least)\n",
        "Beta: value of best choice so far for MIN (“at most”)\n",
        "\n",
        "Can also do iterative deepening. \n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" Because time is limited, we can cut off early by using a heuristic evaluation function treating nodes as if they were terminal. (chess pieces, etc). And we can calculate here expected value. \n",
        "\n",
        "There is other type of pruning called forward pruning which gets rid of moves that look like “bad moves”. There is a ProbCut algorithm which is a version of the alpha beta that uses statistics from past experiences. \n",
        "\n",
        "Another way to do this is to do lookup for common “moves”. Like openings in chess. \n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" EXPECTIMAX\n",
        "Stochastic games bring a random element like dice. The nodes are chance nodes, in addition to min and max nodes. We base our decision on expected value. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" In a simple game, environment is:\n",
        "Static – no change while you decide\n",
        "Discrete – final set of actions\n",
        "Observable – nothing hidden\n",
        "Multi agent – more than 1 player\n",
        "Strategic \n",
        "\n",
        "In a complicated game, it is continuous and possibly stochastic. \n",
        "\n",
        "Games as search: \n",
        "Initial state – how is board when it starts\n",
        "Successor function – available moves \n",
        "Terminal state – when the game is over\n",
        "Utility function – value at the terminal state\n",
        "Max – uses search tree to move\n",
        "\n",
        "MINIMAX\n",
        "You run evaluation function to get an idea of how good position is (tictactoe example)\n",
        "You assume opponent is rational \n",
        "\n",
        "Process: \n",
        "Start with Max \n",
        "Expand tree number of plies\n",
        "Apply evaluation function to each leaf\n",
        "Calculate back up value bottom up \n",
        "Pick up move that benefits max at root\n",
        "Wait for min to move \n",
        "\n",
        "Alpha beta pruning, does not evaluate unnecessary leaves \n",
        "One limitation of alpha-beta is the assumption that leaves are randomly distributed in the last layer\n",
        "\n",
        "EXPECTIMAX\n",
        "Uses expected value, not worst case min value\n",
        "You can’t do pruning as easily. \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1040
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "7215d24c-0f25-4e89-b62f-569d8262cb13"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games. \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Minimax calculates the minimax value of each state in the tree. The value is the utility of being in that space. Minimax performs a complete depth first exploration of the game tree. \n",
              "Time complexity is o(b^m) and space O(bm). Not practical for very large games. \n",
              "\n",
              "Best way to think of alpha-beta\n",
              "Alpha: value of best choice we have found so far for MAX (“at least)\n",
              "Beta: value of best choice so far for MIN (“at most”)\n",
              "\n",
              "Can also do iterative deepening. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Because time is limited, we can cut off early by using a heuristic evaluation function treating nodes as if they were terminal. (chess pieces, etc). And we can calculate here expected value. \n",
              "\n",
              "There is other type of pruning called forward pruning which gets rid of moves that look like “bad moves”. There is a ProbCut algorithm which is a version of the alpha beta that uses statistics from past experiences. \n",
              "\n",
              "Another way to do this is to do lookup for common “moves”. Like openings in chess. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " EXPECTIMAX\n",
              "Stochastic games bring a random element like dice. The nodes are chance nodes, in addition to min and max nodes. We base our decision on expected value. \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " In a simple game, environment is:\n",
              "Static – no change while you decide\n",
              "Discrete – final set of actions\n",
              "Observable – nothing hidden\n",
              "Multi agent – more than 1 player\n",
              "Strategic \n",
              "\n",
              "In a complicated game, it is continuous and possibly stochastic. \n",
              "\n",
              "Games as search: \n",
              "Initial state – how is board when it starts\n",
              "Successor function – available moves \n",
              "Terminal state – when the game is over\n",
              "Utility function – value at the terminal state\n",
              "Max – uses search tree to move\n",
              "\n",
              "MINIMAX\n",
              "You run evaluation function to get an idea of how good position is (tictactoe example)\n",
              "You assume opponent is rational \n",
              "\n",
              "Process: \n",
              "Start with Max \n",
              "Expand tree number of plies\n",
              "Apply evaluation function to each leaf\n",
              "Calculate back up value bottom up \n",
              "Pick up move that benefits max at root\n",
              "Wait for min to move \n",
              "\n",
              "Alpha beta pruning, does not evaluate unnecessary leaves \n",
              "One limitation of alpha-beta is the assumption that leaves are randomly distributed in the last layer\n",
              "\n",
              "EXPECTIMAX\n",
              "Uses expected value, not worst case min value\n",
              "You can’t do pruning as easily. \n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Higher order constraints also known as global constraints (two + two = four) \"\"\"\n",
        "chapter6_2 = \"\"\" constraint propagation: use the constraints to reduce the number of values for a variable\n",
        "local consistency  - when enforced eliminates inconsistent values\n",
        "arc-consistent  - if every value in its domain satisfies the variable’s binary constraints\n",
        "\n",
        "Arc consistency is enforced through AC-3 – a queue of Arcs to consider, pops one at random and if it reduces the value in any way, it goes back in the queue and it runs again until there are no more values changed. \n",
        "\n",
        "AC3 domain size d, c constraints, n variables. Time is worst case O(cd^3)\n",
        "\n",
        "Path consistency: tightens binary constraints by looking at triples of variables and using implicit constraints. \n",
        "K-consistency: a CSP is k-consistent if for any set of k-1 variables, a consistent value can be assigned to any kth variable. \n",
        "Global constraints -  arbitrary number of variables. Like Alldiff constraints (Sudoku). \n",
        "Resource constraints\n",
        "Bounds propagation – airline scheduling problem (domains represented by upper and lower bounds). \n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking – When after constraint propagation you will have many possible values. You have to search for solution. \n",
        "Select unassigned variable in the code means you pick a random number to see if it works. \n",
        "MRV (minimum remaining values – pick the variable with fewest legal values. ( aka most constrained variable or fail first)\n",
        "\n",
        "Inference – simplest for is “forward checking”. If a variable X is assigned, check arc consistency. For ever unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is not consistent with value of X. \n",
        "\n",
        "MAC (maintaining arc consistency) takes it a step further  - more powerful thatn forward checking. \n",
        "Chronological backtracking backs up the preceding variable (the most recent). \n",
        "Constraint learning – finds the minimum set of values from the conflict set that causes the problem. This set is called “no good” \n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search is done with MIN CONFLICTS (n queens) \"\"\"\n",
        "chapter6_5 = \"\"\" Big problems can be reduced to independent subproblems. \n",
        "Can be determined by finding connected components of the graph. \n",
        "This can be done by ordering it as a tree and doing a topological sort. \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" World is single agent, deterministic, fully observed and discrete state space. \n",
        "Sequence is unimportant. \n",
        "3 elements: \n",
        "Variables\n",
        "Domain of possible values\n",
        "Constraints\n",
        "\n",
        "A consistent assignment does not violate constraints, complete when each variable gets a value. \n",
        "\n",
        "Solution is complete and consistent. \n",
        "\n",
        "Applications: map coloring, vlsi, scheduling\n",
        "\n",
        "Nodes are variables, arcs are constraints\n",
        "Constraints are unary (one), binary(two) higher order (3+). \n",
        "\n",
        "Soft constraints (preferences) can be acheieved with a cost. \n",
        "\n",
        "Solved as a search problem: \n",
        "Initial state – empty assignment\n",
        "Successor function – assign value as long as it doesn’t violate constraints\n",
        "Goal test – assignment is complete \n",
        "Path cost – constant cost for each step \n",
        "\n",
        "DFS ideal. It’s commutative (order doesn’t affect outcome) and that allows to prune many branches of trees. (not graph) \n",
        "\n",
        "DFS with single variable is called backtracking. Basic uninformed algorithm for CSP. \n",
        "\n",
        "Backtracking can be improved with Heuristics: (Australia)\n",
        "1)\tMost constrained variable (least number of possible values)\n",
        "2)\tMost constraining variable (pick variable that puts most constraints on others)\n",
        "3)\tLeast constraining value – pick the one that will rule out the fewest variables in other variables\n",
        "4)\tForward checking \n",
        "\n",
        "Arc Consistency\n",
        "The main idea here is inference. Edges are converted into arcs. \n",
        "\n",
        "Constraint propagation – use constraints to eliminate labels simultaneously:\n",
        "Assign every node all possible values \n",
        "For every neighbor remove value where arc is not consistent. \n",
        "\n",
        "\n",
        "AC3 \n",
        "Next step. \n",
        "1)\tQueue with all the arcs\n",
        "2)\tRemove inconsistent values\n",
        "3)\tAdd back neighbors to queue whenever a node has values removed \n",
        "\n",
        "Worst case complexity is O(n^2d^3) \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1159
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "df91a3f2-47ba-4941-f861-3ae35441d074"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Higher order constraints also known as global constraints (two + two = four) \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " constraint propagation: use the constraints to reduce the number of values for a variable\n",
              "local consistency  - when enforced eliminates inconsistent values\n",
              "arc-consistent  - if every value in its domain satisfies the variable’s binary constraints\n",
              "\n",
              "Arc consistency is enforced through AC-3 – a queue of Arcs to consider, pops one at random and if it reduces the value in any way, it goes back in the queue and it runs again until there are no more values changed. \n",
              "\n",
              "AC3 domain size d, c constraints, n variables. Time is worst case O(cd^3)\n",
              "\n",
              "Path consistency: tightens binary constraints by looking at triples of variables and using implicit constraints. \n",
              "K-consistency: a CSP is k-consistent if for any set of k-1 variables, a consistent value can be assigned to any kth variable. \n",
              "Global constraints -  arbitrary number of variables. Like Alldiff constraints (Sudoku). \n",
              "Resource constraints\n",
              "Bounds propagation – airline scheduling problem (domains represented by upper and lower bounds). \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Backtracking – When after constraint propagation you will have many possible values. You have to search for solution. \n",
              "Select unassigned variable in the code means you pick a random number to see if it works. \n",
              "MRV (minimum remaining values – pick the variable with fewest legal values. ( aka most constrained variable or fail first)\n",
              "\n",
              "Inference – simplest for is “forward checking”. If a variable X is assigned, check arc consistency. For ever unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is not consistent with value of X. \n",
              "\n",
              "MAC (maintaining arc consistency) takes it a step further  - more powerful thatn forward checking. \n",
              "Chronological backtracking backs up the preceding variable (the most recent). \n",
              "Constraint learning – finds the minimum set of values from the conflict set that causes the problem. This set is called “no good” \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Local search is done with MIN CONFLICTS (n queens) \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Big problems can be reduced to independent subproblems. \n",
              "Can be determined by finding connected components of the graph. \n",
              "This can be done by ordering it as a tree and doing a topological sort. \n",
              "\n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " World is single agent, deterministic, fully observed and discrete state space. \n",
              "Sequence is unimportant. \n",
              "3 elements: \n",
              "Variables\n",
              "Domain of possible values\n",
              "Constraints\n",
              "\n",
              "A consistent assignment does not violate constraints, complete when each variable gets a value. \n",
              "\n",
              "Solution is complete and consistent. \n",
              "\n",
              "Applications: map coloring, vlsi, scheduling\n",
              "\n",
              "Nodes are variables, arcs are constraints\n",
              "Constraints are unary (one), binary(two) higher order (3+). \n",
              "\n",
              "Soft constraints (preferences) can be acheieved with a cost. \n",
              "\n",
              "Solved as a search problem: \n",
              "Initial state – empty assignment\n",
              "Successor function – assign value as long as it doesn’t violate constraints\n",
              "Goal test – assignment is complete \n",
              "Path cost – constant cost for each step \n",
              "\n",
              "DFS ideal. It’s commutative (order doesn’t affect outcome) and that allows to prune many branches of trees. (not graph) \n",
              "\n",
              "DFS with single variable is called backtracking. Basic uninformed algorithm for CSP. \n",
              "\n",
              "Backtracking can be improved with Heuristics: (Australia)\n",
              "1)\tMost constrained variable (least number of possible values)\n",
              "2)\tMost constraining variable (pick variable that puts most constraints on others)\n",
              "3)\tLeast constraining value – pick the one that will rule out the fewest variables in other variables\n",
              "4)\tForward checking \n",
              "\n",
              "Arc Consistency\n",
              "The main idea here is inference. Edges are converted into arcs. \n",
              "\n",
              "Constraint propagation – use constraints to eliminate labels simultaneously:\n",
              "Assign every node all possible values \n",
              "For every neighbor remove value where arc is not consistent. \n",
              "\n",
              "\n",
              "AC3 \n",
              "Next step. \n",
              "1)\tQueue with all the arcs\n",
              "2)\tRemove inconsistent values\n",
              "3)\tAdd back neighbors to queue whenever a node has values removed \n",
              "\n",
              "Worst case complexity is O(n^2d^3) \n",
              " \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" KB may contain some background knowledge.  \"\"\"\n",
        "chapter7_2 = \"\"\" For the record I think Wampas are adorable and are being unfairly attacked. They’re just trying to feed their baby wampas. Shame on you Skywalker. \n",
        "\n",
        "Performance Measure – cost and rewards\n",
        "Environment – grid\n",
        "Actuators – what the agent can do \n",
        "Sensors – what agent perceives - returned in the form of a vector\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" Logic defines semantics which tell us the truth of a sentence with respect to a possible world. \n",
        "Entailment is used to derive conclusions, this is logical inference. \n",
        "Inference algorithm is called model checking because it checks all possible models where a is true and in which KB is true. \n",
        "\n",
        "Soundness is important. It means it derives ONLY entailed sentences \n",
        "Completeness is also important = if it derives any sentence that is entailed \n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"  \"\"\"\n",
        "chapter7_5 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Knowledge-Based Agents use reasoning. Main component is Knowledge Base (KB)\n",
        "Knowledge Representation language contains an assertion\n",
        "\n",
        "2 types:\n",
        "Axiom – Given\n",
        "Derived – derived from others done through inference \n",
        "\n",
        "Wampa word- is discrete, deterministic, single agent, sequential and partially observable \n",
        "\n",
        "Logic serves as a representation of knowledge based agents. This is propositional logic. \n",
        "KB is sentences in representation language\n",
        "Representation language has a syntax\n",
        "A logic defines the semantics (meaning) of their sentences \n",
        "Semantics define the truth of each sentence with respect to a possible world, which will be called model. \n",
        "\n",
        "Models are mathematical abstractions\n",
        "Is a is true in model m \n",
        "We say m satisfies a  or m is a model of a\n",
        "M(a) = set of models of a\n",
        "\n",
        "Logical entailment is when one sentence follows logically another one. If a entails B, a is more specific than B. \n",
        "My pet is a cat entails my pet is an animal \n",
        "Logical inference is when entailment is applied to derive conclusions. We do that through the design of inference algorithms. \n",
        "\n",
        "Propositional logic\n",
        "Uses atonic sentences that can be true of false. \n",
        "There should be : \n",
        "\n",
        "Soundness – inference algorithm should only derive entailed sentences \n",
        "Completeness – the algorithm is complete if it can derive all the sentences that are entailed \n",
        "\n",
        "Theorem proving: \n",
        "CNF – Conjunctive Normal Form \n",
        "Eliminate  by replacing with a => B AND B => A\n",
        "Eliminate => by replacing with NOT a V not B\n",
        "Move NOT inwards, eliminate double negation and apply Demorgan\n",
        "Apply distributivity law to distribute V over AND wherever possible \n",
        "\n",
        "Forward Chaining: Data-driven reasoning\n",
        "Start with known data \n",
        "Add new premises as percepts come in\n",
        "Apply forward chaining algo and derive new conclusions \n",
        "\n",
        "Backward Chaining – works back from a query goal-directed reasoning) \n",
        "If we know query is true do nothing\n",
        "Otherwise work back to find implications in the KBthat have the query as a conclusion\n",
        "If all premises of a query prove to be true, the query is true\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 873
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "f299a1bb-b128-49a6-e5dc-1b24ab50c636"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " KB may contain some background knowledge.  \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " For the record I think Wampas are adorable and are being unfairly attacked. They’re just trying to feed their baby wampas. Shame on you Skywalker. \n",
              "\n",
              "Performance Measure – cost and rewards\n",
              "Environment – grid\n",
              "Actuators – what the agent can do \n",
              "Sensors – what agent perceives - returned in the form of a vector\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Logic defines semantics which tell us the truth of a sentence with respect to a possible world. \n",
              "Entailment is used to derive conclusions, this is logical inference. \n",
              "Inference algorithm is called model checking because it checks all possible models where a is true and in which KB is true. \n",
              "\n",
              "Soundness is important. It means it derives ONLY entailed sentences \n",
              "Completeness is also important = if it derives any sentence that is entailed \n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "  \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Knowledge-Based Agents use reasoning. Main component is Knowledge Base (KB)\n",
              "Knowledge Representation language contains an assertion\n",
              "\n",
              "2 types:\n",
              "Axiom – Given\n",
              "Derived – derived from others done through inference \n",
              "\n",
              "Wampa word- is discrete, deterministic, single agent, sequential and partially observable \n",
              "\n",
              "Logic serves as a representation of knowledge based agents. This is propositional logic. \n",
              "KB is sentences in representation language\n",
              "Representation language has a syntax\n",
              "A logic defines the semantics (meaning) of their sentences \n",
              "Semantics define the truth of each sentence with respect to a possible world, which will be called model. \n",
              "\n",
              "Models are mathematical abstractions\n",
              "Is a is true in model m \n",
              "We say m satisfies a  or m is a model of a\n",
              "M(a) = set of models of a\n",
              "\n",
              "Logical entailment is when one sentence follows logically another one. If a entails B, a is more specific than B. \n",
              "My pet is a cat entails my pet is an animal \n",
              "Logical inference is when entailment is applied to derive conclusions. We do that through the design of inference algorithms. \n",
              "\n",
              "Propositional logic\n",
              "Uses atonic sentences that can be true of false. \n",
              "There should be : \n",
              "\n",
              "Soundness – inference algorithm should only derive entailed sentences \n",
              "Completeness – the algorithm is complete if it can derive all the sentences that are entailed \n",
              "\n",
              "Theorem proving: \n",
              "CNF – Conjunctive Normal Form \n",
              "Eliminate  by replacing with a => B AND B => A\n",
              "Eliminate => by replacing with NOT a V not B\n",
              "Move NOT inwards, eliminate double negation and apply Demorgan\n",
              "Apply distributivity law to distribute V over AND wherever possible \n",
              "\n",
              "Forward Chaining: Data-driven reasoning\n",
              "Start with known data \n",
              "Add new premises as percepts come in\n",
              "Apply forward chaining algo and derive new conclusions \n",
              "\n",
              "Backward Chaining – works back from a query goal-directed reasoning) \n",
              "If we know query is true do nothing\n",
              "Otherwise work back to find implications in the KBthat have the query as a conclusion\n",
              "If all premises of a query prove to be true, the query is true\n",
              "\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 20,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 6404
        },
        "id": "T3cm1WV542_a",
        "outputId": "347b0655-bb04-437d-f3cb-58af0c1d347c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " \n",
              "An agent perceives through sensors and acts through actuators.\n",
              "\n",
              "Percept to refer to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
              "\n",
              "Agent’s behavior when percept sequence leads to an action. The agent function for an artificial agent will be implemented by an agent program.  The agent function is an abstract mathematical description; the agent program is an implementation. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure.\n",
              "\n",
              "An omniscient agent knows the actual outcome of its actions and can act accordingly; but omniscience is impossible in reality.\n",
              "\n",
              "Rational agent maximizes expected performance. \n",
              "Information gathering – doing actions to modify future percepts. \n",
              " \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " \n",
              "Task environment. PEAS (Performance, Environment, Actuators, Sensors) description:\n",
              "\n",
              "Properties: \n",
              "\n",
              "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: Fully observable if an agent’s sensors give it access to the complete state of the environment at each point in time.\n",
              "\n",
              "SINGLE-AGENT VS. MULTIAGENT: How many parties are involved.\n",
              "\n",
              "COMPETITIVE VS COOPERATIVE: Self described\n",
              "\n",
              "Deterministic vs. nondeterministic. If the next state of the environment is completely determined by the current state and the action executed by the agent, the environment is deterministic, otherwise nondeterministic. Stochastic if it deals with probabilities. \n",
              "\n",
              "EPISODIC VS. SEQUENTIAL: In episodic the agent receives a percept and then performs a single action. The next episode does not depend on the actions taken in previous episodes. Many classification tasks are episodic. Chess and taxi driving are sequential. Episodic is simpler because you don’t need to think ahead. \n",
              "\n",
              "STATIC VS. DYNAMIC: If the environment can change while an agent is figuring out solution, environment is dynamic, otherwise it’s static. If the environment itself does not change with the passage of time but the agent’s performance score does, the environment is semi dynamic. Taxi dynamic, chess with clock semi dynamic, crossword static. \n",
              "\n",
              "DISCRETE VS. CONTINUOUS: Applies to the way time is handled in the environment. Chess is discrete, taxi is continuous.\n",
              "\n",
              "KNOWN VS. UNKNOWN: Does agent know “laws of physics” of the environment. An unknown environment can be fully observable (videogame visible, what buttons do is not known). \n",
              "\n",
              "The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. Taxi driving is hard in all these senses\n",
              "AI aims to design an agent that implements the agent function,  the mapping from percepts to actions. The architecture will be the device with sensors and actuators. \n",
              "agent = architecture + program .\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " AGENTS\n",
              "Simple reflex agent. These agents act on current percept, and ignore the rest of the percept history. It may randomize to escape infinite loop. And it can do better than other agents. \n",
              "\n",
              "When there is partial observability, agent should maintain some internal state that depends on history and reflects some of the unobserved aspects of the current state. \n",
              "\n",
              "“how the world works” is a transition model of the world.  How info of the world is reflected in percepts is called sensor model. \n",
              "\n",
              "Agent uses the transition model and sensor model to keep track of the state of the world, this makes it a  model-based agent.\n",
              "\n",
              "Goal based agent = self explanatory \n",
              "\n",
              "Utility-based agents behave ‘well’ in most environments. There is a utility function that is an internalization of the performance measure. The agent will try to maximize its expected utility. \n",
              "\n",
              "Model-free agent learns what action is best in a particular situation without ever learning exactly how that action changes the environment.\n",
              "\n",
              "Learning Agents\n",
              "Learning element, is responsible for making improvements, and the performance element selects external actions.\n",
              "The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to improve it in the future.\n",
              "Problem generator. It is responsible for suggesting actions that will lead to new and informative experiences\n",
              "Feedback comes in the form of reward or penalty. \n",
              "\n",
              "How do they work? \n",
              "In an atomic representation each state of the world is indivisible—it has no internal structure\n",
              "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. \n",
              "A structured representation, in which objects like cars and dogs and their relationships can be described explicitly. \n",
              "The axis along which atomic, factored, and structured representations lie is the axis of increasing expressiveness.\n",
              "The mapping between concepts and memory locations is the localist representation. If the representation of a concept is spread over many locations (memory) , it’s a  distributed representation.\n",
              "\n",
              " \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " There are four-phase problem-solving process:\n",
              "1.\tGOAL FORMULATION\n",
              "2.\tPROBLEM FORMULATION: An abstraction of the relevant part of the world. Agent describes states and the actions necessary to reach the goal. \n",
              "3.\tSEARCH: Agent simulates actions in its model and searches until it reaches the goal. This is a solution. \n",
              "4.\tEXECUTION – Takes the actual steps. \n",
              "\n",
              "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost among all solutions\n",
              "\n",
              "The removal of detail from a representation is called abstraction.\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " A standardized problem is used to show other problem solving methods \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " A search algorithm takes a search problem as input and returns a solution. Creates a tree in which each node corresponds to a state in the state space. The state space is the possibly infinite set of states. \n",
              "Search tree describes the path between these states. \n",
              "\n",
              "Best-first search (Dijktra’s, goes with the min cost first and expands from there). \n",
              "\n",
              "Three kinds of queues are used in search algorithms: \n",
              "1.\tA priority queue first pops the node with the minimum cost( used in best-first search)\n",
              "2.\t FIFO queue pops the node that was added to the queue first(BFS)\n",
              "3.\tLIFO queue (stack) pops first the most recently added node(DFS) \n",
              "Graph search checks redundant paths, tree-like does not. \n",
              "To be complete, a search algorithm must be systematic in the way it explores an infinite state space\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " If all actions have same cost, BFS is best. BFS finds solution with min num of actions because it has generated all the nodes at d-1 depth. It does however have high space complexity. \n",
              "If actions have different costs, Best-first is the way to go (Dijkstra’s aka uniform cost search). \n",
              "A variant of DFS  called backtracking search uses even less memory.\n",
              "To avoid infinite loop in DFS you can apply a depth limit and treat that limit like there are no successors at that point. Furthermore you can do iterative deepening which tries depth values increasing every time. \n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Reflex Agent – ignores percept history, just reacts to current percept \n",
              "Problem-Solving Agent – Needs to do search, process of finding a solution\n",
              "Task Environment:\n",
              "If Fully observable, deterministic, known => fixed sequence of actions\n",
              "If partially observable, non deterministic => branching strategy\n",
              "\n",
              "Process: State goal, formulate search problem, find solution\n",
              "\n",
              "Formal Definition\n",
              "1)\tState: set S\n",
              "2)\tInitial state\n",
              "3)\tActions\n",
              "4)\tTransition model (successors)\n",
              "5)\tPath Cost (performance measure)\n",
              "6)\tGoal test\n",
              "State Space = all states\n",
              "Path = sequence of actions\n",
              "Frontier = states available for expanding \n",
              "Solution = Path of states that satisfy the goal test\n",
              "\n",
              "World is complex and you need to do an abstraction to be able to approach it. \n",
              "Graph vs Tree = Graph uses queue avoids infinite loops\n",
              "Uninformed Search = all nodes look equally good \n",
              "Informed Search = Some nodes can be ranked above others \n",
              "\n",
              "How we evaluate:\n",
              "Completeness = Does it find the Solution\n",
              "Optimality  = Does it find the optimal (lowest cost) solution\n",
              "Time Complexity = # of nodes it visit \n",
              "Space = # of nodes in memory\n",
              "\n",
              "BFS \n",
              "Expand to shallowest node \n",
              "Uses FIFO queue\n",
              "It is complete and optimal\n",
              "Time O(b^d)\n",
              "Space O(b^d)\n",
              "\n",
              "DFS\n",
              "Expand deepest \n",
              "LIFO queue – successors go to the front \n",
              "It’s not complete if there are loops \n",
              "Not optimal \n",
              "Time O(b^m)\n",
              "Space 0(b *m) linear! \n",
              "\n",
              "DFS vs BFS: \n",
              "DFS if it’s space-restricted and long paths terminate quickly. Search can be fine-tuned\n",
              "BFS if possible infinite paths, some solutions are short and can discard unlikely paths. \n",
              "\n",
              "Depth limit and Iterative … look at table. \n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Greedy best-first search is a form of best-first search that expands first the node with the lowest value—the node that appears to be closest to the goal\n",
              "f(n) = h(n).\n",
              "\n",
              "A* search\n",
              "a best-first search that uses the evaluation function f(n) = g(n) + h(n)\n",
              "it’s complete – cost optimality depends on properties of the heuristic (admissibility). If heuristic is admissible, it’s cost optimal. \n",
              "It has consistency which is a form of the triangle equality – no two sides can be shorter than one. \n",
              "It’s efficient because it prunes nodes that are not necessary. \n",
              "\n",
              "Other search algorithms\n",
              "Bounded suboptimal – within a constant factor\n",
              "Bounded cost -  as long as cost is below certain C\n",
              "Unbounded cost = any cost as long as it’s done quickly \n",
              "\n",
              "Issue with A* is its use of memory (visited, to visit etc)\n",
              "There is terative deepening search = won’t keep all reached states (risk visiting them many times). \n",
              " \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Heuristics: \n",
              "A typical is manhattan distance, \n",
              "Effective branching factor  - closest to 1 is best. \n",
              " \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform Cost = Moves away from unit cost. Used in weighted graphs. Similar to BFS but uses priority queue with next node being the lowest cost. Another difference is that it tests goal when selected for expansion, not when added to frontier. \n",
              "\n",
              "Heuristic is an educated guess that reduces the space of possible solutions. \n",
              "\n",
              "Greedy Best-First Search – Uses priority queue based on the h(n)  - the heuristic, not the lowest cost. \n",
              "It’s NOT optimal  - it does not find the shorter, it might not make it to the queue\n",
              "It’s NOT complete because it can get stuck in loops. \n",
              "\n",
              "A* - Expands to most promising node first with the lowest f(n) where:\n",
              " F(n) = g(n) + h(n) where g(n) is cost so far and h(n) is heuristic cost. \n",
              "\n",
              "Heuristic has to be admissible. Whether a heuristic is better is called dominance. A dominant heuristic will have a higher heuristic cost at every node. It still has to be less than the actual distance. \n",
              "\n",
              "A heuristic is admissible is greater than zero and less than true cost. \n",
              "\n",
              "Properties of A* - expand in different order by including cost so far. That will avoid going in the wrong direction and being optimal and complete. \n",
              " \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " The games most commonly studied within AI (such as chess and Go) are what game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games. \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Minimax calculates the minimax value of each state in the tree. The value is the utility of being in that space. Minimax performs a complete depth first exploration of the game tree. \n",
              "Time complexity is o(b^m) and space O(bm). Not practical for very large games. \n",
              "\n",
              "Best way to think of alpha-beta\n",
              "Alpha: value of best choice we have found so far for MAX (“at least)\n",
              "Beta: value of best choice so far for MIN (“at most”)\n",
              "\n",
              "Can also do iterative deepening. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Because time is limited, we can cut off early by using a heuristic evaluation function treating nodes as if they were terminal. (chess pieces, etc). And we can calculate here expected value. \n",
              "\n",
              "There is other type of pruning called forward pruning which gets rid of moves that look like “bad moves”. There is a ProbCut algorithm which is a version of the alpha beta that uses statistics from past experiences. \n",
              "\n",
              "Another way to do this is to do lookup for common “moves”. Like openings in chess. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " EXPECTIMAX\n",
              "Stochastic games bring a random element like dice. The nodes are chance nodes, in addition to min and max nodes. We base our decision on expected value. \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " In a simple game, environment is:\n",
              "Static – no change while you decide\n",
              "Discrete – final set of actions\n",
              "Observable – nothing hidden\n",
              "Multi agent – more than 1 player\n",
              "Strategic \n",
              "\n",
              "In a complicated game, it is continuous and possibly stochastic. \n",
              "\n",
              "Games as search: \n",
              "Initial state – how is board when it starts\n",
              "Successor function – available moves \n",
              "Terminal state – when the game is over\n",
              "Utility function – value at the terminal state\n",
              "Max – uses search tree to move\n",
              "\n",
              "MINIMAX\n",
              "You run evaluation function to get an idea of how good position is (tictactoe example)\n",
              "You assume opponent is rational \n",
              "\n",
              "Process: \n",
              "Start with Max \n",
              "Expand tree number of plies\n",
              "Apply evaluation function to each leaf\n",
              "Calculate back up value bottom up \n",
              "Pick up move that benefits max at root\n",
              "Wait for min to move \n",
              "\n",
              "Alpha beta pruning, does not evaluate unnecessary leaves \n",
              "One limitation of alpha-beta is the assumption that leaves are randomly distributed in the last layer\n",
              "\n",
              "EXPECTIMAX\n",
              "Uses expected value, not worst case min value\n",
              "You can’t do pruning as easily. \n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Higher order constraints also known as global constraints (two + two = four) \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " constraint propagation: use the constraints to reduce the number of values for a variable\n",
              "local consistency  - when enforced eliminates inconsistent values\n",
              "arc-consistent  - if every value in its domain satisfies the variable’s binary constraints\n",
              "\n",
              "Arc consistency is enforced through AC-3 – a queue of Arcs to consider, pops one at random and if it reduces the value in any way, it goes back in the queue and it runs again until there are no more values changed. \n",
              "\n",
              "AC3 domain size d, c constraints, n variables. Time is worst case O(cd^3)\n",
              "\n",
              "Path consistency: tightens binary constraints by looking at triples of variables and using implicit constraints. \n",
              "K-consistency: a CSP is k-consistent if for any set of k-1 variables, a consistent value can be assigned to any kth variable. \n",
              "Global constraints -  arbitrary number of variables. Like Alldiff constraints (Sudoku). \n",
              "Resource constraints\n",
              "Bounds propagation – airline scheduling problem (domains represented by upper and lower bounds). \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Backtracking – When after constraint propagation you will have many possible values. You have to search for solution. \n",
              "Select unassigned variable in the code means you pick a random number to see if it works. \n",
              "MRV (minimum remaining values – pick the variable with fewest legal values. ( aka most constrained variable or fail first)\n",
              "\n",
              "Inference – simplest for is “forward checking”. If a variable X is assigned, check arc consistency. For ever unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is not consistent with value of X. \n",
              "\n",
              "MAC (maintaining arc consistency) takes it a step further  - more powerful thatn forward checking. \n",
              "Chronological backtracking backs up the preceding variable (the most recent). \n",
              "Constraint learning – finds the minimum set of values from the conflict set that causes the problem. This set is called “no good” \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Local search is done with MIN CONFLICTS (n queens) \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Big problems can be reduced to independent subproblems. \n",
              "Can be determined by finding connected components of the graph. \n",
              "This can be done by ordering it as a tree and doing a topological sort. \n",
              "\n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " World is single agent, deterministic, fully observed and discrete state space. \n",
              "Sequence is unimportant. \n",
              "3 elements: \n",
              "Variables\n",
              "Domain of possible values\n",
              "Constraints\n",
              "\n",
              "A consistent assignment does not violate constraints, complete when each variable gets a value. \n",
              "\n",
              "Solution is complete and consistent. \n",
              "\n",
              "Applications: map coloring, vlsi, scheduling\n",
              "\n",
              "Nodes are variables, arcs are constraints\n",
              "Constraints are unary (one), binary(two) higher order (3+). \n",
              "\n",
              "Soft constraints (preferences) can be acheieved with a cost. \n",
              "\n",
              "Solved as a search problem: \n",
              "Initial state – empty assignment\n",
              "Successor function – assign value as long as it doesn’t violate constraints\n",
              "Goal test – assignment is complete \n",
              "Path cost – constant cost for each step \n",
              "\n",
              "DFS ideal. It’s commutative (order doesn’t affect outcome) and that allows to prune many branches of trees. (not graph) \n",
              "\n",
              "DFS with single variable is called backtracking. Basic uninformed algorithm for CSP. \n",
              "\n",
              "Backtracking can be improved with Heuristics: (Australia)\n",
              "1)\tMost constrained variable (least number of possible values)\n",
              "2)\tMost constraining variable (pick variable that puts most constraints on others)\n",
              "3)\tLeast constraining value – pick the one that will rule out the fewest variables in other variables\n",
              "4)\tForward checking \n",
              "\n",
              "Arc Consistency\n",
              "The main idea here is inference. Edges are converted into arcs. \n",
              "\n",
              "Constraint propagation – use constraints to eliminate labels simultaneously:\n",
              "Assign every node all possible values \n",
              "For every neighbor remove value where arc is not consistent. \n",
              "\n",
              "\n",
              "AC3 \n",
              "Next step. \n",
              "1)\tQueue with all the arcs\n",
              "2)\tRemove inconsistent values\n",
              "3)\tAdd back neighbors to queue whenever a node has values removed \n",
              "\n",
              "Worst case complexity is O(n^2d^3) \n",
              " \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " KB may contain some background knowledge.  \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " For the record I think Wampas are adorable and are being unfairly attacked. They’re just trying to feed their baby wampas. Shame on you Skywalker. \n",
              "\n",
              "Performance Measure – cost and rewards\n",
              "Environment – grid\n",
              "Actuators – what the agent can do \n",
              "Sensors – what agent perceives - returned in the form of a vector\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Logic defines semantics which tell us the truth of a sentence with respect to a possible world. \n",
              "Entailment is used to derive conclusions, this is logical inference. \n",
              "Inference algorithm is called model checking because it checks all possible models where a is true and in which KB is true. \n",
              "\n",
              "Soundness is important. It means it derives ONLY entailed sentences \n",
              "Completeness is also important = if it derives any sentence that is entailed \n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "  \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Knowledge-Based Agents use reasoning. Main component is Knowledge Base (KB)\n",
              "Knowledge Representation language contains an assertion\n",
              "\n",
              "2 types:\n",
              "Axiom – Given\n",
              "Derived – derived from others done through inference \n",
              "\n",
              "Wampa word- is discrete, deterministic, single agent, sequential and partially observable \n",
              "\n",
              "Logic serves as a representation of knowledge based agents. This is propositional logic. \n",
              "KB is sentences in representation language\n",
              "Representation language has a syntax\n",
              "A logic defines the semantics (meaning) of their sentences \n",
              "Semantics define the truth of each sentence with respect to a possible world, which will be called model. \n",
              "\n",
              "Models are mathematical abstractions\n",
              "Is a is true in model m \n",
              "We say m satisfies a  or m is a model of a\n",
              "M(a) = set of models of a\n",
              "\n",
              "Logical entailment is when one sentence follows logically another one. If a entails B, a is more specific than B. \n",
              "My pet is a cat entails my pet is an animal \n",
              "Logical inference is when entailment is applied to derive conclusions. We do that through the design of inference algorithms. \n",
              "\n",
              "Propositional logic\n",
              "Uses atonic sentences that can be true of false. \n",
              "There should be : \n",
              "\n",
              "Soundness – inference algorithm should only derive entailed sentences \n",
              "Completeness – the algorithm is complete if it can derive all the sentences that are entailed \n",
              "\n",
              "Theorem proving: \n",
              "CNF – Conjunctive Normal Form \n",
              "Eliminate  by replacing with a => B AND B => A\n",
              "Eliminate => by replacing with NOT a V not B\n",
              "Move NOT inwards, eliminate double negation and apply Demorgan\n",
              "Apply distributivity law to distribute V over AND wherever possible \n",
              "\n",
              "Forward Chaining: Data-driven reasoning\n",
              "Start with known data \n",
              "Add new premises as percepts come in\n",
              "Apply forward chaining algo and derive new conclusions \n",
              "\n",
              "Backward Chaining – works back from a query goal-directed reasoning) \n",
              "If we know query is true do nothing\n",
              "Otherwise work back to find implications in the KBthat have the query as a conclusion\n",
              "If all premises of a query prove to be true, the query is true\n",
              "\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Midterm Notes final.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
