{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4159f84f-7541-476b-8fa7-1a73dfcf295b"
      },
      "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": "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": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e0770356-a483-45ba-ad7b-8b7fc4850424"
      },
      "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": "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 = \"\"\" AI has gained increasing popularity over the years. The Turing \\\n",
        " test was proposed to determine whether or not a computer can truly think. The \\\n",
        " computer would need to have natural language processing, knowledge representation, \\\n",
        " automated reasoning, and machine learning. To pass the total Turing test a robot \\\n",
        " needs computer vision and robotics to perceive and manipulate the world around them. \\\n",
        " We can study human thought through introspection, psychological experiments, and \\\n",
        " brain imaging. This is largely done in cognitive science. The idea of an agent is \\\n",
        " introduced, which acts. A rational agent acts to reach some best outcome. However, \\\n",
        " the issue of limited rationality often appears. \"\"\" \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\" : \"an agent's perceptual inputs at any time\",\n",
        "\"agent function\": \"f:P->a, maps a sequence of percept vectors to some action from a set\",\n",
        "\"agent program\": \"is run on the physical architecture to make the agent function\",\n",
        "\"sensors\": \"used to perceive the environment, ex: eyes, ears\",\n",
        "\"actuators\": \"used by agent to act upon the environment, ex: hands, legs\",\n",
        "\"rational agent\": \"an agent that behaves rationally (does the right thing)\",\n",
        "\"performance measure\": \"some objective criteria to judge the success of an agent's behavior\",\n",
        "\"task environment\": \"use PEAS: performance measure, environment, actuators, sensors\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "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": 878
        },
        "cellView": "form",
        "outputId": "1a2bc2c4-0775-4b31-8631-4bba645fa87a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n AI has gained increasing popularity over the years. The Turing  test was proposed to determine whether or not a computer can truly think. The  computer would need to have natural language processing, knowledge representation,  automated reasoning, and machine learning. To pass the total Turing test a robot  needs computer vision and robotics to perceive and manipulate the world around them.  We can study human thought through introspection, psychological experiments, and  brain imaging. This is largely done in cognitive science. The idea of an agent is  introduced, which acts. A rational agent acts to reach some best outcome. However,  the issue of limited rationality often appears. \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** - an agent's perceptual inputs at any time\n* **Agent function** - f:P->a, maps a sequence of percept vectors to some action from a set\n* **Agent program** - is run on the physical architecture to make the agent function\n* **Sensors** - used to perceive the environment, ex: eyes, ears\n* **Actuators** - used by agent to act upon the environment, ex: hands, legs\n* **Rational agent** - an agent that behaves rationally (does the right thing)\n* **Performance measure** - some objective criteria to judge the success of an agent's behavior\n* **Task environment** - use PEAS: performance measure, environment, actuators, sensors\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 = \"\"\" In PYthon all data is treated as objects, deleted once unreachable. \\\n",
        "It is strongly typed meaning that every object has a fixed type and the interpreter \\\n",
        "doesn't allow things incompatible with type. It is also dynamically typed \\\n",
        "so variables come into existence when first assigned and functions have no type \\\n",
        "signatures. Type errors are thus only caught at runtime. string operations are \\\n",
        "split(string), join(words), capitalize(), upper(), and strip(string). Lists are \\\n",
        "mutable, but tuples and strings are not. List operations include append(val), \\\n",
        "insert(index, val), index(val), count(val), remove(val), reverse(), sort() \\\n",
        "or sort(some_function). Dictionaries are unordered and work by hashing, thus \\\n",
        "keys are immutable. \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"if a var can be updated after created\",\n",
        "\"default values for arguments\": \"can be done in function header for args\",\n",
        "\"keyword args\": \"calling functions with arguments out of order, specify args in call\",\n",
        "\"*args\": \"arg for a function when you want to accept a variable # of non-keyword args\",\n",
        "\"**kwargs\": \" want to accept a variable # of keyword args to function\",\n",
        "\"dynamic scope\": \"functions use the most current value of variables\",\n",
        "}"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 362
        },
        "outputId": "feb5176b-9e47-44ed-ab1c-789822a7084e"
      },
      "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": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n In PYthon all data is treated as objects, deleted once unreachable. It is strongly typed meaning that every object has a fixed type and the interpreter doesn't allow things incompatible with type. It is also dynamically typed so variables come into existence when first assigned and functions have no type signatures. Type errors are thus only caught at runtime. string operations are split(string), join(words), capitalize(), upper(), and strip(string). Lists are mutable, but tuples and strings are not. List operations include append(val), insert(index, val), index(val), count(val), remove(val), reverse(), sort() or sort(some_function). Dictionaries are unordered and work by hashing, thus keys are immutable. \n\n## Module 2 Definitions\n* **Mutability** - if a var can be updated after created\n* **Default values for arguments** - can be done in function header for args\n* **Keyword args** - calling functions with arguments out of order, specify args in call\n* ***args** - arg for a function when you want to accept a variable # of non-keyword args\n* ****kwargs** -  want to accept a variable # of keyword args to function\n* **Dynamic scope** - functions use the most current value of variables\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": "527ea0f4-ec06-4e39-d8c9-0f03087bebf3"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \"\"\"\n",
        "chapter3_2 = \"\"\" Sliding-Tile Puzzle Example \\\\\n",
        "\n",
        "States : all the locations of the tiles \\\\\n",
        "\n",
        "Initial State : any \\\\\n",
        "\n",
        "Actions : swapping tile with blank space going up, down, left, or right \\\\\n",
        "\n",
        "Transition Model : result of taking an action \\\\\n",
        "\n",
        "Goal State: when tiles are ordered 123456789 \\\\\n",
        "\n",
        "Action Cost : cost of moving a tile > all 1 in this puzzle \\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \"\"\"\n",
        "chapter3_4 = \"\"\" Breadth-first Search: All actions have the same cost and all \\\n",
        "successors of the current frontier are expanded in order. Best if there are \\\n",
        "possibly infinite paths and some solutions have short paths. This uses the FIFO \\\n",
        "queue and the set of reached nodes is a set of states rather than a mapping of \\\n",
        "states to nodes.\n",
        "```\n",
        "Psuedo-Code: \n",
        "initialize NODE\n",
        "if NODE is GOAL, return\n",
        "intialize FRONTIER and REACHED (FIFO queue [list] and [set])\n",
        "while FRONTIER not empty: \n",
        "  pop, check if GOAL or add to REACHED and FRONTIER\n",
        "return failure if no sol'n\n",
        "```\n",
        "Time Complexity : $O(b^d)$ \\\\\n",
        "\n",
        "Space Complexity : $O(b^d)$, all nodes remain in memory \\\\\n",
        "\n",
        "Complete, but only cost-optimal when all actions have the same cost\\\\\n",
        "\n",
        "Dijkstra's (Uniform-cost Search) BFS in uniform depth, Dijkstra's in uniform path-cost.\\\n",
        "Time and Space Complexity : *O(b^(1+[C/\\epsilon]))$ which can potentially be more than BFS.\\\n",
        "Uniform-cost search is complete and cost-optimal \\\\\n",
        "\n",
        "Depth-first Search Expands to deepest node in the frontier first. Best for \\\n",
        "space restricted and many possible solutions with long paths. \\\n",
        "Time Complexity : O(b^m) Space Complexity : O(bm) where m is the max depth \\\n",
        "Not complete (unless m is bounded (limited depth)) or cost-optimal \\\\\n",
        "\n",
        "Depth-limited Search Cut off DFS at limit l and treat all nodes at limit was \\\n",
        "if they had no successors. Same complexity as DFS with d = l. \\\n",
        "If l < d, then incomplete; if l > d, then not optimal \\\\\n",
        "\n",
        "```\n",
        "function \n",
        "```\n",
        "\n",
        "Iterative Deepening Search for depth = 0 to $\\infty$, do depth-limited search. \\\n",
        "$O(bd)$ if there is a solution or O(bm) when there is not. Preferred when search \\\n",
        "state is larger than memory (can't use BFS) and depth of solution is unknown \\\n",
        "(can't use DFS). \\\\\n",
        "\n",
        "```\n",
        "for l = 0 to infinity do:\n",
        "  depth-limited seach to level l\n",
        "  if success:\n",
        "    return solution\n",
        "```\n",
        "\n",
        "Bidirectional Search Searches from initial state and backwards from goal state(s).\\\n",
        " Has frontier (priority queue) and reached states for forward and backward search. \\\n",
        "Complete and optimal with O(b^(d/2)) Time and Space complexity\\\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" The propertires of the task environment change the \\\n",
        "type of solution needed. Environments that are fully observable, deterministic, \\\n",
        "and known require a fixed sequence of actions. If the env is partially observable \\\n",
        "or nondeterministic then the solution must recommend different future actions depending \\\n",
        "on the percepts it receives, this could be in the form of a branching strategy. \\\\\n",
        "\n",
        "An example search problem is the sliding tile. The goal is for the pieces to end \\\n",
        "up in order: 9! possible states,  $\\leq$ 4 possible actions at a time, performance \\\n",
        "measure = minimizing total moves. \\\\\n",
        "\n",
        "Tree search is a basic search alg that enumerates in some order all possible \\\n",
        "paths from the initial state. It treats diff paths to the same node as distinct. \\\n",
        "However, failure to detect repeated states can make a linear problem exponential. \\\n",
        "This is solved through a graph search which adds a DS to check to see if a node \\\n",
        "has been visited \\ before adding it to a search queue. It takes more memory as \\\n",
        "you must keep track of all possible states. \\\\\n",
        "\n",
        "Uninformed (blind) search strategies uses info in the problem definition. BFS expands the shallowest \\\n",
        "unexpanded node. Frontier is FIFO queue, placing successors at the end of frontier. \\\n",
        "DFS expands deepest unexpanded node and the frontier is LIFO queue, placing \\\n",
        "successors at the front of frontier. Use DFS if space is restricted, there are many \\\n",
        "possible solutions with long paths and wrong paths are terminated quickly, or \\\n",
        "if search can be fine-tuned quickly. Use BFS if there are possible infinite paths, \\\n",
        "some solutions have short paths, or you can quickly discard unlikely paths. Depth \\\n",
        "limited search adds a depth limit, nodes at depth l have no successors. Iterative \\\n",
        "deepening search uses depth-limited seaech as subrouting with increasing l until solution.\\\\\n",
        "\n",
        "BFS, Uniform, IDS, Bidrectional: complete and optimal \\\\\n",
        "\n",
        "BFS, uniform and ids are complete if b is finite or if state space has a solution \\\n",
        "or is finite. Uniform will be complete if all action costs are $\\geq \\epsilon$ and \\\n",
        "$> 0$. BFS, Iterative, and Bidrectional are cost-optimal if action costs are identical. \\\\\n",
        "\n",
        "Bidirectional is complete and optimal if both directions use BFS/Uniform-cost \\\n",
        "\n",
        "DFS and depth-limited: not complete or optimal \\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(module3_lecture_notes.split(' ')))\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",
        "\"reflex agent\" : \"will select an action based on the current percept, ignoring history\",\n",
        "\"search\": \"the computational process of a problem-solving agent\",\n",
        "\"solution\": \"sequence of actions the agent takes to solve problem, path from initial to goal state\",\n",
        "\"formal definition of a problem\": \"states, initial state, actions, transition model, \\\n",
        "path cost, goal test\",\n",
        "\"state space\": \"the set of all states that's reachable from the initial state by \\\n",
        "any sequence of actions\",\n",
        "\"path\": \"sequence of actions leading from one state to another\",\n",
        "\"frontier\": \"states available for expanding\",\n",
        "\"dimensions for evaluation\": \"completeness, optimality, time complexity, space complexity\",\n",
        "\"properties of BFS\": \"complete if b is finite; time: $O(b^d)$; space: $O(b^d)$, \\\n",
        "optimal if cost = 1 per step\",\n",
        "\"properties of DFS\": \"not complete due to loops; time: $O(b^m)$, terrible if m much \\\n",
        "larger than d; space: $O(bm)$; not optimal\",\n",
        "\"properties of DLS\": \"only optimal if l = d, if l < d then incomplete else not \\\n",
        "optimal; time: $O(b^l)$; space: $O(bl)$\",\n",
        "\"properties of IDS\": \"complete; optimal; time: $O(b^d)$; space: $O(bd)$; optimal \\\n",
        "if step cost is 1\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 366\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7b55b38a-5d5c-4c46-d020-e6049d32924e"
      },
      "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": 14,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n\n## AIMA Chapter 3.2 Example Problems\n Sliding-Tile Puzzle Example States : all the locations of the tiles \\\n\nInitial State : any \\\n\nActions : swapping tile with blank space going up, down, left, or right \\\n\nTransition Model : result of taking an action \\\n\nGoal State: when tiles are ordered 123456789 \\\n\nAction Cost : cost of moving a tile > all 1 in this puzzle \\\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth-first Search: All actions have the same cost and all successors of the current frontier are expanded in order. Best if there are possibly infinite paths and some solutions have short paths. This uses the FIFO queue and the set of reached nodes is a set of states rather than a mapping of states to nodes.\n```\nPsuedo-Code: \ninitialize NODE\nif NODE is GOAL, return\nintialize FRONTIER and REACHED (FIFO queue [list] and [set])\nwhile FRONTIER not empty: \n  pop, check if GOAL or add to REACHED and FRONTIER\nreturn failure if no sol'n\n```\nTime Complexity : $O(b^d)$ \\\n\nSpace Complexity : $O(b^d)$, all nodes remain in memory \\\n\nComplete, but only cost-optimal when all actions have the same cost\\\n\nDijkstra's (Uniform-cost Search) BFS in uniform depth, Dijkstra's in uniform path-cost.Time and Space Complexity : *O(b^(1+[C/\\epsilon]))$ which can potentially be more than BFS.Uniform-cost search is complete and cost-optimal \\\n\nDepth-first Search Expands to deepest node in the frontier first. Best for space restricted and many possible solutions with long paths. Time Complexity : O(b^m) Space Complexity : O(bm) where m is the max depth Not complete (unless m is bounded (limited depth)) or cost-optimal \\\n\nDepth-limited Search Cut off DFS at limit l and treat all nodes at limit was if they had no successors. Same complexity as DFS with d = l. If l < d, then incomplete; if l > d, then not optimal \\\n\n```\nfunction \n```\n\nIterative Deepening Search for depth = 0 to $\\infty$, do depth-limited search. $O(bd)$ if there is a solution or O(bm) when there is not. Preferred when search state is larger than memory (can't use BFS) and depth of solution is unknown (can't use DFS). \\\n\n```\nfor l = 0 to infinity do:\n  depth-limited seach to level l\n  if success:\n    return solution\n```\n\nBidirectional Search Searches from initial state and backwards from goal state(s). Has frontier (priority queue) and reached states for forward and backward search. Complete and optimal with O(b^(d/2)) Time and Space complexity \n\n## Module 3 Lecture Notes\n The propertires of the task environment change the type of solution needed. Environments that are fully observable, deterministic, and known require a fixed sequence of actions. If the env is partially observable or nondeterministic then the solution must recommend different future actions depending on the percepts it receives, this could be in the form of a branching strategy. An example search problem is the sliding tile. The goal is for the pieces to end up in order: 9! possible states,  $\\leq$ 4 possible actions at a time, performance measure = minimizing total moves. \\\n\nTree search is a basic search alg that enumerates in some order all possible paths from the initial state. It treats diff paths to the same node as distinct. However, failure to detect repeated states can make a linear problem exponential. This is solved through a graph search which adds a DS to check to see if a node has been visited \\ before adding it to a search queue. It takes more memory as you must keep track of all possible states. \\\n\nUninformed (blind) search strategies uses info in the problem definition. BFS expands the shallowest unexpanded node. Frontier is FIFO queue, placing successors at the end of frontier. DFS expands deepest unexpanded node and the frontier is LIFO queue, placing successors at the front of frontier. Use DFS if space is restricted, there are many possible solutions with long paths and wrong paths are terminated quickly, or if search can be fine-tuned quickly. Use BFS if there are possible infinite paths, some solutions have short paths, or you can quickly discard unlikely paths. Depth limited search adds a depth limit, nodes at depth l have no successors. Iterative deepening search uses depth-limited seaech as subrouting with increasing l until solution.\\\n\nBFS, Uniform, IDS, Bidrectional: complete and optimal \\\n\nBFS, uniform and ids are complete if b is finite or if state space has a solution or is finite. Uniform will be complete if all action costs are $\\geq \\epsilon$ and $> 0$. BFS, Iterative, and Bidrectional are cost-optimal if action costs are identical. \\\n\nBidirectional is complete and optimal if both directions use BFS/Uniform-cost \nDFS and depth-limited: not complete or optimal \n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** - will select an action based on the current percept, ignoring history\n* **Search** - the computational process of a problem-solving agent\n* **Solution** - sequence of actions the agent takes to solve problem, path from initial to goal state\n* **Formal definition of a problem** - states, initial state, actions, transition model, path cost, goal test\n* **State space** - the set of all states that's reachable from the initial state by any sequence of actions\n* **Path** - sequence of actions leading from one state to another\n* **Frontier** - states available for expanding\n* **Dimensions for evaluation** - completeness, optimality, time complexity, space complexity\n* **Properties of bfs** - complete if b is finite; time: $O(b^d)$; space: $O(b^d)$, optimal if cost = 1 per step\n* **Properties of dfs** - not complete due to loops; time: $O(b^m)$, terrible if m much larger than d; space: $O(bm)$; not optimal\n* **Properties of dls** - only optimal if l = d, if l < d then incomplete else not optimal; time: $O(b^l)$; space: $O(bl)$\n* **Properties of ids** - complete; optimal; time: $O(b^d)$; space: $O(bd)$; optimal if step cost is 1\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b2890fdd-08ad-402c-90df-623131a332ed"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" A* expands all nodes with $f(n) < C*$, it might expand those \\\n",
        "equal to C* before selecting a goal node and never those greater than C*. A* \\\n",
        "won't be the best answer when the number of nodes expanded can be exponential \\\n",
        "in the solution length. Using an inadmissible heuristic can risk missing the \\\n",
        "optimal solution but can possibly be more accurate as we reduce the number of \\\n",
        "nodes expanded. \\\\\n",
        "\n",
        "Suppose the optimal path is C*, but the alg returns C > C*. There must be an unexpanded \\\n",
        "node n on the optimal path. A* only returns cost-optimal paths proof (through contradiction): \\\n",
        "$$f(n)> C*,$$ else we would have expanded n\n",
        "$$f(n) = g(n) + h(n),$$ by def\n",
        "$$f(n) =g*(n)+h(n),$$ since n is on an optimal path\n",
        "$$f(n) \\leq  g*(n) +h*(n),$$ due to admissibility\n",
        "$$f(n) \\leq C*,$$ by def $C* = g*(n) +h*(n)$ \\\\\n",
        "\n",
        "The last line is a contradiction. \\\\\n",
        "\n",
        "We can use a weighted A* search to weigh the heuristic value more \\\n",
        "heavily. A* is inefficient with memory, best-first searches can save space by not \\\n",
        "storing states on the frontier in the frontier and reached states \\\n",
        "or by removing states from reached after proving they're not needed. Can also \\\n",
        "keep reference counts for the # of times a state has been reached, removing from \\\n",
        "reached when there's not other possible way to reach it. \\\\\n",
        "\n",
        "Beam search saves mem by limiting the size of the frontier. Most commonly done by only keeping the k \\\n",
        "nodes that have the best f-scores, but search is incomplete and suboptimal. Can \\\n",
        "also keep every node whose f-score is within $\\delta$ of the best f-score. \\\\\n",
        "\n",
        "IDA* changes the cutoff from the depth to the f-cost (g+h): the smallest f-cost of \\\n",
        "any node that exceeded the cutoff on the prev iteration. Recursive best-first \\\n",
        "search uses the f_limit var to track the f-value of the best alternative path \\\n",
        "available from any ancestor nodes. Recursion unwinds if the current node exceeds \\\n",
        "the limit. Its space-complexity depends on the heuristic accuracy and how often \\\n",
        "the best path changes when nodes are expanded. \\\\\n",
        "\n",
        "Simplified memory-bounded A* (SMA*) solves the issue of IDA* and RBFS using too \n",
        "little memory by expanding the best leaf until mem is full: then it drops the \\\n",
        "oldest worst leaf (in case f-values are the same) and expands the newest best leaf. \\\n",
        "It's complete if there's a reachable solution (the depth of the shallowest goal \\\n",
        "node is less than mem size) and optimal if reachablem else returning the best \\\n",
        "reachable solution. \\\\\n",
        "\n",
        "Bidirectional heuristic search uses $f_F(n) = g_F(n) +h_F(n)$ \\\n",
        "for forward direction and $f_B(n) = g_B(n) +h_B(n)$ for backward (goal state as root). \\\n",
        "With a forward path going to node m and a backward path from goal to a node n a \\\n",
        "lower bound for a solution that goes from initial state to m to n to the goal is: \\\n",
        "$$lb(m,n) = max(gF(m)+gB(n), fF(m), fB(n))$$. \\\n",
        "$$f_2(n) = max(2g(n), g(n) +h(n)),$$ expanding the node that minimizes f2 from either \\\n",
        "frontier\"\"\"\n",
        "chapter3_6 = \"\"\"Characterize the quality of a heuristic with an effective branching \\\n",
        "factor $b*$: $$N+1 = 1 + b* +(b*)^2 +...+(b*)^d,$$ if A* generates \\\n",
        "N nodes with solution depth at d. Korf and Reid argue characterizing the effect \\\n",
        "of A* pruning with a heuristic is whether it reduces the effective depth by some \\\n",
        "constant $k_h$ when compared to the true depth. Total search cost = $O(b^{d-k_h})$, \\\n",
        "compared to $O(b^d)$ in uninformed search. \\\\\n",
        "\n",
        "Any optimal solution in an original problem is also a solution in the relaxed \\\n",
        "problem, as relaxing will only add edges. In a relaxed problem the state-space \\\n",
        "graph is a supergraph as it adds edges to the graph by removing restrictions. \\\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic \\\n",
        "for the original problem. For landmark points an optimal path is inadmissible if\\\n",
        "it doesn't pass through one. \\\\\n",
        "\n",
        "An agent can also improve their own searching due to metalevel state space. Each state in this \\\n",
        "space captures the internal/computational state of a program searching in an \\\n",
        "ordinary state space. A metalevel learning alg learns from the experiences in the \\\n",
        "state space to avoid exploring unpromising subtrees. \"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_5.split(' ')))\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" USC is an extension of BFS, expanding node with the \\\n",
        "lowest path cost. It's implemented with a frontier as a priority queue ordered by \\\n",
        "g(n). Unlike BFS, you test if a node is a goal state when selecting it for \\\n",
        "expansion, not when it's added to the frontier. It will update a node on the frontier \\\n",
        "if a better path on the same state is found. It will always enqueue a node before \\\n",
        "checking whether it is a goal; favors lower cost paths. \\\\\n",
        "\n",
        "$A*$: $f(n) = g(n) + h(n)$ \\\\\n",
        "\n",
        "g(n) = actual cost so far to reach node \\\\\n",
        "\n",
        "h(n) = estimated cost to get from node to goal \\\\\n",
        "\n",
        "f(n) = estimated total cost of path through n to goal\\\\\n",
        "\n",
        "A heuristic is admissible if $0 \\leq h(n) \\leq h*(n)$, where h(n) is true cost to \\\n",
        "nearest goal \\\\\n",
        "\n",
        "Every consistent heuristic is admissible, so if there is a consistent heuristic, \\\n",
        "A* is cost-optimal. If a heuristic is inadmissible, A* is cost-optimal if there's \\\n",
        "at least one cost-optimal path on which h(n) is admissible for every node on the \\\n",
        "path. It can also be cost-optimal if the optimal solution has cost C* and \\\n",
        "second best is $C_2$ and if h(n) never overestimates costs by more than $C_2 - C*$. \\\n",
        "Contours draw in the state space to visualize a search. Inside a contour, nodes \\\n",
        "will have $$f(n) = g(n) + h(n) \\leq X$$ \\\\\n",
        "\n",
        "A* applications: pathing/routing (GPS), video games, robot motion planning, \\\n",
        "resource planing problems \\\\\n",
        "\n",
        "\n",
        "UCS has contours of g + h and expands equally in all directions. \\\n",
        "If A* has a good heuristic, g + h bands stretch towards a goal state, becoming \\\n",
        "more narrowly focused on an optimal path. When extending a path, g costs will \\\n",
        "be monotonic. g + h costs are monotonic iff $h(n) \\leq c(n, a, n') + h(n')$ which \\\n",
        "is true when the heuristic is consistent. \\\\\n",
        "\n",
        "Greedy best-first search expands on the node that appears to be closest to the goal, \\\n",
        "whichever has the lowest h(n). \\\\\n",
        "Evaluation function: f(n) = h(n). \\\\\n",
        "\n",
        "Worst-cases time and space complexity is $O(|V|)$, with a good heuristic can be \\\n",
        "$O(bm)$. \\\\\n",
        "\n",
        "A* search: eval function $f(n) = g(n) + h(n)$ (the path cost from \\\n",
        "the initial state to current plus the estimated cost of the shortest path from curr \\\n",
        "to a goal state)  \\\\\n",
        "\n",
        "```\n",
        "GREEDY BEST-FIRST SEARCH PSEUDOCODE:\n",
        "\n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = {}\n",
        "came_from[start] = None\n",
        "while not frontier.empty():\n",
        "  current = frontier.get()\n",
        "  if current == goal:\n",
        "    break\n",
        "  for next in graph.neighbors(current):\n",
        "    if next not in came_from:\n",
        "      priority = heuristic(goal, next)\n",
        "      frontier.put(next, priority)\n",
        "      came_from[next] = current\n",
        "\n",
        "A* PSEUDOCODE: \n",
        "\n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = dict()\n",
        "cost_so_far = dict()\n",
        "came_from[start] = None\n",
        "cost_so_far[start] = 0\n",
        "while not frontier.empty():\n",
        "  current = frontier.get()\n",
        "  if current == goal:\n",
        "    break\n",
        "  for next in graph.neighbors(current):\n",
        "    new_cost = cost_so_far[current] + graph.cost(current, next)\n",
        "    if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
        "      cost_so_far[next] = new_cost\n",
        "      priority = new_cost + heuristic(goal, next)\n",
        "      frontier.put(next, priority)\n",
        "      came_from[next] = current\n",
        "\n",
        "ITERATIVE DEEPENING SEARCH PSEUDOCODE:\n",
        "\n",
        "def IDS(problem) returns a solution node or failure\n",
        "  for depth = 0 to infinity:\n",
        "    result = iddfs_helper(problem, depth)\n",
        "    if result != cutoff:\n",
        "      return result\n",
        "def iddfs_helper(problem, l):\n",
        "  frontier = LIFO queue (stack) \n",
        "  frontier.push(initial_node)\n",
        "  result = failure\n",
        "  while frontier not empty:\n",
        "    node = frontier.pop()\n",
        "    if is_goal(node):\n",
        "      return node\n",
        "    if depth(node) > l:\n",
        "      result = cutoff\n",
        "    else if not is_cycle(node):\n",
        "      for child in successors(node):\n",
        "        frontier.push(child)\n",
        "  return result\n",
        "\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"g(N)\" : \"path cost function, equal to depth(N) in search tree\",    \n",
        "\"uniform cost search (USC)\": \"tree search to traverse/ search a weighted tree/graph\",\n",
        "\"informed search\": \"uses domain-specific hints (heuristics) about the goal locations\",\n",
        "\"heuristic function\": \"h(n), estimates cost of the cheapest path from current state to goal\",\n",
        "\"greedy best-first search\": \"form of best-FS, first expands node with lowest h(n); $f(n) = h(n)$\",\n",
        "\"admissible heuristic\": \"will never overestimate the cost to reach a goal, optimistic\",\n",
        "\"A* search\": \"expands nodes with minimal $f(n) = g(n) + h(n)$. Complete and optimal \\\n",
        "if admissible heuristic, space-complexity is an issue sometimes\",\n",
        "\"consistency\": \"if for every node and every successor of the node we have \\\n",
        "$h(n) \\leq c(n, a, n') + h(n')$\",\n",
        "\"triangle inequality\": \"side of a trangle can't be longer than the sum of the 2 other sides\",\n",
        "\"monotonic\": \"path cost will always increase as you go along a path since action \\\n",
        "costs are positive\",\n",
        "\"pruning\": \"removing nodes that are not needed, done by A*\",\n",
        "\"surely expanded nodes\": \"A* expands because they can be reached from the initial \\\n",
        "state on a path where every node $f(n) < C*$\",\n",
        "\"optimally efficient\": \"any alg that extends search paths from the initial state, \\\n",
        "must expand any node surely expanded by A*\",\n",
        "\"satisficing\": \"explore fewer nodes to accept solutions that are suboptimal but good enough\",\n",
        "\"weighted A* search\": \"weigh the heuristic value more heavily, eval function is \\\n",
        "$f(n) = g(n) + W * h(n)$, W > 1\",\n",
        "\"bounded suboptimal search\": \"find solution that's within a constant factor W \\\n",
        "of the optimal cost; guaranteed by weighted A*\",\n",
        "\"unbounded-cost search\": \"accept any solution as long as it can be found quickly\",\n",
        "\"speedy search\": \"unbounded-cost search, version of greedy best-first whose \\\n",
        "heuristic is the est # of actions to reach a goal (ignores cost)\",\n",
        "\"recursive best-first search\": \"recursive DFS that stops at f_limit, more efficient \\\n",
        "than IDA*, optimal with admissible heuristic, linear space\",\n",
        "\"backed-up value\": \"the best f-value of a node's children, RBFS updates each node\\\n",
        "along the path with this\",\n",
        "\"thrashing\": \"too many pages in mem causing comp to constantly \\\n",
        "swap; similar to SMA* weakness due to limited memory\",\n",
        "\"front-to-end search\": \"heuristics $h_F$ and $h_B$ to estimate distances to goal \\\n",
        "and the start respectively\",\n",
        "\"front-to-front search\": \"attempts to estimate the distance to the other frontier\",\n",
        "\"bidectional search\": \"optimal and complete with $f_2$ eval function and an \\\n",
        "admissible heuristic h\",\n",
        "\"effective branching factor (b*)\": \"characterizes quality of a heuristic\",\n",
        "\"domination\": \"if $h_2$ in A* never expands more nodes than when using $h_1$, it \\\n",
        "dominates the heuristic\",\n",
        "\"relaxed problem\": \"a problem with fewer restrictions on the actions\",\n",
        "\"pattern databases\": \"record cost of every new pattern encountered and store \\\n",
        " exact solution costs for every subproblem instance\",\n",
        " \"precomputation\": \"calculating some optimal path costs before alg is run, \\\n",
        " can be time-consuming but only has to be done once\",\n",
        " \"landmark points\": \"used for precomputation and compute and store path costs from each \\\n",
        " vertex to these points\",\n",
        " \"shortcuts\": \"artificial edges in the graph that define an optimal multi-action path\",\n",
        " \"differential heuristic\": \"$h_{DH}(n) = max_{L \\in Landmarks}|C*(n,L) - C*(goal,L)|$\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 488\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4kMOxZDOvkJG"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "777184f6-4eab-4313-c312-37bc20e3e016"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A* expands all nodes with $f(n) < C*$, it might expand those equal to C* before selecting a goal node and never those greater than C*. A* won't be the best answer when the number of nodes expanded can be exponential in the solution length. Using an inadmissible heuristic can risk missing the optimal solution but can possibly be more accurate as we reduce the number of nodes expanded. Suppose the optimal path is C*, but the alg returns C > C*. There must be an unexpanded node n on the optimal path. A* only returns cost-optimal paths proof (through contradiction): $$f(n)> C*,$$ else we would have expanded n\n$$f(n) = g(n) + h(n),$$ by def\n$$f(n) =g*(n)+h(n),$$ since n is on an optimal path\n$$f(n) \\leq  g*(n) +h*(n),$$ due to admissibility\n$$f(n) \\leq C*,$$ by def $C* = g*(n) +h*(n)$ \\\n\nThe last line is a contradiction. \\\n\nWe can use a weighted A* search to weigh the heuristic value more heavily. A* is inefficient with memory, best-first searches can save space by not storing states on the frontier in the frontier and reached states or by removing states from reached after proving they're not needed. Can also keep reference counts for the # of times a state has been reached, removing from reached when there's not other possible way to reach it. \\\n\nBeam search saves mem by limiting the size of the frontier. Most commonly done by only keeping the k nodes that have the best f-scores, but search is incomplete and suboptimal. Can also keep every node whose f-score is within $\\delta$ of the best f-score. \\\n\nIDA* changes the cutoff from the depth to the f-cost (g+h): the smallest f-cost of any node that exceeded the cutoff on the prev iteration. Recursive best-first search uses the f_limit var to track the f-value of the best alternative path available from any ancestor nodes. Recursion unwinds if the current node exceeds the limit. Its space-complexity depends on the heuristic accuracy and how often the best path changes when nodes are expanded. \\\n\nSimplified memory-bounded A* (SMA*) solves the issue of IDA* and RBFS using too \nlittle memory by expanding the best leaf until mem is full: then it drops the oldest worst leaf (in case f-values are the same) and expands the newest best leaf. It's complete if there's a reachable solution (the depth of the shallowest goal node is less than mem size) and optimal if reachablem else returning the best reachable solution. \\\n\nBidirectional heuristic search uses $f_F(n) = g_F(n) +h_F(n)$ for forward direction and $f_B(n) = g_B(n) +h_B(n)$ for backward (goal state as root). With a forward path going to node m and a backward path from goal to a node n a lower bound for a solution that goes from initial state to m to n to the goal is: $$lb(m,n) = max(gF(m)+gB(n), fF(m), fB(n))$$. $$f_2(n) = max(2g(n), g(n) +h(n)),$$ expanding the node that minimizes f2 from either frontier\n\n## AIMA Chapter 3.6 Heuristic Functions\nCharacterize the quality of a heuristic with an effective branching factor $b*$: $$N+1 = 1 + b* +(b*)^2 +...+(b*)^d,$$ if A* generates N nodes with solution depth at d. Korf and Reid argue characterizing the effect of A* pruning with a heuristic is whether it reduces the effective depth by some constant $k_h$ when compared to the true depth. Total search cost = $O(b^{d-k_h})$, compared to $O(b^d)$ in uninformed search. Any optimal solution in an original problem is also a solution in the relaxed problem, as relaxing will only add edges. In a relaxed problem the state-space graph is a supergraph as it adds edges to the graph by removing restrictions. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. For landmark points an optimal path is inadmissible ifit doesn't pass through one. \\\n\nAn agent can also improve their own searching due to metalevel state space. Each state in this space captures the internal/computational state of a program searching in an ordinary state space. A metalevel learning alg learns from the experiences in the state space to avoid exploring unpromising subtrees. \n\n## Module 4 Lecture Notes\n USC is an extension of BFS, expanding node with the lowest path cost. It's implemented with a frontier as a priority queue ordered by g(n). Unlike BFS, you test if a node is a goal state when selecting it for expansion, not when it's added to the frontier. It will update a node on the frontier if a better path on the same state is found. It will always enqueue a node before checking whether it is a goal; favors lower cost paths. Every consistent heuristic is admissible, so if there is a consistent heuristic, A* is cost-optimal. If a heuristic is inadmissible, A* is cost-optimal if there's at least one cost-optimal path on which h(n) is admissible for every node on the path. It can also be cost-optimal if the optimal solution has cost C* and second best is $C_2$ and if h(n) never overestimates costs by more than $C_2 - C*$. Contours draw in the state space to visualize a search. Inside a contour, nodes will have $$f(n) = g(n) + h(n) \\leq X$$ UCS has contours of g + h that are circular around the start state and spread out equally in all directions. If A* has a good heuristic, g + h bands stretch towards a goal state, becoming more narrowly focused on an optimal path. When extending a path, g costs will be monotonic. g + h costs are monotonic iff $h(n) \\leq c(n, a, n') + h(n')$ which is true when the heuristic is consistent. \\\n\nGreedy best-first search expands on the node that appears to be closest to the goal, whichever has the lowest h(n). Its evaluation function is f(n) = h(n). Worst-cases time and space complexity is $O(|V|)$, but with a good heuristic can be $O(bm)$. A* search uses the eval function $f(n) = g(n) + h(n)$ or the path cost from the initial state to current plus the estimated cost of the shortest path from curr to a goal state.  \\\n\n```\nGREEDY BEST-FIRST SEARCH PSEUDOCODE:\n\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = {}\ncame_from[start] = None\nwhile not frontier.empty():\n  current = frontier.get()\n  if current == goal:\n    break\n  for next in graph.neighbors(current):\n    if next not in came_from:\n      priority = heuristic(goal, next)\n      frontier.put(next, priority)\n      came_from[next] = current\n\nA* PSEUDOCODE: \n\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = dict()\ncost_so_far = dict()\ncame_from[start] = None\ncost_so_far[start] = 0\nwhile not frontier.empty():\n  current = frontier.get()\n  if current == goal:\n    break\n  for next in graph.neighbors(current):\n    new_cost = cost_so_far[current] + graph.cost(current, next)\n    if next not in cost_so_far or new_cost < cost_so_far[next]:\n      cost_so_far[next] = new_cost\n      priority = new_cost + heuristic(goal, next)\n      frontier.put(next, priority)\n      came_from[next] = current\n\nITERATIVE DEEPENING SEARCH PSEUDOCODE:\n\ndef IDS(problem) returns a solution node or failure\n  for depth = 0 to infinity:\n    result = iddfs_helper(problem, depth)\n    if result \neq cutoff:\n      return result\ndef iddfs_helper(problem, l):\n  frontier = LIFO queue (stack) \n  frontier.push(initial_node)\n  result = failure\n  while frontier not empty:\n    node = frontier.pop()\n    if is_goal(node):\n      return node\n    if depth(node) > l:\n      result = cutoff\n    else if not is_cycle(node):\n      for child in successors(node):\n        frontier.push(child)\n  return result\n\n```\n\n\n## Module 4 Definitions\n* **G(n)** - path cost function, equal to depth(N) in search tree\n* **Uniform cost search (usc)** - tree search to traverse/ search a weighted tree/graph\n* **Informed search** - uses domain-specific hints (heuristics) about the goal locations\n* **Heuristic function** - h(n), estimates cost of the cheapest path from current state to goal\n* **Greedy best-first search** - form of best-FS, first expands node with lowest h(n); $f(n) = h(n)$\n* **Admissible heuristic** - will never overestimate the cost to reach a goal, optimistic\n* **A* search** - expands nodes with minimal $f(n) = g(n) + h(n)$. Complete and optimal if admissible heuristic, space-complexity is an issue sometimes\n* **Consistency** - if for every node and every successor of the node we have $h(n) \\leq c(n, a, n') + h(n')$\n* **Triangle inequality** - side of a trangle can't be longer than the sum of the 2 other sides\n* **Monotonic** - path cost will always increase as you go along a path since action costs are positive\n* **Pruning** - removing nodes that are not needed, done by A*\n* **Surely expanded nodes** - A* expands because they can be reached from the initial state on a path where every node $f(n) < C*$\n* **Optimally efficient** - any alg that extends search paths from the initial state, must expand any node surely expanded by A*\n* **Satisficing** - explore fewer nodes to accept solutions that are suboptimal but good enough\n* **Weighted a* search** - weigh the heuristic value more heavily, eval function is $f(n) = g(n) + W * h(n)$, W > 1\n* **Bounded suboptimal search** - find solution that's within a constant factor W of the optimal cost; guaranteed by weighted A*\n* **Unbounded-cost search** - accept any solution as long as it can be found quickly\n* **Speedy search** - unbounded-cost search, version of greedy best-first whose heuristic is the est # of actions to reach a goal (ignores cost)\n* **Recursive best-first search** - recursive DFS that stops at f_limit, more efficient than IDA*, optimal with admissible heuristic, linear space\n* **Backed-up value** - the best f-value of a node's children, RBFS updates each nodealong the path with this\n* **Thrashing** - too many pages in mem causing comp to constantly swap; similar to SMA* weakness due to limited memory\n* **Front-to-end search** - heuristics $h_F$ and $h_B$ to estimate distances to goal and the start respectively\n* **Front-to-front search** - attempts to estimate the distance to the other frontier\n* **Bidectional search** - optimal and complete with $f_2$ eval function and an admissible heuristic h\n* **Effective branching factor (b*)** - characterizes quality of a heuristic\n* **Domination** - if $h_2$ in A* never expands more nodes than when using $h_1$, it dominates the heuristic\n* **Relaxed problem** - a problem with fewer restrictions on the actions\n* **Pattern databases** - record cost of every new pattern encountered and store  exact solution costs for every subproblem instance\n* **Precomputation** - calculating some optimal path costs before alg is run,  can be time-consuming but only has to be done once\n* **Landmark points** - used for precomputation and compute and store path costs from each  vertex to these points\n* **Shortcuts** - artificial edges in the graph that define an optimal multi-action path\n* **Differential heuristic** - $h_{DH}(n) = max_{L \\in Landmarks}|C*(n,L) - C*(goal,L)|$\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" hi \"\"\"\n",
        " \n",
        "chapter5_2 = \"\"\" With minmax search, given a game tree we can determine the optimal strategy by working out minmax value of each state \\\n",
        "Minmax value is the utility for Max player of being in that particular state assuming that both players play optimally from there to the \\\n",
        "end of the game. We know that the minmax value of each terminal state is just the utility (which is given by utility function).\\\n",
        "Max will move to the next highest valued node and then min moves to next lowest value node and so on.\\\\\n",
        "\n",
        "For multiplayer games we use vector of values instead $<V_1, V_2, V_3>$ \\\n",
        "Alpha Beta pruning the idea: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the same\\\n",
        "level or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\\\n",
        "\n",
        "$\\Alpha$ is the value of the best (highest val) chioce we have found so far at any choice point along the path for Max.\\\\\n",
        "\n",
        "$\\Beta$ is the value of the best (lowest val) choice we have found so far at any choice point along the path for Min.\\\\\n",
        "\n",
        "Move ordering is a way to ensure even faster pruning as well. Which if done perfectly brings runtime down from $O(b^m)$ to $O(b^{m/2})$\\\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" A heuristic evaluation function, EVAL(s,p) returns an estimate of the expected utility of the state s to player p.\\\\\n",
        "\n",
        "We want to be able to use this to our advantage and cut it off the search as early as possible. \\\n",
        "For some terminal state $S_x$ EVAL($S_x$,p) is equal to Utility($S_x$, p)\\\\\n",
        "\n",
        "We can create an evaluation function by picking criteria that are easy to calculate and are highly correlated with winning.\\\\\n",
        "\n",
        "For example we can use a material advantage method which assigns value to parts of a state. In chess, the pieces.\\\\\n",
        "\n",
        "We add up the values of each of the factors and that is the value of the eval function.\\\\\n",
        "\n",
        "Output should be normalized so that $$0 \\leq eval \\leq 1$$ where 1 is winning and 0 is losing.\\\\\n",
        "\n",
        "Things that can get in the way of EVAL effectiveness:\\\\\n",
        "\n",
        "Eval function should only be applied to positions that are quiescent. Checking if a state is quiescent is called a quiescent search.\\\\\n",
        "\n",
        "The horizon effect can be stopped by allowing singular extensions.\\\\\n",
        "\n",
        "Forward pruning prunes moves that seem bad but might be good. This decreases comp time at the expense of possible error.\\\\\n",
        "\n",
        "One example of it is beam search which only considers a beam of n best moves according to eval function. (might get rid of good moves).\\\\\n",
        "\n",
        "Another example is Late move reduction which assumes good move ordering and so it doesn't do a full search of children nodes to save time.\\\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" in stochastic game trees you must include chance nodes in addition to max and min nodes. Branches leading from chance nodes go to\\\n",
        "\n",
        "each different possibility/outcome. Ex: dice roll labeled with outcome and probability.\\\\\n",
        "\n",
        "Positions in this treedo not have definitive minmax values but instead we calculate the expected value of a position.\\\\\n",
        "\n",
        "Average over all possible outcomes of the chance nodes.\\\\\n",
        "\n",
        "We use expectimax value for games with chance nodes. Terminal nodes and min/max nodes work the same.\\\\\n",
        "\n",
        "For chance nodes we use expected value: sum of the value over all outcomes weighted by probability of each chance action.\\\\\n",
        "\n",
        "Just like with minmax game trees we can use eval functions. With these games though we must return values that are a positive linear transformation of \\\\\n",
        "the probability of winning.\\\\\n",
        "\n",
        "Runtime is $O(b^mn^m)$ where n is the number of rolls of dice/times probability is introduced.\\\\\n",
        "\n",
        "We can do something similar to Alpha Beta pruning as well by placing bounds on the utility function we can actually arrive at bounds for the average\\\\\n",
        "\n",
        "of a chance node without looking at the all the children.\"\"\"\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\\\\\n",
        "\n",
        "Environment is assumed to be episodic.\\\\\n",
        "\n",
        "The utility function assings a numerical value to a state to express it's desirability.\\\\\n",
        "\n",
        "Expected Utility = average utility of all outcomes times probability that outcome happens\\\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" We can consider each set of outcomes from an action as a lottery where each outcome is \\\n",
        "assigned a probability. L= [prob1, action1; prob2, action2...]\\\\\n",
        "\n",
        "There are multiple axioms of utility theory:\\\\\n",
        " \n",
        "-ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\\\\\n",
        " \n",
        "-TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\\\\\n",
        " \n",
        "-CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be\\\n",
        "indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p.\\\\\n",
        " \n",
        "-SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B , then the agent is indifferent between two more complex \\\n",
        "lotteries that are the same except that B is substituted for A in one of them.\\\\\n",
        " \n",
        "-MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B\\\n",
        ". If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A(and vice versa)\\\\\n",
        " \n",
        "-DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\\\n",
        "We can derive the following from these:\\\\\n",
        " \n",
        "EXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U\\\\\n",
        " \n",
        "EXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome\\\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Although according to Decision theory people should be maximizing expected utility, in reality people are actually\\\\\n",
        " \n",
        "picking things with the highest estimated expected utility. Estimates can be WAYYYY off. Optimistic expectations are valued higher as a result.\\\\\n",
        " \n",
        "Decision theory is a normative theory - how agents SHOULD act.\\\\\n",
        "\n",
        "Descriptive Theory is how agents do act.\"\"\"\n",
        " \n",
        "# Lecture notes\n",
        "module5_lecture_notes = \"\"\" A game tree represents a game problem space. Nodes are board positions and the edges are legal moves from that state. \\\\\n",
        "\n",
        "Each even level represents that it's Max's turn to move. Each odd level represents that it's Min's turn to move.\\\\\n",
        "\n",
        "Minmax algorithm, recurse to the leaves and return the utility for those nodes using utility function. Then, depending on if the node above (parent)\\\\\n",
        "\n",
        "min or max, select the min/max value returned respectively.\\\\\n",
        "\n",
        "continue this process recursively until you reach top.\\\\\n",
        " \n",
        "We assume that min and max will play optimally.\\\\\n",
        " \n",
        "For alpha beta search the idea is that: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the same\\\n",
        "level or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\\\n",
        " \n",
        "For an evaluation function, we are basically given a numeric value for how good a board is.\\\\\n",
        " \n",
        "If it is greater than 0 max is winning. If it is 0 Max is tied at that state. If it is less than zero max is losing.\\\\\n",
        " \n",
        "We can use the eval function to stop a minmax tree from going too long. We can essentially cut a tree off after a certain ply (see definitions)\\\\\n",
        " \n",
        "and then for the leaves we assign them a value based on the eval function and run minmax that way.\\\\\n",
        " \n",
        "There are games also that involve chance. In order to deal with unknown moves, we add chance nodes. The value of these nodes are the outcome (say rolling a 6\\\\\n",
        " \n",
        "the value would be a 6) and then the edge weight would be the probability that that outcome occurs.\\\\\n",
        " \n",
        "the value of the chance node then is the sum of the individual outcomes multiplied by their respective probabilities.\\\\\n",
        " \n",
        "There is a form of pruning that can be done on this. See above lesson 5.5\\\n",
        " \n",
        "\"\"\"\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"minmax value\" : \"the utility for max of being in that particular game state assuming that both players play optimally\",\n",
        "\"minmax runtime\": \"$O(b^m)$\",\n",
        "\"alpha beta pruning\": \"a method of simplifying calculations by eliminating subtrees with suboptimal moves\",\n",
        "\"alpha\": \"the value of the best (highest value) choice we have found at any choice point along the path max\",\n",
        "\"beta\": \"the value of the best (lowest value) choice we have found at any choice point along the path min\",\n",
        "\"transpositions\": \"different permutations of the move sequence that end up in the same position (leads to redundancy)\",\n",
        "\"Transposition table\": \"caches heuristic values of states. stops transpositions\",\n",
        "\"Type A Strategy\": \"wide but shallowc considers all possible moves to a certain ply, then uses heuristic eval function to estimate utility\",\n",
        "\"Type B Strategy\": \"ignore moves that look bad and follow good looking paths.\",\n",
        "\"horizon effect\": \"when a bad move is inevitable but the comp prolongs it by using delaying tactics\",\n",
        "\"beam search\": \"a forward pruning method that only looks at the n best moves according to eval function\",\n",
        "\"late move reduction\": \"doesn't check all vals but assumes good move ordering so doesn't check all the way to save time\",\n",
        "\"stochastic game trees\": \"game trees that have chance nodes\",\n",
        "\"preference elicitation\": \"the process of working out a human's utility function\",\n",
        "\"optimizers curse\": \"the tendency of the estimated expected utility of the best choice to be too high\",\n",
        "\"normative theory\": \"how agents should act\",\n",
        "\"descriptive theory\": \"how agents actually act in reality\",\n",
        "\"ply\": \"one move by one player, identifiable as a single layer of a game tree\",\n",
        "\"evaluation funciton\": \"eval(s,p) evaluates how good a certain board position is\",\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d42b1aa0-8a0f-4725-d7fa-6a0b0f707380"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n hi \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n With minmax search, given a game tree we can determine the optimal strategy by by working out minmax value of each state Minmax value is the utility for Max player of being in that particular state assuming that both players play optimally from there to the end of the game. We know that the minmax value of each terminal state is just the utility (which is given by utility function).Max will move to the next highest valued node and then min moves to next lowest value node and so on.For multiplayer games we use vector of values instead $<V_1, V_2, V_3>$ Alpha Beta pruning the idea: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the samelevel or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\n\n$\\Alpha$ is the value of the best (highest val) chioce we have found so far at any choice point along the path for Max.\\\n\n$\\Beta$ is the value of the best (lowest val) choice we have found so far at any choice point along the path for Min.\\\n\nMove ordering is a way to ensure even faster pruning as well. Which if done perfectly brings runtime down from $O(b^m)$ to $O(b^{m/2})$\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function, EVAL(s,p) returns an estimate of the expected utility of the state s to player p.We want to be able to use this to our advantage and cut it off the search as early as possible. For some terminal state $S_x$ EVAL($S_x$,p) is equal to Utility($S_x$, p)\\\n\nWe can create an evaluation function by picking criteria that are easy to calculate and are highly correlated with winning.\\\n\nFor example we can use a material advantage method which assigns value to parts of a state. In chess, the pieces.\\\n\nWe add up the values of each of the factors and that is the value of the eval function.\\\n\nOutput should be normalized so that $$0 \\leq eval \\leq 1$$ where 1 is winning and 0 is losing.\\\n\nThings that can get in the way of EVAL effectiveness:\\\n\nEval function should only be applied to positions that are quiescent. Checking if a state is quiescent is called a quiescent search.\\\n\nThe horizon effect can be stopped by allowing singular extensions.\\\n\nForward pruning prunes moves that seem bad but might be good. This decreases comp time at the expense of possible error.\\\n\nOne example of it is beam search which only considers a beam of n best moves according to eval function. (might get rid of good moves).\\\n\nAnother example is Late move reduction which assumes good move ordering and so it doesn't do a full search of children nodes to save time.\n\n## AIMA Chapter 5.5 Stochastic Games\n in stochastic game trees you must include chance nodes in addition to max and min nodes. Branches leading from chance nodes go to\neach different possibility/outcome. Ex: dice roll labeled with outcome and probability.\\\n\nPositions in this treedo not have definitive minmax values but instead we calculate the expected value of a position.\\\n\nAverage over all possible outcomes of the chance nodes.\\\n\nWe use expectimax value for games with chance nodes. Terminal nodes and min/max nodes work the same.\\\n\nFor chance nodes we use expected value: sum of the value over all outcomes weighted by probability of each chance action.\\\n\nJust like with minmax game trees we can use eval functions. With these games though we must return values that are a positive linear transformation of \\\nthe probability of winning.\\\n\nRuntime is $O(b^mn^m)$ where n is the number of rolls of dice/times probability is introduced.\\\n\nWe can do something similar to Alpha Beta pruning as well by placing bounds on the utility function we can actually arrive at bounds for the average\\\n\nof a chance node without looking at the all the children.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.Environment is assumed to be episodic.\\\n\nThe utility function assings a numerical value to a state to express it's desirability.\\\n\nExpected Utility = average utility of all outcomes times probability that outcome happens\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We can consider each set of outcomes from an action as a lottery where each outcome is assigned a probability. L= [prob1, action1; prob2, action2...]There are multiple axioms of utility theory:\\\n \n-ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\\\n \n-TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\\\n \n-CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will beindifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p.\\\n \n-SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B , then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them.\\\n \n-MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A(and vice versa)\\\n \n-DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.We can derive the following from these:\\\n \nEXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U\\\n \nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome\n\n## AIMA Chapter 16.3 Utility Functions\n Although according to Decision theory people should be maximizing expected utility, in reality people are actually\\ \npicking things with the highest estimated expected utility. Estimates can be WAYYYY off. Optimistic expectations are valued higher as a result.\\\n \nDecision theory is a normative theory - how agents SHOULD act.\\\n\nDescriptive Theory is how agents do act.\n\n## Module 5 Lecture Notes\n A game tree represents a game problem space. Nodes are board positions and the edges are legal moves from that state. Each even level represents that it's Max's turn to move. Each odd level represents that it's Min's turn to move.\\\n\nMinmax algorithm, recurse to the leaves and return the utility for those nodes using utility function. Then, depending on if the node above (parent)\\\n\nmin or max, select the min/max value returned respectively.\\\n\ncontinue this process recursively until you reach top.\\\n \nWe assume that min and max will play optimally.\\\n \nFor alpha beta search the idea is that: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the samelevel or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\n \nFor an evaluation function, we are basically given a numeric value for how good a board is.\\\n \nIf it is greater than 0 max is winning. If it is 0 Max is tied at that state. If it is less than zero max is losing.\\\n \nWe can use the eval function to stop a minmax tree from going too long. We can essentially cut a tree off after a certain ply (see definitions)\\\n \nand then for the leaves we assign them a value based on the eval function and run minmax that way.\\\n \nThere are games also that involve chance. In order to deal with unknown moves, we add chance nodes. The value of these nodes are the outcome (say rolling a 6\\\n \nthe value would be a 6) and then the edge weight would be the probability that that outcome occurs.\\\n \nthe value of the chance node then is the sum of the individual outcomes multiplied by their respective probabilities.\\\n \nThere is a form of pruning that can be done on this. See above lesson 5.5 \n\n\n## Module 5 Definitions\n* **Minmax value** - the utility for max of being in that particular game state assuming that both players play optimally\n* **Minmax runtime** - $O(b^m)$\n* **Alpha beta pruning** - a method of simplifying calculations by eliminating subtrees with suboptimal moves\n* **Alpha** - the value of the best (highest value) choice we have found at any choice point along the path max\n* **Beta** - the value of the best (lowest value) choice we have found at any choice point along the path min\n* **Transpositions** - different permutations of the move sequence that end up in the same position (leads to redundancy)\n* **Transposition table** - caches heuristic values of states. stops transpositions\n* **Type a strategy** - wide but shallowc considers all possible moves to a certain ply, then uses heuristic eval function to estimate utility\n* **Type b strategy** - ignore moves that look bad and follow good looking paths.\n* **Horizon effect** - when a bad move is inevitable but the comp prolongs it by using delaying tactics\n* **Beam search** - a forward pruning method that only looks at the n best moves according to eval function\n* **Late move reduction** - doesn't check all vals but assumes good move ordering so doesn't check all the way to save time\n* **Stochastic game trees** - game trees that have chance nodes\n* **Preference elicitation** - the process of working out a human's utility function\n* **Optimizers curse** - the tendency of the estimated expected utility of the best choice to be too high\n* **Normative theory** - how agents should act\n* **Descriptive theory** - how agents actually act in reality\n* **Ply** - one move by one player, identifiable as a single layer of a game tree\n* **Evaluation funciton** - eval(s,p) evaluates how good a certain board position is\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" 3 components to csp: X (set of variables),D (set of domains f/variable), C (constraints, that allow combinations). \\\n",
        "Each constraint C_j made up of <scope, relation> pair. EX:D = {1,2,3}, C = <(X_1, X_2), {(2,1), (3,1), (3,2)}>\\\\\n",
        "\n",
        "Solving a CSP is an NP-complete task.\\\n",
        "\n",
        "Representing CSPs as constraint graph is good where the nodes are the variables and edges are scopes\\\\\n",
        "\n",
        "3 Main Reasons for CSP: \\\\\n",
        "\n",
        "1) Easy to make a problem into a csp \\\\\n",
        "\n",
        "2) Much research put into csp to make fast and efficient. Prune stace space(ss) \\\n",
        "faster than atomic ss searcher sss can only check if goal, but csp cuts down if states are bad\\\\\n",
        "\n",
        "3) The simplest csp are those with discrete finite domains such as with the 8-queens (1..8 limit and discrete \\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" Constraint Propagation: Inference in CSPs: atomic sss expand \\\n",
        "nodes to visit a successor while csps has choices based on new variables. \\\n",
        "Our key idea is local consistency, where each variable is a node and binary constraint \\\n",
        "edge enforcing local consistency will make the rest of the graph consistent.\n",
        "1) Node Consistency\\\\\n",
        "\n",
        "2) Arc Consistency\\\\\n",
        "\n",
        "AC-3: Pops off arbitrary arc X_i/X_j and makes X_i arc-consistent to X_j. If the \\\n",
        "domain changes of X_i we queue all the arcs (X_k, X_i) and continue from there. \\\n",
        "O(cd^3) c=binary constraints, d=maxsizeof(domain) \\\\\n",
        "\n",
        "3) Path Consistency\n",
        "\n",
        "4) K-Consistency\\\\\n",
        "\n",
        "5) Global Constraints\\\\\n",
        "\n",
        "\n",
        "6) Sudoku: enforcing Alldiff for box, row and call, with arc consistency \\\n",
        "255,960 different path constraints for P-3\\\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" After constraint propagation we might still have multiple values, \\\n",
        "so we have to search for the solution \\\\\n",
        "\n",
        "Backtracking search algorithms work on partial assignments. The issue for using \\\n",
        "standard depth-limited search is that because the branching factor O(nd) at the \\\n",
        "top level, so we would have n!d^n leaves. But we only have d^n possible assignments. \\\n",
        "We remove the n! factor by understanding that the csp's are commutative, at each \\\n",
        "level we choose a variable to deal with but never backtrack to over our choice \\\\\n",
        "\n",
        "1) Variable and value ordering\\\\\n",
        "\n",
        "Degree heuristic(DH) helps choosing the first color because MRV doesn't help with \\\n",
        "thatDH tries to reduce the branching factor on the future by picking the variable \\\n",
        "that is involved with the most constraints on other unassigned variables. \\\\\n",
        "\n",
        "The least-constraining-value heuristic is used as the method for selecting \\\n",
        "values after getting a variable. It is to select the value that restricts the \\\n",
        "fewest neighbors in the constraint graph\\\\\n",
        "\n",
        "Variables selection is fail-first. Value selection is fail-last\\\\\n",
        "\n",
        "2) Interleaving search and inference\\\\\n",
        "\n",
        "Forward checking does not detect every inconsistency, doesn't look far enough ahead \\\\\n",
        "\n",
        "Maintaining Arc Consistency (MAC) finds inconsistencies that forward checking \\\n",
        "can't find because of depth limitations. \\\\\n",
        "\n",
        "MAC after a X_i is assigned a value, the inference will call AC-3, but the \\\n",
        "queue will only have the arcs of (X_j, X_i) for unassigned neighbors. And runs \\\n",
        "AC-3 normally if the domain is empty of any variable, it will immediately backtrack. \\\n",
        "MAC is stronger,because forward checking doesn't propagate constraints when changes \\\n",
        "are made to the domain. \\\\\n",
        "3) Intelligent backtracking \\\\\n",
        "4) Constraint learning \\\\\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search algorithms use a complete-state formulation where \\\n",
        "each state assigns value to every variable. Then during the search one variable \\\n",
        "is changed at a time. We randomly chose a conflicted variable and selected a \\\n",
        "value using the min-conflicts heuristic. \\\\\n",
        "\n",
        "For the n-queens problem, The run time of min-conflicts is roughly independent \\\n",
        "of problem size. And min-conflicts are effective for many CSP's. Hubble Space \\\n",
        "Telescope uses min-conflicts to reduce scheduling time 3weeks to 10 min. \\\\\n",
        "\n",
        "With min-conflicts there can be Plateaus of states with the same score. \\\n",
        "So Plateau Search allows us to move sideways to another state to find a way \\\n",
        "off the plateau. This technique is called tabu search. Where we forbid the \\\n",
        "algorithm from returned to a small list of visited statesSimulated annealing \\\n",
        "can also be used \\\\\n",
        "\n",
        "Constraint Weighting focuses the search on important constraints.\\\\\n",
        "\n",
        "The constraints are given a numerical weight, which all start at 1. During the \\\n",
        "searchThe algorithm chooses a variable to change that will result \\\n",
        "in the lowest total weight of all the inconsistent constraints. Then for all \\\n",
        "violated constraints by the assignment the weights are incremented n 2 benefits:\\\\\n",
        "\n",
        "1) Topography to the plateaus \\\\\n",
        "\n",
        "2) Difficult constraints are given higher weights\\\\\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" Independence can be found by finding connected components of \\\n",
        "the constraint graph.\\\\\n",
        "\n",
        "The reason why we want to break down our problem is because we can get our run \\\n",
        "time down to O(d^c* n/c) where c is the number of connected components.\\\\\n",
        "\n",
        "Constraint graph is a tree when 2 variables are connected by only 1 path. Any \\\n",
        "tree-structured CSP(tsCSP) can be solved in linear time. The reason for this is \\\n",
        "because of direction arc consistency (DAC). A csp is DAC if in an ordered \\\n",
        "X_1...X_n iff X_i is arc-consistent j > i.\\\\\n",
        "\n",
        "When solving tsCSP we pick a variable to be our root and then have an ordering. \\\n",
        "We can use toposort to order them. We can make it arc consistent in O(nd^2). \\\\\n",
        "\n",
        "1) Cutset conditioning\\\\\n",
        "\n",
        "We select subset S that allows our graph to be a tree this is the cycle cutset \\\n",
        "For each assignment for S that satisfies the constraints a. remove the values \\\n",
        "from the domains that would cause inconsistency. b. return the solution if the \\\n",
        "csp has one with S included the total runtime would be O(d^c *(n-c)d^2). This \\\n",
        "approach is called cutset conditioning. \\\\\n",
        "2) Tree decomposition \\\\\n",
        "\n",
        "- In at least one of the tree nodes, every variable is present \\\\\n",
        "\n",
        "- If two variables are connected by a constraint then then must appear in at \\\n",
        "least one node together\\\\\n",
        "\n",
        "\n",
        "3) Value symmetry\\\\\n",
        "\n",
        "That will allow us to avoid branching. It is NP-hard to eliminate all symmetry, \\\n",
        "but it is important and effective\\\\\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint satisfaction problem\": \"problem represented as states having set of\\\n",
        " vars having vals, solved when values for all variables fit constraint\",\n",
        "\"relation\": \"the vals that the vars in the scope can have\",\n",
        "\"scope\": \"vars  in the constraint\",\n",
        "\"domain\": \"valid values for var $X_i$\",\n",
        "\"consistent\": \"legal assignment that doesn't violate any constraints\",\n",
        "\"complete assignment\": \"every var has a val\",\n",
        "\"solution\": \"consistent and complete assignment\",\n",
        "\"disjunctive constraint\": \"when 2 tasks can't happen at the same time $(t + d) < t2$ or $(t2+d) < t$\",\n",
        "\"precedence constraints\": \"If a task has to happen before another with a duration \\\n",
        "we have $T_1 + d \\leq T_2$\",\n",
        "\"unary constraint\": \"when a constraint is not allowed for a single var $<X, X!= green>$\",\n",
        "\"binary constraint\": \"when a constraint relates 2 vars $<(X_1, X_2), X_2 != X_1>$\",\n",
        "\"binary csp\": \"csp that only uses unary and binary constraints\",\n",
        "\"global constraint\": \"constraint that considers an arbitrary # of variables\",\n",
        "\"cryptarithmetic puzzle\": \"each letter represents a diff digit\",\n",
        "\"constraint hypergraph\": \"graph of nodes and hypernodes(squares) that indicate n-ary constraints\",\n",
        "\"preference constraints\": \"constraint that is allowable, but not optimal\",\n",
        "\"constrained optimization problem\": \"CSPs with preference solved with optimization, preference indicated by cost on variable\",\n",
        "\"constraint propagation\": \"reducing legal values using constraints, then reducing the legal values for another var using new values\",\n",
        "\"node-consistent\": \"for the unary constraints, if all values satisfy\",\n",
        "\"arc-consistent\": \"domain satisfies binary constraints\",\n",
        "\"k-consistency\": \"if for any k-1 vars, being able to assign the k-th var to keep everything consistent\",\n",
        "\"strongly k-consistent\": \"1 to k-consistent\",\n",
        "\"bounds-consistent\": \"For upper and lower bounds of X there is value between X and Y that satisfies constraints for every Y\",\n",
        "\"conflict set\": \"set of vars and values that conflict with another var\",\n",
        "\"backjumping\": \"backtracking to the most recently assigned in the conflict set\",\n",
        "\"constraint learning\": \"from the conflict set, finding the minimum set of vars that cause a problem\",\n",
        "\"no-good\": \"set of vars that caused the problem found in constraint learning\",\n",
        "   \n",
        "}\n"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1d7bca39-dfff-49e7-f9a0-187a6386cce6"
      },
      "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": 144,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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* **Constraint satisfaction problem** - problem represented as states having set of vars having vals, solved when values for all variables fit constraint\n* **Relation** - the vals that the vars in the scope can have\n* **Scope** - vars  in the constraint\n* **Domain** - valid values for var $X_i$\n* **Consistent** - legal assignment that doesn't violate any constraints\n* **Complete assignment** - every var has a val\n* **Solution** - consistent and complete assignment\n* **Disjunctive constraint** - when 2 tasks can't happen at the same time $(t + d) < t2$ or $(t2+d) < t$\n* **Precedence constraints** - If a task has to happen before another with a duration we have $T_1 + d \\leq T_2$\n* **Unary constraint** - when a constraint is not allowed for a single var $<X, X!= green>$\n* **Binary constraint** - when a constraint relates 2 vars $<(X_1, X_2), X_2 != X_1>$\n* **Binary csp** - csp that only uses unary and binary constraints\n* **Global constraint** - constraint that considers an arbitrary # of variables\n* **Cryptarithmetic puzzle** - each letter represents a diff digit\n* **Constraint hypergraph** - graph of nodes and hypernodes(squares) that indicate n-ary constraints\n* **Preference constraints** - constraint that is allowable, but not optimal\n* **Constrained optimization problem** - CSPs with preference solved with optimization, preference indicated by cost on variable\n* **Constraint propagation** - reducing legal values using constraints, then reducing the legal values for another var using new values\n* **Node-consistent** - for the unary constraints, if all values satisfy\n* **Arc-consistent** - domain satisfies binary constraints\n* **K-consistency** - if for any k-1 vars, being able to assign the k-th var to keep everything consistent\n* **Strongly k-consistent** - 1 to k-consistent\n* **Bounds-consistent** - For upper and lower bounds of X there is value between X and Y that satisfies constraints for every Y\n* **Conflict set** - set of vars and values that conflict with another var\n* **Backjumping** - backtracking to the most recently assigned in the conflict set\n* **Constraint learning** - from the conflict set, finding the minimum set of vars that cause a problem\n* **No-good** - set of vars that caused the problem found in constraint learning\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" 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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "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": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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": {}
        }
      ]
    },
    {
      "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/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "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.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": {}
        }
      ]
    }
  ]
}