{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "67418739-f647-4251-bfa2-d0c80db07b4a"
      },
      "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)))\n"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ed20828a-b274-418f-fa17-02ed33d033a5"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" 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 = \"\"\" Simple reflex agent operates best in environents that are fully observable, which allows the agent to know more useful information from the environment and thus make optimal actions.\n",
        "It reacts to the immediate percept and uses rules to choose an action. \n",
        "\\n A simple reflex performs actions based on a current situation. When something happens in the environment of a simple reflex agent, the agent quickly scans its knowledge base for how to respond to the situation at-hand based on pre-determined rules. \n",
        " \\n Agent: Touchless faucets, thermostat, pet hamster\n",
        " \\n Agent's choice of action at at given instant depends on its perception.\n",
        " \\n In some competitive environments, random behavior could be rational.\"\"\"\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 environment through sensors and act in an environment through actuators\",\n",
        "\"rational agent\" : \"act to get best outcome or best expected outcome(uncertain), it maximize expected performance, not guarantee optimal\",\n",
        "\"perfection agent\":\"maximizes actual performance\",\n",
        "\"simple reflex agent\" : \"select actions based on current percept not previous percept\",\n",
        "\"agent function\": \"maps a sequence of perceptions into action, implemented as the agent program, describe agent behavior\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 868
        },
        "cellView": "form",
        "outputId": "f136b77f-49a7-4b8b-8852-04132ffcdab4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\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 Simple reflex agent operates best in environents that are fully observable, which allows the agent to know more useful information from the environment and thus make optimal actions.\nIt reacts to the immediate percept and uses rules to choose an action. \n\n A simple reflex performs actions based on a current situation. When something happens in the environment of a simple reflex agent, the agent quickly scans its knowledge base for how to respond to the situation at-hand based on pre-determined rules. \n \n Agent: Touchless faucets, thermostat, pet hamster\n \n Agent's choice of action at at given instant depends on its perception.\n \n In some competitive environments, random behavior could be rational.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive environment through sensors and act in an environment through actuators\n* **Rational agent** - act to get best outcome or best expected outcome(uncertain), it maximize expected performance, not guarantee optimal\n* **Perfection agent** - maximizes actual performance\n* **Simple reflex agent** - select actions based on current percept not previous percept\n* **Agent function** - maps a sequence of perceptions into action, implemented as the agent program, describe agent behavior\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 = \"\"\" Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n",
        "\\n Python function could take unlimited arguments when you use **args \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 232
        },
        "outputId": "2c2eab12-8e4e-41cd-e2dc-2c9865dd9dda"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n\n Python function could take unlimited arguments when you use **args \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Agent's problem solving process:goal formulation, problem formulation, search execution.\\n A search a problem has state space, initial state, goal states, actions, transition model, action cost function.\\n\n",
        " optimal solution has the lowest path cost among all solutions. \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problem is intended to illustrate or exercise various problem-solving methods. A real-world problem is a solution that people actually use and the formulation is idiosyncratic not standardized. \"\"\"\n",
        "chapter3_3 = \"\"\" A search method is uniformed if it only has access to the problem definition. \n",
        "\\n A search method is informed if it has access to the problem definition and heuristic function h(n).\n",
        "\\n Best-first search is choose a node with minimum value of some evaluation function.\n",
        "\\n 4 ways to evaluate algorithm's performace: completeness, cost optimality, time complexity, space complexity. \n",
        "\\n A search algorithm is complete if the algorithm is guaranteed to find a solution if there is one and to correctly report failure when there is not.\n",
        "\\n a search algorithm is optimal if it find a solution with the lowest path cost.\n",
        "\\n a graph search checks for redundant paths (it does'n waste time on examining redundant paths, thus it runs quicker), use more memory becasuse it store what states have been reached and what paths are redundant.\n",
        "\\n a tree search doesn't check for redundant paths, use less space than graph search, slower than graph search\"\"\"\n",
        "chapter3_4 = \"\"\" Breadth-first search is expand the root node first, then expand all the successors of the root node, then their successors. \n",
        "\\n Uniform-cost soearch use best-first search, the evaluation function is the cost of the path from the root to the current node. It's complete and cost-optimal. \n",
        "\\n Depth-first search expands the deepest node in the frontier first.\n",
        "\\n Backtracking search [robotic assembly] (variant of dfs) only one successor is generated at a time, each partially expanded node remembers which successor to generate next. Use less memory than dfs.\n",
        "\\n Depth-Limited search (variant of dfs)  which a depth limit l, to keep dfs from wandering down an infinite path, treat all nodes at depth l as if they had no successors.\n",
        "\\n Interative deepening search picking a good value for l by trying all values until either a solution is found or the depth-limited search returns the failure value rather than the cutoff value. \n",
        "\\n Bidirectional search simulataneously searches forward from the initial state and backwards from the goal states to see the two searches will meet.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" BFS: Complete, Time:b^d, Space: b^d, Optimal \n",
        "\\n Uniform-Cost: Complete, Time:b^d, Space: b^d, Optimal \n",
        "\\n DFS: Incomplete, Time:b^m, Space:bm, Not Optimal\n",
        "\\n Depth-Limited:Incomplete, Time:b^l, Space:bl, Not Optimal\n",
        "\\n Iterative deepening: Complete, Time:b^d, Space: bd, Optimal\n",
        "\\n Biderectional: Complete, Time: O(b^{d/2}), Space:b^{d/2}, Optimal )\n",
        "\\n Uniform-cost search: complete, f(n) = g(n), Time: b^{1+c*/e}> b^d, optimal [similar to BFS] \n",
        "\\n Complete Algorithm: BFS, Uniform-Cost Search, Iterative Deepening Search, Bidirectional Search\n",
        "\\n The space complexity of DFS is O(bm), while for ID is O(bd). m is the maximum depth of search tree, while d is the depth of the shallowest solution (m >= d).\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "    \"state space\":\"a set of possible states that the environment can be in \",\n",
        "    \"initial state\":\"the agent starts in this state\", \"path\":\"a sequence of actions\",\"solution\":\"a path from the initial state to a goal state\",\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"planning agents\":\"agent that use factored or structure representations of states\",\n",
        "\"search problem\": \"the process of an agent looking for sequence actions to take that reaches the goal\", \n",
        "\"uniform-cost search\": \"= Dijkstra's algorithm, the evaluation function = the cost of path from root -> current node\", \n",
        "\"heuristic function\":\"estimates the cost of the cheapest path from the state at current node to goal node\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5897e518-764b-4281-aa22-c68f90a3ad45"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Agent's problem solving process:goal formulation, problem formulation, search execution.\n A search a problem has state space, initial state, goal states, actions, transition model, action cost function.\n\n optimal solution has the lowest path cost among all solutions. \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problem is intended to illustrate or exercise various problem-solving methods. A real-world problem is a solution that people actually use and the formulation is idiosyncratic not standardized. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search method is uniformed if it only has access to the problem definition. \n\n A search method is informed if it has access to the problem definition and heuristic function h(n).\n\n Best-first search is choose a node with minimum value of some evaluation function.\n\n 4 ways to evaluate algorithm's performace: completeness, cost optimality, time complexity, space complexity. \n\n A search algorithm is complete if the algorithm is guaranteed to find a solution if there is one and to correctly report failure when there is not.\n\n a search algorithm is optimal if it find a solution with the lowest path cost.\n\n a graph search checks for redundant paths (it does'n waste time on examining redundant paths, thus it runs quicker), use more memory becasuse it store what states have been reached and what paths are redundant.\n\n a tree search doesn't check for redundant paths, use less space than graph search, slower than graph search\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth-first search is expand the root node first, then expand all the successors of the root node, then their successors. \n\n Uniform-cost soearch use best-first search, the evaluation function is the cost of the path from the root to the current node. It's complete and cost-optimal. \n\n Depth-first search expands the deepest node in the frontier first.\n\n Backtracking search [robotic assembly] (variant of dfs) only one successor is generated at a time, each partially expanded node remembers which successor to generate next. Use less memory than dfs.\n\n Depth-Limited search (variant of dfs)  which a depth limit l, to keep dfs from wandering down an infinite path, treat all nodes at depth l as if they had no successors.\n\n Interative deepening search picking a good value for l by trying all values until either a solution is found or the depth-limited search returns the failure value rather than the cutoff value. \n\n Bidirectional search simulataneously searches forward from the initial state and backwards from the goal states to see the two searches will meet.\n\n## Module 3 Lecture Notes\n BFS: Complete, Time:b^d, Space: b^d, Optimal \n\n Uniform-Cost: Complete, Time:b^d, Space: b^d, Optimal \n\n DFS: Incomplete, Time:b^m, Space:bm, Not Optimal\n\n Depth-Limited:Incomplete, Time:b^l, Space:bl, Not Optimal\n\n Iterative deepening: Complete, Time:b^d, Space: bd, Optimal\n\n Biderectional: Complete, Time: O(b^{d/2}), Space:b^{d/2}, Optimal )\n\n Uniform-cost search: complete, f(n) = g(n), Time: b^{1+c*/e}> b^d, optimal [similar to BFS] \n\n Complete Algorithm: BFS, Uniform-Cost Search, Iterative Deepening Search, Bidirectional Search\n\n The space complexity of DFS is O(bm), while for ID is O(bd). m is the maximum depth of search tree, while d is the depth of the shallowest solution (m >= d).\n  \n\n## Module 3 Definitions\n* **State space** - a set of possible states that the environment can be in \n* **Initial state** - the agent starts in this state\n* **Path** - a sequence of actions\n* **Solution** - a path from the initial state to a goal state\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Planning agents** - agent that use factored or structure representations of states\n* **Search problem** - the process of an agent looking for sequence actions to take that reaches the goal\n* **Uniform-cost search** - = Dijkstra's algorithm, the evaluation function = the cost of path from root -> current node\n* **Heuristic function** - estimates the cost of the cheapest path from the state at current node to goal node\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Greedy best-first search (best-first search) expands the node with the lowest h(n) value first, which is the node that likely closest to the goal, and could lead to a solution quiakly.\n",
        "\\n A* search (best-first search) expands nodes with minimum f(n) = g(n)+h(n), where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of the shortest path from n to a goal state (consistent heuristic is also admissible)\n",
        "\\n A* search: Larger heuristic could better estimate the actual cost to reach the goal and thus more accurate. If both are admissible heuristic, we always have h2(n)>= h1(n), h2(n) is more accurate than h1(n).\n",
        " \\n Iterative-deepening A* search is A* without the requirement to keep all reached states in memory, at a cost of visting some states multiple times. \"\"\"\n",
        "chapter3_6 = \"\"\" Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when 2 frontier meet.\n",
        "\\n RBFS (Recursive best-first search) and SMA* () simplified memory-bounded A* are robust optimal search glgorithms that use very little memory, given enough time, they can solve problems for which A* runs out of memory.\n",
        "\\n Weighted A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Greedy best-first: Complete(only in finite state spaces), f(n) = h(n), O(|V|) if good heuristic could be O(bm.) Not optimal Find solution without expand a node not on the solution path.\\n\n",
        " A*: Complete, O(b^d), f(n) = g(n)+h(n) = estimated cost of the best path that continues from n to a goal, cost optimal(If h(n) is admissible). \n",
        " \\n Weighted A * search is the heuristic value weighted more heavily, f(n) = g(n) + W x h(n), for some W > 1. \n",
        "\\n Priority queue: Greedy Best-First Search, Uniform Cost Search, A* Search (these 3 are informed search).\n",
        "\\n FIFO queue: Breadth-First Search\n",
        "\\n A well-designed heuristic would have a value of branching factor close to 1. Smaller branching factor means more nodes will be pruned and make the algorithm more efficient.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Greedy best-first search\" : \"expand node with lowest h(n) value first (node that closest to the goal). f(n) = h(n)\",    \n",
        "\"admissible heuristic\":\"= optimistic, never overestimates the cost to reach a goal\",\n",
        "\"consistency\": \"for every node n and every successor n^ of n generated by an action a, h(n) <= c(n, a, n^)+h(n^)\",\n",
        "\"Monotonic\":\"the path cost always increases as go along a path (extend a path), because action costs are always positive.\",\n",
        "\"Iterative-deepening A* (IDA*)\": \"A* does not keep all reached states in memory, but visit some states multiple times \",\n",
        "\"Recursive best-first search(RBFS)\" : \"keep track of the value of best alternative path from any ancestor of current, if current node exceeds the limit, back.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 802
        },
        "outputId": "ab277630-8aa2-489e-ad39-b268d1369d59"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Recursive best-first search(RBFS)' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search (best-first search) expands the node with the lowest h(n) value first, which is the node that likely closest to the goal, and could lead to a solution quiakly.\n\n A* search (best-first search) expands nodes with minimum f(n) = g(n)+h(n), where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of the shortest path from n to a goal state (consistent heuristic is also admissible)\n\n A* search: Larger heuristic could better estimate the actual cost to reach the goal and thus more accurate. If both are admissible heuristic, we always have h2(n)>= h1(n), h2(n) is more accurate than h1(n).\n \n Iterative-deepening A* search is A* without the requirement to keep all reached states in memory, at a cost of visting some states multiple times. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when 2 frontier meet.\n\n RBFS (Recursive best-first search) and SMA* () simplified memory-bounded A* are robust optimal search glgorithms that use very little memory, given enough time, they can solve problems for which A* runs out of memory.\n\n Weighted A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n\n## Module 4 Lecture Notes\n Greedy best-first: Complete(only in finite state spaces), f(n) = h(n), O(|V|) if good heuristic could be O(bm.) Not optimal Find solution without expand a node not on the solution path.\n\n A*: Complete, O(b^d), f(n) = g(n)+h(n) = estimated cost of the best path that continues from n to a goal, cost optimal(If h(n) is admissible). \n \n Weighted A * search is the heuristic value weighted more heavily, f(n) = g(n) + W x h(n), for some W > 1. \n\n Priority queue: Greedy Best-First Search, Uniform Cost Search, A* Search (these 3 are informed search).\n\n FIFO queue: Breadth-First Search\n\n A well-designed heuristic would have a value of branching factor close to 1. Smaller branching factor means more nodes will be pruned and make the algorithm more efficient.\n \n\n## Module 4 Definitions\n* **Greedy best-first search** - expand node with lowest h(n) value first (node that closest to the goal). f(n) = h(n)\n* **Admissible heuristic** - = optimistic, never overestimates the cost to reach a goal\n* **Consistency** - for every node n and every successor n^ of n generated by an action a, h(n) <= c(n, a, n^)+h(n^)\n* **Monotonic** - the path cost always increases as go along a path (extend a path), because action costs are always positive.\n* **Iterative-deepening a* (ida*)** - A* does not keep all reached states in memory, but visit some states multiple times \n* **Recursive best-first search(rbfs)** - keep track of the value of best alternative path from any ancestor of current, if current node exceeds the limit, back.\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 = \"\"\" perfect information = fully observable. zero-sum games means what is good for one player is as bad for the other, no win-win. Mover = action, position = state.\n",
        "\\n A game has initial state, TO-move(which player to move in the state), actions (set of legal moves), Result (transition model), is-terminal (terminal test), utility. \n",
        "\\n Adversarial search problems are multi-agent.\"\"\"\n",
        "chapter5_2 = \"\"\" Minimax search is for game with multiple outcome scores. Evalues nodes in the same order as Depth First search, it solves perfect information zero-sum games. \n",
        "\\n minimax value is the utility  (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game.\n",
        "\\n The minimax decision maximizes the utility under the assumption that the opponent plays perfectly. \n",
        "\\n The value of a node = optimal value of its children. For MAX, it's the highest value, for MIN, it's the lowest value.\n",
        "\\n Alpha-Beta's effectiveness depend on the order in which successor nodes are examined, which the order affects the nodes to be pruned.\"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Game of chance can be handled by expectiminimax \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" The principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes the agent's expected utility.\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" \"Probility Theory is what an agent should believe on the basis of evidence. \n",
        "\\n Utility Theory is what an agent wants.\n",
        "\\n Decision theory is a normative theory, it descirbes how a rational agent should act. Descriptive theory describes how actual agents [ex. Human] really do act. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"Minimax: Time: O(B^m), b = number of legal moves at each node, m= maximum depth of the tree. \n",
        "\\n MAX can't search for a single sequence of events from an initial state to a winning terminal state before the game begins, because the best possible move made by MAX at any point in time will depend on the previous move made by MIN.\n",
        "\\n if a game where the outcome of a player making a mover is deterministic, Minimax and Expectiminimax will always produce  optimal solution.\n",
        "\\n A minimax algorithm with Alpha Beta Pruning will take approximately the same amount of time for finding solutions on the small game as that withou Alpha Beta pruning. \n",
        "\\n the limitation of Alpha Beta Pruning is the assumption that the leaf evaluations are randomly distributed across the last layer of the tree.\n",
        "\\n When the move is deterministic, Expectiminimax will also choose the optimal movement (No chance to take a random movement) just like minimax \n",
        "\\n Evaluate MAX node: if V' > V, V = V', if V' >= Beta, return V, if V' > Alpha, alpha = V'.\n",
        "\\n Evaluate Min node: if V' < V, V = V', if V' <= Alpha, return V, if V' < Beta, beta = V'. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Stochastic Games\" : \"chnace nodes denoting the probabilities associated with each action and expecti-minimax values are included in minimax tree\",   \n",
        "\"Evaluation function\": \"Return an estimate of the expected utility of the game from a given position.\",\n",
        "\"Transition model\":\"defines the state resulting from taking action a in the state s\" ,\n",
        "\"terminal test\":\"is true when the game is over.\",\n",
        "\"terminal state\":\"states when the game has ended\",\n",
        "\"utility function (objective function/payoff function)\": \"defines the final numeric value to player p when the game ends in terminal state s. \",\n",
        "\"Alpha-beta prunning\":\"it prunes branches of the tree that can have no effect on the final evaluation\",\n",
        "\"Forward prunning\":\"it prunes moves that appear to be poor moves, but might possibly be good ones\",\n",
        "\"rational agent\":\"a system that makes decisions by considering all possible actions and choosing the one that laeds to the best expected outcome\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1e2aaa24-25a7-40c5-9e51-5a5011330889"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'rational agent' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n perfect information = fully observable. zero-sum games means what is good for one player is as bad for the other, no win-win. Mover = action, position = state.\n\n A game has initial state, TO-move(which player to move in the state), actions (set of legal moves), Result (transition model), is-terminal (terminal test), utility. \n\n Adversarial search problems are multi-agent.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax search is for game with multiple outcome scores. Evalues nodes in the same order as Depth First search, it solves perfect information zero-sum games. \n\n minimax value is the utility  (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game.\n\n The minimax decision maximizes the utility under the assumption that the opponent plays perfectly. \n\n The value of a node = optimal value of its children. For MAX, it's the highest value, for MIN, it's the lowest value.\n\n Alpha-Beta's effectiveness depend on the order in which successor nodes are examined, which the order affects the nodes to be pruned.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Game of chance can be handled by expectiminimax \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes the agent's expected utility.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n \"Probility Theory is what an agent should believe on the basis of evidence. \n\n Utility Theory is what an agent wants.\n\n Decision theory is a normative theory, it descirbes how a rational agent should act. Descriptive theory describes how actual agents [ex. Human] really do act. \n\n## Module 5 Lecture Notes\nMinimax: Time: O(B^m), b = number of legal moves at each node, m= maximum depth of the tree. \n\n MAX can't search for a single sequence of events from an initial state to a winning terminal state before the game begins, because the best possible move made by MAX at any point in time will depend on the previous move made by MIN.\n\n if a game where the outcome of a player making a mover is deterministic, Minimax and Expectiminimax will always produce  optimal solution.\n\n A minimax algorithm with Alpha Beta Pruning will take approximately the same amount of time for finding solutions on the small game as that withou Alpha Beta pruning. \n\n the limitation of Alpha Beta Pruning is the assumption that the leaf evaluations are randomly distributed across the last layer of the tree.\n\n When the move is deterministic, Expectiminimax will also choose the optimal movement (No chance to take a random movement) just like minimax \n\n Evaluate MAX node: if V' > V, V = V', if V' >= Beta, return V, if V' > Alpha, alpha = V'.\n\n Evaluate Min node: if V' < V, V = V', if V' <= Alpha, return V, if V' < Beta, beta = V'. \n\n## Module 5 Definitions\n* **Stochastic games** - chnace nodes denoting the probabilities associated with each action and expecti-minimax values are included in minimax tree\n* **Evaluation function** - Return an estimate of the expected utility of the game from a given position.\n* **Transition model** - defines the state resulting from taking action a in the state s\n* **Terminal test** - is true when the game is over.\n* **Terminal state** - states when the game has ended\n* **Utility function (objective function/payoff function)** - defines the final numeric value to player p when the game ends in terminal state s. \n* **Alpha-beta prunning** - it prunes branches of the tree that can have no effect on the final evaluation\n* **Forward prunning** - it prunes moves that appear to be poor moves, but might possibly be good ones\n* **Rational agent** - a system that makes decisions by considering all possible actions and choosing the one that laeds to the best expected outcome\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 = \"\"\" CSP example: Map coloring, Job-shop scheduling, Cryptarithmetic puzzles, Sudoku. CSP represent the conditions for a solution with a set of constraints on the variables. \n",
        "\\n It reprsents a state with a set of variable/value pairs.\"\"\"\n",
        "chapter6_2 = \"\"\" The key idea behind inference in CSP is enforcing k-consistency. \n",
        "\\n CSP algorithm can generate successors by choosing a new variable assignment, \n",
        "\\n or Constraint Propagation which is a specific type of inference using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable. \n",
        "\\n A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints.\n",
        "\\n A variable in CSP is arc-consistent if every value in its domain satisfies the variable's binary constraints. \n",
        "\\n AC3 enforcing arc consistency (it cannot solve all CSP) to enforce the adherence to constraints between two variables, or binary constraints. \n",
        "\\n Process of AC3:Place all the arcs in a queue, pop arcs. For each arc, remove inconsistent values. If we change the value of a node, add its arcs to the queue. Terminate when the queue is empty.\n",
        "\\n Path consistency tightens the binary constraints by using implicit constriants that are inferred by loooking at triples of variables.\n",
        "\\n K-consistency is for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n",
        "\\n Strongly k-consistent is if the CSP is k-consistent, k-1 consistent,...,1-consistent.\n",
        "\\n Bonds-consistent is if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y. \n",
        "\\n In search problems, states are black boxes with a transition model to move between boxes. In CSP, the agent can see inside the states and move between states accordingly.\"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking is a form of depth first search commonly used for solving CSP. It occurs when no legal assignment can be found for a variable. \n",
        "\\n Forward checking: whenever a variable X is assigned, we establish arc consistency for x. For each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X.\n",
        "\\n Maintaining Arc Consistency (MAC) recursively propogrates constraints (but forward checking doesn't). MAC is a way of interleaving search and inference. AC-3 is pure inference\"\"\"\n",
        "chapter6_4 = \"\"\" Min-conflicts heuristic select the value that results in the minimum number of conflicts iwht other variables \"\"\"\n",
        "chapter6_5 = \"\"\" Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Solving an arbitrary CSP takes exponential time in the number of variables. \n",
        "\\n Solvoing a tree-structured CSP takes linear time in the number of variables.\n",
        "\\n Cutset conditioning is used to reduce a general CSP to a tree structured CSP. But in general, it is not always more efficient thant solving a CSP directly. \n",
        "\\n It is efficient if a small cutset can be found. It is more efficient thant Tree decomposition.\n",
        "\\n It can be executed in linear memory, while tree decomposition requires memory exponential in the tree width w.\n",
        "\\n Tree decomposition technique transform the CSP into a tree of subproblems. \n",
        "\\n Efficient if the tree width of the constraint graph is small. It is more time efficient thant cutset conditioning.\n",
        "\\n Path consistency: k-consistency for k = 3, Arc consistency: k-consistency for k = 2, Node consistency: k-consistency for k = 1. \n",
        "\\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory. It is widely applicable in domains including real numbered-values and integer values with no upper bounds.  But there is not always a known sub-exponential algorithm to find the correct solution. \n",
        "\\n CSP are good fit for manufacturing process which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step. \n",
        "\\n Minimax is a better algorithm for chess.  \n",
        "\\n A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\n",
        "\\n CSP algorithms do not provide any guarantees about the cost. However, if the problem is solvable, then the algorithm will return a solution that satisfies the given constraints.\n",
        "\\n A naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time. There is no guarantee that AC3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution.\n",
        "\\n CSPs allow for a mixture of search (expanding a node to visit its successors) and inference, where the current choice of nodes and values are reduced by propagating constraints.\n",
        "\\n In arc consistency checks, we check all values in the tail and remove any that are not allowed by the head.  We always check all values on the tail, but we can stop checking values on the head when we first see a value that allows the value that we’re checking on the tail.\n",
        "\\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory,\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Constraint Satisfaction Problem (CSP)\" : \"a problem is solved when each variable has a value that satisfies all the constriants on the variable.\",    \n",
        "\"Complete assignment\":\"every variable is assigned a value\",\n",
        "\"CSP solution\":\"consistent complete assignment\",\n",
        "\"partial assignment\":\"leaves some variables unassigned\",\n",
        "\"partial solution\":\"partial assignment is consistent\",\n",
        "\"unary constraint\":\"it restricts the value of a single variable\",\n",
        "\"binary constraint\": \"it restricts the value of two variable\",\n",
        "\"binary CSP\":\"one with only unary and binary constraints\",\n",
        "\"global constraint\":\"a constraint involving an arbitrary number of variables\",\n",
        "\"MRV heuristic\":\"Minimum Remaining Value, chooses the variable with the fewest 'legal' value\",\n",
        "\"Degree heuristic\": \"chooses the variable with the largest number of constraints\",\n",
        "\"Least constraining value heuristic\":\"heuristic chooses the value that rules out the fewest values for neighboring variables\",\n",
        "\"Constraint learning\":\"records the conflicts as they are encountered in the search in order to aviod the same conflict later\",\n",
        "\"Resource Constraint\":\"Atmost constraint\",\n",
        "\"Chronological Backtracking\":\"When a branch of the search fails, it back up to the preceding variable and try a different value for it. (revisit the most recent decision point)\",\n",
        "\"Backjumping\":\"backtracks to the most recent assignment in the conflict set\",\n",
        "\"Inference (in CSP)\":\"Using problem constraints to reduce the number of legal values on variables.\",\n",
        "\"Declarative programming\":\"Representing a problem formally (without regards to implementation) as a CSP problem, defined by expressing logical formulas that should hold\",\n",
        "\"Imperative programming\":\"a series of statements that should be carried out\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "19bedede-b040-4ed3-ab9b-a6f344034aac"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Chronological Backtracking' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP example: Map coloring, Job-shop scheduling, Cryptarithmetic puzzles, Sudoku. CSP represent the conditions for a solution with a set of constraints on the variables. \n\n It reprsents a state with a set of variable/value pairs.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n The key idea behind inference in CSP is enforcing k-consistency. \n\n CSP algorithm can generate successors by choosing a new variable assignment, \n\n or Constraint Propagation which is a specific type of inference using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable. \n\n A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints.\n\n A variable in CSP is arc-consistent if every value in its domain satisfies the variable's binary constraints. \n\n AC3 enforcing arc consistency (it cannot solve all CSP) to enforce the adherence to constraints between two variables, or binary constraints. \n\n Process of AC3:Place all the arcs in a queue, pop arcs. For each arc, remove inconsistent values. If we change the value of a node, add its arcs to the queue. Terminate when the queue is empty.\n\n Path consistency tightens the binary constraints by using implicit constriants that are inferred by loooking at triples of variables.\n\n K-consistency is for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\n Strongly k-consistent is if the CSP is k-consistent, k-1 consistent,...,1-consistent.\n\n Bonds-consistent is if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y. \n\n In search problems, states are black boxes with a transition model to move between boxes. In CSP, the agent can see inside the states and move between states accordingly.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking is a form of depth first search commonly used for solving CSP. It occurs when no legal assignment can be found for a variable. \n\n Forward checking: whenever a variable X is assigned, we establish arc consistency for x. For each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X.\n\n Maintaining Arc Consistency (MAC) recursively propogrates constraints (but forward checking doesn't). MAC is a way of interleaving search and inference. AC-3 is pure inference\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Min-conflicts heuristic select the value that results in the minimum number of conflicts iwht other variables \n\n## AIMA Chapter 6.5 The Structure of Problems\n Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time. \n\n## Module 6 Lecture Notes\n Solving an arbitrary CSP takes exponential time in the number of variables. \n\n Solvoing a tree-structured CSP takes linear time in the number of variables.\n\n Cutset conditioning is used to reduce a general CSP to a tree structured CSP. But in general, it is not always more efficient thant solving a CSP directly. \n\n It is efficient if a small cutset can be found. It is more efficient thant Tree decomposition.\n\n It can be executed in linear memory, while tree decomposition requires memory exponential in the tree width w.\n\n Tree decomposition technique transform the CSP into a tree of subproblems. \n\n Efficient if the tree width of the constraint graph is small. It is more time efficient thant cutset conditioning.\n\n Path consistency: k-consistency for k = 3, Arc consistency: k-consistency for k = 2, Node consistency: k-consistency for k = 1. \n\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory. It is widely applicable in domains including real numbered-values and integer values with no upper bounds.  But there is not always a known sub-exponential algorithm to find the correct solution. \n\n CSP are good fit for manufacturing process which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step. \n\n Minimax is a better algorithm for chess.  \n\n A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\n\n CSP algorithms do not provide any guarantees about the cost. However, if the problem is solvable, then the algorithm will return a solution that satisfies the given constraints.\n\n A naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time. There is no guarantee that AC3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution.\n\n CSPs allow for a mixture of search (expanding a node to visit its successors) and inference, where the current choice of nodes and values are reduced by propagating constraints.\n\n In arc consistency checks, we check all values in the tail and remove any that are not allowed by the head.  We always check all values on the tail, but we can stop checking values on the head when we first see a value that allows the value that we’re checking on the tail.\n\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory,\n\n## Module 6 Definitions\n* **Constraint satisfaction problem (csp)** - a problem is solved when each variable has a value that satisfies all the constriants on the variable.\n* **Complete assignment** - every variable is assigned a value\n* **Csp solution** - consistent complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment is consistent\n* **Unary constraint** - it restricts the value of a single variable\n* **Binary constraint** - it restricts the value of two variable\n* **Binary csp** - one with only unary and binary constraints\n* **Global constraint** - a constraint involving an arbitrary number of variables\n* **Mrv heuristic** - Minimum Remaining Value, chooses the variable with the fewest 'legal' value\n* **Degree heuristic** - chooses the variable with the largest number of constraints\n* **Least constraining value heuristic** - heuristic chooses the value that rules out the fewest values for neighboring variables\n* **Constraint learning** - records the conflicts as they are encountered in the search in order to aviod the same conflict later\n* **Resource constraint** - Atmost constraint\n* **Chronological backtracking** - When a branch of the search fails, it back up to the preceding variable and try a different value for it. (revisit the most recent decision point)\n* **Backjumping** - backtracks to the most recent assignment in the conflict set\n* **Inference (in csp)** - Using problem constraints to reduce the number of legal values on variables.\n* **Declarative programming** - Representing a problem formally (without regards to implementation) as a CSP problem, defined by expressing logical formulas that should hold\n* **Imperative programming** - a series of statements that should be carried out\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 = \"\"\" Intelligent agents need knowledge about the world in order to reach good decisions. Knowledge within agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" convert to CNF (Conjunctive Normal Form): \n",
        "\\n 1. eliminate <=> replace A <=> B with (a => B) ^ (b => a)\n",
        "\\n 2. Eliminate =>, replace a=>b with -| A V B\n",
        "\\n 3. move -| inward. such as: -|(-|a)= a, -|(a ^ b) = (-|a v -|b),  -|(a v b) = (-|a ^ -|b)\n",
        "\\n distributing V over ^ whenever possible. Such as (a^b)vc = (avc)^(bvc)\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Sound inference algorithms derive only sentences that are entailed. Complete algorithms derive all sentences that are entailed \n",
        "\\n (A ∧ B) ⇔ (C ⋁ D)\n",
        "\\n ((A ∧ B) ⇒ (C ⋁ D)) ∧ ((C ⋁ D) ⇒ (A ∧ B))    (biconditional elimination)\n",
        "\\n (-(A ∧ B) ⋁ (C ⋁ D)) ∧ (-(C ⋁ D) ⋁ (A ∧ B))    (implication elimination)\n",
        "\\n ((-A ⋁ -B) ⋁ (C ⋁ D)) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (DeMorgan x2)\n",
        "\\n (-A ⋁ -B ⋁ C ⋁ D) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (Associativity of ⋁)\n",
        "\\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ∧ -D) ⋁ A) ∧ ((-C ∧ -D) ⋁ B))    (Distributivity of ⋁ over ∧)\n",
        "\\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ⋁ A) ∧ (-D ⋁ A)) ∧ ((-C ⋁ B) ∧ (-D ⋁ B)))    (Distributivity of ⋁ over ∧)\n",
        "\\n CNF = (-A ⋁ -B ⋁ C ⋁ D) ∧ (-C ⋁ A) ∧ (-D ⋁ A) ∧ (-C ⋁ B) ∧ (-D ⋁ B)    (Associativity of ∧)\n",
        "\\n Sensor models can be written in logical form for partially observable environments and a logical agent can maintain a belief state.\n",
        "\\Wampas World task environment is partially observable\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "    \"knowledge base agent\":\"initialize a knowledge base with some background knowledge, needs to tell the knowledge base what it perceives at the begining of programming calls.\",\n",
        "\"declarative approach\" : \"tell sentences one by one until the agent knows how to operate\",  \n",
        "\"procedural approach\" : \"encodes ideal behaviors directly using program code\",  \n",
        "\"syntax\":\"defines a representation language, specifies the structure of sentences\",\n",
        "\"semantics\":\"defines the truth of each sentence in each possible world or model\",\n",
        "\"inference\":\"the process of deriving new sentences from old ones.\",\n",
        "\"Inference Rule\":\"patterns of sound inference that can be used to find proofs.\",\n",
        "\"Propositional logic\":\"a simple language consisting of proposition symbols and logical connectives, when propositions that are known to be true/false/completely unknown.\",\n",
        "\"CNF\":\"can be exponentially longer than the simplest representation of a logical formula.\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "bf642604-1688-4e9f-d7b7-db2d529f433b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'knowledge base agent' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Intelligent agents need knowledge about the world in order to reach good decisions. Knowledge within agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\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 convert to CNF (Conjunctive Normal Form): \n\n 1. eliminate <=> replace A <=> B with (a => B) ^ (b => a)\n\n 2. Eliminate =>, replace a=>b with -| A V B\n\n 3. move -| inward. such as: -|(-|a)= a, -|(a ^ b) = (-|a v -|b),  -|(a v b) = (-|a ^ -|b)\n\n distributing V over ^ whenever possible. Such as (a^b)vc = (avc)^(bvc)\n \n\n## Module 7 Lecture Notes\nSound inference algorithms derive only sentences that are entailed. Complete algorithms derive all sentences that are entailed \n\n (A ∧ B) ⇔ (C ⋁ D)\n\n ((A ∧ B) ⇒ (C ⋁ D)) ∧ ((C ⋁ D) ⇒ (A ∧ B))    (biconditional elimination)\n\n (-(A ∧ B) ⋁ (C ⋁ D)) ∧ (-(C ⋁ D) ⋁ (A ∧ B))    (implication elimination)\n\n ((-A ⋁ -B) ⋁ (C ⋁ D)) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (DeMorgan x2)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (Associativity of ⋁)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ∧ -D) ⋁ A) ∧ ((-C ∧ -D) ⋁ B))    (Distributivity of ⋁ over ∧)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ⋁ A) ∧ (-D ⋁ A)) ∧ ((-C ⋁ B) ∧ (-D ⋁ B)))    (Distributivity of ⋁ over ∧)\n\n CNF = (-A ⋁ -B ⋁ C ⋁ D) ∧ (-C ⋁ A) ∧ (-D ⋁ A) ∧ (-C ⋁ B) ∧ (-D ⋁ B)    (Associativity of ∧)\n\n Sensor models can be written in logical form for partially observable environments and a logical agent can maintain a belief state.\n\\Wampas World task environment is partially observable\n\n## Module 7 Definitions\n* **Knowledge base agent** - initialize a knowledge base with some background knowledge, needs to tell the knowledge base what it perceives at the begining of programming calls.\n* **Declarative approach** - tell sentences one by one until the agent knows how to operate\n* **Procedural approach** - encodes ideal behaviors directly using program code\n* **Syntax** - defines a representation language, specifies the structure of sentences\n* **Semantics** - defines the truth of each sentence in each possible world or model\n* **Inference** - the process of deriving new sentences from old ones.\n* **Inference rule** - patterns of sound inference that can be used to find proofs.\n* **Propositional logic** - a simple language consisting of proposition symbols and logical connectives, when propositions that are known to be true/false/completely unknown.\n* **Cnf** - can be exponentially longer than the simplest representation of a logical formula.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "bca516e4-4394-4f92-a004-8301bfd15310"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\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 Simple reflex agent operates best in environents that are fully observable, which allows the agent to know more useful information from the environment and thus make optimal actions.\nIt reacts to the immediate percept and uses rules to choose an action. \n\n A simple reflex performs actions based on a current situation. When something happens in the environment of a simple reflex agent, the agent quickly scans its knowledge base for how to respond to the situation at-hand based on pre-determined rules. \n \n Agent: Touchless faucets, thermostat, pet hamster\n \n Agent's choice of action at at given instant depends on its perception.\n \n In some competitive environments, random behavior could be rational.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive environment through sensors and act in an environment through actuators\n* **Rational agent** - act to get best outcome or best expected outcome(uncertain), it maximize expected performance, not guarantee optimal\n* **Perfection agent** - maximizes actual performance\n* **Simple reflex agent** - select actions based on current percept not previous percept\n* **Agent function** - maps a sequence of perceptions into action, implemented as the agent program, describe agent behavior\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n\n Python function could take unlimited arguments when you use **args \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 Agent's problem solving process:goal formulation, problem formulation, search execution.\n A search a problem has state space, initial state, goal states, actions, transition model, action cost function.\n\n optimal solution has the lowest path cost among all solutions. \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problem is intended to illustrate or exercise various problem-solving methods. A real-world problem is a solution that people actually use and the formulation is idiosyncratic not standardized. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search method is uniformed if it only has access to the problem definition. \n\n A search method is informed if it has access to the problem definition and heuristic function h(n).\n\n Best-first search is choose a node with minimum value of some evaluation function.\n\n 4 ways to evaluate algorithm's performace: completeness, cost optimality, time complexity, space complexity. \n\n A search algorithm is complete if the algorithm is guaranteed to find a solution if there is one and to correctly report failure when there is not.\n\n a search algorithm is optimal if it find a solution with the lowest path cost.\n\n a graph search checks for redundant paths (it does'n waste time on examining redundant paths, thus it runs quicker), use more memory becasuse it store what states have been reached and what paths are redundant.\n\n a tree search doesn't check for redundant paths, use less space than graph search, slower than graph search\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Breadth-first search is expand the root node first, then expand all the successors of the root node, then their successors. \n\n Uniform-cost soearch use best-first search, the evaluation function is the cost of the path from the root to the current node. It's complete and cost-optimal. \n\n Depth-first search expands the deepest node in the frontier first.\n\n Backtracking search [robotic assembly] (variant of dfs) only one successor is generated at a time, each partially expanded node remembers which successor to generate next. Use less memory than dfs.\n\n Depth-Limited search (variant of dfs)  which a depth limit l, to keep dfs from wandering down an infinite path, treat all nodes at depth l as if they had no successors.\n\n Interative deepening search picking a good value for l by trying all values until either a solution is found or the depth-limited search returns the failure value rather than the cutoff value. \n\n Bidirectional search simulataneously searches forward from the initial state and backwards from the goal states to see the two searches will meet.\n\n## Module 3 Lecture Notes\n BFS: Complete, Time:b^d, Space: b^d, Optimal \n\n Uniform-Cost: Complete, Time:b^d, Space: b^d, Optimal \n\n DFS: Incomplete, Time:b^m, Space:bm, Not Optimal\n\n Depth-Limited:Incomplete, Time:b^l, Space:bl, Not Optimal\n\n Iterative deepening: Complete, Time:b^d, Space: bd, Optimal\n\n Biderectional: Complete, Time: O(b^{d/2}), Space:b^{d/2}, Optimal )\n\n Uniform-cost search: complete, f(n) = g(n), Time: b^{1+c*/e}> b^d, optimal [similar to BFS] \n\n Complete Algorithm: BFS, Uniform-Cost Search, Iterative Deepening Search, Bidirectional Search\n\n The space complexity of DFS is O(bm), while for ID is O(bd). m is the maximum depth of search tree, while d is the depth of the shallowest solution (m >= d).\n  \n\n## Module 3 Definitions\n* **State space** - a set of possible states that the environment can be in \n* **Initial state** - the agent starts in this state\n* **Path** - a sequence of actions\n* **Solution** - a path from the initial state to a goal state\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Planning agents** - agent that use factored or structure representations of states\n* **Search problem** - the process of an agent looking for sequence actions to take that reaches the goal\n* **Uniform-cost search** - = Dijkstra's algorithm, the evaluation function = the cost of path from root -> current node\n* **Heuristic function** - estimates the cost of the cheapest path from the state at current node to goal node\n\n\n## WARNING: Your definition of 'Recursive best-first search(RBFS)' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search (best-first search) expands the node with the lowest h(n) value first, which is the node that likely closest to the goal, and could lead to a solution quiakly.\n\n A* search (best-first search) expands nodes with minimum f(n) = g(n)+h(n), where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of the shortest path from n to a goal state (consistent heuristic is also admissible)\n\n A* search: Larger heuristic could better estimate the actual cost to reach the goal and thus more accurate. If both are admissible heuristic, we always have h2(n)>= h1(n), h2(n) is more accurate than h1(n).\n \n Iterative-deepening A* search is A* without the requirement to keep all reached states in memory, at a cost of visting some states multiple times. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when 2 frontier meet.\n\n RBFS (Recursive best-first search) and SMA* () simplified memory-bounded A* are robust optimal search glgorithms that use very little memory, given enough time, they can solve problems for which A* runs out of memory.\n\n Weighted A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n\n## Module 4 Lecture Notes\n Greedy best-first: Complete(only in finite state spaces), f(n) = h(n), O(|V|) if good heuristic could be O(bm.) Not optimal Find solution without expand a node not on the solution path.\n\n A*: Complete, O(b^d), f(n) = g(n)+h(n) = estimated cost of the best path that continues from n to a goal, cost optimal(If h(n) is admissible). \n \n Weighted A * search is the heuristic value weighted more heavily, f(n) = g(n) + W x h(n), for some W > 1. \n\n Priority queue: Greedy Best-First Search, Uniform Cost Search, A* Search (these 3 are informed search).\n\n FIFO queue: Breadth-First Search\n\n A well-designed heuristic would have a value of branching factor close to 1. Smaller branching factor means more nodes will be pruned and make the algorithm more efficient.\n \n\n## Module 4 Definitions\n* **Greedy best-first search** - expand node with lowest h(n) value first (node that closest to the goal). f(n) = h(n)\n* **Admissible heuristic** - = optimistic, never overestimates the cost to reach a goal\n* **Consistency** - for every node n and every successor n^ of n generated by an action a, h(n) <= c(n, a, n^)+h(n^)\n* **Monotonic** - the path cost always increases as go along a path (extend a path), because action costs are always positive.\n* **Iterative-deepening a* (ida*)** - A* does not keep all reached states in memory, but visit some states multiple times \n* **Recursive best-first search(rbfs)** - keep track of the value of best alternative path from any ancestor of current, if current node exceeds the limit, back.\n\n\n## WARNING: Your definition of 'rational agent' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n perfect information = fully observable. zero-sum games means what is good for one player is as bad for the other, no win-win. Mover = action, position = state.\n\n A game has initial state, TO-move(which player to move in the state), actions (set of legal moves), Result (transition model), is-terminal (terminal test), utility. \n\n Adversarial search problems are multi-agent.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax search is for game with multiple outcome scores. Evalues nodes in the same order as Depth First search, it solves perfect information zero-sum games. \n\n minimax value is the utility  (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game.\n\n The minimax decision maximizes the utility under the assumption that the opponent plays perfectly. \n\n The value of a node = optimal value of its children. For MAX, it's the highest value, for MIN, it's the lowest value.\n\n Alpha-Beta's effectiveness depend on the order in which successor nodes are examined, which the order affects the nodes to be pruned.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Game of chance can be handled by expectiminimax \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes the agent's expected utility.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n \"Probility Theory is what an agent should believe on the basis of evidence. \n\n Utility Theory is what an agent wants.\n\n Decision theory is a normative theory, it descirbes how a rational agent should act. Descriptive theory describes how actual agents [ex. Human] really do act. \n\n## Module 5 Lecture Notes\nMinimax: Time: O(B^m), b = number of legal moves at each node, m= maximum depth of the tree. \n\n MAX can't search for a single sequence of events from an initial state to a winning terminal state before the game begins, because the best possible move made by MAX at any point in time will depend on the previous move made by MIN.\n\n if a game where the outcome of a player making a mover is deterministic, Minimax and Expectiminimax will always produce  optimal solution.\n\n A minimax algorithm with Alpha Beta Pruning will take approximately the same amount of time for finding solutions on the small game as that withou Alpha Beta pruning. \n\n the limitation of Alpha Beta Pruning is the assumption that the leaf evaluations are randomly distributed across the last layer of the tree.\n\n When the move is deterministic, Expectiminimax will also choose the optimal movement (No chance to take a random movement) just like minimax \n\n Evaluate MAX node: if V' > V, V = V', if V' >= Beta, return V, if V' > Alpha, alpha = V'.\n\n Evaluate Min node: if V' < V, V = V', if V' <= Alpha, return V, if V' < Beta, beta = V'. \n\n## Module 5 Definitions\n* **Stochastic games** - chnace nodes denoting the probabilities associated with each action and expecti-minimax values are included in minimax tree\n* **Evaluation function** - Return an estimate of the expected utility of the game from a given position.\n* **Transition model** - defines the state resulting from taking action a in the state s\n* **Terminal test** - is true when the game is over.\n* **Terminal state** - states when the game has ended\n* **Utility function (objective function/payoff function)** - defines the final numeric value to player p when the game ends in terminal state s. \n* **Alpha-beta prunning** - it prunes branches of the tree that can have no effect on the final evaluation\n* **Forward prunning** - it prunes moves that appear to be poor moves, but might possibly be good ones\n* **Rational agent** - a system that makes decisions by considering all possible actions and choosing the one that laeds to the best expected outcome\n\n\n## WARNING: Your definition of 'Chronological Backtracking' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP example: Map coloring, Job-shop scheduling, Cryptarithmetic puzzles, Sudoku. CSP represent the conditions for a solution with a set of constraints on the variables. \n\n It reprsents a state with a set of variable/value pairs.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n The key idea behind inference in CSP is enforcing k-consistency. \n\n CSP algorithm can generate successors by choosing a new variable assignment, \n\n or Constraint Propagation which is a specific type of inference using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable. \n\n A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints.\n\n A variable in CSP is arc-consistent if every value in its domain satisfies the variable's binary constraints. \n\n AC3 enforcing arc consistency (it cannot solve all CSP) to enforce the adherence to constraints between two variables, or binary constraints. \n\n Process of AC3:Place all the arcs in a queue, pop arcs. For each arc, remove inconsistent values. If we change the value of a node, add its arcs to the queue. Terminate when the queue is empty.\n\n Path consistency tightens the binary constraints by using implicit constriants that are inferred by loooking at triples of variables.\n\n K-consistency is for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\n Strongly k-consistent is if the CSP is k-consistent, k-1 consistent,...,1-consistent.\n\n Bonds-consistent is if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y. \n\n In search problems, states are black boxes with a transition model to move between boxes. In CSP, the agent can see inside the states and move between states accordingly.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking is a form of depth first search commonly used for solving CSP. It occurs when no legal assignment can be found for a variable. \n\n Forward checking: whenever a variable X is assigned, we establish arc consistency for x. For each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X.\n\n Maintaining Arc Consistency (MAC) recursively propogrates constraints (but forward checking doesn't). MAC is a way of interleaving search and inference. AC-3 is pure inference\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Min-conflicts heuristic select the value that results in the minimum number of conflicts iwht other variables \n\n## AIMA Chapter 6.5 The Structure of Problems\n Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time. \n\n## Module 6 Lecture Notes\n Solving an arbitrary CSP takes exponential time in the number of variables. \n\n Solvoing a tree-structured CSP takes linear time in the number of variables.\n\n Cutset conditioning is used to reduce a general CSP to a tree structured CSP. But in general, it is not always more efficient thant solving a CSP directly. \n\n It is efficient if a small cutset can be found. It is more efficient thant Tree decomposition.\n\n It can be executed in linear memory, while tree decomposition requires memory exponential in the tree width w.\n\n Tree decomposition technique transform the CSP into a tree of subproblems. \n\n Efficient if the tree width of the constraint graph is small. It is more time efficient thant cutset conditioning.\n\n Path consistency: k-consistency for k = 3, Arc consistency: k-consistency for k = 2, Node consistency: k-consistency for k = 1. \n\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory. It is widely applicable in domains including real numbered-values and integer values with no upper bounds.  But there is not always a known sub-exponential algorithm to find the correct solution. \n\n CSP are good fit for manufacturing process which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step. \n\n Minimax is a better algorithm for chess.  \n\n A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\n\n CSP algorithms do not provide any guarantees about the cost. However, if the problem is solvable, then the algorithm will return a solution that satisfies the given constraints.\n\n A naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time. There is no guarantee that AC3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution.\n\n CSPs allow for a mixture of search (expanding a node to visit its successors) and inference, where the current choice of nodes and values are reduced by propagating constraints.\n\n In arc consistency checks, we check all values in the tail and remove any that are not allowed by the head.  We always check all values on the tail, but we can stop checking values on the head when we first see a value that allows the value that we’re checking on the tail.\n\n Constraint satisfaction approaches cannot be solved in polynomial time on certain domains according to current theory,\n\n## Module 6 Definitions\n* **Constraint satisfaction problem (csp)** - a problem is solved when each variable has a value that satisfies all the constriants on the variable.\n* **Complete assignment** - every variable is assigned a value\n* **Csp solution** - consistent complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment is consistent\n* **Unary constraint** - it restricts the value of a single variable\n* **Binary constraint** - it restricts the value of two variable\n* **Binary csp** - one with only unary and binary constraints\n* **Global constraint** - a constraint involving an arbitrary number of variables\n* **Mrv heuristic** - Minimum Remaining Value, chooses the variable with the fewest 'legal' value\n* **Degree heuristic** - chooses the variable with the largest number of constraints\n* **Least constraining value heuristic** - heuristic chooses the value that rules out the fewest values for neighboring variables\n* **Constraint learning** - records the conflicts as they are encountered in the search in order to aviod the same conflict later\n* **Resource constraint** - Atmost constraint\n* **Chronological backtracking** - When a branch of the search fails, it back up to the preceding variable and try a different value for it. (revisit the most recent decision point)\n* **Backjumping** - backtracks to the most recent assignment in the conflict set\n* **Inference (in csp)** - Using problem constraints to reduce the number of legal values on variables.\n* **Declarative programming** - Representing a problem formally (without regards to implementation) as a CSP problem, defined by expressing logical formulas that should hold\n* **Imperative programming** - a series of statements that should be carried out\n\n\n## WARNING: Your definition of 'knowledge base agent' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Intelligent agents need knowledge about the world in order to reach good decisions. Knowledge within agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\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 convert to CNF (Conjunctive Normal Form): \n\n 1. eliminate <=> replace A <=> B with (a => B) ^ (b => a)\n\n 2. Eliminate =>, replace a=>b with -| A V B\n\n 3. move -| inward. such as: -|(-|a)= a, -|(a ^ b) = (-|a v -|b),  -|(a v b) = (-|a ^ -|b)\n\n distributing V over ^ whenever possible. Such as (a^b)vc = (avc)^(bvc)\n \n\n## Module 7 Lecture Notes\nSound inference algorithms derive only sentences that are entailed. Complete algorithms derive all sentences that are entailed \n\n (A ∧ B) ⇔ (C ⋁ D)\n\n ((A ∧ B) ⇒ (C ⋁ D)) ∧ ((C ⋁ D) ⇒ (A ∧ B))    (biconditional elimination)\n\n (-(A ∧ B) ⋁ (C ⋁ D)) ∧ (-(C ⋁ D) ⋁ (A ∧ B))    (implication elimination)\n\n ((-A ⋁ -B) ⋁ (C ⋁ D)) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (DeMorgan x2)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ ((-C ∧ -D) ⋁ (A ∧ B))    (Associativity of ⋁)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ∧ -D) ⋁ A) ∧ ((-C ∧ -D) ⋁ B))    (Distributivity of ⋁ over ∧)\n\n (-A ⋁ -B ⋁ C ⋁ D) ∧ (((-C ⋁ A) ∧ (-D ⋁ A)) ∧ ((-C ⋁ B) ∧ (-D ⋁ B)))    (Distributivity of ⋁ over ∧)\n\n CNF = (-A ⋁ -B ⋁ C ⋁ D) ∧ (-C ⋁ A) ∧ (-D ⋁ A) ∧ (-C ⋁ B) ∧ (-D ⋁ B)    (Associativity of ∧)\n\n Sensor models can be written in logical form for partially observable environments and a logical agent can maintain a belief state.\n\\Wampas World task environment is partially observable\n\n## Module 7 Definitions\n* **Knowledge base agent** - initialize a knowledge base with some background knowledge, needs to tell the knowledge base what it perceives at the begining of programming calls.\n* **Declarative approach** - tell sentences one by one until the agent knows how to operate\n* **Procedural approach** - encodes ideal behaviors directly using program code\n* **Syntax** - defines a representation language, specifies the structure of sentences\n* **Semantics** - defines the truth of each sentence in each possible world or model\n* **Inference** - the process of deriving new sentences from old ones.\n* **Inference rule** - patterns of sound inference that can be used to find proofs.\n* **Propositional logic** - a simple language consisting of proposition symbols and logical connectives, when propositions that are known to be true/false/completely unknown.\n* **Cnf** - can be exponentially longer than the simplest representation of a logical formula.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}