{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of DRAFT Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 500 word summary of the lectures for each model.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "80d605c8-0ead-4be4-f3f6-83dc97211e76"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e31cbd9d-e211-4d3c-c0fe-80fd6e4ea1e3"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "AI - field of understanding and building intelligence; how can machines be programmed to \\\n",
        "act effectively and safely in various situations and environments.\\n\n",
        "An intelligent agent can be defined to be one that acts rationally, aka doing the right thing.\\n\n",
        "How can we program computers to pass as a human? (Turing test)\\n\n",
        "1) Natural Language Processing - communicate successfully\\n\n",
        "2) Knowledge Representation - to remember what is heard/taught\\n\n",
        "3) Automated Reasoning - to answer questions and draw conclusions\\n\n",
        "4) ML - adapting, detection of patterns\\n\n",
        "The TOTAL Turing test encompasses the 4, in addition to being able to interact with the physical world.\\\n",
        "Would need:\\n\n",
        "5) Vision - for perception\\n\n",
        "6) Robotics - to manipulate objects/move\\n\n",
        "Rational Agent - an agent that always acts in a way to achieve the best outcome in certainty, and the best\n",
        "expected outcome in uncertainty\\n\n",
        "Value alignment problem - trying to achieve agreement between the humans preferences and the objective \\\n",
        "that is input into the machine. We strive to create machines that aren't just solely focused \\\n",
        "on achieving the objective by any means necessary, but machines that act cautiously in the pursuit \\\n",
        "of some objective. We want agents that are provably beneficial to humans.\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" 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 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\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"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9ebf48cf-766e-406c-9866-a99d9daec5de"
      },
      "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",
        "    if(len(summary) > 3000 or len(summary.split(' ')) > 500):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nAI - field of understanding and building intelligence; how can machines be programmed to act effectively and safely in various situations and environments.\n\nAn intelligent agent can be defined to be one that acts rationally, aka doing the right thing.\n\nHow can we program computers to pass as a human? (Turing test)\n\n1) Natural Language Processing - communicate successfully\n\n2) Knowledge Representation - to remember what is heard/taught\n\n3) Automated Reasoning - to answer questions and draw conclusions\n\n4) ML - adapting, detection of patterns\n\nThe TOTAL Turing test encompasses the 4, in addition to being able to interact with the physical world.Would need:\n\n5) Vision - for perception\n\n6) Robotics - to manipulate objects/move\n\nRational Agent - an agent that always acts in a way to achieve the best outcome in certainty, and the best\nexpected outcome in uncertainty\n\nValue alignment problem - trying to achieve agreement between the humans preferences and the objective that is input into the machine. We strive to create machines that aren't just solely focused on achieving the objective by any means necessary, but machines that act cautiously in the pursuit of some objective. We want agents that are provably beneficial to humans.\n \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 Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \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": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"An agent can ONLY commit an action based on information \\\n",
        "that has been perceived/stored in their percept sequence and their own knowledge. \\\n",
        "They cannot make decisions based on things they have yet to perceive.\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"agent\" : \"something that can perceive its environment and interact with it\",\n",
        "\"actuators\" : \"things that agents use to interact with the world (hands)\",\n",
        "\"percept\" : \"the information that an agent's sensors are perceiving\",\n",
        "\"percept sequence\" : \"history of everything that an agent has perceived\",\n",
        "\"agent function\" : \"maps a percept sequence to an action\",\n",
        "\"agent program\" : \"program that implements the agent function, a physical system\",\n",
        "\"rational agent\" : \"agent that strives to optimize the best expected outcome\",\n",
        "\"mutability\" : \"your definition here\",\n",
        "\n",
        "}"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 345
        },
        "outputId": "82fec875-fa01-4f68-8aa5-532d88ca99dd"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nAn agent can ONLY commit an action based on information that has been perceived/stored in their percept sequence and their own knowledge. They cannot make decisions based on things they have yet to perceive.\n\n## Module 2 Definitions\n* **Agent** - something that can perceive its environment and interact with it\n* **Actuators** - things that agents use to interact with the world (hands)\n* **Percept** - the information that an agent's sensors are perceiving\n* **Percept sequence** - history of everything that an agent has perceived\n* **Agent function** - maps a percept sequence to an action\n* **Agent program** - program that implements the agent function, a physical system\n* **Rational agent** - agent that strives to optimize the best expected outcome\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5bc5283a-34ce-425b-df67-8837ef86c88c"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "A SEARCH PROBLEM is made up of initial states, state space, goal state(s), transition model, \\\n",
        "actions, and an action cost function. We try to find the optimal solution, which is a solution \\\n",
        "with the lowest path cost out of all of the solutions, and asssume that all action costs are \\\n",
        "positive. \"\"\"\n",
        "chapter3_2 = \"\"\" There are two types of problems, standardized and real-world. Standardizes \\\n",
        "problems are created and used with the intention of being some benchmark. They are used to test \\\n",
        "the performance of algorithms. Real-world is like the real-world, the formulation is distinctive.\n",
        "\n",
        "A grid world problem is a grid where agents can move between cells, where its movements are specified \\\n",
        "to the problem. There may be obstacles in the cells, and agents may act upon these cells/interact \\\n",
        "with them in some way. The vacuum world, where the agent is a vacuum and the obstacles are the dirt \\\n",
        "in the cells, is one such problem.\n",
        "\n",
        "In a sokoban puzzle, the goal of an agent is to push a number of scattered boxed on a grid into \\\n",
        "designated spots, where there can only be at most one box per cell. In a grid with n empty cells \\\n",
        "and b boxes, there are $$n x n!/(b!(n-b)!)$$ states.\n",
        "\n",
        "There is also the sliding-tile puzzles, with the numbers in a 3x3 grid. Another variation is the \\\n",
        "parking lot one.\"\"\"\n",
        "chapter3_3 = \"\"\"Concerning search algorithms, their solution can be likened to a search tree that \\\n",
        "is superimposed over a state-space graph. Search algorithms form various paths, starting from the \\\n",
        "root node (starting state), and branch out in the paths until it finds the goal state. There is \\\n",
        "a distinction between the state space and the search tree; the state space is the set of possible \\\n",
        "infinite states of some problem, while a search tree is the description of the paths of some search \\\n",
        "algorithm, until it reaches the goal state. There is always a unique and distinct path back to the \\\n",
        "root node for any node in a search tree. The node can be expanded by considering the available \\\n",
        "actions of that specific node, and looking at the result function to see where the consequence of \\\n",
        "a specific action will end up, with each of the results being a newly generated (child) node. The \\\n",
        "frontier of a graph separates the interior and exterior regions of the graph, where the interior \\\n",
        "consists of nodes that have been reached and expanded, and exterior consisting of unreached nodes. \n",
        "\n",
        "A general approach to choose which node on a frontier to expand is BEST-first search. BFS chooses \\\n",
        "a node with a minimum evaluation function f(n), and then expands it. If the chosen node is the goal \\\n",
        "state, then return. Else, expand and if its children have not been reached before, add it to the \\\n",
        "frontier. If it has been reached but it has now been reached with a lower path cost, read it to \\\n",
        "the frontier. Depending on how f(n) is defined, we can derive different algorithms. This alg will \\\n",
        "always return an indication of failure or the optimal solution to the goal state. \n",
        "\n",
        "Search data structures\n",
        "Each node should keep track of the state, parent, action, and path-cost. Parent pointers can be \\\n",
        "followed from the goal state to the initial state in order to return the solution.\n",
        "\n",
        "Frontier should be represented as a queue, because we can use operations is-empty, pop, top (peek),\\\n",
        " add. \n",
        "\n",
        "There are 3 types: priority, FIFO, and LIFO.\n",
        "\n",
        "Priority is used for best-search first, which pops the node with the minimum cost according to f(n).\n",
        "\n",
        "FIFO is for Breadth FS.\n",
        "\n",
        "LIFO is for DFS. \n",
        "\n",
        "How to prevent cycles from happening in a search algorithm? We can \n",
        "1. Remember all previously reached states (best-first search), only keeping track of the best path to \\\n",
        "each state.\n",
        "2. Not remember past states at all. For some problems, repeating states may be rare or impossible.\n",
        "3. Check for cycles, but not redundant paths, by travling up the parental chain.\n",
        "\n",
        "Algorithms are measured based on their completeness, cost optimality, time/space complexity. \\\n",
        "They must be systematic, especially with an infinite state space.\"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "UNINFORMED SEARCH ALGORITHMS don't have any idea how close a state is to the goal. \n",
        "\n",
        "BREADTH FIRST SEARCH is uninformed. Best to use when all actions are same cost. Can implement \\\n",
        "BFS by calling BEST first search, and the eval funct f(n) is the DEPTH of the node. That's dumb, \\\n",
        "better to use a FIFO queue. REACHED can be a set of states instead of a mapping. All nodes remain \\\n",
        "in memory. => COMPLETE, OPTIMAL\n",
        "\n",
        "For exponential-complexity problems, do not use uninformed searchs unless they are small problems.\n",
        "\n",
        "DIJKSTRA's, aka UNIFORM-COST SEARCH, finds the shortest path on weights undirected graphs. \\\n",
        "Complexity of Disjkstra's depends on the COST, C*, of the optimal solution, and lower bounded \\\n",
        "by the cost of each action ε > 0. => COMPLETE, OPTIMAL\n",
        "\n",
        "DFS COULD be implemented with BEST FS, with the eval funct is the NEGATIVE of the depth. \\\n",
        "Usually implemented as a tree-like search, doesn't keep track of reached states. DFS is \\\n",
        "NOT cost-optimal, will return the first solution it finds. Works best with searching \\\n",
        "through trees, may repeat states in acyclic state spaces, but will eventually find something, \\\n",
        "can get stuck in infinite state spaces. => INCOMPLETE, NOT OPTIMAL\n",
        "\n",
        "Why use DFS? Uses less memory, since it doesn't keep a reached table, best to use DFS on \\\n",
        "a tree.\n",
        "\n",
        "BACKTRACKING SEARCH is a variant of DFS that uses even less memory. Only one successor \\\n",
        "is generated at a time, rather than all successors at the same time. Additionally, it \\\n",
        "modifies the state description rather than allocating memory for a new state. Reduces \\\n",
        "memory requirements from O(bm) to O(m). Can also maintain set of states on the current \\\n",
        "path, so checking if a cycle exists can take O(1) time, in comparison to O(m) by following \\\n",
        "parent pointers.\n",
        "\n",
        "DEPTH-LIMITED SEARCH is the same as DFS, except now we supply a limit, l. We treat nodes \\\n",
        "at depth l as if they have no successors, we do not expand. Possible to be incomplete \\\n",
        "if the wrong l is chosen.\n",
        "\n",
        "ITERATIVE DEEPENING is good uninformed search method when the search state is \\\n",
        "larger than memory and depth of solution is unknown. We gradually increase the \\\n",
        "limit on DFS, until we either get a solution or return failure if we reach the \\\n",
        "cutoff value. It does not remember previously traveled paths once we increment l, \\\n",
        "so it takes less memory at the expense of time.\n",
        "\n",
        "BIDIRECTIONAL SEARCH starts from both the start and end goal, and maintains two \\\n",
        "frontiers, two reached tables, and expands towards the middle together. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"informed\" : \"agent can estimate cost to goal\",\n",
        "\"uninformed\" : \"agent cannot estimate how far away goal is\",\n",
        "\"search algorithm\" : \"solves search problems, inputs a search problem and returns \\\n",
        "a solution if one exists, or failure\",\n",
        "\"reached\" : \"describes a state that has had a child node generated for it\",\n",
        "\"frontier\" : \"a set of unexpanded nodes\",\n",
        "\"repeated state\" : \"state in a search tree that has multiple paths leading to it\",\n",
        "\"cycle\" : \"aka redundant path, when a state has more than one path leading to it\",\n",
        "\"graph search\" : \"search algorithm that checks for redundant paths\",\n",
        "\"tree-like search\" : \"search algorithm that does not check for redundant paths\",\n",
        "\"admissible heuristic\" : \"function that never overesetimates the cost to reach a goal, is optimistic\",\n",
        "\"completeness\" : \"quality of an algorithm to return a solution when it exists, else some indication of failure\",\n",
        "\"cost optimality\" : \"solution that is the BEST, nothing else can top it\",\n",
        "\"depth\" : \"number of actions or states in an optimal solution\",\n",
        "\"branching factor\" : \"the number of successors/children of a node\",\n",
        "\"early goal test\" : \"method of checking for a goal state, checks ASA a node is generated, Breadth FS\",\n",
        "\"late goal test\" : \"method of checking for a goal state, checks once a node is popped off the queue, Best FS\",\n",
        "\"diameter\" : \"the (max) number of path length between any two states\",\n",
        "\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_3))\n",
        "\n"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 446\n",
            "The length in characters is 2658\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1b510a2a-35e7-4f10-c0f3-c08c2cef39f4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nA SEARCH PROBLEM is made up of initial states, state space, goal state(s), transition model, actions, and an action cost function. We try to find the optimal solution, which is a solution with the lowest path cost out of all of the solutions, and asssume that all action costs are positive. \n\n## AIMA Chapter 3.2 Example Problems\n There are two types of problems, standardized and real-world. Standardizes problems are created and used with the intention of being some benchmark. They are used to test the performance of algorithms. Real-world is like the real-world, the formulation is distinctive.\n\nA grid world problem is a grid where agents can move between cells, where its movements are specified to the problem. There may be obstacles in the cells, and agents may act upon these cells/interact with them in some way. The vacuum world, where the agent is a vacuum and the obstacles are the dirt in the cells, is one such problem.\n\nIn a sokoban puzzle, the goal of an agent is to push a number of scattered boxed on a grid into designated spots, where there can only be at most one box per cell. In a grid with n empty cells and b boxes, there are $$n x n!/(b!(n-b)!)$$ states.\n\nThere is also the sliding-tile puzzles, with the numbers in a 3x3 grid. Another variation is the parking lot one.\n\n## AIMA Chapter 3.3 Search Algorithms\nConcerning search algorithms, their solution can be likened to a search tree that is superimposed over a state-space graph. Search algorithms form various paths, starting from the root node (starting state), and branch out in the paths until it finds the goal state. There is a distinction between the state space and the search tree; the state space is the set of possible infinite states of some problem, while a search tree is the description of the paths of some search algorithm, until it reaches the goal state. There is always a unique and distinct path back to the root node for any node in a search tree. The node can be expanded by considering the available actions of that specific node, and looking at the result function to see where the consequence of a specific action will end up, with each of the results being a newly generated (child) node. The frontier of a graph separates the interior and exterior regions of the graph, where the interior consists of nodes that have been reached and expanded, and exterior consisting of unreached nodes. \n\nA general approach to choose which node on a frontier to expand is BEST-first search. BFS chooses a node with a minimum evaluation function f(n), and then expands it. If the chosen node is the goal state, then return. Else, expand and if its children have not been reached before, add it to the frontier. If it has been reached but it has now been reached with a lower path cost, read it to the frontier. Depending on how f(n) is defined, we can derive different algorithms. This alg will always return an indication of failure or the optimal solution to the goal state. \n\nSearch data structures\nEach node should keep track of the state, parent, action, and path-cost. Parent pointers can be followed from the goal state to the initial state in order to return the solution.\n\nFrontier should be represented as a queue, because we can use operations is-empty, pop, top (peek), add. \n\nThere are 3 types: priority, FIFO, and LIFO.\n\nPriority is used for best-search first, which pops the node with the minimum cost according to f(n).\n\nFIFO is for Breadth FS.\n\nLIFO is for DFS. \n\nHow to prevent cycles from happening in a search algorithm? We can \n1. Remember all previously reached states (best-first search), only keeping track of the best path to each state.\n2. Not remember past states at all. For some problems, repeating states may be rare or impossible.\n3. Check for cycles, but not redundant paths, by travling up the parental chain.\n\nAlgorithms are measured based on their completeness, cost optimality, time/space complexity. They must be systematic, especially with an infinite state space.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nUNINFORMED SEARCH ALGORITHMS don't have any idea how close a state is to the goal. \n\nBREADTH FIRST SEARCH is uninformed. Best to use when all actions are same cost. Can implement BFS by calling BEST first search, and the eval funct f(n) is the DEPTH of the node. That's dumb, better to use a FIFO queue. REACHED can be a set of states instead of a mapping. All nodes remain in memory. => COMPLETE, OPTIMAL\n\nFor exponential-complexity problems, do not use uninformed searchs unless they are small problems.\n\nDIJKSTRA's, aka UNIFORM-COST SEARCH, finds the shortest path on weights undirected graphs. Complexity of Disjkstra's depends on the COST, C*, of the optimal solution, and lower bounded by the cost of each action ε > 0. => COMPLETE, OPTIMAL\n\nDFS COULD be implemented with BEST FS, with the eval funct is the NEGATIVE of the depth. Usually implemented as a tree-like search, doesn't keep track of reached states. DFS is NOT cost-optimal, will return the first solution it finds. Works best with searching through trees, may repeat states in acyclic state spaces, but will eventually find something, can get stuck in infinite state spaces. => INCOMPLETE, NOT OPTIMAL\n\nWhy use DFS? Uses less memory, since it doesn't keep a reached table, best to use DFS on a tree.\n\nBACKTRACKING SEARCH is a variant of DFS that uses even less memory. Only one successor is generated at a time, rather than all successors at the same time. Additionally, it modifies the state description rather than allocating memory for a new state. Reduces memory requirements from O(bm) to O(m). Can also maintain set of states on the current path, so checking if a cycle exists can take O(1) time, in comparison to O(m) by following parent pointers.\n\nDEPTH-LIMITED SEARCH is the same as DFS, except now we supply a limit, l. We treat nodes at depth l as if they have no successors, we do not expand. Possible to be incomplete if the wrong l is chosen.\n\nITERATIVE DEEPENING is good uninformed search method when the search state is larger than memory and depth of solution is unknown. We gradually increase the limit on DFS, until we either get a solution or return failure if we reach the cutoff value. It does not remember previously traveled paths once we increment l, so it takes less memory at the expense of time.\n\nBIDIRECTIONAL SEARCH starts from both the start and end goal, and maintains two frontiers, two reached tables, and expands towards the middle together. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed** - agent can estimate cost to goal\n* **Uninformed** - agent cannot estimate how far away goal is\n* **Search algorithm** - solves search problems, inputs a search problem and returns a solution if one exists, or failure\n* **Reached** - describes a state that has had a child node generated for it\n* **Frontier** - a set of unexpanded nodes\n* **Repeated state** - state in a search tree that has multiple paths leading to it\n* **Cycle** - aka redundant path, when a state has more than one path leading to it\n* **Graph search** - search algorithm that checks for redundant paths\n* **Tree-like search** - search algorithm that does not check for redundant paths\n* **Admissible heuristic** - function that never overesetimates the cost to reach a goal, is optimistic\n* **Completeness** - quality of an algorithm to return a solution when it exists, else some indication of failure\n* **Cost optimality** - solution that is the BEST, nothing else can top it\n* **Depth** - number of actions or states in an optimal solution\n* **Branching factor** - the number of successors/children of a node\n* **Early goal test** - method of checking for a goal state, checks ASA a node is generated, Breadth FS\n* **Late goal test** - method of checking for a goal state, checks once a node is popped off the queue, Best FS\n* **Diameter** - the (max) number of path length between any two states\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "INFORMED SEARCH uses domain-specific hints to know better where the goal state is, with \\\n",
        "the help of a heuristic function h(n), which estimates the cost of the cheapest path to \\\n",
        "the goal.\n",
        "\n",
        "GREEDY BEST FIRST SEARCH is a variant of BEST FS, it expands the node with the minimal \\\n",
        "h(n). Thus, the eval funct f(n) = h(n). Complete in finite state spaces only. The quality \\\n",
        "of this alg depends on the quality of the heuristic function.\n",
        "\n",
        "A* SEARCH is a variant of BEST FS, with the eval funct f(n) = g(n) + h(n), where g(n) is \\\n",
        "the path cost from the initial state to node n, h(n) is an estimate of the cost of the \\\n",
        "shortest path from n to the goal. A* search is optimal if the heauristic is ADMISSIBLE. \\\n",
        "A heuristic is CONSISTENT if, for every node n and every successor n' of n generated by \\\n",
        "an action a $$h(n) <= c(n, a, n') + h(n')$$\n",
        "\n",
        "A heuristic that is consistent is also admissible, but an admissible heuristic is not \\\n",
        "necessarily consistent. With a consistent heauristic, A* is cost optimal. With an \\\n",
        "inconsistent h(n), it's possible to have multiple paths to the same state. Would cost \\\n",
        "both time and space to keep track of these multiple paths. A* may or may not be cost-\\\n",
        "optimal with an inadmissible heuristic. \n",
        "\n",
        "When is A* cost-optimal with inadmissible h(n)?\n",
        "1. if there exists a cost-optimal path where h(n) is admissible for all nodes on the path\n",
        "2. if optimal solution C*, and second optimal C_2, and h(n) overestimates some, but not \\\n",
        "more than C_2 - C*, then A* returns cost-optimal soln \n",
        "\n",
        "For weighted A* search, if optimal solution costs C*, then the returned solution will be \\\n",
        "between C* and W x C*, closer to C* in practice\"\"\"\n",
        "chapter3_6 = \"\"\" Heuristic h2 is BETTER than h1 if it DOMINATES h1. For any node n, h2(n) \\\n",
        ">= h1(n). Why? A better heuristic h2 for A* means that more nodes will be expanded than \\\n",
        "h1.\n",
        "\n",
        "How to choose the best heuristic if there are multiples? \n",
        "h(n) = max{h1(n), ..., hk(n)}\n",
        "\n",
        "Admissible heuristics can be derived from a subproblem.\n",
        "\n",
        "Multiple ways to generate a good heuristic function: \n",
        "1. Relaxing problem definition\n",
        "2. Storing precomputed solution costs for subproblems in a pattern database\n",
        "3. Defining landmarks\n",
        "4. Learning from experience w the problem class\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\", \n",
        "\"admissible heuristic\" : \"a heuristic that never overestimates the cost to reach a goal, aka optimistic\",\n",
        "\"inadmissible heuristic\" : \"a heuristic that may overestimate the cost to reach a goal\",\n",
        "\"consistency\" : \"a property of a heuristic\",\n",
        "\"triangle inequality\" : \"any side of a triangle can not be longer than the sum of the other two sides\",\n",
        "\"satisficing solution\" : \"sub optimal solution, but its good enough. Use inadmissible heuristic\",\n",
        "\"detour index\" : \"value to that is multiplied with the straight line distance, accounts for curvature of roads\",\n",
        "\"Weighted A* Search\" : \"eval function f(n+ = g(n) + W x h(n), for some W > 1\",\n",
        "\"Bounded Suboptimal Search\" : \"search algorithm that looks for a solution within a constant factor W of the optimal cost, weighted A*\",\n",
        "\"Bounded Cost Search\" : \"search algorithm that returns a solution with cost less than some constant C\",\n",
        "\"Unbounded Cost Search\" : \"search algorithm looking for any solution, cost is irrelevant factor, speed is priority, speedy search\",\n",
        "\"Reference Counts\" : \"count for each time a state has been reached, used to conserve memory\",\n",
        "\"Beam Search\" : \"limits size of frontier, incomplete and suboptimal, often finds decent solutions, faster than complete searches\",\n",
        "\"Iterative-deepening A* Search (IDA*)\" : \"Iterative version of A*, iterates on the cost of the node\",\n",
        "\"Recursive Best-First Search (RBFS) \" : \"robust, optimal, with limited amount of memory, can solve problems with enough time\",\n",
        "\"Backed-up Value\" : \"\",\n",
        "\"Memory-Bounded A* (MA*)\" : \"\",\n",
        "\"Simple Memory-Bounded A* (SMA*)\" : \"\",\n",
        "\"Thrashing\" : \"\",\n",
        "\"Front-to-end\" : \"\",\n",
        "\"Front-to-front\" : \"\",\n",
        "\"Manhattan Distance (city-block distance)\" : \"sum of horizontal and vertical distances\",\n",
        "\"Effective branching factor b*\" : \"characterizes quality of heuristic, N+1 = 1 + b* + (b*)^2 + ... + (b*)^d\",\n",
        "\"Effective depth\" : \"\",\n",
        "\"Relaxed problem\" : \"problem with fewer restrictions on the actions\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8488bc9a-9f0b-4c1e-ddee-16bfb081f6a1"
      },
      "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\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nINFORMED SEARCH uses domain-specific hints to know better where the goal state is, with the help of a heuristic function h(n), which estimates the cost of the cheapest path to the goal.\n\nGREEDY BEST FIRST SEARCH is a variant of BEST FS, it expands the node with the minimal h(n). Thus, the eval funct f(n) = h(n). Complete in finite state spaces only. The quality of this alg depends on the quality of the heuristic function.\n\nA* SEARCH is a variant of BEST FS, with the eval funct f(n) = g(n) + h(n), where g(n) is the path cost from the initial state to node n, h(n) is an estimate of the cost of the shortest path from n to the goal. A* search is optimal if the heauristic is ADMISSIBLE. A heuristic is CONSISTENT if, for every node n and every successor n' of n generated by an action a $$h(n) <= c(n, a, n') + h(n')$$\n\nA heuristic that is consistent is also admissible, but an admissible heuristic is not necessarily consistent. With a consistent heauristic, A* is cost optimal. With an inconsistent h(n), it's possible to have multiple paths to the same state. Would cost both time and space to keep track of these multiple paths. A* may or may not be cost-optimal with an inadmissible heuristic. \n\nWhen is A* cost-optimal with inadmissible h(n)?\n1. if there exists a cost-optimal path where h(n) is admissible for all nodes on the path\n2. if optimal solution C*, and second optimal C_2, and h(n) overestimates some, but not more than C_2 - C*, then A* returns cost-optimal soln \n\nFor weighted A* search, if optimal solution costs C*, then the returned solution will be between C* and W x C*, closer to C* in practice\n\n## AIMA Chapter 3.6 Heuristic Functions\n Heuristic h2 is BETTER than h1 if it DOMINATES h1. For any node n, h2(n) >= h1(n). Why? A better heuristic h2 for A* means that more nodes will be expanded than h1.\n\nHow to choose the best heuristic if there are multiples? \nh(n) = max{h1(n), ..., hk(n)}\n\nAdmissible heuristics can be derived from a subproblem.\n\nMultiple ways to generate a good heuristic function: \n1. Relaxing problem definition\n2. Storing precomputed solution costs for subproblems in a pattern database\n3. Defining landmarks\n4. Learning from experience w the problem class\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n* **Admissible heuristic** - a heuristic that never overestimates the cost to reach a goal, aka optimistic\n* **Inadmissible heuristic** - a heuristic that may overestimate the cost to reach a goal\n* **Consistency** - a property of a heuristic\n* **Triangle inequality** - any side of a triangle can not be longer than the sum of the other two sides\n* **Satisficing solution** - sub optimal solution, but its good enough. Use inadmissible heuristic\n* **Detour index** - value to that is multiplied with the straight line distance, accounts for curvature of roads\n* **Weighted a* search** - eval function f(n+ = g(n) + W x h(n), for some W > 1\n* **Bounded suboptimal search** - search algorithm that looks for a solution within a constant factor W of the optimal cost, weighted A*\n* **Bounded cost search** - search algorithm that returns a solution with cost less than some constant C\n* **Unbounded cost search** - search algorithm looking for any solution, cost is irrelevant factor, speed is priority, speedy search\n* **Reference counts** - count for each time a state has been reached, used to conserve memory\n* **Beam search** - limits size of frontier, incomplete and suboptimal, often finds decent solutions, faster than complete searches\n* **Iterative-deepening a* search (ida*)** - Iterative version of A*, iterates on the cost of the node\n* **Recursive best-first search (rbfs) ** - robust, optimal, with limited amount of memory, can solve problems with enough time\n* **Backed-up value** - \n* **Memory-bounded a* (ma*)** - \n* **Simple memory-bounded a* (sma*)** - \n* **Thrashing** - \n* **Front-to-end** - \n* **Front-to-front** - \n* **Manhattan distance (city-block distance)** - sum of horizontal and vertical distances\n* **Effective branching factor b*** - characterizes quality of heuristic, N+1 = 1 + b* + (b*)^2 + ... + (b*)^d\n* **Effective depth** - \n* **Relaxed problem** - problem with fewer restrictions on the actions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 130
        },
        "outputId": "82fe828f-4bc1-40e4-ebc9-9e52482b6880"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "Three ways to approach multi-agent environnments:\n",
        "1. Economy - large number of agents, treating them all as one economy, we can predict \\\n",
        "increasing demand, without having to predict the action of an individual agent\n",
        "2. Environment - consider the adversarial agents as a part of the environment that \\\n",
        "makes it nondeterministic \n",
        "3. Adversarial game-tree search - using a tree to represent optimal moves\n",
        "\n",
        "A game is formally defined by: \n",
        "1. initial state\n",
        "2. to-move(s) - player whose turn it is to move in a state s\n",
        "3. actions(s)\n",
        "4. result(s, a)\n",
        "5. is-terminal(s)\n",
        "6. utility(s, p)\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax search is used when a game has multiple outcome scores. Assumes that BOTH players \\\n",
        "play optimally. MAX seeks to play the move with the largest score, MIN seeks to play the \\\n",
        "move that will cause minimal damage. The minimax value is the utility of being in that state.\n",
        "\n",
        "The minimax decision is the best decision for either the max or min node at that level.\n",
        "\n",
        "If MIN does not play optimally, then MAX will do at least as well against an optimal \\\n",
        "player.\n",
        "\n",
        "Minimax can be extended to >2 players, where the value of each node becomes a vector \\\n",
        "of values.\n",
        "\n",
        "Minimax is depth-first, but thanks to alpha-beta pruning, we can cut off paths that we \\\n",
        "know aren't worth exploring.\n",
        "With alpha-beta, would need to examine only O(b^{m/2}) nodes in order to pick the best \\\n",
        "move, while minimax would be O(b^m). That is, the effective branching factor for \\\n",
        "alpha-beta is sqrt(b) instead of b.\n",
        "\n",
        "Even with pruning, minimax would not work for games like Chess, there are just too \\\n",
        "many damn states.\n",
        "\n",
        "Two types of strategies are proposed here:\n",
        "Type A strategy - considers all possible moves up to a certain depth, uses heuristic \\\n",
        "function to estimate the utilites of the states at that depth, wide and shallow\n",
        "\n",
        "Type B strategy - ignores moves that looks bad, follows promising paths for as long as \\\n",
        "possible, deep and narrow\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "Forward pruning removes moves that only appear to be bad moves, but they could be good. \\\n",
        "Saves time at the risk of making an error. Could be considered a Type B strategy.\n",
        "\n",
        "Beam Search is an example of forward pruning\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Stochastic games are games with a random element, like backgammon or rolling a die. Game \\\n",
        "trees for stochastic games must have chance nodes along with their MAX and MIN nodes. \\\n",
        "Decisions in such a game tree are made by calculating the expected value of a position. \\\n",
        "\n",
        "Games of chance are not as straightforward as games with evaluation function for chess, \\\n",
        "where a higher value equates to a better position. To avoid these problems, the eval function\\ \n",
        " for chance games need to return values that are a positive linear transformation of \\\n",
        " the probability of winning (or expected utility for games with outcomes that are not \\\n",
        " just win/lose)\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Competitive Environments\" : \"2 or more agents have conflicting goals\",\n",
        "\"Adversarial Search Problems\" : \"\",\n",
        "\"Pruning\" : \"Ignoring portions of the tree that do not affect the optimal solution\",\n",
        "\"Imperfect Information\" : \"games where you don't know all the information, like poker\",\n",
        "\"Perfect Information\" : \"games where all information can be perceived, aka fully observable\",\n",
        "\"Zero-sum\" : \"games where a good move for one player is equally as bad for its opponent\",\n",
        "\"Position\" : \"synonym for state\",\n",
        "\"Move\" : \"synonym for action\",\n",
        "\"Transition Model\" : \" defines state returned from performing action a on state s\",\n",
        "\"Terminal Test\" : \"true when game is over, false o.w.\",\n",
        "\"Utility Function\" : \"Defines final numeric value to player p when the game ends in terminal state s\",\n",
        "\"State Space Graph\" : \"graph whose vertices are states, edges are moves\",\n",
        "\"Game Tree\" : \"tree that shows every possible move and states all the way to the terminal state\",\n",
        "\"Alpha-Bete Pruning\" : \"a: lower bound for MAX (at least), b: upper bound for MIN (at most)\",\n",
        "\"Transpositions\" : \"repeated state that is reached via different permutations of move sequences\",\n",
        "\"Transposition Table\" : \"table the caches the heuristic value of states\",\n",
        "\"Heuristic Evaluation Function\" : \"returns as estimate of the expected utility of state s to player p\",\n",
        "\"Forward Pruning\" : \"removing moves and their subsequent moves if the move looks poor\",\n",
        "\"Expected Value\" : \"the average value over all the possible outcomes of the chance nodes\",\n",
        "\"Expectiminimax Value\" : \"generalization of minimax values for deterministic games\",\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "error",
          "ename": "SyntaxError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-1-9d54c6345098>\"\u001b[0;36m, line \u001b[0;32m85\u001b[0m\n\u001b[0;31m    \"concept\" : \"definition\",\u001b[0m\n\u001b[0m              ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "626d5971-4b58-440f-e3fd-0a3d0b057a3c"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \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 Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \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 Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.4 Monte Carlo Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}