{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "47629f6d-93bd-43b9-cea9-4f329a9b9c32"
      },
      "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": 41,
      "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": "51a55c75-69ed-4df3-9126-6cd7b30f2209"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Acting humanly: The Turing test: NLP, knowledge representation, automated reasoning, maching learning. Total TT: + computer vision Robotics \\\n",
        "Thinking humanly, acting rationally The rational agent approach, thinking rationally (probability and logic).\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly, rationality is not the same as perfection \\\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "agent = architecture+program\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "condition–action rule simple reflex agent, It acts according to a rule whose condition matches the current state, as defined by the percept. \n",
        "\n",
        "Escape from infinite loops is possible if the agent can randomize its actions \n",
        "\n",
        "model-based agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved Internal state \\\n",
        "aspects of the current state\n",
        "\n",
        "knowledge about “how the world works”-- transition model\n",
        "some information about how the state of the world is reflected in the agent’s percepts -- sensor model\n",
        "\n",
        "goal based agent\n",
        "\n",
        "Utility-based agents: utility function is essentially an internalization of the performance measure, How happy I will be\n",
        "in such a state\n",
        "\n",
        "Learning agents: problem generator: suggesting actions that will lead to new and informative experiences; learning element: making improvements; performance element: selecting external actions\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "1.1 Turing test A human evaluator would judge text-based conversations between a human and a machine designed to \\\n",
        "generate human-like responses. If the evaluator cannot reliably tell the machine from the human, the machine passes the test. The test \\\n",
        "results do not depend on the ability to give correct answers to questions, only how closely one's answers resemble those a human would give. \\\n",
        "\n",
        "John Searle The Chinese Room Daniel Dennett brain in a vat \\\n",
        "OBSERVABLE AGENTS# DETERMINISTIC EPISODIC/Sequential STATIC DISCRETE UNKNOWN OUTCOMES\n",
        "When something behavior can best be described as having its own performance measure, then we should consider it to be an agent. \\\n",
        "\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",
        "\"rational agent\": \"acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\",\n",
        "\"percept\" : \"the agent’s perceptual inputs at any given instance\",\n",
        "'performance measure':' An objective criterion for success of an agents behavior given the evidence provided by the percept sequence.',\n",
        "'reflex agent': 'selects an action based on the current percept, and ignores the rest of the percept history',\n",
        "'problem-solving agent': \"consider a sequence of actions that form a path to a goal state, search\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ddb21518-67ab-4acf-c194-1ab236d39702"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nActing humanly: The Turing test: NLP, knowledge representation, automated reasoning, maching learning. Total TT: + computer vision Robotics Thinking humanly, acting rationally The rational agent approach, thinking rationally (probability and logic).\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nAn omniscient agent knows the actual outcome of its actions and can act accordingly, rationality is not the same as perfection  \n\n## AIMA 2.3 The Nature of Environments\n \nagent = architecture+program\n \n\n## AIMA 2.4 The Structure of Agents\n \ncondition–action rule simple reflex agent, It acts according to a rule whose condition matches the current state, as defined by the percept. \n\nEscape from infinite loops is possible if the agent can randomize its actions \n\nmodel-based agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved Internal state aspects of the current state\n\nknowledge about “how the world works”-- transition model\nsome information about how the state of the world is reflected in the agent’s percepts -- sensor model\n\ngoal based agent\n\nUtility-based agents: utility function is essentially an internalization of the performance measure, How happy I will be\nin such a state\n\nLearning agents: problem generator: suggesting actions that will lead to new and informative experiences; learning element: making improvements; performance element: selecting external actions\n\n\n \n\n## Module 1 Lecture Notes\n \n1.1 Turing test A human evaluator would judge text-based conversations between a human and a machine designed to generate human-like responses. If the evaluator cannot reliably tell the machine from the human, the machine passes the test. The test results do not depend on the ability to give correct answers to questions, only how closely one's answers resemble those a human would give. \nJohn Searle The Chinese Room Daniel Dennett brain in a vat OBSERVABLE AGENTS# DETERMINISTIC EPISODIC/Sequential STATIC DISCRETE UNKNOWN OUTCOMES\nWhen something behavior can best be described as having its own performance measure, then we should consider it to be an agent. \n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Percept** - the agent’s perceptual inputs at any given instance\n* **Performance measure** -  An objective criterion for success of an agents behavior given the evidence provided by the percept sequence.\n* **Reflex agent** - selects an action based on the current percept, and ignores the rest of the percept history\n* **Problem-solving agent** - consider a sequence of actions that form a path to a goal state, search\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",
        "strong, dynamic typing\n",
        "print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n",
        "strings are immutable\n",
        "lists are mutable, use y = x[:] to get a (shallow) copy of any sequence\n",
        "\n",
        "# Sequence Types:\n",
        "Tuple\n",
        "▪ A simple immutable ordered sequence of items\n",
        "▪ Immutable: a tuple cannot be modified once created\n",
        "▪ Items can be of mixed types, including collection types\n",
        "o Strings\n",
        "▪ Immutable\n",
        "▪ Regular strings are Unicode and use 2-byte characters (Regular strings in\n",
        "Python 2 use 8-bit characters)\n",
        "o List\n",
        "▪ Mutable ordered sequence of items of mixed types\n",
        "\n",
        "```\n",
        ">>> a = [1, 2, 3]\n",
        ">>> b = ['a', 'b', 'c', 'd']\n",
        ">>> list(zip(a, b))\n",
        "[(1, 'a'), (2, 'b'), (3, 'c')]\n",
        "\n",
        ">>> list(zip(\"foo\", \"bar\"))\n",
        "[('f', 'b'), ('o', 'a'), ('o', 'r')]\n",
        "\n",
        ">>> d = {'user' : 'R2D2', 'pswd': 1234}\n",
        ">>> d['user']\n",
        ">>> d['pswd'] = 'thx1138' # Assigning to an existing key replaces its value.\n",
        "\n",
        ">>> d.keys() # List of current keys\n",
        "dict_keys(['user', 'p', 'i’])\n",
        ">>> d.values() # List of current values.\n",
        "dict_values(['R2D2', 1234, 34])\n",
        ">>> d.items() # List of item tuples.\n",
        "dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n",
        "\n",
        "from collections import defaultdict\n",
        "d = defaultdict(str)\n",
        "d['a']\n",
        "\"\"\n",
        "from collections import Counter\n",
        "d = Counter()\n",
        "d['a']\n",
        "0\n",
        "d['dog'] += 10\n",
        "d['dog']\n",
        "10\n",
        "```\n",
        "Multiple Return Values is tuple\n",
        "\n",
        "Non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n",
        "```\n",
        "def myfun(a, b, c):\n",
        ">>> myfun(a=2, b=3, 5) # error\n",
        "```\n",
        "\n",
        "# *args non-keyword at variable number\n",
        "```\n",
        "def print_everything(*args):\n",
        "print(args)\n",
        "print_everything('a', 'b', 'c’)\n",
        "('a', 'b', 'c’)\n",
        "lst = ['a', 'b', 'c’]\n",
        "print_everything(*lst)\n",
        "('a', 'b', 'c')\n",
        "```\n",
        "# **kwargs a variable number of keyword arguments\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",
        "{'first_name': 'John', 'last_name': 'Doe’}\n",
        "my_dict = {'first_name': 'Wei', 'last_name': 'Xu’}\n",
        "print_keyword_args(**my_dict)\n",
        "{'first_name': 'Wei', 'last_name': 'Xu'}\n",
        "\n",
        "[i for i in [1, 2, 3, 4, 5] if is_even(i)]\n",
        "\n",
        "# class and subclass\n",
        "\n",
        "```\n",
        " __init__\n",
        "class AI_Student(Student):\n",
        "def __init__(self, name, dept):\n",
        "Student.__init__(self, name, dept)\n",
        "```\n",
        "# magic function\n",
        "```\n",
        "__init__: The constructor for the class.\n",
        "__len__ : Define how len( obj ) works.\n",
        "__copy__: Define how to copy a class.\n",
        "__cmp__ : Define how == works for class.\n",
        "__add__ : Define how + works for class\n",
        "__neg__ : Define how unary negation works for class\n",
        "\n",
        "class A(object):\n",
        "def foo(self):\n",
        "print('Foo!')\n",
        "class B(object):\n",
        "def foo(self):\n",
        "print('Foo?')\n",
        "def bar(self):\n",
        "print('Bar!')\n",
        "class C(A, B):\n",
        "def foobar(self):\n",
        "super().foo() # Foo!\n",
        "super().bar() # Bar!\n",
        "\n",
        "if __name__ == '__main__':\n",
        "\n",
        "# for loop\n",
        "lst1 = [1, 2, 3]\n",
        "lst2 = [2, 3, 4]\n",
        "lst3 = [3, 4, 5]\n",
        "res = [(x, y, z) for x in lst1 if x < 2 \\\n",
        "for y in lst2 \\\n",
        "for z in lst3 if x + y + z < 8]\n",
        "# Both value of res: [(1, 2, 3), (1, 2, 4), (1, 3, 3)]\n",
        "\n",
        "lst1 = [('a', 1), ('b', 2), ('c', 'hi’)]\n",
        "lst2 = ['x', 'a', 6]\n",
        "d = { k: v for k,v in lst1 }\n",
        "s = { x for x in lst2 }\n",
        "# Both value of d: {'a': 1, 'b': 2, 'c': 'hi’}\n",
        "# Both value of d: {'x', 'a', 6}\n",
        "```\n",
        "## iterator\n",
        "```\n",
        ">>> i = iter(k)\n",
        ">>> next(i)\n",
        "1\n",
        ">>> i.__next__()\n",
        "2\n",
        ">>> i.next()\n",
        "\n",
        "o for <item> in <iterable>:\n",
        "<statements>\n",
        "o First line is just syntactic sugar for: ▪ 1. Initialize: Call <iterable>.__iter__() to create an iterator\n",
        "o Each iteration: ▪ 2. Call iterator.__next__() and bind <item> ▪ 2a. Catch StopIteration exceptions\n",
        "o To be iterable: has __iter__ method ▪ which returns an iterator obj\n",
        "o To be iterator: has __next__ method ▪ which throws StopIteration when done\n",
        "\n",
        "```\n",
        "## Benefits of using generators\n",
        "\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",
        "o Generators are iterators (with __next()__ method)\n",
        "o Creating Generators: yield\n",
        "▪ Functions that contain the yield keyword automatically return a generator when called\n",
        "\n",
        "```\n",
        ">>> def f(n):\n",
        "... yield n\n",
        "... yield n+1\n",
        "...\n",
        ">>>\n",
        ">>> type(f)\n",
        "<class 'function'>\n",
        ">>> type(f(5))\n",
        "<class 'generator'>\n",
        ">>> [i for i in f(6)]\n",
        "[6, 7]\n",
        "\n",
        ">>> gen = f(5) # no need to say f(5).__iter__()\n",
        ">>> gen\n",
        "<generator object f at 0x1008cc9b0>\n",
        ">>> gen.__next__()\n",
        "5\n",
        ">>> next(gen)\n",
        "6\n",
        ">>> gen.__next__() # error\n",
        "\n",
        "# Problem: merge two sorted lists, using the output as a stream (i.e. not storing it).\n",
        "def merge(l, r):\n",
        "llen = len(l)\n",
        "rlen = len(r)\n",
        "i = 0\n",
        "j = 0\n",
        "while i < llen or j < rlen:\n",
        "if j == rlen or (i < llen and l[i] < r[j]):\n",
        "yield l[i]\n",
        "i += 1\n",
        "else:\n",
        "yield r[j]\n",
        "j += 1\n",
        "\n",
        "[x for x in merge([1,3,5],[2,4])]\n",
        "[1, 2, 3, 4, 5]\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",
        "sum(x for x in xrange(10**8) if x%5==0)\n",
        "999999950000000L\n",
        "Than version this which creates the whole list first\n",
        "sum([x for x in xrange(10**8) if x%5==0])\n",
        "999999950000000L\n",
        "\n",
        "import math\n",
        "math.sqrt(9)\n",
        "3.0\n",
        "from math import sqrt\n",
        "sqrt(9)\n",
        "# Not as good to do this:\n",
        "from math import *\n",
        "sqrt(9) # unclear where function defined\n",
        "# create alias or nickname\n",
        "import numpy as np\n",
        "\n",
        "# priority Q sorted\n",
        "import queue as Q\n",
        "q = Q.PriorityQueue()\n",
        "q.put((10, \"Prepare to die.\"))\n",
        "q.put((1, \"Hello,\"))\n",
        "q.put((5, \"Diego Montoya.\"))\n",
        "q.put((2, \"My name is\"))\n",
        "while not q.empty():\n",
        "print(q.get()[1])\n",
        "Hello,\n",
        "My name is\n",
        "Diego Montoya.\n",
        "\n",
        "# the digraph constructor\n",
        "class DiGraph:\n",
        "def __init__(self, edges):\n",
        "self.adj = {}\n",
        "for u, v in edges:\n",
        "if u not in self.adj:\n",
        "self.adj[u] = [v]\n",
        "else:\n",
        "self.adj[u].append(v)\n",
        "d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n",
        "print(d.adj)\n",
        "{1: [2, 3], 2: [4], 4: [3, 1]} \n",
        "\n",
        "# the magic method\n",
        "class DiGraph:\n",
        "def __str__(self):\n",
        "return '\\n'.join(['%s -> %s'% (u,v) \\\n",
        "for u in self.adj \\\n",
        "for v in self.adj[u]])\n",
        "d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n",
        "print(d)\n",
        "1 -> 2\n",
        "1 -> 3\n",
        "2 -> 4\n",
        "4 -> 3\n",
        "4 -> 1\n",
        "\n",
        "# search method yield\n",
        "class DiGraph:\n",
        "def search(self, u, visited):\n",
        "# If we haven't visited this node...\n",
        "if u not in visited:\n",
        "yield u # yield it\n",
        "visited.add(u) # and remember we've visited it now.\n",
        "# Then, if there are any adjacent nodes...\n",
        "if u in self.adj:\n",
        "for v in self.adj[u]: # for each adjacent node...\n",
        "# search for all nodes reachable from *it*...\n",
        "for w in self.search(v, visited):\n",
        "# and yield each one.\n",
        "yield w\n",
        "\n",
        "d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n",
        "[v for v in d.search(1, set())]\n",
        "[1, 2, 4, 3]\n",
        "```\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "55cb5d30-b2a7-4ddf-8980-67d4560c391b"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nstrong, dynamic typing\nprint(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\nstrings are immutable\nlists are mutable, use y = x[:] to get a (shallow) copy of any sequence\n\n# Sequence Types:\nTuple\n▪ A simple immutable ordered sequence of items\n▪ Immutable: a tuple cannot be modified once created\n▪ Items can be of mixed types, including collection types\no Strings\n▪ Immutable\n▪ Regular strings are Unicode and use 2-byte characters (Regular strings in\nPython 2 use 8-bit characters)\no List\n▪ Mutable ordered sequence of items of mixed types\n\n```\n>>> a = [1, 2, 3]\n>>> b = ['a', 'b', 'c', 'd']\n>>> list(zip(a, b))\n[(1, 'a'), (2, 'b'), (3, 'c')]\n\n>>> list(zip(\"foo\", \"bar\"))\n[('f', 'b'), ('o', 'a'), ('o', 'r')]\n\n>>> d = {'user' : 'R2D2', 'pswd': 1234}\n>>> d['user']\n>>> d['pswd'] = 'thx1138' # Assigning to an existing key replaces its value.\n\n>>> d.keys() # List of current keys\ndict_keys(['user', 'p', 'i’])\n>>> d.values() # List of current values.\ndict_values(['R2D2', 1234, 34])\n>>> d.items() # List of item tuples.\ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n\nfrom collections import defaultdict\nd = defaultdict(str)\nd['a']\n\"\"\nfrom collections import Counter\nd = Counter()\nd['a']\n0\nd['dog'] += 10\nd['dog']\n10\n```\nMultiple Return Values is tuple\n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError\n```\ndef myfun(a, b, c):\n>>> myfun(a=2, b=3, 5) # error\n```\n\n# *args non-keyword at variable number\n```\ndef print_everything(*args):\nprint(args)\nprint_everything('a', 'b', 'c’)\n('a', 'b', 'c’)\nlst = ['a', 'b', 'c’]\nprint_everything(*lst)\n('a', 'b', 'c')\n```\n# **kwargs a variable number of keyword arguments\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{'first_name': 'John', 'last_name': 'Doe’}\nmy_dict = {'first_name': 'Wei', 'last_name': 'Xu’}\nprint_keyword_args(**my_dict)\n{'first_name': 'Wei', 'last_name': 'Xu'}\n\n[i for i in [1, 2, 3, 4, 5] if is_even(i)]\n\n# class and subclass\n\n```\n __init__\nclass AI_Student(Student):\ndef __init__(self, name, dept):\nStudent.__init__(self, name, dept)\n```\n# magic function\n```\n__init__: The constructor for the class.\n__len__ : Define how len( obj ) works.\n__copy__: Define how to copy a class.\n__cmp__ : Define how == works for class.\n__add__ : Define how + works for class\n__neg__ : Define how unary negation works for class\n\nclass A(object):\ndef foo(self):\nprint('Foo!')\nclass B(object):\ndef foo(self):\nprint('Foo?')\ndef bar(self):\nprint('Bar!')\nclass C(A, B):\ndef foobar(self):\nsuper().foo() # Foo!\nsuper().bar() # Bar!\n\nif __name__ == '__main__':\n\n# for loop\nlst1 = [1, 2, 3]\nlst2 = [2, 3, 4]\nlst3 = [3, 4, 5]\nres = [(x, y, z) for x in lst1 if x < 2 for y in lst2 for z in lst3 if x + y + z < 8]\n# Both value of res: [(1, 2, 3), (1, 2, 4), (1, 3, 3)]\n\nlst1 = [('a', 1), ('b', 2), ('c', 'hi’)]\nlst2 = ['x', 'a', 6]\nd = { k: v for k,v in lst1 }\ns = { x for x in lst2 }\n# Both value of d: {'a': 1, 'b': 2, 'c': 'hi’}\n# Both value of d: {'x', 'a', 6}\n```\n## iterator\n```\n>>> i = iter(k)\n>>> next(i)\n1\n>>> i.__next__()\n2\n>>> i.next()\n\no for <item> in <iterable>:\n<statements>\no First line is just syntactic sugar for: ▪ 1. Initialize: Call <iterable>.__iter__() to create an iterator\no Each iteration: ▪ 2. Call iterator.__next__() and bind <item> ▪ 2a. Catch StopIteration exceptions\no To be iterable: has __iter__ method ▪ which returns an iterator obj\no To be iterator: has __next__ method ▪ which throws StopIteration when done\n\n```\n## Benefits of using generators\n\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\no Generators are iterators (with __next()__ method)\no Creating Generators: yield\n▪ Functions that contain the yield keyword automatically return a generator when called\n\n```\n>>> def f(n):\n... yield n\n... yield n+1\n...\n>>>\n>>> type(f)\n<class 'function'>\n>>> type(f(5))\n<class 'generator'>\n>>> [i for i in f(6)]\n[6, 7]\n\n>>> gen = f(5) # no need to say f(5).__iter__()\n>>> gen\n<generator object f at 0x1008cc9b0>\n>>> gen.__next__()\n5\n>>> next(gen)\n6\n>>> gen.__next__() # error\n\n# Problem: merge two sorted lists, using the output as a stream (i.e. not storing it).\ndef merge(l, r):\nllen = len(l)\nrlen = len(r)\ni = 0\nj = 0\nwhile i < llen or j < rlen:\nif j == rlen or (i < llen and l[i] < r[j]):\nyield l[i]\ni += 1\nelse:\nyield r[j]\nj += 1\n\n[x for x in merge([1,3,5],[2,4])]\n[1, 2, 3, 4, 5]\n\ng = merge([2,4], [1, 3, 5])\nwhile True:\ntry:\nprint(g.__next__())\nexcept StopIteration:\nprint('Done’)\nbreak\n\nsum(x for x in xrange(10**8) if x%5==0)\n999999950000000L\nThan version this which creates the whole list first\nsum([x for x in xrange(10**8) if x%5==0])\n999999950000000L\n\nimport math\nmath.sqrt(9)\n3.0\nfrom math import sqrt\nsqrt(9)\n# Not as good to do this:\nfrom math import *\nsqrt(9) # unclear where function defined\n# create alias or nickname\nimport numpy as np\n\n# priority Q sorted\nimport queue as Q\nq = Q.PriorityQueue()\nq.put((10, \"Prepare to die.\"))\nq.put((1, \"Hello,\"))\nq.put((5, \"Diego Montoya.\"))\nq.put((2, \"My name is\"))\nwhile not q.empty():\nprint(q.get()[1])\nHello,\nMy name is\nDiego Montoya.\n\n# the digraph constructor\nclass DiGraph:\ndef __init__(self, edges):\nself.adj = {}\nfor u, v in edges:\nif u not in self.adj:\nself.adj[u] = [v]\nelse:\nself.adj[u].append(v)\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\nprint(d.adj)\n{1: [2, 3], 2: [4], 4: [3, 1]} \n\n# the magic method\nclass DiGraph:\ndef __str__(self):\nreturn '\n'.join(['%s -> %s'% (u,v) for u in self.adj for v in self.adj[u]])\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\nprint(d)\n1 -> 2\n1 -> 3\n2 -> 4\n4 -> 3\n4 -> 1\n\n# search method yield\nclass DiGraph:\ndef search(self, u, visited):\n# If we haven't visited this node...\nif u not in visited:\nyield u # yield it\nvisited.add(u) # and remember we've visited it now.\n# Then, if there are any adjacent nodes...\nif u in self.adj:\nfor v in self.adj[u]: # for each adjacent node...\n# search for all nodes reachable from *it*...\nfor w in self.search(v, visited):\n# and yield each one.\nyield w\n\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n[v for v in d.search(1, set())]\n[1, 2, 4, 3]\n```\n\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",
        "A transition model, which describes what each action does. RESULT(s, a) returns the Transition model\n",
        "state that results from doing action a in state s. For example,\n",
        "RESULT(Arad; ToZerind) = Zerind \n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "Touring problems describe a set of locations that must be visited, rather than a single\n",
        "goal destination. The traveling salesperson problem (TSP) is a touring problem in which\n",
        "every city on a map must be visited. The aim is to find a tour with cost < C \n",
        "\n",
        "A VLSI layout problem requires positioning millions of components and connections on\n",
        "a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\n",
        "manufacturing yield. cell layout and channel routing\n",
        "\n",
        "Robot navigation is a generalization of the route-finding problem described earlier.\n",
        "Rather than following distinct paths (such as the roads in Romania), a robot can roam around,\n",
        "in effect making its own paths.\n",
        "\n",
        "Automatic assembly sequencing Minimizing the amount of manual human\n",
        "labor on the assembly line can produce significant savings in time and cost. In assembly\n",
        "problems, the aim is to find an order in which to assemble the parts of some object. protein design, in which the goal is to find a sequence of amino acids that will fold into a\n",
        "three-dimensional protein with the right properties\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "best-first search, in which we choose a node, n, with minimum value of some Best- first search evaluation function, f (n).\n",
        "\n",
        "• node.STATE: the state to which the node corresponds;\n",
        "• node.PARENT: the node in the tree that generated this node;\n",
        "• node.ACTION: the action that was applied to the parent’s state to generate this node;\n",
        "• node.PATH-COST: the total cost of the path from the initial state to this node. g(node)\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "bidirectional search simultaneously\n",
        "searches forward from the initial state and backwards from the goal state(s), hoping that the\n",
        "two searches will meet. The motivation is that bd=2+bd=2 is much less than bd (e.g., 50,000\n",
        "times less when b=d=10).\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "The properties of the task environments change the types of solutions that we need.\n",
        "If an environment is:\n",
        "• Fully observable\n",
        "• Deterministic\n",
        "• Known environment\n",
        "The solution to any problem in such an environment is a fixed sequence of actions.\n",
        "In environments that are\n",
        "• Partially observable or\n",
        "• Nondeterministic\n",
        "The solution must recommend different future actions depending on the what\n",
        "percepts it receives. This could be in the form of a branching strategy.\n",
        "\n",
        "# formulate a search problem\n",
        "1. States: a set S\n",
        "2. An initial state si\n",
        "∈ S\n",
        "3. Actions: a set A\n",
        "∀ s Actions(s) = the set of actions that can be executed in s, that are applicable in s.\n",
        "4. Transition Model: ∀ s∀ a∈Actions(s) Result(s, a) → sr\n",
        "sr is called a successor of s\n",
        "{si }∪ Successors(si )* = state space\n",
        "5. Path cost (Performance Measure): Must be additive, e.g. sum of distances, number of\n",
        "actions executed, …\n",
        "c(x,a,y) is the step cost, assumed ≥ 0\n",
        "• (where action a goes from state x to state y)\n",
        "6. Goal test: Goal(s)\n",
        "Can be implicit, e.g. checkmate(s)\n",
        "s is a goal state if Goal(s) is true\n",
        "\n",
        "Vacuum World With n cells, there are n*2^n states\n",
        "\n",
        "A solution is a sequence of actions from the initial state to a goal\n",
        "state.\n",
        "\n",
        "Optimal Solution: A solution is optimal if no solution has a lower\n",
        "path cost.\n",
        "\n",
        "Decide:\n",
        "Which properties matter & how to represent\n",
        "• Initial State, Goal State, Possible Intermediate States\n",
        "Which actions are possible & how to represent\n",
        "• Operator Set: Actions and Transition Model\n",
        "Which action is next\n",
        "• Path Cost Function\n",
        "\n",
        "\n",
        "State space: the set of all states reachable from the initial state by any\n",
        "sequence of actions\n",
        "• When several operators can apply to each state, this gets large very quickly\n",
        "• Might be a proper subset of the set of configurations\n",
        "Path: a sequence of actions leading from one state sj to another state sk\n",
        "Frontier: those states that are available for expanding (for applying legal\n",
        "actions to)\n",
        "Solution: a path from the initial state si to a state sf that satisfies the goal test\n",
        "17\n",
        "\n",
        "** tree search\n",
        "```\n",
        "function TREE-SEARCH(problem, strategy) return a solution or failure\n",
        "  Initialize frontier to the initial state of the problem\n",
        "do\n",
        "  if the frontier is empty then return failure\n",
        "choose leaf node for expansion according to strategy & remove from frontier\n",
        "  if node contains goal state then return solution\n",
        "  else expand the node and add resulting nodes to the frontier\n",
        "```\n",
        "** graph search\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",
        "A state is a (representation of a) physical configuration\n",
        "A node is a data structure constituting part of a search tree\n",
        "• Also includes parent, children, depth, path cost g(x)\n",
        "• Here node= <state, parent-node, children,\n",
        "action, path-cost, depth>\n",
        "\n",
        "** search strategies\n",
        "Review: Strategy = order of tree expansion\n",
        "• Implemented by different queue structures (LIFO, FIFO, priority)\n",
        "\n",
        "Use depth-first if\n",
        "• Space is restricted\n",
        "• There are many possible solutions with long paths and wrong paths are usually\n",
        "terminated quickly\n",
        "• Search can be fine-tuned quickly\n",
        "Use breadth-first if\n",
        "• Possible infinite paths\n",
        "• Some solutions have short paths\n",
        "• Can quickly discard unlikely paths\n",
        "\n",
        "Breadth first search \n",
        "\n",
        "function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n",
        "  node NODE(problem.INITIAL)\n",
        "  if problem.IS-GOAL(node.STATE) then return node\n",
        "  frontier a FIFO queue, with node as an element\n",
        "  reached {problem.INITIAL}\n",
        "  while not IS-EMPTY(frontier) do\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 in reached then\n",
        "      add s to reached\n",
        "      add child to frontier\n",
        "return failure\n",
        "\n",
        "```\n",
        "frontier = Queue()\n",
        "frontier.put(start )\n",
        "reached = set()\n",
        "reached.add(start)\n",
        "\n",
        "while not frontier.empty():\n",
        "   current = frontier.get()\n",
        "   for next in graph.neighbors(current):\n",
        "      if next not in reached:\n",
        "         frontier.put(next)\n",
        "         reached.add(next)\n",
        "```\n",
        "\n",
        "function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure\n",
        "node <- a node with STATE = problem.INITIAL-STATE, PATH-COST=0\n",
        "if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\n",
        "frontier <- a FIFO queue with node as the only element\n",
        "loop do\n",
        "if EMPTY?(frontier) then return failure\n",
        "node <- POP(frontier) // chooses the shallowest node in frontier\n",
        "add node.STATE to explored\n",
        "for each action in problem.ACTIONS(node.STATE) do\n",
        "child <- CHILD-NODE(problem, node, action)\n",
        "if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)\n",
        "frontier <- INSERT(child, frontier)\n",
        "\n",
        "function EXPAND(problem, node) yields nodes\n",
        "  s node.STATE\n",
        "  for each action in problem.ACTIONS(s) do\n",
        "    s0 problem.RESULT(s, action)\n",
        "    cost node.PATH-COST + problem.ACTION-COST(s, action, s0)\n",
        "    yield NODE(STATE=s0, PARENT=node, ACTION=action, PATH-COST=cost)\n",
        "\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",
        "'Uninformed search': 'All non-goal nodes in frontier look equally good',\n",
        "'Informed search': 'Some non-goal nodes can be ranked above others.'\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d2ed4158-fe5e-49a5-b2f3-070da8a1976c"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nA transition model, which describes what each action does. RESULT(s, a) returns the Transition model\nstate that results from doing action a in state s. For example,\nRESULT(Arad; ToZerind) = Zerind \n \n\n## AIMA Chapter 3.2 Example Problems\n \nTouring problems describe a set of locations that must be visited, rather than a single\ngoal destination. The traveling salesperson problem (TSP) is a touring problem in which\nevery city on a map must be visited. The aim is to find a tour with cost < C \n\nA VLSI layout problem requires positioning millions of components and connections on\na chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\nmanufacturing yield. cell layout and channel routing\n\nRobot navigation is a generalization of the route-finding problem described earlier.\nRather than following distinct paths (such as the roads in Romania), a robot can roam around,\nin effect making its own paths.\n\nAutomatic assembly sequencing Minimizing the amount of manual human\nlabor on the assembly line can produce significant savings in time and cost. In assembly\nproblems, the aim is to find an order in which to assemble the parts of some object. protein design, in which the goal is to find a sequence of amino acids that will fold into a\nthree-dimensional protein with the right properties\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nbest-first search, in which we choose a node, n, with minimum value of some Best- first search evaluation function, f (n).\n\n• node.STATE: the state to which the node corresponds;\n• node.PARENT: the node in the tree that generated this node;\n• node.ACTION: the action that was applied to the parent’s state to generate this node;\n• node.PATH-COST: the total cost of the path from the initial state to this node. g(node)\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nbidirectional search simultaneously\nsearches forward from the initial state and backwards from the goal state(s), hoping that the\ntwo searches will meet. The motivation is that bd=2+bd=2 is much less than bd (e.g., 50,000\ntimes less when b=d=10).\n \n\n## Module 3 Lecture Notes\n \nThe properties of the task environments change the types of solutions that we need.\nIf an environment is:\n• Fully observable\n• Deterministic\n• Known environment\nThe solution to any problem in such an environment is a fixed sequence of actions.\nIn environments that are\n• Partially observable or\n• Nondeterministic\nThe solution must recommend different future actions depending on the what\npercepts it receives. This could be in the form of a branching strategy.\n\n# formulate a search problem\n1. States: a set S\n2. An initial state si\n∈ S\n3. Actions: a set A\n∀ s Actions(s) = the set of actions that can be executed in s, that are applicable in s.\n4. Transition Model: ∀ s∀ a∈Actions(s) Result(s, a) → sr\nsr is called a successor of s\n{si }∪ Successors(si )* = state space\n5. Path cost (Performance Measure): Must be additive, e.g. sum of distances, number of\nactions executed, …\nc(x,a,y) is the step cost, assumed ≥ 0\n• (where action a goes from state x to state y)\n6. Goal test: Goal(s)\nCan be implicit, e.g. checkmate(s)\ns is a goal state if Goal(s) is true\n\nVacuum World With n cells, there are n*2^n states\n\nA solution is a sequence of actions from the initial state to a goal\nstate.\n\nOptimal Solution: A solution is optimal if no solution has a lower\npath cost.\n\nDecide:\nWhich properties matter & how to represent\n• Initial State, Goal State, Possible Intermediate States\nWhich actions are possible & how to represent\n• Operator Set: Actions and Transition Model\nWhich action is next\n• Path Cost Function\n\n\nState space: the set of all states reachable from the initial state by any\nsequence of actions\n• When several operators can apply to each state, this gets large very quickly\n• Might be a proper subset of the set of configurations\nPath: a sequence of actions leading from one state sj to another state sk\nFrontier: those states that are available for expanding (for applying legal\nactions to)\nSolution: a path from the initial state si to a state sf that satisfies the goal test\n17\n\n** tree search\n```\nfunction TREE-SEARCH(problem, strategy) return a solution or failure\n  Initialize frontier to the initial state of the problem\ndo\n  if the frontier is empty then return failure\nchoose leaf node for expansion according to strategy & remove from frontier\n  if node contains goal state then return solution\n  else expand the node and add resulting nodes to the frontier\n```\n** graph search\n```\nfunction 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\nloop 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```\nA state is a (representation of a) physical configuration\nA node is a data structure constituting part of a search tree\n• Also includes parent, children, depth, path cost g(x)\n• Here node= <state, parent-node, children,\naction, path-cost, depth>\n\n** search strategies\nReview: Strategy = order of tree expansion\n• Implemented by different queue structures (LIFO, FIFO, priority)\n\nUse depth-first if\n• Space is restricted\n• There are many possible solutions with long paths and wrong paths are usually\nterminated quickly\n• Search can be fine-tuned quickly\nUse breadth-first if\n• Possible infinite paths\n• Some solutions have short paths\n• Can quickly discard unlikely paths\n\nBreadth first search \n\nfunction BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n  node NODE(problem.INITIAL)\n  if problem.IS-GOAL(node.STATE) then return node\n  frontier a FIFO queue, with node as an element\n  reached {problem.INITIAL}\n  while not IS-EMPTY(frontier) do\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 in reached then\n      add s to reached\n      add child to frontier\nreturn failure\n\n```\nfrontier = Queue()\nfrontier.put(start )\nreached = set()\nreached.add(start)\n\nwhile not frontier.empty():\n   current = frontier.get()\n   for next in graph.neighbors(current):\n      if next not in reached:\n         frontier.put(next)\n         reached.add(next)\n```\n\nfunction BREADTH-FIRST-SEARCH(problem) returns a solution, or failure\nnode <- a node with STATE = problem.INITIAL-STATE, PATH-COST=0\nif problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\nfrontier <- a FIFO queue with node as the only element\nloop do\nif EMPTY?(frontier) then return failure\nnode <- POP(frontier) // chooses the shallowest node in frontier\nadd node.STATE to explored\nfor each action in problem.ACTIONS(node.STATE) do\nchild <- CHILD-NODE(problem, node, action)\nif problem.GOAL-TEST(child.STATE) then return SOLUTION(child)\nfrontier <- INSERT(child, frontier)\n\nfunction EXPAND(problem, node) yields nodes\n  s node.STATE\n  for each action in problem.ACTIONS(s) do\n    s0 problem.RESULT(s, action)\n    cost node.PATH-COST + problem.ACTION-COST(s, action, s0)\n    yield NODE(STATE=s0, PARENT=node, ACTION=action, PATH-COST=cost)\n\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Uninformed search** - All non-goal nodes in frontier look equally good\n* **Informed search** - Some non-goal nodes can be ranked above others.\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  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
        "The concept of pruning—eliminating possibilities from consideration without having to examine them\n",
        "\n",
        "detour index, which is Detour index a multiplier applied to the straight-line distance to account for the typical curvature of roads\n",
        "\n",
        "weighted A  search where we weight the heuristic value more heavily, giving us the Weighted A  search evaluation function f (n) = g(n)+W  h(n), for someW > 1.\n",
        "\n",
        "Satis cing search: Inadmissible heuristics and weighted A \n",
        "\n",
        "The main issue with A  is its use of memory\n",
        "Iterative-deepening A  search (IDA ) is to A  what iterative-deepening search is to Iterative-deepening\n",
        "A  search depth-first: IDA  gives us the benefits of A  without the requirement to keep all reached\n",
        "states in memory, at a cost of visiting some states multiple times.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "** Uniform-cost search (UCS)\n",
        "o Extension of BF-search:\n",
        "▪ Expand node with lowest path cost\n",
        "o Implementation:\n",
        "▪ frontier = priority queue ordered by g(n)\n",
        "o Subtle but significant difference from BFS:\n",
        "▪ Tests if a node is a goal state when it is selected for expansion, not when it is\n",
        "added to the frontier.\n",
        "▪ Updates a node on the frontier if a better path to the same state is found.\n",
        "▪ So always enqueues a node before checking whether it is a goal.\n",
        "```\n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = dict()\n",
        "cost_so_far = dict()\n",
        "came_from[start] = None\n",
        "cost_so_far[start] = 0\n",
        "\n",
        "while not frontier.empty():\n",
        "   current = frontier.get()\n",
        "\n",
        "   if current == goal:\n",
        "      break\n",
        "   \n",
        "   for next in graph.neighbors(current):\n",
        "      new_cost = cost_so_far[current] + graph.cost(current, next)\n",
        "      if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
        "         cost_so_far[next] = new_cost\n",
        "         priority = new_cost\n",
        "         frontier.put(next, priority)\n",
        "         came_from[next] = current\n",
        "```\n",
        "\n",
        "\n",
        "**Best-first search: node selected for expansion based on an evaluation function f(n)\n",
        "✔ f(n) includes estimate of distance to goal (new idea!)\n",
        "o Implementation: Sort frontier queue by this new f(n).\n",
        "▪ Special cases: greedy search, and A* search\n",
        "\n",
        "\n",
        "**A heuristic function h(n) takes a state n and returns an estimate of the distance from n to the goal.\n",
        "\n",
        "** Greedy best-first search: f(n) = h(n)\n",
        "```\n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = dict()\n",
        "came_from[start] = None\n",
        "\n",
        "while not frontier.empty():\n",
        "   current = frontier.get()\n",
        "\n",
        "   if current == goal:\n",
        "      break\n",
        "   \n",
        "   for next in graph.neighbors(current):\n",
        "      if next not in came_from:\n",
        "         priority = heuristic(goal, next)\n",
        "         frontier.put(next, priority)\n",
        "         came_from[next] = current\n",
        "\n",
        "def heuristic(a, b):\n",
        "   # Manhattan distance on a square grid\n",
        "   return abs(a.x - b.x) + abs(a.y - b.y)\n",
        "\n",
        "```\n",
        "Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs\n",
        "\n",
        "Inadmissible (pessimistic) heuristics break optimality by trapping good plans on the frontier\n",
        "\n",
        "For the 8-puzzle: hoop(n) = number of out of place tiles\n",
        "hmd(n) = total Manhattan distance (i.e., # of moves from desired location of each tile)\n",
        "\n",
        "A problem with fewer restrictions on the actions than the original is called a relaxed\n",
        "problem\n",
        "\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
        "original problem\n",
        "\n",
        "If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\n",
        "gives the shortest solution\n",
        "\n",
        "If the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\n",
        "gives the shortest solution\n",
        "\n",
        "Cost of an exact solution to a relaxed problem (fewer restrictions on operator)\n",
        "Constraints on Full Problem:\n",
        "A tile can move from square A to square B if A is adjacent to B and B is blank.\n",
        "• Constraints on relaxed problems:\n",
        "• A tile can move from square A to square B if A is adjacent to B. (hmd)\n",
        "• A tile can move from square A to square B if B is blank.\n",
        "• A tile can move from square A to square B. (hoop)\n",
        "\n",
        "If h2(n) ≥ h1(n) for all n (both admissible)\n",
        "• then h2 dominates h1\n",
        "So h2 is optimistic, but more accurate than h1\n",
        "• h2 is therefore better for search\n",
        "• Notice: hmd dominates hoop\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "568aa72c-c616-47c5-cb5b-cf21c9ecd203"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nA  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\nThe concept of pruning—eliminating possibilities from consideration without having to examine them\n\ndetour index, which is Detour index a multiplier applied to the straight-line distance to account for the typical curvature of roads\n\nweighted A  search where we weight the heuristic value more heavily, giving us the Weighted A  search evaluation function f (n) = g(n)+W  h(n), for someW > 1.\n\nSatis cing search: Inadmissible heuristics and weighted A \n\nThe main issue with A  is its use of memory\nIterative-deepening A  search (IDA ) is to A  what iterative-deepening search is to Iterative-deepening\nA  search depth-first: IDA  gives us the benefits of A  without the requirement to keep all reached\nstates in memory, at a cost of visiting some states multiple times.\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n \n** Uniform-cost search (UCS)\no Extension of BF-search:\n▪ Expand node with lowest path cost\no Implementation:\n▪ frontier = priority queue ordered by g(n)\no Subtle but significant difference from BFS:\n▪ Tests if a node is a goal state when it is selected for expansion, not when it is\nadded to the frontier.\n▪ Updates a node on the frontier if a better path to the same state is found.\n▪ So always enqueues a node before checking whether it is a goal.\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = dict()\ncost_so_far = dict()\ncame_from[start] = None\ncost_so_far[start] = 0\n\nwhile not frontier.empty():\n   current = frontier.get()\n\n   if current == goal:\n      break\n   \n   for next in graph.neighbors(current):\n      new_cost = cost_so_far[current] + graph.cost(current, next)\n      if next not in cost_so_far or new_cost < cost_so_far[next]:\n         cost_so_far[next] = new_cost\n         priority = new_cost\n         frontier.put(next, priority)\n         came_from[next] = current\n```\n\n\n**Best-first search: node selected for expansion based on an evaluation function f(n)\n✔ f(n) includes estimate of distance to goal (new idea!)\no Implementation: Sort frontier queue by this new f(n).\n▪ Special cases: greedy search, and A* search\n\n\n**A heuristic function h(n) takes a state n and returns an estimate of the distance from n to the goal.\n\n** Greedy best-first search: f(n) = h(n)\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = dict()\ncame_from[start] = None\n\nwhile not frontier.empty():\n   current = frontier.get()\n\n   if current == goal:\n      break\n   \n   for next in graph.neighbors(current):\n      if next not in came_from:\n         priority = heuristic(goal, next)\n         frontier.put(next, priority)\n         came_from[next] = current\n\ndef heuristic(a, b):\n   # Manhattan distance on a square grid\n   return abs(a.x - b.x) + abs(a.y - b.y)\n\n```\nAdmissible (optimistic) heuristics slow down bad plans but never outweigh true costs\n\nInadmissible (pessimistic) heuristics break optimality by trapping good plans on the frontier\n\nFor the 8-puzzle: hoop(n) = number of out of place tiles\nhmd(n) = total Manhattan distance (i.e., # of moves from desired location of each tile)\n\nA problem with fewer restrictions on the actions than the original is called a relaxed\nproblem\n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem\n\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\ngives the shortest solution\n\nIf the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\ngives the shortest solution\n\nCost of an exact solution to a relaxed problem (fewer restrictions on operator)\nConstraints on Full Problem:\nA tile can move from square A to square B if A is adjacent to B and B is blank.\n• Constraints on relaxed problems:\n• A tile can move from square A to square B if A is adjacent to B. (hmd)\n• A tile can move from square A to square B if B is blank.\n• A tile can move from square A to square B. (hoop)\n\nIf h2(n) ≥ h1(n) for all n (both admissible)\n• then h2 dominates h1\nSo h2 is optimistic, but more accurate than h1\n• h2 is therefore better for search\n• Notice: hmd dominates hoop\n\n\n\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Sequential Decision Problems\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "* key property of game \n",
        "1. Two players alternate moves\n",
        "2. Zero-sum: one player’s loss is another’s gain\n",
        "3. Clear set of legal moves\n",
        "4. Well-defined outcomes (e.g. win, lose, draw)\n",
        "\n",
        "o Most card games (e.g. Hearts, Bridge, etc.) and Scrabble\n",
        "▪ Stochastic, not deterministic\n",
        "▪ Not fully observable: lacking in perfect information\n",
        "o Real-time strategy games\n",
        "▪ Continuous rather than discrete\n",
        "▪ No pause between actions, don’t take turns\n",
        "o Cooperative games\n",
        "\n",
        "1. Two players: MAX and MIN; MAX moves first.\n",
        "2. MAX and MIN take turns until the game is over.\n",
        "3. Winner gets award, loser gets penalty.\n",
        "\n",
        "o Games as search:\n",
        "▪ Initial state: e.g. board configuration of chess\n",
        "▪ Successor function: list of (move,state) pairs specifying legal moves.\n",
        "▪ Terminal test: Is the game finished?\n",
        "▪ Utility function: Gives numerical value of terminal states.\n",
        "e.g. win (+∞), lose (-∞) and draw (0)\n",
        "▪ MAX uses search tree to determine next move.\n",
        "\n",
        "game tree:\n",
        "▪ Nodes represent ‘board positions’; edges represent legal moves.\n",
        "▪ Root node is the first position in which a decision must be made.\n",
        "\n",
        "**Minmax\n",
        "Idea: Make the best move for MAX assuming that MIN always replies with the best\n",
        "move for MIN\n",
        "Easily computed by a recursive process\n",
        "• The backed-up value of each node in the tree is determined by the values of its\n",
        "children:\n",
        "• For a MAX node, the backed-up value is the maximum of the values of its\n",
        "children (i.e. the best for MAX)\n",
        "• For a MIN node, the backed-up value is the minimum of the values of its\n",
        "children (i.e. the best for MIN)\n",
        "```\n",
        "def max-value(state):\n",
        "  if the state is a terminal state:\n",
        "    return the state’s utility\n",
        "  initialize v = -∞\n",
        "  for each successor of state:\n",
        "    v = max(v, min-value(successor))\n",
        "  return v\n",
        "\n",
        "def min-value(state):\n",
        "  if the state is a terminal state:\n",
        "    return the state’s utility\n",
        "  initialize v = +∞\n",
        "  for each successor of state:\n",
        "    v = min(v, max-value(successor))\n",
        "  return v\n",
        "```\n",
        "Why wouldn’t we know what the result of an action will be? ▪ Explicit randomness: rolling dice ▪ Unpredictable opponents: the opponent isn’t optimal ▪ Actions can fail: when moving a robot, wheels might slip\n",
        "o Values should now reflect average-case (expectimax)\n",
        "outcomes, not worst-case (minimax) outcomes\n",
        "o Expectimax search: compute the average score under optimal\n",
        "play ▪ Max nodes as in minimax search ▪ Chance nodes are like min nodes but the outcome is\n",
        "uncertain ▪ Calculate their expected utilities ▪ I.e. take weighted average (expectation) of children\n",
        "o Later, we’ll learn how to formalize the underlying\n",
        "uncertain-result problems as Markov Decision Processes\n",
        "\n",
        "```\n",
        "def value(state):\n",
        "if the state is a terminal state: return the state’s\n",
        "utility\n",
        "if the next agent is MAX: return max-value(state)\n",
        "if the next agent is EXP: return exp-value(state)\n",
        "\n",
        "def max-value(state):\n",
        "initialize v = -∞\n",
        "for each successor of state:\n",
        "v = max(v, value(successor))\n",
        "return v\n",
        "\n",
        "def exp-value(state):\n",
        "initialize v = 0\n",
        "for each successor of state:\n",
        "p = probability(successor)\n",
        "v += p *\n",
        "value(successor)\n",
        "return v\n",
        "```\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "    \"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2d30d286-ceb0-4678-a1db-762ad28efe42"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nSequential Decision Problems\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \n* key property of game \n1. Two players alternate moves\n2. Zero-sum: one player’s loss is another’s gain\n3. Clear set of legal moves\n4. Well-defined outcomes (e.g. win, lose, draw)\n\no Most card games (e.g. Hearts, Bridge, etc.) and Scrabble\n▪ Stochastic, not deterministic\n▪ Not fully observable: lacking in perfect information\no Real-time strategy games\n▪ Continuous rather than discrete\n▪ No pause between actions, don’t take turns\no Cooperative games\n\n1. Two players: MAX and MIN; MAX moves first.\n2. MAX and MIN take turns until the game is over.\n3. Winner gets award, loser gets penalty.\n\no Games as search:\n▪ Initial state: e.g. board configuration of chess\n▪ Successor function: list of (move,state) pairs specifying legal moves.\n▪ Terminal test: Is the game finished?\n▪ Utility function: Gives numerical value of terminal states.\ne.g. win (+∞), lose (-∞) and draw (0)\n▪ MAX uses search tree to determine next move.\n\ngame tree:\n▪ Nodes represent ‘board positions’; edges represent legal moves.\n▪ Root node is the first position in which a decision must be made.\n\n**Minmax\nIdea: Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN\nEasily computed by a recursive process\n• The backed-up value of each node in the tree is determined by the values of its\nchildren:\n• For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX)\n• For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)\n```\ndef max-value(state):\n  if the state is a terminal state:\n    return the state’s utility\n  initialize v = -∞\n  for each successor of state:\n    v = max(v, min-value(successor))\n  return v\n\ndef min-value(state):\n  if the state is a terminal state:\n    return the state’s utility\n  initialize v = +∞\n  for each successor of state:\n    v = min(v, max-value(successor))\n  return v\n```\nWhy wouldn’t we know what the result of an action will be? ▪ Explicit randomness: rolling dice ▪ Unpredictable opponents: the opponent isn’t optimal ▪ Actions can fail: when moving a robot, wheels might slip\no Values should now reflect average-case (expectimax)\noutcomes, not worst-case (minimax) outcomes\no Expectimax search: compute the average score under optimal\nplay ▪ Max nodes as in minimax search ▪ Chance nodes are like min nodes but the outcome is\nuncertain ▪ Calculate their expected utilities ▪ I.e. take weighted average (expectation) of children\no Later, we’ll learn how to formalize the underlying\nuncertain-result problems as Markov Decision Processes\n\n```\ndef value(state):\nif the state is a terminal state: return the state’s\nutility\nif the next agent is MAX: return max-value(state)\nif the next agent is EXP: return exp-value(state)\n\ndef max-value(state):\ninitialize v = -∞\nfor each successor of state:\nv = max(v, value(successor))\nreturn v\n\ndef exp-value(state):\ninitialize v = 0\nfor each successor of state:\np = probability(successor)\nv += p *\nvalue(successor)\nreturn 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 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Clean specification of many problems, generic goal,\n",
        "successor function & heuristics\n",
        "▪ Just represent problem as a CSP & solve with general package\n",
        "o CSP “knows” which variables violate a constraint\n",
        "▪ And hence where to focus the search\n",
        "o CSPs: Automatically prune off all branches that violate\n",
        "constraints\n",
        "▪ (State space search could do this only by hand-building constraints\n",
        "into the successor function)\n",
        "\n",
        "** search tree 1\n",
        "n variables of domain size d ∙ Branching factor at the root is n*d ∙ Branching factor at next level is (n-1)*d ∙ Tree has n!*dn leaves\n",
        "\n",
        "** search tree2 because communitive to reach a partial complete\n",
        "Only need to consider assignments to a single variable at each node\n",
        "▪ b = d and there are dn leaves (n variables, domain size d )\n",
        "\n",
        "Depth-first search for CSPs with single-variable assignments is called\n",
        "backtracking search\n",
        "o The term backtracking search is used for a depth-first search that chooses\n",
        "values for one variable at a time and backtracks when a variable has no legal\n",
        "values left to assign.\n",
        "o Backtracking search is the basic uninformed algorithm for CSPs\n",
        "\n",
        "**Improving backtracking efficiency\n",
        "∙ General-purpose methods & general-purpose heuristics\n",
        "can give huge gains in speed, on average\n",
        "∙ Heuristics:\n",
        "▪ Q: Which variable should be assigned next?\n",
        "1. Most constrained variable (minimum remaining values (MRV))\n",
        "2. (if ties:) Most constraining variable (most C)\n",
        "▪ Q: In what order should that variable’s values be tried?\n",
        "3. Least constraining value\n",
        "▪ Q: Can we detect inevitable failure early?\n",
        "4. Forward checking: Keep track of remaining legal values for unassigned variables\n",
        "▪ Terminate search when any unassigned variable has no remaining\n",
        "legal values\n",
        "\n",
        "CSP solvers combine search and inference\n",
        "▪ Search\n",
        "• assigning a value to a variable\n",
        "▪ Constraint propagation (inference)\n",
        "• Eliminates possible values for a variable\n",
        "if the value would violate local consistency\n",
        "▪ Can do inference first, or intertwine it with search\n",
        "• You’ll investigate this in the Sudoku homework\n",
        "o Local consistency\n",
        "▪ Node consistency: satisfies unary constraints\n",
        "• This is trivial!\n",
        "▪ Arc consistency: satisfies binary constraints\n",
        "• (Xi is arc-consistent w.r.t. Xj if for every value v in Di, there is some value w in\n",
        "Dj that satisfies the binary constraint on the arc between Xi and Xj)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 920
        },
        "outputId": "b5669930-06ee-4ce7-87c9-208f85cbdec4"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\nClean specification of many problems, generic goal,\nsuccessor function & heuristics\n▪ Just represent problem as a CSP & solve with general package\no CSP “knows” which variables violate a constraint\n▪ And hence where to focus the search\no CSPs: Automatically prune off all branches that violate\nconstraints\n▪ (State space search could do this only by hand-building constraints\ninto the successor function)\n\n** search tree 1\nn variables of domain size d ∙ Branching factor at the root is n*d ∙ Branching factor at next level is (n-1)*d ∙ Tree has n!*dn leaves\n\n** search tree2 because communitive to reach a partial complete\nOnly need to consider assignments to a single variable at each node\n▪ b = d and there are dn leaves (n variables, domain size d )\n\nDepth-first search for CSPs with single-variable assignments is called\nbacktracking search\no The term backtracking search is used for a depth-first search that chooses\nvalues for one variable at a time and backtracks when a variable has no legal\nvalues left to assign.\no Backtracking search is the basic uninformed algorithm for CSPs\n\n**Improving backtracking efficiency\n∙ General-purpose methods & general-purpose heuristics\ncan give huge gains in speed, on average\n∙ Heuristics:\n▪ Q: Which variable should be assigned next?\n1. Most constrained variable (minimum remaining values (MRV))\n2. (if ties:) Most constraining variable (most C)\n▪ Q: In what order should that variable’s values be tried?\n3. Least constraining value\n▪ Q: Can we detect inevitable failure early?\n4. Forward checking: Keep track of remaining legal values for unassigned variables\n▪ Terminate search when any unassigned variable has no remaining\nlegal values\n\nCSP solvers combine search and inference\n▪ Search\n• assigning a value to a variable\n▪ Constraint propagation (inference)\n• Eliminates possible values for a variable\nif the value would violate local consistency\n▪ Can do inference first, or intertwine it with search\n• You’ll investigate this in the Sudoku homework\no Local consistency\n▪ Node consistency: satisfies unary constraints\n• This is trivial!\n▪ Arc consistency: satisfies binary constraints\n• (Xi is arc-consistent w.r.t. Xj if for every value v in Di, there is some value w in\nDj that satisfies the binary constraint on the arc between Xi and Xj)\n\n\n\n\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",
        "Logic can serve as a general class of representations for knowledge-based agents.\n",
        "Here we are going to examine Propositional Logic.\n",
        "• KB consists of sentences in the representation language\n",
        "• Representation language has a syntax that specifies sentences that are well-formed\n",
        "• A logic defines the semantics of the sentences, which is their meaning\n",
        "• The semantics defines the truth of each sentence with respect to a possible world,\n",
        "which we will often call a model.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 573
        },
        "outputId": "97bee726-47cc-4130-9675-5e70545afd93"
      },
      "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": 57,
      "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\nLogic can serve as a general class of representations for knowledge-based agents.\nHere we are going to examine Propositional Logic.\n• KB consists of sentences in the representation language\n• Representation language has a syntax that specifies sentences that are well-formed\n• A logic defines the semantics of the sentences, which is their meaning\n• The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model.\n\n\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": "484d2dc7-ad09-4fc3-dbac-d4ca1c7612e9"
      },
      "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": 58,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nActing humanly: The Turing test: NLP, knowledge representation, automated reasoning, maching learning. Total TT: + computer vision Robotics Thinking humanly, acting rationally The rational agent approach, thinking rationally (probability and logic).\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nAn omniscient agent knows the actual outcome of its actions and can act accordingly, rationality is not the same as perfection  \n\n## AIMA 2.3 The Nature of Environments\n \nagent = architecture+program\n \n\n## AIMA 2.4 The Structure of Agents\n \ncondition–action rule simple reflex agent, It acts according to a rule whose condition matches the current state, as defined by the percept. \n\nEscape from infinite loops is possible if the agent can randomize its actions \n\nmodel-based agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved Internal state aspects of the current state\n\nknowledge about “how the world works”-- transition model\nsome information about how the state of the world is reflected in the agent’s percepts -- sensor model\n\ngoal based agent\n\nUtility-based agents: utility function is essentially an internalization of the performance measure, How happy I will be\nin such a state\n\nLearning agents: problem generator: suggesting actions that will lead to new and informative experiences; learning element: making improvements; performance element: selecting external actions\n\n\n \n\n## Module 1 Lecture Notes\n \n1.1 Turing test A human evaluator would judge text-based conversations between a human and a machine designed to generate human-like responses. If the evaluator cannot reliably tell the machine from the human, the machine passes the test. The test results do not depend on the ability to give correct answers to questions, only how closely one's answers resemble those a human would give. \nJohn Searle The Chinese Room Daniel Dennett brain in a vat OBSERVABLE AGENTS# DETERMINISTIC EPISODIC/Sequential STATIC DISCRETE UNKNOWN OUTCOMES\nWhen something behavior can best be described as having its own performance measure, then we should consider it to be an agent. \n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Percept** - the agent’s perceptual inputs at any given instance\n* **Performance measure** -  An objective criterion for success of an agents behavior given the evidence provided by the percept sequence.\n* **Reflex agent** - selects an action based on the current percept, and ignores the rest of the percept history\n* **Problem-solving agent** - consider a sequence of actions that form a path to a goal state, search\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nstrong, dynamic typing\nprint(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\nstrings are immutable\nlists are mutable, use y = x[:] to get a (shallow) copy of any sequence\n\n# Sequence Types:\nTuple\n▪ A simple immutable ordered sequence of items\n▪ Immutable: a tuple cannot be modified once created\n▪ Items can be of mixed types, including collection types\no Strings\n▪ Immutable\n▪ Regular strings are Unicode and use 2-byte characters (Regular strings in\nPython 2 use 8-bit characters)\no List\n▪ Mutable ordered sequence of items of mixed types\n\n```\n>>> a = [1, 2, 3]\n>>> b = ['a', 'b', 'c', 'd']\n>>> list(zip(a, b))\n[(1, 'a'), (2, 'b'), (3, 'c')]\n\n>>> list(zip(\"foo\", \"bar\"))\n[('f', 'b'), ('o', 'a'), ('o', 'r')]\n\n>>> d = {'user' : 'R2D2', 'pswd': 1234}\n>>> d['user']\n>>> d['pswd'] = 'thx1138' # Assigning to an existing key replaces its value.\n\n>>> d.keys() # List of current keys\ndict_keys(['user', 'p', 'i’])\n>>> d.values() # List of current values.\ndict_values(['R2D2', 1234, 34])\n>>> d.items() # List of item tuples.\ndict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n\nfrom collections import defaultdict\nd = defaultdict(str)\nd['a']\n\"\"\nfrom collections import Counter\nd = Counter()\nd['a']\n0\nd['dog'] += 10\nd['dog']\n10\n```\nMultiple Return Values is tuple\n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError\n```\ndef myfun(a, b, c):\n>>> myfun(a=2, b=3, 5) # error\n```\n\n# *args non-keyword at variable number\n```\ndef print_everything(*args):\nprint(args)\nprint_everything('a', 'b', 'c’)\n('a', 'b', 'c’)\nlst = ['a', 'b', 'c’]\nprint_everything(*lst)\n('a', 'b', 'c')\n```\n# **kwargs a variable number of keyword arguments\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{'first_name': 'John', 'last_name': 'Doe’}\nmy_dict = {'first_name': 'Wei', 'last_name': 'Xu’}\nprint_keyword_args(**my_dict)\n{'first_name': 'Wei', 'last_name': 'Xu'}\n\n[i for i in [1, 2, 3, 4, 5] if is_even(i)]\n\n# class and subclass\n\n```\n __init__\nclass AI_Student(Student):\ndef __init__(self, name, dept):\nStudent.__init__(self, name, dept)\n```\n# magic function\n```\n__init__: The constructor for the class.\n__len__ : Define how len( obj ) works.\n__copy__: Define how to copy a class.\n__cmp__ : Define how == works for class.\n__add__ : Define how + works for class\n__neg__ : Define how unary negation works for class\n\nclass A(object):\ndef foo(self):\nprint('Foo!')\nclass B(object):\ndef foo(self):\nprint('Foo?')\ndef bar(self):\nprint('Bar!')\nclass C(A, B):\ndef foobar(self):\nsuper().foo() # Foo!\nsuper().bar() # Bar!\n\nif __name__ == '__main__':\n\n# for loop\nlst1 = [1, 2, 3]\nlst2 = [2, 3, 4]\nlst3 = [3, 4, 5]\nres = [(x, y, z) for x in lst1 if x < 2 for y in lst2 for z in lst3 if x + y + z < 8]\n# Both value of res: [(1, 2, 3), (1, 2, 4), (1, 3, 3)]\n\nlst1 = [('a', 1), ('b', 2), ('c', 'hi’)]\nlst2 = ['x', 'a', 6]\nd = { k: v for k,v in lst1 }\ns = { x for x in lst2 }\n# Both value of d: {'a': 1, 'b': 2, 'c': 'hi’}\n# Both value of d: {'x', 'a', 6}\n```\n## iterator\n```\n>>> i = iter(k)\n>>> next(i)\n1\n>>> i.__next__()\n2\n>>> i.next()\n\no for <item> in <iterable>:\n<statements>\no First line is just syntactic sugar for: ▪ 1. Initialize: Call <iterable>.__iter__() to create an iterator\no Each iteration: ▪ 2. Call iterator.__next__() and bind <item> ▪ 2a. Catch StopIteration exceptions\no To be iterable: has __iter__ method ▪ which returns an iterator obj\no To be iterator: has __next__ method ▪ which throws StopIteration when done\n\n```\n## Benefits of using generators\n\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\no Generators are iterators (with __next()__ method)\no Creating Generators: yield\n▪ Functions that contain the yield keyword automatically return a generator when called\n\n```\n>>> def f(n):\n... yield n\n... yield n+1\n...\n>>>\n>>> type(f)\n<class 'function'>\n>>> type(f(5))\n<class 'generator'>\n>>> [i for i in f(6)]\n[6, 7]\n\n>>> gen = f(5) # no need to say f(5).__iter__()\n>>> gen\n<generator object f at 0x1008cc9b0>\n>>> gen.__next__()\n5\n>>> next(gen)\n6\n>>> gen.__next__() # error\n\n# Problem: merge two sorted lists, using the output as a stream (i.e. not storing it).\ndef merge(l, r):\nllen = len(l)\nrlen = len(r)\ni = 0\nj = 0\nwhile i < llen or j < rlen:\nif j == rlen or (i < llen and l[i] < r[j]):\nyield l[i]\ni += 1\nelse:\nyield r[j]\nj += 1\n\n[x for x in merge([1,3,5],[2,4])]\n[1, 2, 3, 4, 5]\n\ng = merge([2,4], [1, 3, 5])\nwhile True:\ntry:\nprint(g.__next__())\nexcept StopIteration:\nprint('Done’)\nbreak\n\nsum(x for x in xrange(10**8) if x%5==0)\n999999950000000L\nThan version this which creates the whole list first\nsum([x for x in xrange(10**8) if x%5==0])\n999999950000000L\n\nimport math\nmath.sqrt(9)\n3.0\nfrom math import sqrt\nsqrt(9)\n# Not as good to do this:\nfrom math import *\nsqrt(9) # unclear where function defined\n# create alias or nickname\nimport numpy as np\n\n# priority Q sorted\nimport queue as Q\nq = Q.PriorityQueue()\nq.put((10, \"Prepare to die.\"))\nq.put((1, \"Hello,\"))\nq.put((5, \"Diego Montoya.\"))\nq.put((2, \"My name is\"))\nwhile not q.empty():\nprint(q.get()[1])\nHello,\nMy name is\nDiego Montoya.\n\n# the digraph constructor\nclass DiGraph:\ndef __init__(self, edges):\nself.adj = {}\nfor u, v in edges:\nif u not in self.adj:\nself.adj[u] = [v]\nelse:\nself.adj[u].append(v)\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\nprint(d.adj)\n{1: [2, 3], 2: [4], 4: [3, 1]} \n\n# the magic method\nclass DiGraph:\ndef __str__(self):\nreturn '\n'.join(['%s -> %s'% (u,v) for u in self.adj for v in self.adj[u]])\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\nprint(d)\n1 -> 2\n1 -> 3\n2 -> 4\n4 -> 3\n4 -> 1\n\n# search method yield\nclass DiGraph:\ndef search(self, u, visited):\n# If we haven't visited this node...\nif u not in visited:\nyield u # yield it\nvisited.add(u) # and remember we've visited it now.\n# Then, if there are any adjacent nodes...\nif u in self.adj:\nfor v in self.adj[u]: # for each adjacent node...\n# search for all nodes reachable from *it*...\nfor w in self.search(v, visited):\n# and yield each one.\nyield w\n\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n[v for v in d.search(1, set())]\n[1, 2, 4, 3]\n```\n\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 \nA transition model, which describes what each action does. RESULT(s, a) returns the Transition model\nstate that results from doing action a in state s. For example,\nRESULT(Arad; ToZerind) = Zerind \n \n\n## AIMA Chapter 3.2 Example Problems\n \nTouring problems describe a set of locations that must be visited, rather than a single\ngoal destination. The traveling salesperson problem (TSP) is a touring problem in which\nevery city on a map must be visited. The aim is to find a tour with cost < C \n\nA VLSI layout problem requires positioning millions of components and connections on\na chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\nmanufacturing yield. cell layout and channel routing\n\nRobot navigation is a generalization of the route-finding problem described earlier.\nRather than following distinct paths (such as the roads in Romania), a robot can roam around,\nin effect making its own paths.\n\nAutomatic assembly sequencing Minimizing the amount of manual human\nlabor on the assembly line can produce significant savings in time and cost. In assembly\nproblems, the aim is to find an order in which to assemble the parts of some object. protein design, in which the goal is to find a sequence of amino acids that will fold into a\nthree-dimensional protein with the right properties\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nbest-first search, in which we choose a node, n, with minimum value of some Best- first search evaluation function, f (n).\n\n• node.STATE: the state to which the node corresponds;\n• node.PARENT: the node in the tree that generated this node;\n• node.ACTION: the action that was applied to the parent’s state to generate this node;\n• node.PATH-COST: the total cost of the path from the initial state to this node. g(node)\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nbidirectional search simultaneously\nsearches forward from the initial state and backwards from the goal state(s), hoping that the\ntwo searches will meet. The motivation is that bd=2+bd=2 is much less than bd (e.g., 50,000\ntimes less when b=d=10).\n \n\n## Module 3 Lecture Notes\n \nThe properties of the task environments change the types of solutions that we need.\nIf an environment is:\n• Fully observable\n• Deterministic\n• Known environment\nThe solution to any problem in such an environment is a fixed sequence of actions.\nIn environments that are\n• Partially observable or\n• Nondeterministic\nThe solution must recommend different future actions depending on the what\npercepts it receives. This could be in the form of a branching strategy.\n\n# formulate a search problem\n1. States: a set S\n2. An initial state si\n∈ S\n3. Actions: a set A\n∀ s Actions(s) = the set of actions that can be executed in s, that are applicable in s.\n4. Transition Model: ∀ s∀ a∈Actions(s) Result(s, a) → sr\nsr is called a successor of s\n{si }∪ Successors(si )* = state space\n5. Path cost (Performance Measure): Must be additive, e.g. sum of distances, number of\nactions executed, …\nc(x,a,y) is the step cost, assumed ≥ 0\n• (where action a goes from state x to state y)\n6. Goal test: Goal(s)\nCan be implicit, e.g. checkmate(s)\ns is a goal state if Goal(s) is true\n\nVacuum World With n cells, there are n*2^n states\n\nA solution is a sequence of actions from the initial state to a goal\nstate.\n\nOptimal Solution: A solution is optimal if no solution has a lower\npath cost.\n\nDecide:\nWhich properties matter & how to represent\n• Initial State, Goal State, Possible Intermediate States\nWhich actions are possible & how to represent\n• Operator Set: Actions and Transition Model\nWhich action is next\n• Path Cost Function\n\n\nState space: the set of all states reachable from the initial state by any\nsequence of actions\n• When several operators can apply to each state, this gets large very quickly\n• Might be a proper subset of the set of configurations\nPath: a sequence of actions leading from one state sj to another state sk\nFrontier: those states that are available for expanding (for applying legal\nactions to)\nSolution: a path from the initial state si to a state sf that satisfies the goal test\n17\n\n** tree search\n```\nfunction TREE-SEARCH(problem, strategy) return a solution or failure\n  Initialize frontier to the initial state of the problem\ndo\n  if the frontier is empty then return failure\nchoose leaf node for expansion according to strategy & remove from frontier\n  if node contains goal state then return solution\n  else expand the node and add resulting nodes to the frontier\n```\n** graph search\n```\nfunction 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\nloop 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```\nA state is a (representation of a) physical configuration\nA node is a data structure constituting part of a search tree\n• Also includes parent, children, depth, path cost g(x)\n• Here node= <state, parent-node, children,\naction, path-cost, depth>\n\n** search strategies\nReview: Strategy = order of tree expansion\n• Implemented by different queue structures (LIFO, FIFO, priority)\n\nUse depth-first if\n• Space is restricted\n• There are many possible solutions with long paths and wrong paths are usually\nterminated quickly\n• Search can be fine-tuned quickly\nUse breadth-first if\n• Possible infinite paths\n• Some solutions have short paths\n• Can quickly discard unlikely paths\n\nBreadth first search \n\nfunction BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n  node NODE(problem.INITIAL)\n  if problem.IS-GOAL(node.STATE) then return node\n  frontier a FIFO queue, with node as an element\n  reached {problem.INITIAL}\n  while not IS-EMPTY(frontier) do\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 in reached then\n      add s to reached\n      add child to frontier\nreturn failure\n\n```\nfrontier = Queue()\nfrontier.put(start )\nreached = set()\nreached.add(start)\n\nwhile not frontier.empty():\n   current = frontier.get()\n   for next in graph.neighbors(current):\n      if next not in reached:\n         frontier.put(next)\n         reached.add(next)\n```\n\nfunction BREADTH-FIRST-SEARCH(problem) returns a solution, or failure\nnode <- a node with STATE = problem.INITIAL-STATE, PATH-COST=0\nif problem.GOAL-TEST(node.STATE) then return SOLUTION(node)\nfrontier <- a FIFO queue with node as the only element\nloop do\nif EMPTY?(frontier) then return failure\nnode <- POP(frontier) // chooses the shallowest node in frontier\nadd node.STATE to explored\nfor each action in problem.ACTIONS(node.STATE) do\nchild <- CHILD-NODE(problem, node, action)\nif problem.GOAL-TEST(child.STATE) then return SOLUTION(child)\nfrontier <- INSERT(child, frontier)\n\nfunction EXPAND(problem, node) yields nodes\n  s node.STATE\n  for each action in problem.ACTIONS(s) do\n    s0 problem.RESULT(s, action)\n    cost node.PATH-COST + problem.ACTION-COST(s, action, s0)\n    yield NODE(STATE=s0, PARENT=node, ACTION=action, PATH-COST=cost)\n\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Uninformed search** - All non-goal nodes in frontier look equally good\n* **Informed search** - Some non-goal nodes can be ranked above others.\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nA  is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\nThe concept of pruning—eliminating possibilities from consideration without having to examine them\n\ndetour index, which is Detour index a multiplier applied to the straight-line distance to account for the typical curvature of roads\n\nweighted A  search where we weight the heuristic value more heavily, giving us the Weighted A  search evaluation function f (n) = g(n)+W  h(n), for someW > 1.\n\nSatis cing search: Inadmissible heuristics and weighted A \n\nThe main issue with A  is its use of memory\nIterative-deepening A  search (IDA ) is to A  what iterative-deepening search is to Iterative-deepening\nA  search depth-first: IDA  gives us the benefits of A  without the requirement to keep all reached\nstates in memory, at a cost of visiting some states multiple times.\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n \n** Uniform-cost search (UCS)\no Extension of BF-search:\n▪ Expand node with lowest path cost\no Implementation:\n▪ frontier = priority queue ordered by g(n)\no Subtle but significant difference from BFS:\n▪ Tests if a node is a goal state when it is selected for expansion, not when it is\nadded to the frontier.\n▪ Updates a node on the frontier if a better path to the same state is found.\n▪ So always enqueues a node before checking whether it is a goal.\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = dict()\ncost_so_far = dict()\ncame_from[start] = None\ncost_so_far[start] = 0\n\nwhile not frontier.empty():\n   current = frontier.get()\n\n   if current == goal:\n      break\n   \n   for next in graph.neighbors(current):\n      new_cost = cost_so_far[current] + graph.cost(current, next)\n      if next not in cost_so_far or new_cost < cost_so_far[next]:\n         cost_so_far[next] = new_cost\n         priority = new_cost\n         frontier.put(next, priority)\n         came_from[next] = current\n```\n\n\n**Best-first search: node selected for expansion based on an evaluation function f(n)\n✔ f(n) includes estimate of distance to goal (new idea!)\no Implementation: Sort frontier queue by this new f(n).\n▪ Special cases: greedy search, and A* search\n\n\n**A heuristic function h(n) takes a state n and returns an estimate of the distance from n to the goal.\n\n** Greedy best-first search: f(n) = h(n)\n```\nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = dict()\ncame_from[start] = None\n\nwhile not frontier.empty():\n   current = frontier.get()\n\n   if current == goal:\n      break\n   \n   for next in graph.neighbors(current):\n      if next not in came_from:\n         priority = heuristic(goal, next)\n         frontier.put(next, priority)\n         came_from[next] = current\n\ndef heuristic(a, b):\n   # Manhattan distance on a square grid\n   return abs(a.x - b.x) + abs(a.y - b.y)\n\n```\nAdmissible (optimistic) heuristics slow down bad plans but never outweigh true costs\n\nInadmissible (pessimistic) heuristics break optimality by trapping good plans on the frontier\n\nFor the 8-puzzle: hoop(n) = number of out of place tiles\nhmd(n) = total Manhattan distance (i.e., # of moves from desired location of each tile)\n\nA problem with fewer restrictions on the actions than the original is called a relaxed\nproblem\n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem\n\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then hoop(n)\ngives the shortest solution\n\nIf the rules are relaxed so that a tile can move to any adjacent square, then hmd(n)\ngives the shortest solution\n\nCost of an exact solution to a relaxed problem (fewer restrictions on operator)\nConstraints on Full Problem:\nA tile can move from square A to square B if A is adjacent to B and B is blank.\n• Constraints on relaxed problems:\n• A tile can move from square A to square B if A is adjacent to B. (hmd)\n• A tile can move from square A to square B if B is blank.\n• A tile can move from square A to square B. (hoop)\n\nIf h2(n) ≥ h1(n) for all n (both admissible)\n• then h2 dominates h1\nSo h2 is optimistic, but more accurate than h1\n• h2 is therefore better for search\n• Notice: hmd dominates hoop\n\n\n\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 Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nSequential Decision Problems\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \n* key property of game \n1. Two players alternate moves\n2. Zero-sum: one player’s loss is another’s gain\n3. Clear set of legal moves\n4. Well-defined outcomes (e.g. win, lose, draw)\n\no Most card games (e.g. Hearts, Bridge, etc.) and Scrabble\n▪ Stochastic, not deterministic\n▪ Not fully observable: lacking in perfect information\no Real-time strategy games\n▪ Continuous rather than discrete\n▪ No pause between actions, don’t take turns\no Cooperative games\n\n1. Two players: MAX and MIN; MAX moves first.\n2. MAX and MIN take turns until the game is over.\n3. Winner gets award, loser gets penalty.\n\no Games as search:\n▪ Initial state: e.g. board configuration of chess\n▪ Successor function: list of (move,state) pairs specifying legal moves.\n▪ Terminal test: Is the game finished?\n▪ Utility function: Gives numerical value of terminal states.\ne.g. win (+∞), lose (-∞) and draw (0)\n▪ MAX uses search tree to determine next move.\n\ngame tree:\n▪ Nodes represent ‘board positions’; edges represent legal moves.\n▪ Root node is the first position in which a decision must be made.\n\n**Minmax\nIdea: Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN\nEasily computed by a recursive process\n• The backed-up value of each node in the tree is determined by the values of its\nchildren:\n• For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX)\n• For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)\n```\ndef max-value(state):\n  if the state is a terminal state:\n    return the state’s utility\n  initialize v = -∞\n  for each successor of state:\n    v = max(v, min-value(successor))\n  return v\n\ndef min-value(state):\n  if the state is a terminal state:\n    return the state’s utility\n  initialize v = +∞\n  for each successor of state:\n    v = min(v, max-value(successor))\n  return v\n```\nWhy wouldn’t we know what the result of an action will be? ▪ Explicit randomness: rolling dice ▪ Unpredictable opponents: the opponent isn’t optimal ▪ Actions can fail: when moving a robot, wheels might slip\no Values should now reflect average-case (expectimax)\noutcomes, not worst-case (minimax) outcomes\no Expectimax search: compute the average score under optimal\nplay ▪ Max nodes as in minimax search ▪ Chance nodes are like min nodes but the outcome is\nuncertain ▪ Calculate their expected utilities ▪ I.e. take weighted average (expectation) of children\no Later, we’ll learn how to formalize the underlying\nuncertain-result problems as Markov Decision Processes\n\n```\ndef value(state):\nif the state is a terminal state: return the state’s\nutility\nif the next agent is MAX: return max-value(state)\nif the next agent is EXP: return exp-value(state)\n\ndef max-value(state):\ninitialize v = -∞\nfor each successor of state:\nv = max(v, value(successor))\nreturn v\n\ndef exp-value(state):\ninitialize v = 0\nfor each successor of state:\np = probability(successor)\nv += p *\nvalue(successor)\nreturn 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 Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\nClean specification of many problems, generic goal,\nsuccessor function & heuristics\n▪ Just represent problem as a CSP & solve with general package\no CSP “knows” which variables violate a constraint\n▪ And hence where to focus the search\no CSPs: Automatically prune off all branches that violate\nconstraints\n▪ (State space search could do this only by hand-building constraints\ninto the successor function)\n\n** search tree 1\nn variables of domain size d ∙ Branching factor at the root is n*d ∙ Branching factor at next level is (n-1)*d ∙ Tree has n!*dn leaves\n\n** search tree2 because communitive to reach a partial complete\nOnly need to consider assignments to a single variable at each node\n▪ b = d and there are dn leaves (n variables, domain size d )\n\nDepth-first search for CSPs with single-variable assignments is called\nbacktracking search\no The term backtracking search is used for a depth-first search that chooses\nvalues for one variable at a time and backtracks when a variable has no legal\nvalues left to assign.\no Backtracking search is the basic uninformed algorithm for CSPs\n\n**Improving backtracking efficiency\n∙ General-purpose methods & general-purpose heuristics\ncan give huge gains in speed, on average\n∙ Heuristics:\n▪ Q: Which variable should be assigned next?\n1. Most constrained variable (minimum remaining values (MRV))\n2. (if ties:) Most constraining variable (most C)\n▪ Q: In what order should that variable’s values be tried?\n3. Least constraining value\n▪ Q: Can we detect inevitable failure early?\n4. Forward checking: Keep track of remaining legal values for unassigned variables\n▪ Terminate search when any unassigned variable has no remaining\nlegal values\n\nCSP solvers combine search and inference\n▪ Search\n• assigning a value to a variable\n▪ Constraint propagation (inference)\n• Eliminates possible values for a variable\nif the value would violate local consistency\n▪ Can do inference first, or intertwine it with search\n• You’ll investigate this in the Sudoku homework\no Local consistency\n▪ Node consistency: satisfies unary constraints\n• This is trivial!\n▪ Arc consistency: satisfies binary constraints\n• (Xi is arc-consistent w.r.t. Xj if for every value v in Di, there is some value w in\nDj that satisfies the binary constraint on the arc between Xi and Xj)\n\n\n\n\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\nLogic can serve as a general class of representations for knowledge-based agents.\nHere we are going to examine Propositional Logic.\n• KB consists of sentences in the representation language\n• Representation language has a syntax that specifies sentences that are well-formed\n• A logic defines the semantics of the sentences, which is their meaning\n• The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model.\n\n\n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}