{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c96c8c78-ee94-49f5-b588-3c4fad665de8"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 26,
      "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": "ea33ad92-19ad-4a8c-917e-3832d5a5de5e"
      },
      "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": 25,
      "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": 24,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "questions: Are you concerned with thinking or behavior? Do you want to model humans, or try to achieve the optimal results?\n",
        "standard model-AI is concerned mainly with rational action. \n",
        "An ideal intelligent agent takes the best possible action in a situation.\n",
        "building agents that are intelligent\n",
        "Two refinements: 1 the ability of any agent, human or otherwise, to choose rational actions is limited by the computational intractability of\n",
        "doing so; 2. the concept of a machine that pursues a definite objective needs to be replaced with that of a machine pursuing objectives to benefit humans, but uncertain as\n",
        "to what those objectives are. \"\"\" \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 = \"\"\" Philosophers - weak AI - machines could possibly behave intelligently\n",
        "strong AI - such machines would count as having actual minds (as opposed to simulated minds)\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "Consciousness remains a mystery.\n",
        "Alan Turing insists machines cannot think and replaced it with a behavioral test. \n",
        "objections to the possibility of thinking machines.\n",
        "Few AI researchers pay attention to the Turing test, preferring to concentrate on their systems’ performance on practical tasks, rather than the ability to imitate humans.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "rationality vs omniscience. \n",
        "omniscient agent: knows the actual outcome of its actions and can act accordingly, is impossible in reality.\n",
        "rational choice depends only on the percept sequence to date\n",
        "rationality maximizes expected performance, perfection maximizes actual performance.\n",
        "\n",
        "To the extent that an agent relies on the prior knowledge of its designer rather than on its\n",
        "Autonomy own percepts and learning processes, the agent lacks autonomy. \n",
        "Rational agent should be autonomous, learn what it can to compensate for partial or incorrect prior knowledge.\n",
        "\n",
        "rational at any given time:\n",
        "1. The performance measure that defines the criterion of success.2. The agent’s prior knowledge of the environment.\n",
        "3, The actions that the agent can perform. 4. The agent’s percept sequence to date\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "PEAS:Performance, Environment, Actuators, Sensors \n",
        "1.Fully observable vs partially observable\n",
        "If an agent’s sensors give it access to the  complete state of the environment at each point in time, \n",
        "An environment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data\n",
        "2.Deterministic vs. nondeterministic. \n",
        "deterministic:If the next state of the environment is completely determined by the current state and the action executed by the agents\n",
        "stochastic vs nondeterministic\n",
        "stochastic if it explicitly deals with probabilities and “nondeterministic” if the possibilities are listed without being quantified \n",
        "3. Static vs. dynamic: \n",
        "dynamic If the environment can change while an agent is deliberating, otherwiseit is static\n",
        "4. known and unknown environments is not the same as the one between fully and partially observable environments.\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "1. simple reflex agent:agents select actions on the basis of the current percept, ignoring the rest of the percept history\n",
        "2. model-based reflex agents: simple reflex agents respond directly to percepts\n",
        "model-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept. \n",
        "3. Goal-based agentsL act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"agent function\": \"maps any given percept sequence to an action.abstract mathematical description\",\n",
        "\"agent program\":\"a concrete implementation running within some physical system\",\n",
        "\"rational agent\":\"does the right thing\", \n",
        " \"raltional agent2\":\"select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence.\",\n",
        "\"percept\" : \"content an agent’s sensors are perceiving\",\n",
        "\"percept sequence\" : \"complete history of everything the agent has ever perceived\",\n",
        "\"performance measure\":\"evaluates any given sequence of environment states\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-xypsHMirvcL"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ToAgIWPeqSl8"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "28t00bQLqRGo"
      },
      "source": [
        ""
      ],
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "eff6446a-bf4f-469f-ab1f-deff83f7120a"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nquestions: Are you concerned with thinking or behavior? Do you want to model humans, or try to achieve the optimal results?\nstandard model-AI is concerned mainly with rational action. \nAn ideal intelligent agent takes the best possible action in a situation.\nbuilding agents that are intelligent\nTwo refinements: 1 the ability of any agent, human or otherwise, to choose rational actions is limited by the computational intractability of\ndoing so; 2. the concept of a machine that pursues a definite objective needs to be replaced with that of a machine pursuing objectives to benefit humans, but uncertain as\nto what those objectives are. \n\n## AIMA Chapter 27.1 The Limits of AI\n Philosophers - weak AI - machines could possibly behave intelligently\nstrong AI - such machines would count as having actual minds (as opposed to simulated minds)\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nConsciousness remains a mystery.\nAlan Turing insists machines cannot think and replaced it with a behavioral test. \nobjections to the possibility of thinking machines.\nFew AI researchers pay attention to the Turing test, preferring to concentrate on their systems’ performance on practical tasks, rather than the ability to imitate humans.\n \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nrationality vs omniscience. \nomniscient agent: knows the actual outcome of its actions and can act accordingly, is impossible in reality.\nrational choice depends only on the percept sequence to date\nrationality maximizes expected performance, perfection maximizes actual performance.\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its\nAutonomy own percepts and learning processes, the agent lacks autonomy. \nRational agent should be autonomous, learn what it can to compensate for partial or incorrect prior knowledge.\n\nrational at any given time:\n1. The performance measure that defines the criterion of success.2. The agent’s prior knowledge of the environment.\n3, The actions that the agent can perform. 4. The agent’s percept sequence to date\n \n\n## AIMA 2.3 The Nature of Environments\n \nPEAS:Performance, Environment, Actuators, Sensors \n1.Fully observable vs partially observable\nIf an agent’s sensors give it access to the  complete state of the environment at each point in time, \nAn environment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data\n2.Deterministic vs. nondeterministic. \ndeterministic:If the next state of the environment is completely determined by the current state and the action executed by the agents\nstochastic vs nondeterministic\nstochastic if it explicitly deals with probabilities and “nondeterministic” if the possibilities are listed without being quantified \n3. Static vs. dynamic: \ndynamic If the environment can change while an agent is deliberating, otherwiseit is static\n4. known and unknown environments is not the same as the one between fully and partially observable environments.\n\n## AIMA 2.4 The Structure of Agents\n\n1. simple reflex agent:agents select actions on the basis of the current percept, ignoring the rest of the percept history\n2. model-based reflex agents: simple reflex agents respond directly to percepts\nmodel-based reflex agents maintain internal state to track aspects of the world that are not evident in the current percept. \n3. Goal-based agentsL act to achieve their goals, and utility-based agents try to maximize their own expected “happiness.\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Agent function** - maps any given percept sequence to an action.abstract mathematical description\n* **Agent program** - a concrete implementation running within some physical system\n* **Rational agent** - does the right thing\n* **Raltional agent2** - select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence.\n* **Percept** - content an agent’s sensors are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Performance measure** - evaluates any given sequence of environment states\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6c9789f4-242b-4b15-98f8-42d0e16986a9"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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 = \"\"\" Problem-solving agents use atomic representations.  the agent\n",
        "can follow four-phase problem-solving process:Goal formulation, Problem formulation, search, execution.\n",
        "It is an important property that in a fully observable, deterministic, known environment, the\n",
        "solution to any problem is a fixed sequence of actions. In partially observable or nondeterministic environments, \n",
        "a solution would be a branching strategy that recommends different future actions depending on what percepts arrive.\n",
        "A search problem is formed by:states, initial states, goal states, actions, transition model, action cost function.\n",
        "The state space can be represented as a graph in which the vertices are states and the Graph\n",
        "directed edges between them are actions.In formulating problems. In problem formation, we talked about Abstraction,\n",
        "The abstraction is valid if we can elaborate any abstract solution into a solution in the\n",
        "more detailed world.The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem.\n",
        "Standardized problems include grid worlds, sokoban puzzle. Real word problems include route-finding problem, Touring problems,  VLSI layout,\n",
        "Robot navigation, Automatic assembly sequencing, protein design\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"  We introduce search algorithms. We consider algorithms that superimpose a search tree over the state space graph\n",
        ", forming various paths from the initial state, trying to find a path that reaches a goal state,  \n",
        "generating a new node (called a child node or successor node) for each of the resulting state. \n",
        "the frontier separates two regions of the state-space graph: an interior region\n",
        "where every state has been expanded, and an exterior region of states that have not yet been reached.\n",
        "Each node in the search tree corresponds to a state in the state space and the edges Node in the search tree correspond to actions. \n",
        "The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another.\n",
        "The search tree describes paths between these states, reaching towards the goal. The data structure for search use queue to store frontiers,\n",
        "structure of nodes include: parent, state, action, paht-cost. best search: priorty queue, depth first search LIFO queue, breadth first search FIFO queue.\n",
        "Repeated state in the search tree, generated in this case by a cycle (a loopy path), special case of a redundant path.\n",
        "algorithms that cannot remember the past are doomed to repeat it. solutions: 1. remember all previously reached states\n",
        "2. save memory space if we don’t track reached states and we don’t check.we call it graph search if it checks for redundant\n",
        "paths and a tree-like search if it does not check.3. check for cycles, but not for redundant paths in general. \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" We can evaluate an algorithm’s performance in four ways: Completeness,  Cost optimality, time complexity and space complexity.To be complete, a search algorithm must be systematic in the way it explores an infinite Systematic\n",
        "state space, making sure it can eventually reach any state that is connected to the initial state.\n",
        "1.breadth-first search: all action same cost, complete even in infinite state spaces. BEST-FIRST-SEARCH where the evaluation function f(n) is the depth of the node\n",
        "FIFO queue faster & correct order of nodes & reached can be set & early reach goal.  tree-like search\n",
        "2.Dijkstra’s algorithm or uniform-cost search: actions different costs,  use best-first search where the evaluation function is the cost of the path from the root to the current node.\n",
        "BFS spreads out in waves of depth, BEST-FIRST-SEARCH with PATH-COST as the evaluation function, Uniform-cost search is complete and is cost-optimal\n",
        "3.Depth-first search always expands the deepest node in the frontier first. Depth-first search is not cost-optimal; it returns the first solution it\n",
        "finds, even if it is not cheapest.finite state spaces that are trees it is efficient and complete; cyclic state-infinite loop, incomplete\n",
        "better than bfs: epth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small.\n",
        "backtracking search uses even less memory.\n",
        "Depth-limited and iterative deepening search:supply a depth limit, ℓ, and treat all nodes at depth ℓ as if they had no successors, handle long cycles\n",
        "iterative deepening search:solves the problem of picking a good value for ℓ by trying either a solution is found, or the depth-limited search returns \n",
        "the failure value rather than the cutoff value. In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and\n",
        "the depth of the solution is not known.\n",
        "Bidirectional search:simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet,\n",
        ", we keep track of the best solution found so far, and might have to update that several times before the TERMINATED test proves that there is no possible better solution remaining\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search， an agent may need to to plan aheade\",\n",
        "\"serach\": \"computational process\" ,\n",
        "\"informed algorithms\": \"the agent can estimate how far it is from the goal\", \n",
        " \"uninformed algorithms\": \"no estimate is available\",\n",
        " \"path\":\"A sequence of actions forms a path\",\n",
        " \"Path state\": \"a solution is a path from the initial state to a goal Path state\",\n",
        " \"optimal solution\": \"the lowest path cost among all solutions\",\n",
        " \"abstraction\":\"The process of removing detail from a representation is called abstraction\",\n",
        " \"standardized problem\": \"illustrate or exercise various problem-solving methods\",\n",
        " \"real-world problem\": \"solutions people actually use\",\n",
        " \"search algorithm\": \"take a search problem as input and returns a solution, or an indication of Search algorithm failure.\",\n",
        " \"best-first search\": \"in which we choose a node, n, with minimum value of some Best-first search evaluation function, f(n).\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e7a70679-1770-4e90-9e1d-bf40f88c123c"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-solving agents use atomic representations.  the agent\ncan follow four-phase problem-solving process:Goal formulation, Problem formulation, search, execution.\nIt is an important property that in a fully observable, deterministic, known environment, the\nsolution to any problem is a fixed sequence of actions. In partially observable or nondeterministic environments, \na solution would be a branching strategy that recommends different future actions depending on what percepts arrive.\nA search problem is formed by:states, initial states, goal states, actions, transition model, action cost function.\nThe state space can be represented as a graph in which the vertices are states and the Graph\ndirected edges between them are actions.In formulating problems. In problem formation, we talked about Abstraction,\nThe abstraction is valid if we can elaborate any abstract solution into a solution in the\nmore detailed world.The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem.\nStandardized problems include grid worlds, sokoban puzzle. Real word problems include route-finding problem, Touring problems,  VLSI layout,\nRobot navigation, Automatic assembly sequencing, protein design\n\n\n\n## AIMA Chapter 3.2 Example Problems\n  We introduce search algorithms. We consider algorithms that superimpose a search tree over the state space graph\n, forming various paths from the initial state, trying to find a path that reaches a goal state,  \ngenerating a new node (called a child node or successor node) for each of the resulting state. \nthe frontier separates two regions of the state-space graph: an interior region\nwhere every state has been expanded, and an exterior region of states that have not yet been reached.\nEach node in the search tree corresponds to a state in the state space and the edges Node in the search tree correspond to actions. \nThe state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another.\nThe search tree describes paths between these states, reaching towards the goal. The data structure for search use queue to store frontiers,\nstructure of nodes include: parent, state, action, paht-cost. best search: priorty queue, depth first search LIFO queue, breadth first search FIFO queue.\nRepeated state in the search tree, generated in this case by a cycle (a loopy path), special case of a redundant path.\nalgorithms that cannot remember the past are doomed to repeat it. solutions: 1. remember all previously reached states\n2. save memory space if we don’t track reached states and we don’t check.we call it graph search if it checks for redundant\npaths and a tree-like search if it does not check.3. check for cycles, but not for redundant paths in general. \n\n## AIMA Chapter 3.3 Search Algorithms\n We can evaluate an algorithm’s performance in four ways: Completeness,  Cost optimality, time complexity and space complexity.To be complete, a search algorithm must be systematic in the way it explores an infinite Systematic\nstate space, making sure it can eventually reach any state that is connected to the initial state.\n1.breadth-first search: all action same cost, complete even in infinite state spaces. BEST-FIRST-SEARCH where the evaluation function f(n) is the depth of the node\nFIFO queue faster & correct order of nodes & reached can be set & early reach goal.  tree-like search\n2.Dijkstra’s algorithm or uniform-cost search: actions different costs,  use best-first search where the evaluation function is the cost of the path from the root to the current node.\nBFS spreads out in waves of depth, BEST-FIRST-SEARCH with PATH-COST as the evaluation function, Uniform-cost search is complete and is cost-optimal\n3.Depth-first search always expands the deepest node in the frontier first. Depth-first search is not cost-optimal; it returns the first solution it\nfinds, even if it is not cheapest.finite state spaces that are trees it is efficient and complete; cyclic state-infinite loop, incomplete\nbetter than bfs: epth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small.\nbacktracking search uses even less memory.\nDepth-limited and iterative deepening search:supply a depth limit, ℓ, and treat all nodes at depth ℓ as if they had no successors, handle long cycles\niterative deepening search:solves the problem of picking a good value for ℓ by trying either a solution is found, or the depth-limited search returns \nthe failure value rather than the cutoff value. In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and\nthe depth of the solution is not known.\nBidirectional search:simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet,\n, we keep track of the best solution found so far, and might have to update that several times before the TERMINATED test proves that there is no possible better solution remaining\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nYour summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search， an agent may need to to plan aheade\n* **Serach** - computational process\n* **Informed algorithms** - the agent can estimate how far it is from the goal\n* **Uninformed algorithms** - no estimate is available\n* **Path** - A sequence of actions forms a path\n* **Path state** - a solution is a path from the initial state to a goal Path state\n* **Optimal solution** - the lowest path cost among all solutions\n* **Abstraction** - The process of removing detail from a representation is called abstraction\n* **Standardized problem** - illustrate or exercise various problem-solving methods\n* **Real-world problem** - solutions people actually use\n* **Search algorithm** - take a search problem as input and returns a solution, or an indication of Search algorithm failure.\n* **Best-first search** - in which we choose a node, n, with minimum value of some Best-first search evaluation function, f(n).\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 = \"\"\" informed search: uses domain-specific hints about the location of goals, hints: a heuristic function-estimated cost of the cheapest path from the state at node n to a goal state,\n",
        "Greedy best-first search is a form of best-first search that expands first the node with the Greedy best-first search lowest h(n) value, Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.\n",
        "A∗ search, 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. A* complete. An admissible heuristic is therefore optimistic,\n",
        "consistency: A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a - triangle inequality, which stipulates that a side of a triangle cannot\n",
        "be longer than the sum of the other two sides，Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A∗ is cost-optimal，\n",
        " first time we reach - optimal path, With an inadmissible heuristic, A∗ may or may not be cost-optimal,n inadmissible heuristic, A∗ may or may not be cost-optimal. Here are two cases\n",
        "where it is: First, if there is even one cost-optimal path on which h(n) is admissible for all\n",
        "nodes n on the path, then that path will be found, no matter what the heuristic says for states\n",
        "off the path. Second, if the optimal solution has cost C∗, and the second-best has cost C2, and if h(n) overestimates some costs, but never by more than C2 −C∗, then A∗\n",
        "is guaranteed to return cost-optimal solutions.\n",
        "\n",
        "Search contours: visualize a search is to draw contours in the state space, just like the contours Contour in a topographic map. because A∗\n",
        "expands the frontier node of lowest f-cost, we can see that an A∗ search fans out from the start node, adding nodes in concentric bands of increasing f-cost.\n",
        "With uniform-cost search, we also have contours, but of g-cost, not g+ h. g costs are monotonic: the path cost Monotonic\n",
        "always increases as you go along a path, because action costs are always positive.\n",
        "If C∗ is the cost of the optimal solution path, then we can say the following:• A∗ expands all nodes that can be reached from the initial state on a path where every\n",
        "node on the path has f(n) < C∗. We say these are surely expanded nodes. Surely expanded nodes• A∗ might then expand some of the nodes right on the “goal contour” (where f(n) =C\n",
        "∗) before selecting a goal node.• A∗ expands no nodes with f(n) > C∗. We say that A∗ Optimally efficient with a consistent heuristic is optimally efficient in the sense that any algorithm\n",
        "that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A∗\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. The concept of pruning—eliminating possibilities from\n",
        "consideration without having to examine them—is important for many areas of AI.hat A∗ search is complete, cost-optimal, and optimally efficient among all such algo\u0002rithms is rather satisfying\n",
        "Satisficing search: Inadmissible heuristics and weighted A∗: A* expands a lot of nodes. We can explore fewer nodes if we are willing to accept solutions that are suboptimal -  satisficing solutions\n",
        "we allow A∗ search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal Inadmissible heuristic solution, but the heuristic can potentially be more accurate.\n",
        "weighted A∗: search where we weight the heuristic value more heavily, giving us the Weighted A∗ search evaluation function f(n) = g(n) +W ×h(n), for some W > 1. E.g. bounded suboptimal search，\n",
        "bounded-cost search， unbounded-cost search\n",
        "A∗ search: g(n) +h(n) (W = 1)\n",
        "Uniform-cost search: g(n) (W = 0)\n",
        "Greedy best-first search: h(n) (W = ∞)\n",
        "Weighted A∗ search: g(n) +W ×h(n) (1 < W < ∞) \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissibility\": \"an admissible heuristic is one that never overestimates the cost to reach a goal.\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 742
        },
        "cellView": "form",
        "outputId": "bfa25398-b8c9-45cb-f34c-44d55e917842"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n informed search: uses domain-specific hints about the location of goals, hints: a heuristic function-estimated cost of the cheapest path from the state at node n to a goal state,\nGreedy best-first search is a form of best-first search that expands first the node with the Greedy best-first search lowest h(n) value, Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.\nA∗ search, 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. A* complete. An admissible heuristic is therefore optimistic,\nconsistency: A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a - triangle inequality, which stipulates that a side of a triangle cannot\nbe longer than the sum of the other two sides，Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A∗ is cost-optimal，\n first time we reach - optimal path, With an inadmissible heuristic, A∗ may or may not be cost-optimal,n inadmissible heuristic, A∗ may or may not be cost-optimal. Here are two cases\nwhere it is: First, if there is even one cost-optimal path on which h(n) is admissible for all\nnodes n on the path, then that path will be found, no matter what the heuristic says for states\noff the path. Second, if the optimal solution has cost C∗, and the second-best has cost C2, and if h(n) overestimates some costs, but never by more than C2 −C∗, then A∗\nis guaranteed to return cost-optimal solutions.\n\nSearch contours: visualize a search is to draw contours in the state space, just like the contours Contour in a topographic map. because A∗\nexpands the frontier node of lowest f-cost, we can see that an A∗ search fans out from the start node, adding nodes in concentric bands of increasing f-cost.\nWith uniform-cost search, we also have contours, but of g-cost, not g+ h. g costs are monotonic: the path cost Monotonic\nalways increases as you go along a path, because action costs are always positive.\nIf C∗ is the cost of the optimal solution path, then we can say the following:• A∗ expands all nodes that can be reached from the initial state on a path where every\nnode on the path has f(n) < C∗. We say these are surely expanded nodes. Surely expanded nodes• A∗ might then expand some of the nodes right on the “goal contour” (where f(n) =C\n∗) before selecting a goal node.• A∗ expands no nodes with f(n) > C∗. We say that A∗ Optimally efficient with a consistent heuristic is optimally efficient in the sense that any algorithm\nthat extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A∗\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. The concept of pruning—eliminating possibilities from\nconsideration without having to examine them—is important for many areas of AI.hat A∗ search is complete, cost-optimal, and optimally efficient among all such algo\u0002rithms is rather satisfying\nSatisficing search: Inadmissible heuristics and weighted A∗: A* expands a lot of nodes. We can explore fewer nodes if we are willing to accept solutions that are suboptimal -  satisficing solutions\nwe allow A∗ search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal Inadmissible heuristic solution, but the heuristic can potentially be more accurate.\nweighted A∗: search where we weight the heuristic value more heavily, giving us the Weighted A∗ search evaluation function f(n) = g(n) +W ×h(n), for some W > 1. E.g. bounded suboptimal search，\nbounded-cost search， unbounded-cost search\nA∗ search: g(n) +h(n) (W = 1)\nUniform-cost search: g(n) (W = 0)\nGreedy best-first search: h(n) (W = ∞)\nWeighted A∗ search: g(n) +W ×h(n) (1 < W < ∞) \n\n## Module 4 Lecture Notes\n \n\n\n \n\n## Module 4 Definitions\n* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "game elements:\n",
        "• S0: The initial state, how the game is set up at the start.\n",
        "• TO-MOVE(s): The player whose turn to move in state s.\n",
        "• ACTIONS(s): set of legal moves in state s.\n",
        "• RESULT(s, a):  transition model, state resulting from taking action a in state s.\n",
        "• IS-TERMINAL(s): A terminal test, which is true when the game is over. terminal states: states where the game has ended. \n",
        "• UTILITY(s, p): A utility function (objective function or payoff function), the final numeric value to player p when the game ends in terminal state s.\n",
        "outcome is a win, loss, or draw-values 1, 0, or 1/2.\n",
        "some have wider range of possible outcomes- the payoffs in backgammon range from 0 to 192. \n",
        "complete game tree : a search tree that follows every sequence of moves all the way to a terminal state \"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "The minimax algorithm: performs a complete depth-first exploration of the game tree.\n",
        "If the maximum depth of the tree is m and there are b legal moves at each point:  time complexity of the minimax algorithm: O(b^m). \n",
        "If an algorithm that generates all actions at once:space complexity is O(bm) \n",
        "If an algorithm that generates actions one at a time, space complexity: O(m) \n",
        "The exponential complexity makes MINIMAX impractical for complex games.\n",
        "\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined,\n",
        "good order cases: alpha–beta examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. - effective branching factor √b instead of b.\n",
        "                  solve a tree roughly twice as deep as minimax in the same amount of time. With random move ordering, the total number of nodes examined will be roughly O(b^3m/4) for moderate b. \n",
        "\n",
        "dynamic move-ordering schemes, e.g. trying first the moves that were found to be best in the past, quite close to the theoretical limit.\n",
        "In game tree search, repeated states can occur because of transpositions — different permutations of the move sequence that end up in the same position, and the problem can be\n",
        "addressed with a transposition table that caches the heuristic value of states.still too many states to explore in the time available\n",
        "solution:\n",
        "Type A strategy(chess programs) considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. - a wide but shallow portion of the tree.\n",
        "A Type B strategy(Go programs) ignores moves that look bad, and follows promising lines “as far as possible.” - a deep but narrow portion of the tree.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "weighted linear function:\n",
        "based on strong assumption: the contribution of each feature is independent of the values of the other features.\n",
        "The most straightforward approach to controlling the amount of search is to set a fixed depth limit so that IS-CUTOFF(state, depth) returns true for all depth greater than\n",
        "some fixed depth d. The depth d is chosen so that a move is selected within the allocated time. \n",
        "A more robust approach: apply iterative deepening. When time runs out, the program returns the move selected by the deepest completed search.\n",
        "If in each round of iterative deepening we keep entries in the transposition table, subsequent rounds will be faster, we can use the evaluations to\n",
        "improve move ordering.\n",
        "\n",
        "A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p.\n",
        "1. terminal states, EVAL(s, p)=UTILITY(s, p)\n",
        "2. nonterminal states, somewhere between a loss and a win: UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p).\n",
        "A good evaluation function: 1.must not take too long!, 2. strongly correlated with the actual chances of winning\n",
        "Most evaluation functions work by calculating various features of the state\n",
        "\n",
        "The horizon effect is more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable,\n",
        "can be temporarily avoided by the use of delaying tactics.\n",
        "\n",
        "Alpha–beta pruning: prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good Forward pruning\n",
        "ones.\n",
        "\n",
        "The evaluation function should be applied only to positions that are quiescent(positions in which there is no pending move) that would wildly swing the evaluation.\n",
        "Nonquiescent positions the IS-CUTOFF returns false, and the search continues until quiescent positions are reached.\n",
        "This extra quiescence search is sometimes restricted to consider only certain types of moves, which will quickly resolve the uncertainties in the position.\n",
        "\n",
        "forward pruning:1. beam search. 2.late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are\n",
        "less likely to be good moves. But rather than pruning them away completely, we just reduce the depth to which we search these moves -> saving time\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "stochastic games:chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\n",
        "Games of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children,\n",
        "weighted by the probability of each child.\n",
        "The obvious approximation to make with expectiminimax is to cut the search off at some point and apply an evaluation function to each leaf.\n",
        "One might think that evaluation functions for games such as backgammon should be just like evaluation functions for chess—they just need to give higher values to better positions. \n",
        "the presence of chance nodes means that one has to be more careful about what the values mean.\n",
        "The program behaves totally differently if we make a change to some of the evaluation values, even if the preference order remains the same.\n",
        "to avoid this problem, the evaluation function must return values that are a positive linear transformation of the probability of winning \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"P(RESULT(a)=s′) = ∑_sP(s)P(s′|s,a). \n",
        "agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function desirability of a state. \n",
        "The expected utility of an action given the evidence, EU(a), is just the Expected utility average utility value of the outcomes, weighted by the probability that the outcome occurs:\n",
        "EU(a) = ∑s′P(RESULT(a)=s′)U(s′)\n",
        "\n",
        "maximum expected utility (MEU):a rational agent should choose the action that maximizes the agent’s expected utility: action = argmaxEU(a).\n",
        "the MEU principle could be seen as a prescription for intelligent behavior. All an intelligent agent has to do is calculate the various quantities, maximize utility over its actions,\n",
        "and away it goes. But this does not mean that the AI problem is solved by the definition!\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice.\n",
        "\n",
        "central justification for the MEU principle:\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure,\n",
        "then the agent will achieve the highest possible performance score (averaged over all the possible environments)\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "The primary issue for utility theory:\n",
        "we list six constraints that we require any reasonable preference relation to obey:\n",
        "orderability, transitivity, continuity, substitutability, monotonicity, and decomposability.\n",
        "\n",
        "once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined.\n",
        "the preceding theorems establish that  a utility function exists for any rational agent. The theorems do not establish that the utility function is unique.\n",
        "\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference ranking on states \"\"\"\n",
        "chapter16_3 = \"\"\" The difference between the EMV of a lottery and its certainty equivalent is called the in\u0002surance premium. Risk aversion is the basis for the insurance industry, because it means that insurance premiums are positive. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"preference elicitation\":\"Process that involves presenting choices to the human and using observed preferences pin down the underlying utility function\",\n",
        "\"decision theory\":\" a normative theory: it describes how a rational agent should act.\",\n",
        "\"value function/ordinal utility function\":\"a preference ranking on states\",\n",
        "\"descriptive theory,\":\" describes how actual agents—for example, humans really do act\",\n",
        "\"ambiguity aversion\":\"people elect the known probability rather than the unknown unknowns\", \n",
        "\"framing effect\":\" the exact wording of a decision problem can have a big impact on the agent’s choices\",\n",
        "\"anchoring effect\":\"People feel more comfortable making relative utility judgments rather than absolute ones.\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 51,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1b60daea-ff42-49fc-af1b-cbfe15d0528f"
      },
      "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": 52,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \ngame elements:\n• S0: The initial state, how the game is set up at the start.\n• TO-MOVE(s): The player whose turn to move in state s.\n• ACTIONS(s): set of legal moves in state s.\n• RESULT(s, a):  transition model, state resulting from taking action a in state s.\n• IS-TERMINAL(s): A terminal test, which is true when the game is over. terminal states: states where the game has ended. \n• UTILITY(s, p): A utility function (objective function or payoff function), the final numeric value to player p when the game ends in terminal state s.\noutcome is a win, loss, or draw-values 1, 0, or 1/2.\nsome have wider range of possible outcomes- the payoffs in backgammon range from 0 to 192. \ncomplete game tree : a search tree that follows every sequence of moves all the way to a terminal state \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nThe minimax algorithm: performs a complete depth-first exploration of the game tree.\nIf the maximum depth of the tree is m and there are b legal moves at each point:  time complexity of the minimax algorithm: O(b^m). \nIf an algorithm that generates all actions at once:space complexity is O(bm) \nIf an algorithm that generates actions one at a time, space complexity: O(m) \nThe exponential complexity makes MINIMAX impractical for complex games.\n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined,\ngood order cases: alpha–beta examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. - effective branching factor √b instead of b.\n                  solve a tree roughly twice as deep as minimax in the same amount of time. With random move ordering, the total number of nodes examined will be roughly O(b^3m/4) for moderate b. \n\ndynamic move-ordering schemes, e.g. trying first the moves that were found to be best in the past, quite close to the theoretical limit.\nIn game tree search, repeated states can occur because of transpositions — different permutations of the move sequence that end up in the same position, and the problem can be\naddressed with a transposition table that caches the heuristic value of states.still too many states to explore in the time available\nsolution:\nType A strategy(chess programs) considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. - a wide but shallow portion of the tree.\nA Type B strategy(Go programs) ignores moves that look bad, and follows promising lines “as far as possible.” - a deep but narrow portion of the tree.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\nweighted linear function:\nbased on strong assumption: the contribution of each feature is independent of the values of the other features.\nThe most straightforward approach to controlling the amount of search is to set a fixed depth limit so that IS-CUTOFF(state, depth) returns true for all depth greater than\nsome fixed depth d. The depth d is chosen so that a move is selected within the allocated time. \nA more robust approach: apply iterative deepening. When time runs out, the program returns the move selected by the deepest completed search.\nIf in each round of iterative deepening we keep entries in the transposition table, subsequent rounds will be faster, we can use the evaluations to\nimprove move ordering.\n\nA heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p.\n1. terminal states, EVAL(s, p)=UTILITY(s, p)\n2. nonterminal states, somewhere between a loss and a win: UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p).\nA good evaluation function: 1.must not take too long!, 2. strongly correlated with the actual chances of winning\nMost evaluation functions work by calculating various features of the state\n\nThe horizon effect is more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable,\ncan be temporarily avoided by the use of delaying tactics.\n\nAlpha–beta pruning: prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good Forward pruning\nones.\n\nThe evaluation function should be applied only to positions that are quiescent(positions in which there is no pending move) that would wildly swing the evaluation.\nNonquiescent positions the IS-CUTOFF returns false, and the search continues until quiescent positions are reached.\nThis extra quiescence search is sometimes restricted to consider only certain types of moves, which will quickly resolve the uncertainties in the position.\n\nforward pruning:1. beam search. 2.late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are\nless likely to be good moves. But rather than pruning them away completely, we just reduce the depth to which we search these moves -> saving time\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nstochastic games:chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\nGames of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children,\nweighted by the probability of each child.\nThe obvious approximation to make with expectiminimax is to cut the search off at some point and apply an evaluation function to each leaf.\nOne might think that evaluation functions for games such as backgammon should be just like evaluation functions for chess—they just need to give higher values to better positions. \nthe presence of chance nodes means that one has to be more careful about what the values mean.\nThe program behaves totally differently if we make a change to some of the evaluation values, even if the preference order remains the same.\nto avoid this problem, the evaluation function must return values that are a positive linear transformation of the probability of winning \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nP(RESULT(a)=s′) = ∑_sP(s)P(s′|s,a). \nagent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function desirability of a state. \nThe expected utility of an action given the evidence, EU(a), is just the Expected utility average utility value of the outcomes, weighted by the probability that the outcome occurs:\nEU(a) = ∑s′P(RESULT(a)=s′)U(s′)\n\nmaximum expected utility (MEU):a rational agent should choose the action that maximizes the agent’s expected utility: action = argmaxEU(a).\nthe MEU principle could be seen as a prescription for intelligent behavior. All an intelligent agent has to do is calculate the various quantities, maximize utility over its actions,\nand away it goes. But this does not mean that the AI problem is solved by the definition!\nThe MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice.\n\ncentral justification for the MEU principle:\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure,\nthen the agent will achieve the highest possible performance score (averaged over all the possible environments)\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nThe primary issue for utility theory:\nwe list six constraints that we require any reasonable preference relation to obey:\norderability, transitivity, continuity, substitutability, monotonicity, and decomposability.\n\nonce the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined.\nthe preceding theorems establish that  a utility function exists for any rational agent. The theorems do not establish that the utility function is unique.\n\nAs in game-playing, in a deterministic environment an agent needs only a preference ranking on states \n\n## AIMA Chapter 16.3 Utility Functions\n The difference between the EMV of a lottery and its certainty equivalent is called the in\u0002surance premium. Risk aversion is the basis for the insurance industry, because it means that insurance premiums are positive. \n\n## Module 5 Lecture Notes\n\n \n\n## Module 5 Definitions\n* **Preference elicitation** - Process that involves presenting choices to the human and using observed preferences pin down the underlying utility function\n* **Decision theory** -  a normative theory: it describes how a rational agent should act.\n* **Value function/ordinal utility function** - a preference ranking on states\n* **Descriptive theory,** -  describes how actual agents—for example, humans really do act\n* **Ambiguity aversion** - people elect the known probability rather than the unknown unknowns\n* **Framing effect** -  the exact wording of a decision problem can have a big impact on the agent’s choices\n* **Anchoring effect** - People feel more comfortable making relative utility judgments rather than absolute ones.\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 = \"\"\"\n",
        "best-known category of continuous-domain CSPs is that of linear programming problems。\n",
        "The simplest type is the unary constraint:restricts the value of a single variable. binary constraint relates two variables.\n",
        "Preference constraints can often be encoded as costs on individual variable assignments,\n",
        "CSPs with preferences can be solved with optimization search methods, either path-based or local- such a problem a constrained optimization problem, or COP.\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "A single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
        "A variable in a CSP is arc-consistent1 Arc consistency if every value in its domain satisfies the variable’s binary constraints.\n",
        "\n",
        "A CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-consistent, ... all the way down to 1-consistent. The total run time is only O(n^2d).\n",
        "constraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take time exponential in n in the worst case.\n",
        "Worse, n-consistency also requires space that is exponential in n. In practice, determining the appropriate level of consistency checking is mostly an empirical science.\n",
        "Alldiff constraints works as follows:\n",
        "if m variables are involved in the constraint, and if they have n possible distinct values alto\u0002gether, and m > n, then the constraint cannot be satisfied\n",
        "\n",
        "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "Stronger forms of propagation can be defined with the notion of k-consistency. A CSP is k consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\n",
        "a consistent value can always be assigned to any kth variable.\"\"\"\n",
        "chapter6_3 = \"\"\"  \n",
        "SELECT-UNASSIGNED-VARIABLE:\n",
        "This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\n",
        "It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.\n",
        "The least-constraining-value heuristic is effective for this. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
        "\n",
        "Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value\n",
        "that is inconsistent with the value chosen for X.\n",
        "\n",
        "No-good This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination\n",
        "of assignments or by keeping a separate cache of no-goods\n",
        "\n",
        "The algorithm called MAC detects inconsistencies like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the\n",
        "lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.  This has two benefits:\n",
        "it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights. \n",
        "the run time of min-conflicts is roughly independent of problem size.\n",
        "constraint weighting aims to concentrate the search on the important constraints.  \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "The complexity of solving a CSP is strongly related to the structure of its constraint graph.\n",
        "Tree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient if a small cutset can be found. \n",
        "Tree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small; \n",
        "however they need memory exponential in the tree width of the constraint graph. Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time.  \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \" global constraint\" : \"one involving an arbitrary number of variables (but not necessarily all variables)\",\n",
        "\"the min-conflicts heuristic\":\"select the value that results in the minimum number of conflicts with other variables，\n",
        "\"resource constraint(the Atmost constrain)\":\" detect an inconsistency simply by checking the sum of the minimum values of the current domains\" ,\n",
        "\"bounds-consistent\":\"if for every variable X, and for both the lower-bound Bounds-consistent and upper-bound values of X, there exists some value of Y that satisfies the constraint between and Y for every variable Y.\"   \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 49,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4d81f66f-6d1a-4ce4-86c4-4abccb55439e"
      },
      "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": 50,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nbest-known category of continuous-domain CSPs is that of linear programming problems。\nThe simplest type is the unary constraint:restricts the value of a single variable. binary constraint relates two variables.\nPreference constraints can often be encoded as costs on individual variable assignments,\nCSPs with preferences can be solved with optimization search methods, either path-based or local- such a problem a constrained optimization problem, or COP.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nA single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\nA variable in a CSP is arc-consistent1 Arc consistency if every value in its domain satisfies the variable’s binary constraints.\n\nA CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-consistent, ... all the way down to 1-consistent. The total run time is only O(n^2d).\nconstraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take time exponential in n in the worst case.\nWorse, n-consistency also requires space that is exponential in n. In practice, determining the appropriate level of consistency checking is mostly an empirical science.\nAlldiff constraints works as follows:\nif m variables are involved in the constraint, and if they have n possible distinct values alto\u0002gether, and m > n, then the constraint cannot be satisfied\n\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\nStronger forms of propagation can be defined with the notion of k-consistency. A CSP is k consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\na consistent value can always be assigned to any kth variable.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n  \nSELECT-UNASSIGNED-VARIABLE:\nThis intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\nIt attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.\nThe least-constraining-value heuristic is effective for this. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\n\nWhenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value\nthat is inconsistent with the value chosen for X.\n\nNo-good This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination\nof assignments or by keeping a separate cache of no-goods\n\nThe algorithm called MAC detects inconsistencies like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nEach constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the\nlowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.  This has two benefits:\nit adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights. \nthe run time of min-conflicts is roughly independent of problem size.\nconstraint weighting aims to concentrate the search on the important constraints.  \n\n## AIMA Chapter 6.5 The Structure of Problems\n\nThe complexity of solving a CSP is strongly related to the structure of its constraint graph.\nTree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient if a small cutset can be found. \nTree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small; \nhowever they need memory exponential in the tree width of the constraint graph. Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time.  \n\n## Module 6 Lecture Notes\n \" global constraint\" : \"one involving an arbitrary number of variables (but not necessarily all variables)\",\n\"the min-conflicts heuristic\":\"select the value that results in the minimum number of conflicts with other variables，\n\"resource constraint(the Atmost constrain)\":\" detect an inconsistency simply by checking the sum of the minimum values of the current domains\" ,\n\"bounds-consistent\":\"if for every variable X, and for both the lower-bound Bounds-consistent and upper-bound values of X, there exists some value of Y that satisfies the constraint between and Y for every variable Y.\"   \n\n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}