{
  "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": "2de2eeda-2979-4713-cc81-83a457265698"
      },
      "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": 57,
      "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": "85f38272-28d8-40e9-f733-a4e02084bbbc"
      },
      "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": 58,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 59,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        " weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\\\\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent’s percept sequence is the complete history of everything the agent has ever perceived.\\\\\n",
        "an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\\\\\n",
        "the agent function for an artificial agent will be implemented by an agent program\\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "Rational:\\\\\n",
        "The performance measure that defines the criterion of success. The agent’s prior knowledge of the environment.\\\\\n",
        "The actions that the agent can perform.\\\\\n",
        "The agent’s percept sequence to date.\\\\\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE:\\\\\n",
        "SINGLE-AGENT VS. MULTIAGEN\\\\\n",
        "Deterministic vs. nondeterministic:If the next state of the environment is completely\n",
        "determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic\\\\\n",
        "EPISODIC VS. SEQUENTIA: In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then\n",
        "performs a single action\\\\\n",
        "STATIC VS. DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent\\\\\n",
        "DISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent.\\\\\n",
        "KNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. In a known environment\\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "The job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture、、\n",
        "the difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history.\\\\\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "Agents include humans, robots, softbots, thermostats, …\\\\\n",
        "A rational agent is an agent that perceives its environment and and behaves rationally\\\\\n",
        "The basic premise is that aggregate social behavior results from the behavior of individual actors, each of whom is making their individual decisions.\\\\\n",
        "performance measure:\\\\\n",
        "An objective criterion for success of an agent's behavior\\\\ given the evidence provided by the percept sequence.\\\\It is better to design performance measures according to what you want to be\n",
        "achieved in the environment, rather than how you think the agent should behave.\\\\\n",
        "Rational Agent:\\\\\n",
        "For each possible percept sequence P, a rational agent selects an action a that maximizes the expected value of its performance measure\\\\\n",
        "\\\\\n",
        "Task Environment:\\\\\n",
        "performance measure/environment/actuators/sensors\\\\\n",
        "Goal of AI practitioner who designs rational agents: \\\\\n",
        "given a PEAS task environment, 1)Construct agent function f that maximizes the expected value of the performance measure, 2)Design an agent program that\n",
        "implements f on a particular architecture\\\\\n",
        "\\\\\n",
        "A simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history\\\\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 60,
      "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": "74d424af-d439-42d9-a0eb-1597ce31da51"
      },
      "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": 61,
      "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\n weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\\\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent’s percept sequence is the complete history of everything the agent has ever perceived.\\\nan agent’s behavior is described by the agent function that maps any given percept sequence to an action.\\\nthe agent function for an artificial agent will be implemented by an agent program\\\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nRational:\\\nThe performance measure that defines the criterion of success. The agent’s prior knowledge of the environment.\\\nThe actions that the agent can perform.\\\nThe agent’s percept sequence to date.\\\n\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE:\\\nSINGLE-AGENT VS. MULTIAGEN\\\nDeterministic vs. nondeterministic:If the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic\\\nEPISODIC VS. SEQUENTIA: In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then\nperforms a single action\\\nSTATIC VS. DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent\\\nDISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent.\\\nKNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. In a known environment\\\n\n \n\n## AIMA 2.4 The Structure of Agents\n\nThe job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture、、\nthe difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history.\\\n\n\n## Module 1 Lecture Notes\n\nAgents include humans, robots, softbots, thermostats, …\\\nA rational agent is an agent that perceives its environment and and behaves rationally\\\nThe basic premise is that aggregate social behavior results from the behavior of individual actors, each of whom is making their individual decisions.\\\nperformance measure:\\\nAn objective criterion for success of an agent's behavior\\ given the evidence provided by the percept sequence.\\It is better to design performance measures according to what you want to be\nachieved in the environment, rather than how you think the agent should behave.\\\nRational Agent:\\\nFor each possible percept sequence P, a rational agent selects an action a that maximizes the expected value of its performance measure\\\n\\\nTask Environment:\\\nperformance measure/environment/actuators/sensors\\\nGoal of AI practitioner who designs rational agents: \\\ngiven a PEAS task environment, 1)Construct agent function f that maximizes the expected value of the performance measure, 2)Design an agent program that\nimplements f on a particular architecture\\\n\\\nA simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history\\\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Slicing: Return Copy of a Subsequence\\\\\n",
        "reverse() sort() are in place, sorted(list) returns a copy\\\\\n",
        "\n",
        "Default Values for Arguments：\\\\\n",
        "These arguments are optional when the function is called\\\\\n",
        "Non-default argument should always precede default arguments;\\\\\n",
        "Functions can be called with arguments out of order \\\\\n",
        "myfun(c=43, b=1, a=2)\\\\\n",
        "\\\\\n",
        "Suppose you want to accept a variable number of non-keyword arguments to your\n",
        "function.\\\\\n",
        "def print_everything(*args):\\\\\n",
        "  args is a tuple of arguments passed to the fn\\\\\n",
        "print(args)\\\\\n",
        "\\\\\n",
        "def print_keyword_args(**kwargs):\\\\\n",
        "# kwargs is a dict of the keyword args passed to the fn\\\\\n",
        "print(kwargs)\\\\\n",
        "print_keyword_args(first_name=\"John\", last_name=\"Doe\")\\\\\n",
        "\n",
        "Python iterators do not have a hasnext() method!\\\\\n",
        "Just catch the StopIteration exception\\\\\n",
        "\n",
        "Benefits of using generators\\\\\n",
        "Less code than writing a standard iterator\\\\\n",
        "Maintains local state automatically\\\\\n",
        "Values are computed one at a time, as they’re needed\\\\\n",
        "Avoids storing the entire sequence in memory\\\\\n",
        "Good for aggregating (summing, counting) items. One pass.\\\\\n",
        "Crucial for infinite sequences\\\\\n",
        "Bad if you need to inspect the individual values\\\\\n",
        "\n",
        "g = merge([2,4], [1, 3, 5])\\\\\n",
        "while True:\\\\\n",
        "try:\\\\\n",
        "print(g.__next__())\\\\\n",
        "except StopIteration:\\\\\n",
        "print('Done’)\\\\\n",
        "break\\\\\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 62,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 824
        },
        "outputId": "ae32e1ee-b412-4d59-9db6-84a6e5285375"
      },
      "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": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nSlicing: Return Copy of a Subsequence\\\nreverse() sort() are in place, sorted(list) returns a copy\\\n\nDefault Values for Arguments：\\\nThese arguments are optional when the function is called\\\nNon-default argument should always precede default arguments;\\\nFunctions can be called with arguments out of order \\\nmyfun(c=43, b=1, a=2)\\\n\\\nSuppose you want to accept a variable number of non-keyword arguments to your\nfunction.\\\ndef print_everything(*args):\\\n  args is a tuple of arguments passed to the fn\\\nprint(args)\\\n\\\ndef print_keyword_args(**kwargs):\\\n# kwargs is a dict of the keyword args passed to the fn\\\nprint(kwargs)\\\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\")\\\n\nPython iterators do not have a hasnext() method!\\\nJust catch the StopIteration exception\\\n\nBenefits of using generators\\\nLess code than writing a standard iterator\\\nMaintains local state automatically\\\nValues are computed one at a time, as they’re needed\\\nAvoids storing the entire sequence in memory\\\nGood for aggregating (summing, counting) items. One pass.\\\nCrucial for infinite sequences\\\nBad if you need to inspect the individual values\\\n\ng = merge([2,4], [1, 3, 5])\\\nwhile True:\\\ntry:\\\nprint(g.__next__())\\\nexcept StopIteration:\\\nprint('Done’)\\\nbreak\\\n\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 = \"\"\"\n",
        "Before an agent can start searching, a well-defined problem must be formulated.\\\\\n",
        "A problem consists of five parts: the initial state, a set of actions, a transition model\n",
        "describing the results of those actions, a set of goal states, and an action cost function.\\\\\n",
        "The environment of the problem is represented by a state space graph. A path through\n",
        "the state space (a sequence of actions) from the initial state to a goal state is a solution.\\\\\n",
        "Search algorithms generally treat states and actions as atomic, without any internal \n",
        "structure (although we introduced features of states when it came time to do learning).\\\\ Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\\\\\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "We say that Arad is a repeated state in the search tree, generated in this case by a cycle (also known as a loopy path). So even though the state space has only 20 states, the complete search tree is infinite because there is no limit to how often one can traverse a loop.\\\\\n",
        "A cycle is a special case of a redundant path. \\\\\n",
        "First, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state\\\\\n",
        "Second, we can not worry about repeating the past. There are some problem formulations where it is rare or impossible for two paths to reach the same state. \\\\\n",
        "Third, we can compromise and check for cycles, but not for redundant paths in general.\\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "```\n",
        "BFS(problem) returns a solution node or failure:\n",
        " node <- Node(problem.INITIAL)\n",
        " if problem.IS-GOAL(node.State) return node\n",
        " frontier <- queue\n",
        " reached <- {problem.INITIAL}\n",
        " while frontier:\n",
        "   node <- Pop(frontier)\n",
        "   for each child in Expand(problem, node) do:\n",
        "     s <- child.STATE\n",
        "     if problem.IS-GOAL(s) then return child\n",
        "     if s is not reached then \n",
        "    add s to reached\n",
        "    add child to frontier\n",
        "return failure\n",
        "```\n",
        "\n",
        "depth-first tree-like search takes time proportional to the number of states, and has memory complexity of only O(bm)\n",
        "where is the branching factor and is the maximum depth of the tree. Some problems that would require exabytes of memory with breadth-first search can be handled with only kilobytes using depth-first search\n",
        "```\n",
        "function ITERATIVE-DEEPENDING-SEARCH(problem) returns a solution node or failure\n",
        " for depth = 0 to +infinity do:\n",
        "   result <- depth-limited-search(problem, depth)\n",
        "   if result not equal to cutoff then return result\n",
        "\n",
        "function Depth-Limited_search(problem, l) retuns a node or failure or cutoff:\n",
        " frontier <- LIFO(stack) with Node(problem.INITIAL) as an element\n",
        " result <- failure\n",
        " while not Is-Empty(frontier) do:\n",
        "   node <- pop(frontier)\n",
        "   if problem.Is-Goal(node.STATE) then return node\n",
        "   if Depth(node) < l then:\n",
        "     result <- cutoff\n",
        "    else if not IS-Cycle(node) do:\n",
        "      for each child in Expand(problem, node) do:\n",
        "        add child to frontier\n",
        "  return result\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Problem: Repeated states\\\\\n",
        "Graph search\\\\\n",
        "• Simple Mod from tree search: Check to see if a node has been visited\n",
        "before adding to search queue\\\\\n",
        "```\n",
        "function TREE-SEARCH(problem) returns a solution, or failure\n",
        "initialize the frontier using the initial state of problem\n",
        "loop do\n",
        "if the frontier is empty then return failure\n",
        "choose a leaf nose and remove it from the frontier\n",
        "if the node contains a goal state then return the corresponding solution\n",
        "expand the chosen node, adding the resulting nodes to the frontier\n",
        "\n",
        "function GRAPH-SEARCH(problem) returns a solution, or failure\n",
        "initialize the frontier using the initial state of problem\n",
        "initialize the explored set to be empty\n",
        "loop do\n",
        "if the frontier is empty then return failure\n",
        "choose a leaf node and remove it from the frontier\n",
        "if the node contains a goal state then return the corresponding solution\n",
        "add node to the explored set\n",
        "expand the chosen node, adding the resulting nodes to the frontier\n",
        "only if not in the frontier of explored set\n",
        "\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4361414a-65c6-47bb-b79b-68f50d126fbe"
      },
      "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": 65,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nBefore an agent can start searching, a well-defined problem must be formulated.\\\nA problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\\\nThe environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\\\nSearch algorithms generally treat states and actions as atomic, without any internal \nstructure (although we introduced features of states when it came time to do learning).\\ Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\\\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n\nWe say that Arad is a repeated state in the search tree, generated in this case by a cycle (also known as a loopy path). So even though the state space has only 20 states, the complete search tree is infinite because there is no limit to how often one can traverse a loop.\\\nA cycle is a special case of a redundant path. \\\nFirst, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state\\\nSecond, we can not worry about repeating the past. There are some problem formulations where it is rare or impossible for two paths to reach the same state. \\\nThird, we can compromise and check for cycles, but not for redundant paths in general.\\\n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n```\nBFS(problem) returns a solution node or failure:\n node <- Node(problem.INITIAL)\n if problem.IS-GOAL(node.State) return node\n frontier <- queue\n reached <- {problem.INITIAL}\n while frontier:\n   node <- Pop(frontier)\n   for each child in Expand(problem, node) do:\n     s <- child.STATE\n     if problem.IS-GOAL(s) then return child\n     if s is not reached then \n    add s to reached\n    add child to frontier\nreturn failure\n```\n\ndepth-first tree-like search takes time proportional to the number of states, and has memory complexity of only O(bm)\nwhere is the branching factor and is the maximum depth of the tree. Some problems that would require exabytes of memory with breadth-first search can be handled with only kilobytes using depth-first search\n```\nfunction ITERATIVE-DEEPENDING-SEARCH(problem) returns a solution node or failure\n for depth = 0 to +infinity do:\n   result <- depth-limited-search(problem, depth)\n   if result not equal to cutoff then return result\n\nfunction Depth-Limited_search(problem, l) retuns a node or failure or cutoff:\n frontier <- LIFO(stack) with Node(problem.INITIAL) as an element\n result <- failure\n while not Is-Empty(frontier) do:\n   node <- pop(frontier)\n   if problem.Is-Goal(node.STATE) then return node\n   if Depth(node) < l then:\n     result <- cutoff\n    else if not IS-Cycle(node) do:\n      for each child in Expand(problem, node) do:\n        add child to frontier\n  return result\n```\n\n\n## Module 3 Lecture Notes\n\nProblem: Repeated states\\\nGraph search\\\n• Simple Mod from tree search: Check to see if a node has been visited\nbefore adding to search queue\\\n```\nfunction TREE-SEARCH(problem) returns a solution, or failure\ninitialize the frontier using the initial state of problem\nloop do\nif the frontier is empty then return failure\nchoose a leaf nose and remove it from the frontier\nif the node contains a goal state then return the corresponding solution\nexpand the chosen node, adding the resulting nodes to the frontier\n\nfunction GRAPH-SEARCH(problem) returns a solution, or failure\ninitialize the frontier using the initial state of problem\ninitialize the explored set to be empty\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution\nadd node to the explored set\nexpand the chosen node, adding the resulting nodes to the frontier\nonly if not in the frontier of explored set\n\n```\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "a proof by\n",
        "contradiction. Suppose the optimal path has cost C* but the algorithm returns a path with\n",
        "cost C > C *. Then there must be some node n which is on the optimal path and is\n",
        "unexpanded (because if all the nodes on the optimal path had been expanded, then we\n",
        "would have returned that optimal solution. So then, using the notation g*(n) to mean the\n",
        "cost of the optimal path from the start to n and h*(n) to mean the cost of the optimal path from n to the nearest goal, we have: f(n) > C* (otherwise would have been expanded)\\\\\n",
        "f(n) = g(n) + h(n)(by definition)\\\\\n",
        "f(n) = g*(n) + h(n) (n is optimal path)\\\\\n",
        "f(n) <= g*(n) + h*(n) (admissibility, h(n) < h*(n))\\\\\n",
        "f(n) <= C* (by definition, C* = g*(n) + h*(n))\\\\\n",
        "The first and last lines form a contradiction\\\\\n",
        "\\\\\n",
        "\n",
        "Consistency: A heuristic is consistent if, for every node and every successor of generated by an action: h(n) <= c(n, a, n') + h(n').\\\\\n",
        "This is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides \\\\\n",
        "\n",
        "with an approach called weighted A* search where we weight the heuristic value more heavily, giving us the evaluation function f(n)=g(n) + W*h(n)for some W > 1\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "The effect of heuristic accuracy on performance:\\\\\n",
        "One way to characterize the quality of a heuristic is the effective branching factor If the total number of nodes generated by A* for a particular problem N is and the solution depth d is then b* is the branching factor that a uniform tree of depth d would have to have in order to contain N+1 node\\\\\n",
        "N+1 = 1 + b* + (b*)^2 + ... + (b*)d\\\\\n",
        "\n",
        "Uninformed search methods have access only to the problem definition. Algorithms build a search tree in an attempt to find a solution. Algorithms differ based on which node they expand first:\\\\\n",
        "– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function. – BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity.\\\\\n",
        "– UNIFORM-COST SEARCH expands the node with lowest path cost, and is optimal for general action costs.\\\\\n",
        "– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound.\\\\\n",
        "– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth limits until a goal is found. It is complete when full cycle checking is done, optimal for unit action costs, has time complexity comparable to breadth-first search, and has linear space complexity.\\\\\n",
        "– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\\\\\n",
        "Informed search methods have access to a heuristic function that estimates the cost of a solution from They may have access to additional information such as pattern databases with solution costs.\\\\\n",
        "– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal but is often efficient.\\\\\n",
        "– A* SEARCH expands nodes with minimal A* is complete and optimal, provided that is admissible. The space complexity of A* is still an issue for many problems.\\\\\n",
        "– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\\\\\n",
        "– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and thus adresses the space complexity issue.\\\\\n",
        "– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A* runs out of memory.\\\\\n",
        "– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\\\\\n",
        "– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality\\\\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "1. Greedy Best First Search: select nodes for expansion with minimal evaluation function f(n) where f(n) is some function that includes estimate heurisitc h(n) of the remaining distance to goal\\\\\n",
        "f(n) = h(n)\\\\\n",
        "Manhatan distance: sbs(a.x - b.x) + abs(a.y - b.y)\n",
        "straight-line Euclidean distance heuristic: \n",
        "```\n",
        "def straight_line_heuristic(pointa, pointb):\n",
        "  #(x,y)\n",
        "  dx = pointa[0] - pointb[0]\n",
        "  dy = pointa[1] - pointb[1]\n",
        "  return math.sqrt((dx**2) + (dy**2))\n",
        "```\n",
        "```\n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = {}\n",
        "came_from[start] = None\n",
        "\n",
        "While not frontier.empty():\n",
        " current = frontier.get()\n",
        " if current == goal:\n",
        "   break;\n",
        "\n",
        " for next in graph.neighbours(current):\n",
        "   if next not in came_from:\n",
        "     priority = heuristic(goal, next)\n",
        "     frontier.put(next, priority)\n",
        "     came_from[next] = current\n",
        "```\n",
        "Not optimal and not complete(can stuck on loops)\\\\\n",
        "\n",
        "2. A*\\\\\n",
        "A heuristic h(n) is admissible if it never overestimates the cost to reach the goal; If h(n) is admissible, A* using Tree Search is optimal\\\\\n",
        "Heuristic functions\\\\\n",
        "A problem with fewer restrictions on the actions than the original is called a relaxed problem\\\\\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\\\\\n",
        "If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n) gives the shortest solution\\\\\n",
        "If the rules are relaxed so that a tile can move to any adjacent square, then hmd(n) gives the shortest solution\\\\\n",
        "Dominance: \\\\\n",
        "If h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1. So h2 is optimistic, but more accurate than h1.\\\\\n",
        "h*(n) - the (unachievable) Oracle heuristic: h*(n) = the true distance from the n to goal\\\\\n",
        "h*(n) dominates all other heuristics, hteleportation(n) is dominated by all heuristics\\\\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 66,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "509c9e5f-345c-4696-b538-ee9ae558b256"
      },
      "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": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \na proof by\ncontradiction. Suppose the optimal path has cost C* but the algorithm returns a path with\ncost C > C *. Then there must be some node n which is on the optimal path and is\nunexpanded (because if all the nodes on the optimal path had been expanded, then we\nwould have returned that optimal solution. So then, using the notation g*(n) to mean the\ncost of the optimal path from the start to n and h*(n) to mean the cost of the optimal path from n to the nearest goal, we have: f(n) > C* (otherwise would have been expanded)\\\nf(n) = g(n) + h(n)(by definition)\\\nf(n) = g*(n) + h(n) (n is optimal path)\\\nf(n) <= g*(n) + h*(n) (admissibility, h(n) < h*(n))\\\nf(n) <= C* (by definition, C* = g*(n) + h*(n))\\\nThe first and last lines form a contradiction\\\n\\\n\nConsistency: A heuristic is consistent if, for every node and every successor of generated by an action: h(n) <= c(n, a, n') + h(n').\\\nThis is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides \\\n\nwith an approach called weighted A* search where we weight the heuristic value more heavily, giving us the evaluation function f(n)=g(n) + W*h(n)for some W > 1\\\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe effect of heuristic accuracy on performance:\\\nOne way to characterize the quality of a heuristic is the effective branching factor If the total number of nodes generated by A* for a particular problem N is and the solution depth d is then b* is the branching factor that a uniform tree of depth d would have to have in order to contain N+1 node\\\nN+1 = 1 + b* + (b*)^2 + ... + (b*)d\\\n\nUninformed search methods have access only to the problem definition. Algorithms build a search tree in an attempt to find a solution. Algorithms differ based on which node they expand first:\\\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function. – BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity.\\\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is optimal for general action costs.\\\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound.\\\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth limits until a goal is found. It is complete when full cycle checking is done, optimal for unit action costs, has time complexity comparable to breadth-first search, and has linear space complexity.\\\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\\\nInformed search methods have access to a heuristic function that estimates the cost of a solution from They may have access to additional information such as pattern databases with solution costs.\\\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal but is often efficient.\\\n– A* SEARCH expands nodes with minimal A* is complete and optimal, provided that is admissible. The space complexity of A* is still an issue for many problems.\\\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\\\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and thus adresses the space complexity issue.\\\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A* runs out of memory.\\\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\\\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality\\\n\n\n## Module 4 Lecture Notes\n\n1. Greedy Best First Search: select nodes for expansion with minimal evaluation function f(n) where f(n) is some function that includes estimate heurisitc h(n) of the remaining distance to goal\\\nf(n) = h(n)\\\nManhatan distance: sbs(a.x - b.x) + abs(a.y - b.y)\nstraight-line Euclidean distance heuristic: \n```\ndef straight_line_heuristic(pointa, pointb):\n  #(x,y)\n  dx = pointa[0] - pointb[0]\n  dy = pointa[1] - pointb[1]\n  return math.sqrt((dx**2) + (dy**2))\n```\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = {}\ncame_from[start] = None\n\nWhile not frontier.empty():\n current = frontier.get()\n if current == goal:\n   break;\n\n for next in graph.neighbours(current):\n   if next not in came_from:\n     priority = heuristic(goal, next)\n     frontier.put(next, priority)\n     came_from[next] = current\n```\nNot optimal and not complete(can stuck on loops)\\\n\n2. A*\\\nA heuristic h(n) is admissible if it never overestimates the cost to reach the goal; If h(n) is admissible, A* using Tree Search is optimal\\\nHeuristic functions\\\nA problem with fewer restrictions on the actions than the original is called a relaxed problem\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\\\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n) gives the shortest solution\\\nIf the rules are relaxed so that a tile can move to any adjacent square, then hmd(n) gives the shortest solution\\\nDominance: \\\nIf h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1. So h2 is optimistic, but more accurate than h1.\\\nh*(n) - the (unachievable) Oracle heuristic: h*(n) = the true distance from the n to goal\\\nh*(n) dominates all other heuristics, hteleportation(n) is dominated by all heuristics\\\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\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",
        "A game can be formally defined with the following elements:\\\\\n",
        "(1)The initial state, which specifies how the game is set up at the start.\\\\\n",
        "(2)TO-MOVE :The player whose turn it is to move in state s.\\\\\n",
        "(3)Actions: The set of legal moves in state s.\\\\\n",
        "(4)The transition model, which defines the state resulting from taking action\\\\\n",
        "(5)A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\\\\\n",
        "(6) A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal state s.\\\\\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "```\n",
        "function Min-Search(game, state) returns an action:\n",
        "  player<- game.To-Move(state)\n",
        "  value, move <- Max-Value(game, state)\n",
        "  return move\n",
        "\n",
        "function Max-Value(game, state) returns a (utility, move) pair:\n",
        " if game.Is-Terminal(state) then return game.Utility(state, player), null\n",
        " v <- -infinite\n",
        " for each a in game.Actions(state) do:\n",
        "  v2, a2 <- Min-Value(game, game.Result(state,a))\n",
        "  if v2 > v then:\n",
        "    v, move <- v2, a\n",
        "  return v, move\n",
        "\n",
        "function Min-Value(game, state) returns a (utility, move) pair:\n",
        "  if game.Is-Terminal(state) then return game.Utility(state, player), null\n",
        "  v <-infinite\n",
        "  for each a in game.Actions(state) do:\n",
        "    v2, a2<- Max-Value(game, game.Result(state, a))\n",
        "    if v2 < v then:\n",
        "      v, move <- v2, a\n",
        "  return v, move\n",
        "```\n",
        "\n",
        "```\n",
        "function ALPHA-BETA-SEARCH(game, state) returns an action:\n",
        "  player <- game.To-Move(state)\n",
        "  value, move <- MAX-VALUE(game, state, -infinite, +infinite)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n",
        " if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n",
        " v <- -infinite\n",
        " for each a in game.ACTIONS(state) do:\n",
        "   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n",
        "   if v2 > v then:\n",
        "     v, move <- v2, a\n",
        "     alpha <- max(alpha, v)\n",
        "   if v >= beta:\n",
        "     return v, move\n",
        " return v, move\n",
        "\n",
        " function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n",
        " if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n",
        " v <- +infinite\n",
        " for each a in game.ACTIONS(state) do:\n",
        "   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n",
        "   if v2 < v then:\n",
        "     v, move <- v2, a\n",
        "     beta <- min(beta, v)\n",
        "   if v <= alpha:\n",
        "     return v, move\n",
        " return v, move\n",
        "\n",
        "```\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "Heuristic Alpha–Beta Tree Search (expected value)\\\\\n",
        "A heuristic evaluation function returns an estimate of the expected utility of state to player , just as the heuristic functions of return an estimate of the distance to the goal. For terminal states, it must be that Eval(s,p) = Utility(s,p)\n",
        "states, and for nonterminal the evaluation must be somewhere between a loss and a win: Utility(loss, p) <= Eval(s,p) <= Utility(win, p)\\\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Stochastic Games\\\\\n",
        "If the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will take , where is the number of distinct rolls.\\\\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "The agent’s preferences are captured by a utility function, , which assigns a single number to express the desirability of a state. \\\\\n",
        "The expected utility of an action given the evidence,, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs\\\\\n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility\\\\\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice. Estimating the probability distribution P(s) over possible states of the world, which folds into , requires perception,\n",
        "learning, knowledge representation, and inference.\\\\\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "1. Constraints on rational preferences：\\\\ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\\\\\n",
        "TRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to , then the agent must prefer A to C.\\\\CONTINUITY: If some lottery is between and in preference, then there is some probability for which the rational agent will be indifferent between getting for sure and the lottery that yields with probability and with probability 1-p.\\\\\n",
        "SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted A for in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\\\\\n",
        "MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A. and B. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for (and vice versa).\\\\\n",
        "DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule\\\\\n",
        "2. Rational preferences lead to utility:\\\\\n",
        "EXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(a) > U(b) if and only if A is preferred to B, and if and only if the agent is indifferent between A and B. \\\\\n",
        "EXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Decision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans— really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. The evidence suggests that humans are “predictably irrational” \\\\\n",
        "It seems that people have ambiguity aversion: gives you a chance of winning, while could be anywhere between 0 and . Similarly, gives you a chance, while could be anywhere between and . Most people elect the known probability rather than the unknown unknowns.\\\\\n",
        "Framing effect. Experiments show that people like a medical procedure that is described as having a “90% survival rate” about twice as much as one described as having a “10% death rate.\\\\\n",
        "People feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering a bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a bottle seem like a bargain. This is called the anchoring effect.\\\\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "1. Game Environment: MultiAgent, Static, Discrete(A finite set of percepts and actions), Fully Obeservable, Strategic \\\\\n",
        "2. While examining the children of a maximizer, if v of maximizer > beta, prune the rest of the children.\\\\\n",
        "   While examining the children of a minimizer, if v of minimizer < alpha, prune the rest of the children.\\\\\n",
        "3. Expectimax Search:\\\\\n",
        "Why wouldn’t we know what the result of an action will be? (1)Explicit randomness: rolling dice. (2)Unpredictable opponents: the opponent isn’t optimal. (3)Actions can fail: when moving a robot, wheels might slip\\\\\n",
        "Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\\\\\n",
        "o Expectimax search: \\\\\n",
        "compute the average score under optimal playMax nodes as in minimax search. Chance nodes are like min nodes but the outcome is uncertain.Calculate their expected utilities. I.e. take weighted average (expectation) of children\\\\\n",
        "```\n",
        "def value(state):\n",
        "  if the state is a terminal state: return the state's utility\n",
        "  if the next agent is MAX: return max-value(state)\n",
        "  if the nexr agent is EXP: return exp-value(state)\n",
        "\n",
        "def max-value(state):\n",
        "  initialize v = -infinity\n",
        "  for each successor of state:\n",
        "    v = max(v, value(successor))\n",
        "  return v\n",
        "\n",
        "def exp-value(state):\n",
        "  initilize v = 0\n",
        "  for each successor of state:\n",
        "    p = probability(successor)\n",
        "    v += p * value(successor)\n",
        "  return v\n",
        "```\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0ff4bd74-e66c-46d9-b3f3-1b100a191cd7"
      },
      "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": 69,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nA game can be formally defined with the following elements:\\\n(1)The initial state, which specifies how the game is set up at the start.\\\n(2)TO-MOVE :The player whose turn it is to move in state s.\\\n(3)Actions: The set of legal moves in state s.\\\n(4)The transition model, which defines the state resulting from taking action\\\n(5)A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\\\n(6) A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal state s.\\\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n```\nfunction Min-Search(game, state) returns an action:\n  player<- game.To-Move(state)\n  value, move <- Max-Value(game, state)\n  return move\n\nfunction Max-Value(game, state) returns a (utility, move) pair:\n if game.Is-Terminal(state) then return game.Utility(state, player), null\n v <- -infinite\n for each a in game.Actions(state) do:\n  v2, a2 <- Min-Value(game, game.Result(state,a))\n  if v2 > v then:\n    v, move <- v2, a\n  return v, move\n\nfunction Min-Value(game, state) returns a (utility, move) pair:\n  if game.Is-Terminal(state) then return game.Utility(state, player), null\n  v <-infinite\n  for each a in game.Actions(state) do:\n    v2, a2<- Max-Value(game, game.Result(state, a))\n    if v2 < v then:\n      v, move <- v2, a\n  return v, move\n```\n\n```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action:\n  player <- game.To-Move(state)\n  value, move <- MAX-VALUE(game, state, -infinite, +infinite)\n  return move\n\nfunction MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n v <- -infinite\n for each a in game.ACTIONS(state) do:\n   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n   if v2 > v then:\n     v, move <- v2, a\n     alpha <- max(alpha, v)\n   if v >= beta:\n     return v, move\n return v, move\n\n function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n v <- +infinite\n for each a in game.ACTIONS(state) do:\n   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n   if v2 < v then:\n     v, move <- v2, a\n     beta <- min(beta, v)\n   if v <= alpha:\n     return v, move\n return v, move\n\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nHeuristic Alpha–Beta Tree Search (expected value)\\\nA heuristic evaluation function returns an estimate of the expected utility of state to player , just as the heuristic functions of return an estimate of the distance to the goal. For terminal states, it must be that Eval(s,p) = Utility(s,p)\nstates, and for nonterminal the evaluation must be somewhere between a loss and a win: Utility(loss, p) <= Eval(s,p) <= Utility(win, p)\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic Games\\\nIf the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will take , where is the number of distinct rolls.\\\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s preferences are captured by a utility function, , which assigns a single number to express the desirability of a state. \\\nThe expected utility of an action given the evidence,, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs\\\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility\\\nThe MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice. Estimating the probability distribution P(s) over possible states of the world, which folds into , requires perception,\nlearning, knowledge representation, and inference.\\\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n1. Constraints on rational preferences：\\ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\\\nTRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to , then the agent must prefer A to C.\\CONTINUITY: If some lottery is between and in preference, then there is some probability for which the rational agent will be indifferent between getting for sure and the lottery that yields with probability and with probability 1-p.\\\nSUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted A for in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\\\nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, A. and B. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for (and vice versa).\\\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule\\\n2. Rational preferences lead to utility:\\\nEXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(a) > U(b) if and only if A is preferred to B, and if and only if the agent is indifferent between A and B. \\\nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\\\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans— really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. The evidence suggests that humans are “predictably irrational” \\\nIt seems that people have ambiguity aversion: gives you a chance of winning, while could be anywhere between 0 and . Similarly, gives you a chance, while could be anywhere between and . Most people elect the known probability rather than the unknown unknowns.\\\nFraming effect. Experiments show that people like a medical procedure that is described as having a “90% survival rate” about twice as much as one described as having a “10% death rate.\\\nPeople feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering a bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a bottle seem like a bargain. This is called the anchoring effect.\\\n\n\n\n## Module 5 Lecture Notes\n\n1. Game Environment: MultiAgent, Static, Discrete(A finite set of percepts and actions), Fully Obeservable, Strategic \\\n2. While examining the children of a maximizer, if v of maximizer > beta, prune the rest of the children.\\\n   While examining the children of a minimizer, if v of minimizer < alpha, prune the rest of the children.\\\n3. Expectimax Search:\\\nWhy wouldn’t we know what the result of an action will be? (1)Explicit randomness: rolling dice. (2)Unpredictable opponents: the opponent isn’t optimal. (3)Actions can fail: when moving a robot, wheels might slip\\\nValues should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\\\no Expectimax search: \\\ncompute the average score under optimal playMax nodes as in minimax search. Chance nodes are like min nodes but the outcome is uncertain.Calculate their expected utilities. I.e. take weighted average (expectation) of children\\\n```\ndef value(state):\n  if the state is a terminal state: return the state's utility\n  if the next agent is MAX: return max-value(state)\n  if the nexr agent is EXP: return exp-value(state)\n\ndef max-value(state):\n  initialize v = -infinity\n  for each successor of state:\n    v = max(v, value(successor))\n  return v\n\ndef exp-value(state):\n  initilize v = 0\n  for each successor of state:\n    p = probability(successor)\n    v += p * value(successor)\n  return v\n```\n\n\n \n\n## Module 5 Definitions\n* **Concept** - definition\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" 1. Node Consistency: A single variable is node-consitent if all the values in the variable's domain satisfy the variable's unary constraints.\\\n",
        " 2. Arc consistency: if every value in its domain satisfies the variables' binary constrains.\\\n",
        " AC-3: algorithm for enforcing arc consistency.\n",
        " ```\n",
        " function AC-3 returns flase if an inconsistency is found and true otherwise\n",
        "   queue <- a que of arcs, initially all the arcs in csp\n",
        "\n",
        "   while queue is not empty do:\n",
        "     (xi, xj) <- pop(queue)\n",
        "     if REVISE(csp, xi, xj) then:\n",
        "       if size of Di = 0 return false\n",
        "       for each xk in xi.neighbours - {xj} do:\n",
        "         add (xk, xi) to queue\n",
        "  return true\n",
        "\n",
        "  function REVISE(csp, xi, xj) return true iff we revise the domain of xi\n",
        "    revised <- false\n",
        "    for each x in Di do:\n",
        "      if no value y in Dj allows (x,y) to satisfy the constraint between xi and xj then:\n",
        "        delete x from Di\n",
        "        revised = true\n",
        "  return revised\n",
        " ```\n",
        " 3. path consistency: tightens the binary constraints by using implicit constraints that are inferred by lokking at triples of variables\\\\\n",
        " 4. A CSP is strongly -consistent if it is -consistent and is also -consistent, - consistent, all the way down to 1-consistent. \n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "```\n",
        "function backtracking-search(csp) returns a solution or failure\n",
        "  return backtrack(csp, {})\n",
        "\n",
        "function backtrack(csp, assignment) returns a solution or failure:\n",
        "    if assignment is complete then return assignment:\n",
        "    var <- Select-Unassigned-Variables(csp, assignment)\n",
        "    for each value in ORDER-DOMAIN-VALUES(csp, var, assignment)do:\n",
        "      if value is consistent with assignment then:\n",
        "        add {var = value} to assignment\n",
        "        inferences <- INFERENCE(csp, var, assignment)\n",
        "        if inferences not equal to failure then:\n",
        "          add inferences to csp\n",
        "          result <- backtrack(csp, assignment)\n",
        "          if result not equal to failure then return result\n",
        "          remove inferences from csp\n",
        "        remove {var = value} from assignment\n",
        "    return failure\n",
        "```\n",
        "IMPROVE backrtacking efficienncy:\\\\\n",
        "1. This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic. \\\n",
        "It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. \\\n",
        "If some variable has no legal values left, the MRV heuristic will select and failure will be detected immediately—avoiding pointless searches through other variables. \\\\\n",
        "\n",
        "2. the degree heuristic comes in handy. 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. can be useful as a tie-breaker\\\\\n",
        "3. Once a variable has been selected, the algorithm must decide on the order in which to examine its values. 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",
        "Inferences:\\\\\n",
        "1. forward checking\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" suppose each\n",
        "has variables from the total of variables, where is a constant. Then there are subproblems, each of which takes at most d^c work to solve, \\\n",
        "where is the size of the domain. Hence, the total work is d^c * n / c, which is linear in ; without the decomposition, the total work is d^n, which is exponential in .\\\\\n",
        "\n",
        "1. cutest conditioning:\\\\\n",
        "The first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\\\\\n",
        "\n",
        "2. tree decomposition:\\\\\n",
        "The second way to reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables. A tree decomposition must satisfy these three requirements:\n",
        "Every variable in the original problem appears in at least one of the tree nodes.\\\\\n",
        "If two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes.\\\\\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\\\\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "1. Planning vs Identification: CSP is special for identification problems\\\\\n",
        "2. CSP consists of: (1) Finite set of variables (2)Non-empty domain of possible value (3) finite set of constraints. \\\\\n",
        "Consistent: does not violate the constraints. Complete: when every variable is assigned a value\\\\\n",
        "3. Benefits: (1) Clean specification of many problems, generic goal, successor function & heuristics;CSP “knows” which variables violate a constraint And hence where to focus the search; Automatically prune off all branches that violate constraints\\\\\n",
        "4. Varieties of CSPs: (1) Discrete variables: finite domains: n variables, domain size d à O(dn) complete assignments//infinite domains: integers, strings, etc. e.g., job scheduling, variables are start/end days for each job//Continuous variables: start/end times for Hubble Space Telescope observations\n",
        "(2) Varieties of constraints: Unary constraints involve a single variable, Binary constraints involve pairs of variables,Higher-order constraints involve 3 or more variables,Preference (soft constraints).\\\\\n",
        "5. Constraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions. faster than forward checking\\\\\n",
        "6. Ac-3 time complexity: All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n2)\\\\\n",
        "o If there are d values, checking arc (i,j) takes O(d2 ) time\\\\\n",
        "o Each arc (i,j) can only be inserted into the queue d times. \\\\\n",
        "Worst case complexity: O(n2d3 )\\\\\n",
        "\n",
        "Given d values, checking arc (i,j) takes O(d2 ) time worst case\\\\\n",
        "\n",
        "In forward checking, whenever a variable X is assigned, we establish arc consistency for X. For each unassigned variable YY that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for XX.\\\\\n",
        "Tree decomposition. Whenever you have a cycle-cutset of size c, there is also a tree of width w<c+1, and it may be far smaller in some cases.\\\\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2ea47c18-d7e9-4d65-b662-68fd2e1d28da"
      },
      "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": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 1. Node Consistency: A single variable is node-consitent if all the values in the variable's domain satisfy the variable's unary constraints. 2. Arc consistency: if every value in its domain satisfies the variables' binary constrains. AC-3: algorithm for enforcing arc consistency.\n ```\n function AC-3 returns flase if an inconsistency is found and true otherwise\n   queue <- a que of arcs, initially all the arcs in csp\n\n   while queue is not empty do:\n     (xi, xj) <- pop(queue)\n     if REVISE(csp, xi, xj) then:\n       if size of Di = 0 return false\n       for each xk in xi.neighbours - {xj} do:\n         add (xk, xi) to queue\n  return true\n\n  function REVISE(csp, xi, xj) return true iff we revise the domain of xi\n    revised <- false\n    for each x in Di do:\n      if no value y in Dj allows (x,y) to satisfy the constraint between xi and xj then:\n        delete x from Di\n        revised = true\n  return revised\n ```\n 3. path consistency: tightens the binary constraints by using implicit constraints that are inferred by lokking at triples of variables\\\n 4. A CSP is strongly -consistent if it is -consistent and is also -consistent, - consistent, all the way down to 1-consistent. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n```\nfunction backtracking-search(csp) returns a solution or failure\n  return backtrack(csp, {})\n\nfunction backtrack(csp, assignment) returns a solution or failure:\n    if assignment is complete then return assignment:\n    var <- Select-Unassigned-Variables(csp, assignment)\n    for each value in ORDER-DOMAIN-VALUES(csp, var, assignment)do:\n      if value is consistent with assignment then:\n        add {var = value} to assignment\n        inferences <- INFERENCE(csp, var, assignment)\n        if inferences not equal to failure then:\n          add inferences to csp\n          result <- backtrack(csp, assignment)\n          if result not equal to failure then return result\n          remove inferences from csp\n        remove {var = value} from assignment\n    return failure\n```\nIMPROVE backrtacking efficienncy:\\\n1. This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic. It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If some variable has no legal values left, the MRV heuristic will select and failure will be detected immediately—avoiding pointless searches through other variables. \\\n\n2. the degree heuristic comes in handy. 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. can be useful as a tie-breaker\\\n3. Once a variable has been selected, the algorithm must decide on the order in which to examine its values. 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\nInferences:\\\n1. forward checking\n\n\n\n\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 suppose each\nhas variables from the total of variables, where is a constant. Then there are subproblems, each of which takes at most d^c work to solve, where is the size of the domain. Hence, the total work is d^c * n / c, which is linear in ; without the decomposition, the total work is d^n, which is exponential in .\\\n\n1. cutest conditioning:\\\nThe first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\\\n\n2. tree decomposition:\\\nThe second way to reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables. A tree decomposition must satisfy these three requirements:\nEvery variable in the original problem appears in at least one of the tree nodes.\\\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes.\\\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\\\n\n\n\n## Module 6 Lecture Notes\n \n1. Planning vs Identification: CSP is special for identification problems\\\n2. CSP consists of: (1) Finite set of variables (2)Non-empty domain of possible value (3) finite set of constraints. \\\nConsistent: does not violate the constraints. Complete: when every variable is assigned a value\\\n3. Benefits: (1) Clean specification of many problems, generic goal, successor function & heuristics;CSP “knows” which variables violate a constraint And hence where to focus the search; Automatically prune off all branches that violate constraints\\\n4. Varieties of CSPs: (1) Discrete variables: finite domains: n variables, domain size d à O(dn) complete assignments//infinite domains: integers, strings, etc. e.g., job scheduling, variables are start/end days for each job//Continuous variables: start/end times for Hubble Space Telescope observations\n(2) Varieties of constraints: Unary constraints involve a single variable, Binary constraints involve pairs of variables,Higher-order constraints involve 3 or more variables,Preference (soft constraints).\\\n5. Constraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions. faster than forward checking\\\n6. Ac-3 time complexity: All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n2)\\\no If there are d values, checking arc (i,j) takes O(d2 ) time\\\no Each arc (i,j) can only be inserted into the queue d times. \\\nWorst case complexity: O(n2d3 )\\\n\nGiven d values, checking arc (i,j) takes O(d2 ) time worst case\\\n\nIn forward checking, whenever a variable X is assigned, we establish arc consistency for X. For each unassigned variable YY that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for XX.\\\nTree decomposition. Whenever you have a cycle-cutset of size c, there is also a tree of width w<c+1, and it may be far smaller in some cases.\\\n\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 = \"\"\"\n",
        "A KB contains a set of sentence that are written in a knowledge representation\n",
        "language. The sentence contains some assertion about the world.\\\\\n",
        "Axioms – a sentence that is given\\\\\n",
        "Derived sentences – a new sentence that is derived from others sentences. The process of deriving new sentences from old sentences is called inference.\\\\\n",
        "A KB can initially contain some background information about the world, and a\n",
        "knowledge-based agent can add to the information in the KB through its observations\n",
        "of the world.\\\\\n",
        "\n",
        "entailment is the idea that a sentence follows logically from another sentence.\\\\\n",
        "This means that alpha is more specific, or stronger than, β. For instances, β could mean\n",
        "that “The agent is a robot” and alpha could mean “The agent is an astromech”.\\\\\n",
        "\n",
        "Entailment can be applied to derive conclusions, which is the process of logical\n",
        "inference.\\\\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 681
        },
        "outputId": "cd6376b7-1c7d-49b9-b401-ff0e2016b93b"
      },
      "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": 75,
      "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\nA KB contains a set of sentence that are written in a knowledge representation\nlanguage. The sentence contains some assertion about the world.\\\nAxioms – a sentence that is given\\\nDerived sentences – a new sentence that is derived from others sentences. The process of deriving new sentences from old sentences is called inference.\\\nA KB can initially contain some background information about the world, and a\nknowledge-based agent can add to the information in the KB through its observations\nof the world.\\\n\nentailment is the idea that a sentence follows logically from another sentence.\\\nThis means that alpha is more specific, or stronger than, β. For instances, β could mean\nthat “The agent is a robot” and alpha could mean “The agent is an astromech”.\\\n\nEntailment can be applied to derive conclusions, which is the process of logical\ninference.\\\n\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/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "4a7b404d-18d7-4a0e-cc60-fac75f3f6d5d"
      },
      "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": 74,
      "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\n weak AI—the idea that machines could act as if they were intelligent—and strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\\\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent’s percept sequence is the complete history of everything the agent has ever perceived.\\\nan agent’s behavior is described by the agent function that maps any given percept sequence to an action.\\\nthe agent function for an artificial agent will be implemented by an agent program\\\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nRational:\\\nThe performance measure that defines the criterion of success. The agent’s prior knowledge of the environment.\\\nThe actions that the agent can perform.\\\nThe agent’s percept sequence to date.\\\n\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE:\\\nSINGLE-AGENT VS. MULTIAGEN\\\nDeterministic vs. nondeterministic:If the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic\\\nEPISODIC VS. SEQUENTIA: In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then\nperforms a single action\\\nSTATIC VS. DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent\\\nDISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent.\\\nKNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. In a known environment\\\n\n \n\n## AIMA 2.4 The Structure of Agents\n\nThe job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture、、\nthe difference between the agent program, which takes the current percept as input, and the agent function, which may depend on the entire percept history.\\\n\n\n## Module 1 Lecture Notes\n\nAgents include humans, robots, softbots, thermostats, …\\\nA rational agent is an agent that perceives its environment and and behaves rationally\\\nThe basic premise is that aggregate social behavior results from the behavior of individual actors, each of whom is making their individual decisions.\\\nperformance measure:\\\nAn objective criterion for success of an agent's behavior\\ given the evidence provided by the percept sequence.\\It is better to design performance measures according to what you want to be\nachieved in the environment, rather than how you think the agent should behave.\\\nRational Agent:\\\nFor each possible percept sequence P, a rational agent selects an action a that maximizes the expected value of its performance measure\\\n\\\nTask Environment:\\\nperformance measure/environment/actuators/sensors\\\nGoal of AI practitioner who designs rational agents: \\\ngiven a PEAS task environment, 1)Construct agent function f that maximizes the expected value of the performance measure, 2)Design an agent program that\nimplements f on a particular architecture\\\n\\\nA simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history\\\n\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\nSlicing: Return Copy of a Subsequence\\\nreverse() sort() are in place, sorted(list) returns a copy\\\n\nDefault Values for Arguments：\\\nThese arguments are optional when the function is called\\\nNon-default argument should always precede default arguments;\\\nFunctions can be called with arguments out of order \\\nmyfun(c=43, b=1, a=2)\\\n\\\nSuppose you want to accept a variable number of non-keyword arguments to your\nfunction.\\\ndef print_everything(*args):\\\n  args is a tuple of arguments passed to the fn\\\nprint(args)\\\n\\\ndef print_keyword_args(**kwargs):\\\n# kwargs is a dict of the keyword args passed to the fn\\\nprint(kwargs)\\\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\")\\\n\nPython iterators do not have a hasnext() method!\\\nJust catch the StopIteration exception\\\n\nBenefits of using generators\\\nLess code than writing a standard iterator\\\nMaintains local state automatically\\\nValues are computed one at a time, as they’re needed\\\nAvoids storing the entire sequence in memory\\\nGood for aggregating (summing, counting) items. One pass.\\\nCrucial for infinite sequences\\\nBad if you need to inspect the individual values\\\n\ng = merge([2,4], [1, 3, 5])\\\nwhile True:\\\ntry:\\\nprint(g.__next__())\\\nexcept StopIteration:\\\nprint('Done’)\\\nbreak\\\n\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\nBefore an agent can start searching, a well-defined problem must be formulated.\\\nA problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\\\nThe environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\\\nSearch algorithms generally treat states and actions as atomic, without any internal \nstructure (although we introduced features of states when it came time to do learning).\\ Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\\\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n\nWe say that Arad is a repeated state in the search tree, generated in this case by a cycle (also known as a loopy path). So even though the state space has only 20 states, the complete search tree is infinite because there is no limit to how often one can traverse a loop.\\\nA cycle is a special case of a redundant path. \\\nFirst, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state\\\nSecond, we can not worry about repeating the past. There are some problem formulations where it is rare or impossible for two paths to reach the same state. \\\nThird, we can compromise and check for cycles, but not for redundant paths in general.\\\n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n```\nBFS(problem) returns a solution node or failure:\n node <- Node(problem.INITIAL)\n if problem.IS-GOAL(node.State) return node\n frontier <- queue\n reached <- {problem.INITIAL}\n while frontier:\n   node <- Pop(frontier)\n   for each child in Expand(problem, node) do:\n     s <- child.STATE\n     if problem.IS-GOAL(s) then return child\n     if s is not reached then \n    add s to reached\n    add child to frontier\nreturn failure\n```\n\ndepth-first tree-like search takes time proportional to the number of states, and has memory complexity of only O(bm)\nwhere is the branching factor and is the maximum depth of the tree. Some problems that would require exabytes of memory with breadth-first search can be handled with only kilobytes using depth-first search\n```\nfunction ITERATIVE-DEEPENDING-SEARCH(problem) returns a solution node or failure\n for depth = 0 to +infinity do:\n   result <- depth-limited-search(problem, depth)\n   if result not equal to cutoff then return result\n\nfunction Depth-Limited_search(problem, l) retuns a node or failure or cutoff:\n frontier <- LIFO(stack) with Node(problem.INITIAL) as an element\n result <- failure\n while not Is-Empty(frontier) do:\n   node <- pop(frontier)\n   if problem.Is-Goal(node.STATE) then return node\n   if Depth(node) < l then:\n     result <- cutoff\n    else if not IS-Cycle(node) do:\n      for each child in Expand(problem, node) do:\n        add child to frontier\n  return result\n```\n\n\n## Module 3 Lecture Notes\n\nProblem: Repeated states\\\nGraph search\\\n• Simple Mod from tree search: Check to see if a node has been visited\nbefore adding to search queue\\\n```\nfunction TREE-SEARCH(problem) returns a solution, or failure\ninitialize the frontier using the initial state of problem\nloop do\nif the frontier is empty then return failure\nchoose a leaf nose and remove it from the frontier\nif the node contains a goal state then return the corresponding solution\nexpand the chosen node, adding the resulting nodes to the frontier\n\nfunction GRAPH-SEARCH(problem) returns a solution, or failure\ninitialize the frontier using the initial state of problem\ninitialize the explored set to be empty\nloop do\nif the frontier is empty then return failure\nchoose a leaf node and remove it from the frontier\nif the node contains a goal state then return the corresponding solution\nadd node to the explored set\nexpand the chosen node, adding the resulting nodes to the frontier\nonly if not in the frontier of explored set\n\n```\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \na proof by\ncontradiction. Suppose the optimal path has cost C* but the algorithm returns a path with\ncost C > C *. Then there must be some node n which is on the optimal path and is\nunexpanded (because if all the nodes on the optimal path had been expanded, then we\nwould have returned that optimal solution. So then, using the notation g*(n) to mean the\ncost of the optimal path from the start to n and h*(n) to mean the cost of the optimal path from n to the nearest goal, we have: f(n) > C* (otherwise would have been expanded)\\\nf(n) = g(n) + h(n)(by definition)\\\nf(n) = g*(n) + h(n) (n is optimal path)\\\nf(n) <= g*(n) + h*(n) (admissibility, h(n) < h*(n))\\\nf(n) <= C* (by definition, C* = g*(n) + h*(n))\\\nThe first and last lines form a contradiction\\\n\\\n\nConsistency: A heuristic is consistent if, for every node and every successor of generated by an action: h(n) <= c(n, a, n') + h(n').\\\nThis is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides \\\n\nwith an approach called weighted A* search where we weight the heuristic value more heavily, giving us the evaluation function f(n)=g(n) + W*h(n)for some W > 1\\\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe effect of heuristic accuracy on performance:\\\nOne way to characterize the quality of a heuristic is the effective branching factor If the total number of nodes generated by A* for a particular problem N is and the solution depth d is then b* is the branching factor that a uniform tree of depth d would have to have in order to contain N+1 node\\\nN+1 = 1 + b* + (b*)^2 + ... + (b*)d\\\n\nUninformed search methods have access only to the problem definition. Algorithms build a search tree in an attempt to find a solution. Algorithms differ based on which node they expand first:\\\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function. – BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity.\\\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is optimal for general action costs.\\\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound.\\\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth limits until a goal is found. It is complete when full cycle checking is done, optimal for unit action costs, has time complexity comparable to breadth-first search, and has linear space complexity.\\\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\\\nInformed search methods have access to a heuristic function that estimates the cost of a solution from They may have access to additional information such as pattern databases with solution costs.\\\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal but is often efficient.\\\n– A* SEARCH expands nodes with minimal A* is complete and optimal, provided that is admissible. The space complexity of A* is still an issue for many problems.\\\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\\\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and thus adresses the space complexity issue.\\\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A* runs out of memory.\\\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\\\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality\\\n\n\n## Module 4 Lecture Notes\n\n1. Greedy Best First Search: select nodes for expansion with minimal evaluation function f(n) where f(n) is some function that includes estimate heurisitc h(n) of the remaining distance to goal\\\nf(n) = h(n)\\\nManhatan distance: sbs(a.x - b.x) + abs(a.y - b.y)\nstraight-line Euclidean distance heuristic: \n```\ndef straight_line_heuristic(pointa, pointb):\n  #(x,y)\n  dx = pointa[0] - pointb[0]\n  dy = pointa[1] - pointb[1]\n  return math.sqrt((dx**2) + (dy**2))\n```\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = {}\ncame_from[start] = None\n\nWhile not frontier.empty():\n current = frontier.get()\n if current == goal:\n   break;\n\n for next in graph.neighbours(current):\n   if next not in came_from:\n     priority = heuristic(goal, next)\n     frontier.put(next, priority)\n     came_from[next] = current\n```\nNot optimal and not complete(can stuck on loops)\\\n\n2. A*\\\nA heuristic h(n) is admissible if it never overestimates the cost to reach the goal; If h(n) is admissible, A* using Tree Search is optimal\\\nHeuristic functions\\\nA problem with fewer restrictions on the actions than the original is called a relaxed problem\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\\\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n) gives the shortest solution\\\nIf the rules are relaxed so that a tile can move to any adjacent square, then hmd(n) gives the shortest solution\\\nDominance: \\\nIf h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1. So h2 is optimistic, but more accurate than h1.\\\nh*(n) - the (unachievable) Oracle heuristic: h*(n) = the true distance from the n to goal\\\nh*(n) dominates all other heuristics, hteleportation(n) is dominated by all heuristics\\\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nA game can be formally defined with the following elements:\\\n(1)The initial state, which specifies how the game is set up at the start.\\\n(2)TO-MOVE :The player whose turn it is to move in state s.\\\n(3)Actions: The set of legal moves in state s.\\\n(4)The transition model, which defines the state resulting from taking action\\\n(5)A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\\\n(6) A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal state s.\\\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n```\nfunction Min-Search(game, state) returns an action:\n  player<- game.To-Move(state)\n  value, move <- Max-Value(game, state)\n  return move\n\nfunction Max-Value(game, state) returns a (utility, move) pair:\n if game.Is-Terminal(state) then return game.Utility(state, player), null\n v <- -infinite\n for each a in game.Actions(state) do:\n  v2, a2 <- Min-Value(game, game.Result(state,a))\n  if v2 > v then:\n    v, move <- v2, a\n  return v, move\n\nfunction Min-Value(game, state) returns a (utility, move) pair:\n  if game.Is-Terminal(state) then return game.Utility(state, player), null\n  v <-infinite\n  for each a in game.Actions(state) do:\n    v2, a2<- Max-Value(game, game.Result(state, a))\n    if v2 < v then:\n      v, move <- v2, a\n  return v, move\n```\n\n```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action:\n  player <- game.To-Move(state)\n  value, move <- MAX-VALUE(game, state, -infinite, +infinite)\n  return move\n\nfunction MAX-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n v <- -infinite\n for each a in game.ACTIONS(state) do:\n   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n   if v2 > v then:\n     v, move <- v2, a\n     alpha <- max(alpha, v)\n   if v >= beta:\n     return v, move\n return v, move\n\n function MIN-VALUE(game, state, alpha, beta) returns a (utility, move) pair:\n if game.IS-TERMINAL(state) then return game.Utility(state, player), null\n v <- +infinite\n for each a in game.ACTIONS(state) do:\n   v2, a2 <- MIN-VALUE(game, game.RESULT(state, a), alpha, beta)\n   if v2 < v then:\n     v, move <- v2, a\n     beta <- min(beta, v)\n   if v <= alpha:\n     return v, move\n return v, move\n\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nHeuristic Alpha–Beta Tree Search (expected value)\\\nA heuristic evaluation function returns an estimate of the expected utility of state to player , just as the heuristic functions of return an estimate of the distance to the goal. For terminal states, it must be that Eval(s,p) = Utility(s,p)\nstates, and for nonterminal the evaluation must be somewhere between a loss and a win: Utility(loss, p) <= Eval(s,p) <= Utility(win, p)\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic Games\\\nIf the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will take , where is the number of distinct rolls.\\\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s preferences are captured by a utility function, , which assigns a single number to express the desirability of a state. \\\nThe expected utility of an action given the evidence,, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs\\\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility\\\nThe MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice. Estimating the probability distribution P(s) over possible states of the world, which folds into , requires perception,\nlearning, knowledge representation, and inference.\\\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n1. Constraints on rational preferences：\\ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\\\nTRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to , then the agent must prefer A to C.\\CONTINUITY: If some lottery is between and in preference, then there is some probability for which the rational agent will be indifferent between getting for sure and the lottery that yields with probability and with probability 1-p.\\\nSUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted A for in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\\\nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, A. and B. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for (and vice versa).\\\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule\\\n2. Rational preferences lead to utility:\\\nEXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(a) > U(b) if and only if A is preferred to B, and if and only if the agent is indifferent between A and B. \\\nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\\\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans— really do act. The application of economic theory would be greatly enhanced if the two coincided, but there appears to be some experimental evidence to the contrary. The evidence suggests that humans are “predictably irrational” \\\nIt seems that people have ambiguity aversion: gives you a chance of winning, while could be anywhere between 0 and . Similarly, gives you a chance, while could be anywhere between and . Most people elect the known probability rather than the unknown unknowns.\\\nFraming effect. Experiments show that people like a medical procedure that is described as having a “90% survival rate” about twice as much as one described as having a “10% death rate.\\\nPeople feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering a bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a bottle seem like a bargain. This is called the anchoring effect.\\\n\n\n\n## Module 5 Lecture Notes\n\n1. Game Environment: MultiAgent, Static, Discrete(A finite set of percepts and actions), Fully Obeservable, Strategic \\\n2. While examining the children of a maximizer, if v of maximizer > beta, prune the rest of the children.\\\n   While examining the children of a minimizer, if v of minimizer < alpha, prune the rest of the children.\\\n3. Expectimax Search:\\\nWhy wouldn’t we know what the result of an action will be? (1)Explicit randomness: rolling dice. (2)Unpredictable opponents: the opponent isn’t optimal. (3)Actions can fail: when moving a robot, wheels might slip\\\nValues should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\\\no Expectimax search: \\\ncompute the average score under optimal playMax nodes as in minimax search. Chance nodes are like min nodes but the outcome is uncertain.Calculate their expected utilities. I.e. take weighted average (expectation) of children\\\n```\ndef value(state):\n  if the state is a terminal state: return the state's utility\n  if the next agent is MAX: return max-value(state)\n  if the nexr agent is EXP: return exp-value(state)\n\ndef max-value(state):\n  initialize v = -infinity\n  for each successor of state:\n    v = max(v, value(successor))\n  return v\n\ndef exp-value(state):\n  initilize v = 0\n  for each successor of state:\n    p = probability(successor)\n    v += p * value(successor)\n  return v\n```\n\n\n \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 1. Node Consistency: A single variable is node-consitent if all the values in the variable's domain satisfy the variable's unary constraints. 2. Arc consistency: if every value in its domain satisfies the variables' binary constrains. AC-3: algorithm for enforcing arc consistency.\n ```\n function AC-3 returns flase if an inconsistency is found and true otherwise\n   queue <- a que of arcs, initially all the arcs in csp\n\n   while queue is not empty do:\n     (xi, xj) <- pop(queue)\n     if REVISE(csp, xi, xj) then:\n       if size of Di = 0 return false\n       for each xk in xi.neighbours - {xj} do:\n         add (xk, xi) to queue\n  return true\n\n  function REVISE(csp, xi, xj) return true iff we revise the domain of xi\n    revised <- false\n    for each x in Di do:\n      if no value y in Dj allows (x,y) to satisfy the constraint between xi and xj then:\n        delete x from Di\n        revised = true\n  return revised\n ```\n 3. path consistency: tightens the binary constraints by using implicit constraints that are inferred by lokking at triples of variables\\\n 4. A CSP is strongly -consistent if it is -consistent and is also -consistent, - consistent, all the way down to 1-consistent. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n```\nfunction backtracking-search(csp) returns a solution or failure\n  return backtrack(csp, {})\n\nfunction backtrack(csp, assignment) returns a solution or failure:\n    if assignment is complete then return assignment:\n    var <- Select-Unassigned-Variables(csp, assignment)\n    for each value in ORDER-DOMAIN-VALUES(csp, var, assignment)do:\n      if value is consistent with assignment then:\n        add {var = value} to assignment\n        inferences <- INFERENCE(csp, var, assignment)\n        if inferences not equal to failure then:\n          add inferences to csp\n          result <- backtrack(csp, assignment)\n          if result not equal to failure then return result\n          remove inferences from csp\n        remove {var = value} from assignment\n    return failure\n```\nIMPROVE backrtacking efficienncy:\\\n1. This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic. It also has been called the “most constrained variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If some variable has no legal values left, the MRV heuristic will select and failure will be detected immediately—avoiding pointless searches through other variables. \\\n\n2. the degree heuristic comes in handy. 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. can be useful as a tie-breaker\\\n3. Once a variable has been selected, the algorithm must decide on the order in which to examine its values. 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\nInferences:\\\n1. forward checking\n\n\n\n\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 suppose each\nhas variables from the total of variables, where is a constant. Then there are subproblems, each of which takes at most d^c work to solve, where is the size of the domain. Hence, the total work is d^c * n / c, which is linear in ; without the decomposition, the total work is d^n, which is exponential in .\\\n\n1. cutest conditioning:\\\nThe first way to reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree.\\\n\n2. tree decomposition:\\\nThe second way to reduce a constraint graph to a tree is based on constructing a tree decomposition of the constraint graph: a transformation of the original graph into a tree where each node in the tree consists of a set of variables. A tree decomposition must satisfy these three requirements:\nEvery variable in the original problem appears in at least one of the tree nodes.\\\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes.\\\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\\\n\n\n\n## Module 6 Lecture Notes\n \n1. Planning vs Identification: CSP is special for identification problems\\\n2. CSP consists of: (1) Finite set of variables (2)Non-empty domain of possible value (3) finite set of constraints. \\\nConsistent: does not violate the constraints. Complete: when every variable is assigned a value\\\n3. Benefits: (1) Clean specification of many problems, generic goal, successor function & heuristics;CSP “knows” which variables violate a constraint And hence where to focus the search; Automatically prune off all branches that violate constraints\\\n4. Varieties of CSPs: (1) Discrete variables: finite domains: n variables, domain size d à O(dn) complete assignments//infinite domains: integers, strings, etc. e.g., job scheduling, variables are start/end days for each job//Continuous variables: start/end times for Hubble Space Telescope observations\n(2) Varieties of constraints: Unary constraints involve a single variable, Binary constraints involve pairs of variables,Higher-order constraints involve 3 or more variables,Preference (soft constraints).\\\n5. Constraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions. faster than forward checking\\\n6. Ac-3 time complexity: All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n2)\\\no If there are d values, checking arc (i,j) takes O(d2 ) time\\\no Each arc (i,j) can only be inserted into the queue d times. \\\nWorst case complexity: O(n2d3 )\\\n\nGiven d values, checking arc (i,j) takes O(d2 ) time worst case\\\n\nIn forward checking, whenever a variable X is assigned, we establish arc consistency for X. For each unassigned variable YY that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for XX.\\\nTree decomposition. Whenever you have a cycle-cutset of size c, there is also a tree of width w<c+1, and it may be far smaller in some cases.\\\n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n 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\nA KB contains a set of sentence that are written in a knowledge representation\nlanguage. The sentence contains some assertion about the world.\\\nAxioms – a sentence that is given\\\nDerived sentences – a new sentence that is derived from others sentences. The process of deriving new sentences from old sentences is called inference.\\\nA KB can initially contain some background information about the world, and a\nknowledge-based agent can add to the information in the KB through its observations\nof the world.\\\n\nentailment is the idea that a sentence follows logically from another sentence.\\\nThis means that alpha is more specific, or stronger than, β. For instances, β could mean\nthat “The agent is a robot” and alpha could mean “The agent is an astromech”.\\\n\nEntailment can be applied to derive conclusions, which is the process of logical\ninference.\\\n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}