{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "726e81f8-654a-47d0-f3f2-ac28ca916516"
      },
      "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": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "87572278-922f-4aa1-bfb7-948e3a68601d"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "AI is defined by two dimensions: human vs. rational and thought vs. behavior. \\\n",
        "Human actions are tested by Turing test. It passes if the human interrogator cannot tell \\\n",
        "the response is from a machine or a human. A total Turing test furter requires it to interact with people \\\n",
        "The computers needs nlp, knowledge representation automatied reasoning, ml, cv and robotics \\\n",
        "to pass a total Turing test. The rational action approach requires the development of an rational agent \\\n",
        "A rational agent approach is the prevailing one since it more general than thought approaches and it is more amenable \\\n",
        "Beyond the technical aspect, machine must not misbehave only for achieving their designated goals to be beneficial to humans. \\\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 = \"\"\" \n",
        "The capability of AI has been questioned in 3 aspects: informality of human behaviours; disability and mathematical unanswerable questions \\\n",
        "But Turing argued that since humans cannot do this either in certain scenarios, a behavioral test might be better for measuring AI. \\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "The question can machine think itself is hard to answer because consciousness is ill-defined. In this sense, human can always \\\n",
        "behave better with their subjective apparatus in certain tasks than intelligent machines.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent perceive its environment and act accordingly. The environment can be anything that we care about when \\\n",
        "designing the agent. It can be mathematically defined as an agent function that maps percepts to actions. \\\n",
        "An agent program is the practical implementation of an agent function\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "A rational agent maximize the expected performance measuring. Rationality doesn't require omniscience because \\\n",
        "it's not possible, but it will gather information from environments and learn in action.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Task environment has multiple properties based on how the world changes when agents acts\"\"\"\n",
        "chapter2_4 = \"\"\" Agent are designed in different ways to act based on percepts, history, goals or utilities \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "agent = architecture + program \\\n",
        "problem solving agents plan ahead\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",
        "\"environment\": \"anything we care about when designing an agent\",\n",
        "\"rational agent\": \"an agent that yields the best expected outcome\",\n",
        "\"percept\" : \"what agents perceives from environment\",\n",
        "\"percept sequence\": \"complete history of percepts\",\n",
        "\"sensor, actuator\": \"percept, action media, respectively\",\n",
        "\"agent function\" : \"mathematical abstraction that maps percepts to actions\",\n",
        "\"agent program\": \"physical implementation of agent function\",\n",
        "\"omniscience\": \"maximize actual outcome\",\n",
        "\"task environment\": \"the target problem with PEAS\",\n",
        "\"PEAS\": \"performance, environment, sensors, actuators\",\n",
        "\"fully observable\": \"agents can always see the complete state of environment\",\n",
        "\"deterministic\": \"previous state and agent action completely determines next state\",\n",
        "\"episodic\":\"percept then act, atomic and independent\",\n",
        "\"sequential\":\"action affects further\",\n",
        "\"static\":\"not changing environment\",\n",
        "\"known\":\"outcomes are given\",\n",
        "\"simple reflex agent\":\"only acts to the current percept\",\n",
        "\"internal state\": \"reflects aspects of current state and depends on percept history\",\n",
        "\"transition model\":\"encodes changes in world to update internal states\",\n",
        "\"utility\":\"measures how good a situation is for the agent\",\n",
        "\"utility function\":'internal performance measure',\n",
        "\"atomic representation\": \"no internal structure in states\",\n",
        "\"factored\":\"divided by avariables\",\n",
        "\"structured\":\"relationships between objects in states\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1218
        },
        "cellView": "form",
        "outputId": "1d3d16e7-1ab1-4df0-96a2-31ddc66c72cf"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nAI is defined by two dimensions: human vs. rational and thought vs. behavior. Human actions are tested by Turing test. It passes if the human interrogator cannot tell the response is from a machine or a human. A total Turing test furter requires it to interact with people The computers needs nlp, knowledge representation automatied reasoning, ml, cv and robotics to pass a total Turing test. The rational action approach requires the development of an rational agent A rational agent approach is the prevailing one since it more general than thought approaches and it is more amenable Beyond the technical aspect, machine must not misbehave only for achieving their designated goals to be beneficial to humans. \n\n## AIMA Chapter 27.1 The Limits of AI\n \nThe capability of AI has been questioned in 3 aspects: informality of human behaviours; disability and mathematical unanswerable questions But Turing argued that since humans cannot do this either in certain scenarios, a behavioral test might be better for measuring AI. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nThe question can machine think itself is hard to answer because consciousness is ill-defined. In this sense, human can always behave better with their subjective apparatus in certain tasks than intelligent machines.\n\n\n## AIMA 2.1 Agents and Environments\n\nAn agent perceive its environment and act accordingly. The environment can be anything that we care about when designing the agent. It can be mathematically defined as an agent function that maps percepts to actions. An agent program is the practical implementation of an agent function\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nA rational agent maximize the expected performance measuring. Rationality doesn't require omniscience because it's not possible, but it will gather information from environments and learn in action.\n\n\n## AIMA 2.3 The Nature of Environments\n Task environment has multiple properties based on how the world changes when agents acts\n\n## AIMA 2.4 The Structure of Agents\n Agent are designed in different ways to act based on percepts, history, goals or utilities \n\n## Module 1 Lecture Notes\n\nagent = architecture + program problem solving agents plan ahead\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Environment** - anything we care about when designing an agent\n* **Rational agent** - an agent that yields the best expected outcome\n* **Percept** - what agents perceives from environment\n* **Percept sequence** - complete history of percepts\n* **Sensor, actuator** - percept, action media, respectively\n* **Agent function** - mathematical abstraction that maps percepts to actions\n* **Agent program** - physical implementation of agent function\n* **Omniscience** - maximize actual outcome\n* **Task environment** - the target problem with PEAS\n* **Peas** - performance, environment, sensors, actuators\n* **Fully observable** - agents can always see the complete state of environment\n* **Deterministic** - previous state and agent action completely determines next state\n* **Episodic** - percept then act, atomic and independent\n* **Sequential** - action affects further\n* **Static** - not changing environment\n* **Known** - outcomes are given\n* **Simple reflex agent** - only acts to the current percept\n* **Internal state** - reflects aspects of current state and depends on percept history\n* **Transition model** - encodes changes in world to update internal states\n* **Utility** - measures how good a situation is for the agent\n* **Utility function** - internal performance measure\n* **Atomic representation** - no internal structure in states\n* **Factored** - divided by avariables\n* **Structured** - relationships between objects in states\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "Python uses strong and dynamic typing. \\n\n",
        "Prefix with r means raw (no escape) \\n\n",
        "Slicing: [start:end:step] \\n\n",
        "dictionary keys must be immutable \\n\n",
        "Python doesn't allow overloading \\n\n",
        "*args for non-keyward and *kwargs (dict) for keywords passing \\n\n",
        " [expression for _ in iterable if condition ] \\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"internal element cannot be changed\",\n",
        "\"strong typing\": \"object has fixed type and incompatible operations won't be allowed\",\n",
        "\"dynamic typing\":\"variables only given type at runtime\",\n",
        "\"static typing\":\"variable can only be declared type\",\n",
        "\"duck typing\":\"no need for interface for methods like __len__\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 415
        },
        "outputId": "9ab17776-9d35-4d6c-971f-33e6bc7bc4e2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nPython uses strong and dynamic typing. \n\nPrefix with r means raw (no escape) \n\nSlicing: [start:end:step] \n\ndictionary keys must be immutable \n\nPython doesn't allow overloading \n\n*args for non-keyward and *kwargs (dict) for keywords passing \n\n [expression for _ in iterable if condition ] \n\n\n\n## Module 2 Definitions\n* **Mutability** - internal element cannot be changed\n* **Strong typing** - object has fixed type and incompatible operations won't be allowed\n* **Dynamic typing** - variables only given type at runtime\n* **Static typing** - variable can only be declared type\n* **Duck typing** - no need for interface for methods like __len__\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",
        "When the environment is fully observable, deterministic, known, the solution is fixed sequence of actions. \\\n",
        "A search problem is defined by state space, initial state, goal state, action, transition model and action cost \\\n",
        "To formulate a problem, abstraction is necessary to remove redundant details.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Examples of standardized problems \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "Search algorithms takes in a search problem and return a solution. It has a tree structure. \\\n",
        "Best-first search choose node with optimal evaluation function. Graph search checks redundant paths \\\n",
        "but tree search doesn't. Tree use less memory but examines redundant paths thus runs slower. \\\n",
        "Search algorithms need to consider completeness, optimality, time and space complexity.   \n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS, IDDFS, Bidirectional search and uniform-cost search are complete and optimal. \\\n",
        "Goal is examined when expanding node in uc search so optimality is guaranteed. \\\n",
        "IDDFS is preferred over BFS when depth of solution is unknown. \\\n",
        "UC search can be seen as best-first search of path cost as eval function.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "BFS time space complexity: both O(b^d) \\n\n",
        "DFS time O(b^m), space O(bm) \\n\n",
        "IDDFS time O(b^d), space O(bd) \\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",
        "\"open loop\": \"percepts are ignored\",\n",
        "\"standardized problems\": \"problems for illustrating or exercising solving methods\",\n",
        "\"branching factor\": \"number of actions to be considered at a node\",\n",
        "\"uninformed\": \"only have access to problem definition\",\n",
        "\"bidirectional search\": \"two frontiers are maintained, on from initial one from goal\",\n",
        "\"depth d\": \"depth of shallowest goal node\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 690
        },
        "outputId": "582436dd-7372-4df0-eafb-5ab1ad625a32"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nWhen the environment is fully observable, deterministic, known, the solution is fixed sequence of actions. A search problem is defined by state space, initial state, goal state, action, transition model and action cost To formulate a problem, abstraction is necessary to remove redundant details.\n\n\n## AIMA Chapter 3.2 Example Problems\n Examples of standardized problems \n\n## AIMA Chapter 3.3 Search Algorithms\n \nSearch algorithms takes in a search problem and return a solution. It has a tree structure. Best-first search choose node with optimal evaluation function. Graph search checks redundant paths but tree search doesn't. Tree use less memory but examines redundant paths thus runs slower. Search algorithms need to consider completeness, optimality, time and space complexity.   \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS, IDDFS, Bidirectional search and uniform-cost search are complete and optimal. Goal is examined when expanding node in uc search so optimality is guaranteed. IDDFS is preferred over BFS when depth of solution is unknown. UC search can be seen as best-first search of path cost as eval function.\n\n\n## Module 3 Lecture Notes\n \nBFS time space complexity: both O(b^d) \n\nDFS time O(b^m), space O(bm) \n\nIDDFS time O(b^d), space O(bd) \n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - percepts are ignored\n* **Standardized problems** - problems for illustrating or exercising solving methods\n* **Branching factor** - number of actions to be considered at a node\n* **Uninformed** - only have access to problem definition\n* **Bidirectional search** - two frontiers are maintained, on from initial one from goal\n* **Depth d** - depth of shallowest goal node\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Greedy best-first search expands nodes with lowest h(n), A* expands g(n)+h(n) \\\n",
        "GBFS complete in finite state space; A* complete with admissible h(n). Consistency \\\n",
        "ensures admissibility, but not vice versa. When, suboptimal solutions can be accepted, there are \\\n",
        "multiple ways to reduce computation by using weighted A*, etc. \n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "The quality of heuristic function greatly influences the performance of heuristic search algorithms. \\\n",
        "A good heuristic can be constructed by methods like relaxing problem, precomputing solution costs of subproblems \\\n",
        "or learning through experience\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Cost of optimal solution to relaxed problem is admissible h(n) for original.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic\" : \"estimate cost from current node to goal\",\n",
        "\"admissible\":\"never overestimating\",\n",
        "\"consistency\": \"$$cost(action)+ h(child) \\geq h(parent)$$\",\n",
        "\"optimally efficient\":\"all other search must expand the expanded nodes in the current search scheme\",\n",
        "\"satisficing search\":\"A* with inadmissible h(n)\",\n",
        "\"speedy search\":\"gbfs with h(n)=# of actions\",\n",
        "\"effective branching factor\": \"N+1 = sum(b*^d)\",\n",
        "\"relaxed problem\":\"few constraints on action\",\n",
        "\"frontier\":\"set of legal states for next action\",\n",
        "\"dominance\":\"h2>h1 for all n\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 549
        },
        "cellView": "form",
        "outputId": "acabb808-bc91-42fd-9797-ec6c87d2a669"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy best-first search expands nodes with lowest h(n), A* expands g(n)+h(n) GBFS complete in finite state space; A* complete with admissible h(n). Consistency ensures admissibility, but not vice versa. When, suboptimal solutions can be accepted, there are multiple ways to reduce computation by using weighted A*, etc. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe quality of heuristic function greatly influences the performance of heuristic search algorithms. A good heuristic can be constructed by methods like relaxing problem, precomputing solution costs of subproblems or learning through experience\n\n\n## Module 4 Lecture Notes\n\nCost of optimal solution to relaxed problem is admissible h(n) for original.\n\n\n## Module 4 Definitions\n* **Heuristic** - estimate cost from current node to goal\n* **Admissible** - never overestimating\n* **Consistency** - $$cost(action)+ h(child) \\geq h(parent)$$\n* **Optimally efficient** - all other search must expand the expanded nodes in the current search scheme\n* **Satisficing search** - A* with inadmissible h(n)\n* **Speedy search** - gbfs with h(n)=# of actions\n* **Effective branching factor** - N+1 = sum(b*^d)\n* **Relaxed problem** - few constraints on action\n* **Frontier** - set of legal states for next action\n* **Dominance** - h2>h1 for all n\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Viewing adversary as economy, part of environment and adversiarial game-tree search makes up \\\n",
        "of the 3 stances on modeling adversarial games. It solves perfect information, zero-sum games\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Optimal play of max assumes opponent plays optimally, but minimax may not be best when \\\n",
        "facing suboptimal opponents. Alliance can be a natural consequence of optimal moves. \\\n",
        "Optimizing search sequence can improve alpha-beta pruning. \n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "To cut down the need of computation power that minimax might pose, methods like h-minimax, \\\n",
        "forward pruning and late move reduction may be applied to cut-off search. Actions found these way \\\n",
        "may not be optimal. Lookup resources in database can also aid searching.\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games introduce random factors like rolling a dice. The minimax search is replaced with \\\n",
        "expectimax to solve such problems. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "The simplest decision making depends on the maximum expected utility principle. \\\n",
        "The decision making theory can be a start point, but cannot solve all AI problems.\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "The axioms of utility guarantees the existence of utility function. Utility function \\\n",
        "is not unique. In a deterministic game environment, only an ordinal utility function is \\\n",
        "necessary. Exact numbers are not vital\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Although money values are often proportional to people's preference, it is often not a good \\\n",
        "utility measurement. Decision theory is normative in that it only models how rational agents behave. \\\n",
        "In real scenarios, people behave more different due to reasons of risk aversion, irrationality, certainty effect, etc.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Values should reflect average case not worst case in expectimax.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"adversarial search problem\" : \"multiple agents with competitive environment\",\n",
        "\"zero-sum\":\"one lose one win\",\n",
        "\"utility function\":\"a numeric value for player when game ends\",\n",
        "\"h-minimax\":\"use heuristic eval as expected utility to use minimax\",\n",
        "\"singular extension\":\"only do moves clearly better at a position\",\n",
        "\"quiescence search\":\"avoid positions with possibly bad moves\",\n",
        "\"horizon effect\":\"agents choose to delay inevitable moves it cant see\",\n",
        "\"expectimax\":\"weighted sum of minimax value of children as node value\",\n",
        "\"utility function\":\"evaluates how desirable a state is\",\n",
        "\"expect utility\":\"average utility of outcomes\",\n",
        "\"ordinal utility function\": \"number for ranking preferences of agent\",\n",
        "\"normalized utilities\":\"value from 0 to 1\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 929
        },
        "outputId": "271aabb2-810c-4f89-9084-c5ce19d0c044"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nViewing adversary as economy, part of environment and adversiarial game-tree search makes up of the 3 stances on modeling adversarial games. It solves perfect information, zero-sum games\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nOptimal play of max assumes opponent plays optimally, but minimax may not be best when facing suboptimal opponents. Alliance can be a natural consequence of optimal moves. Optimizing search sequence can improve alpha-beta pruning. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo cut down the need of computation power that minimax might pose, methods like h-minimax, forward pruning and late move reduction may be applied to cut-off search. Actions found these way may not be optimal. Lookup resources in database can also aid searching.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games introduce random factors like rolling a dice. The minimax search is replaced with expectimax to solve such problems. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nThe simplest decision making depends on the maximum expected utility principle. The decision making theory can be a start point, but cannot solve all AI problems.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nThe axioms of utility guarantees the existence of utility function. Utility function is not unique. In a deterministic game environment, only an ordinal utility function is necessary. Exact numbers are not vital\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nAlthough money values are often proportional to people's preference, it is often not a good utility measurement. Decision theory is normative in that it only models how rational agents behave. In real scenarios, people behave more different due to reasons of risk aversion, irrationality, certainty effect, etc.\n\n\n## Module 5 Lecture Notes\n\nValues should reflect average case not worst case in expectimax.\n\n\n## Module 5 Definitions\n* **Adversarial search problem** - multiple agents with competitive environment\n* **Zero-sum** - one lose one win\n* **Utility function** - evaluates how desirable a state is\n* **H-minimax** - use heuristic eval as expected utility to use minimax\n* **Singular extension** - only do moves clearly better at a position\n* **Quiescence search** - avoid positions with possibly bad moves\n* **Horizon effect** - agents choose to delay inevitable moves it cant see\n* **Expectimax** - weighted sum of minimax value of children as node value\n* **Expect utility** - average utility of outcomes\n* **Ordinal utility function** - number for ranking preferences of agent\n* **Normalized utilities** - value from 0 to 1\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "Variables, domains and constraints together formulate CSPs. Constraints can be n-nary or global. \\\n",
        "n-nary constraints have been proved to be equivalent to binary ones given enough intermediate variables. \\\n",
        "Global constraints are preferred than binary ones for constructing solutions. There are other factors like \\\n",
        "preference constraints in real-world scenarios that introduces constraint optimization problems.\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "One way to solve CSP is through constraint propagation. The key idea is to enforce local consistency. AC-3 is a \\\n",
        "popular method for enforcing arc consistency. Strong k-consistency means k, k-1,...,1 consistent. Other constraints \\\n",
        "like global constraints and resource constraint will involve other strategies in constraint propagation.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Constraint propagation may still run into conditions that multiple possible value assignments exist. To completely \\\n",
        "solve the problem, backtracking search stands out. Due to commutativity, order of inference can be optimized by mrv \\\n",
        "heuristics and degree heuristics. To avoid bad situations of failure, forward checking and backjumping during search \\\n",
        "will also help. Moreover, in backjumping, to avoid running into similar situations, constraint learning can be applied. \n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Local search can solve many CSPs, popular algorithms are min-conflict heuristics and constraint weighting. Local search \\\n",
        "is also effective because it can solve online problems when problems setting change.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "CSPs can be solved by decomposing the constraint graph to independent subgraphs. One popular method is make the graph \\\n",
        "tree like since CSP tree solver can solve it in linear time to number of variables. Another way is tree decomposition. \\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "AC-3 time complexity O(cd^3) worst case. c is number of arcs and d is domain size maximum. \\\n",
        "Tree csp O(nd^2)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"find values for variables satisfying all constraints\",\n",
        "\"node consistency\":\"unary consistency\",\n",
        "\"arc consistency\":\"binary consistency\",\n",
        "\"path consistency\":\"3 consistency\",\n",
        "\"commutative\":\"order of action doesn't matter\",\n",
        "\"mrv heuristic\":'minimum-remainig-values',\n",
        "\"degree heuristic\":\"most constraining value\",\n",
        "\"conflict set\": \"a set of values of other variables conflicting the current variable\",\n",
        "\"constraint learning\":\"find the minimum subset causing the conflict sets\",\n",
        "\"min-conflicts\":\"randomly adjust illegal variables to position with fewest conflicts\",\n",
        "\"constraint weighting\":\"change value with lowest total weight of violated constraints\",\n",
        "\"tree width\":\"size of largest node in tree decomposition - 1\",\n",
        "\"topological sort\":\"child after parent in tree\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 881
        },
        "outputId": "a689e20d-5362-40b2-e702-ff1eb90747cc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nVariables, domains and constraints together formulate CSPs. Constraints can be n-nary or global. n-nary constraints have been proved to be equivalent to binary ones given enough intermediate variables. Global constraints are preferred than binary ones for constructing solutions. There are other factors like preference constraints in real-world scenarios that introduces constraint optimization problems.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nOne way to solve CSP is through constraint propagation. The key idea is to enforce local consistency. AC-3 is a popular method for enforcing arc consistency. Strong k-consistency means k, k-1,...,1 consistent. Other constraints like global constraints and resource constraint will involve other strategies in constraint propagation.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nConstraint propagation may still run into conditions that multiple possible value assignments exist. To completely solve the problem, backtracking search stands out. Due to commutativity, order of inference can be optimized by mrv heuristics and degree heuristics. To avoid bad situations of failure, forward checking and backjumping during search will also help. Moreover, in backjumping, to avoid running into similar situations, constraint learning can be applied. \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search can solve many CSPs, popular algorithms are min-conflict heuristics and constraint weighting. Local search is also effective because it can solve online problems when problems setting change.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nCSPs can be solved by decomposing the constraint graph to independent subgraphs. One popular method is make the graph tree like since CSP tree solver can solve it in linear time to number of variables. Another way is tree decomposition. \n\n## Module 6 Lecture Notes\n\nAC-3 time complexity O(cd^3) worst case. c is number of arcs and d is domain size maximum. Tree csp O(nd^2)\n\n\n## Module 6 Definitions\n* **Csp** - find values for variables satisfying all constraints\n* **Node consistency** - unary consistency\n* **Arc consistency** - binary consistency\n* **Path consistency** - 3 consistency\n* **Commutative** - order of action doesn't matter\n* **Mrv heuristic** - minimum-remainig-values\n* **Degree heuristic** - most constraining value\n* **Conflict set** - a set of values of other variables conflicting the current variable\n* **Constraint learning** - find the minimum subset causing the conflict sets\n* **Min-conflicts** - randomly adjust illegal variables to position with fewest conflicts\n* **Constraint weighting** - change value with lowest total weight of violated constraints\n* **Tree width** - size of largest node in tree decomposition - 1\n* **Topological sort** - child after parent in tree\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 = \"\"\"\n",
        "Knowledge-based agents maintains a knowledge base as a set of assertions of the world. Agent designers \\\n",
        "can TELL the agent by adding new assertions to the KB and ASK it by designing a way to ASK the agent. Inferences \\\n",
        "can be derived from known assertions in the KB. KB agents are amenable to descriptions at its knowledge level. Currently \\\n",
        "Knowledge base are constructed by a combination of declarative and procedural approaches.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"An example of wumpus game\"\"\"\n",
        "chapter7_3 = \"\"\"Inference algorithms should not make things up and preserve truths. It should also be able to derive all \\\n",
        "entailed sentences. To make KB system feasible, we need to ensure that KB is true in the real world, but not merely in agents world.\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" Atomic sentences are given by propositional symbols standing for statements (boolean). \\\n",
        "Complex sentences are combination of simpler ones by parentheses and logical connectives. A simple KB can be constructed this way.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Inference rules help to prove logical problems. If every sentence of propositional logic is CNF, it can lead to a complete inference procedure. \\\n",
        "Resolution algorithms can be applied to CNF clauses to form a KB.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "commutativity, associativity \\n\n",
        "a implies b == not b implies not a == not a or b (Contraposition, implication elimination) \\n\n",
        "a <=> b = ((a =>b) and (b=>a)) (Biconditional elimination) \\n\n",
        "not (a and b) == (not a or not b) (De Morgan) \\n\n",
        "not (a or b) == (not a and not b) (De Morgan) \\n\n",
        "((a and b) or c) == ((a and b) or (a and c)) (Distributivity of and over or) \\n\n",
        "((a or b) and c) == ((a or b) and (a or c)) (Distributivity of or over and) \\n\n",
        "resolution algorithm: CNF->resolve every pair with complementary literal->add new clause if not present \\\n",
        "->end if no new clause(KB not entail a) or empty clauses yielded (KB entails a)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"axiom\" : \"assertion without being derived from other assertions\",\n",
        "\"knowledge level\": \"the extent to which things we need to tell the agent\",\n",
        "\"implementation level\":\"how the knowledge are programed\",\n",
        "\"declarative\":\"sentence one by one\",\n",
        "\"procedural\":\"construct from code\",\n",
        "\"syntax\":\"well-formed representation language\",\n",
        "\"semantics\":\"definition of truths in all possible worlds\",\n",
        "\"|=\":\"entailment, M(a) is subset of M(b) if a|=b\",\n",
        "\"KB|-i a\":\"i derives a from KB, i is the inference algorithm\",\n",
        "\"logical connectives\":\"and, or, not, implies, iff\",\n",
        "\"validity\":\"true in all models\",\n",
        "\"satisfiablity\":\"true in some model\",\n",
        "\"CNF\":\"expressed in a conjunction of clauses\",\n",
        "\"clause\":\"disjunction of literals\",\n",
        "\"definitive clause\":'exactly one literal is positive',\n",
        "\"horn clauses\":\"at most one literal is positive\",\n",
        "\"forward chaining\":'if queried propositional symbol is entailed by a knowledge base of definite clauses',\n",
        "\"backward chaining\":\"if one of q's premises is true, q is true\",\n",
        "\"sound\":\"can only derive entailed sentences\",\n",
        "\"completeness of inference algo\":\"it can derive all entailed sentences\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1127
        },
        "outputId": "db420a8d-1bbb-431b-945a-0abb468584f3"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-based agents maintains a knowledge base as a set of assertions of the world. Agent designers can TELL the agent by adding new assertions to the KB and ASK it by designing a way to ASK the agent. Inferences can be derived from known assertions in the KB. KB agents are amenable to descriptions at its knowledge level. Currently Knowledge base are constructed by a combination of declarative and procedural approaches.\n\n\n## AIMA Chapter 7.2 The Wumpus World\nAn example of wumpus game\n\n## AIMA Chapter 7.3 Logic\nInference algorithms should not make things up and preserve truths. It should also be able to derive all entailed sentences. To make KB system feasible, we need to ensure that KB is true in the real world, but not merely in agents world.\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Atomic sentences are given by propositional symbols standing for statements (boolean). Complex sentences are combination of simpler ones by parentheses and logical connectives. A simple KB can be constructed this way.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nInference rules help to prove logical problems. If every sentence of propositional logic is CNF, it can lead to a complete inference procedure. Resolution algorithms can be applied to CNF clauses to form a KB.\n\n\n## Module 7 Lecture Notes\n\ncommutativity, associativity \n\na implies b == not b implies not a == not a or b (Contraposition, implication elimination) \n\na <=> b = ((a =>b) and (b=>a)) (Biconditional elimination) \n\nnot (a and b) == (not a or not b) (De Morgan) \n\nnot (a or b) == (not a and not b) (De Morgan) \n\n((a and b) or c) == ((a and b) or (a and c)) (Distributivity of and over or) \n\n((a or b) and c) == ((a or b) and (a or c)) (Distributivity of or over and) \n\nresolution algorithm: CNF->resolve every pair with complementary literal->add new clause if not present ->end if no new clause(KB not entail a) or empty clauses yielded (KB entails a)\n\n\n## Module 7 Definitions\n* **Axiom** - assertion without being derived from other assertions\n* **Knowledge level** - the extent to which things we need to tell the agent\n* **Implementation level** - how the knowledge are programed\n* **Declarative** - sentence one by one\n* **Procedural** - construct from code\n* **Syntax** - well-formed representation language\n* **Semantics** - definition of truths in all possible worlds\n* **|=** - entailment, M(a) is subset of M(b) if a|=b\n* **Kb|-i a** - i derives a from KB, i is the inference algorithm\n* **Logical connectives** - and, or, not, implies, iff\n* **Validity** - true in all models\n* **Satisfiablity** - true in some model\n* **Cnf** - expressed in a conjunction of clauses\n* **Clause** - disjunction of literals\n* **Definitive clause** - exactly one literal is positive\n* **Horn clauses** - at most one literal is positive\n* **Forward chaining** - if queried propositional symbol is entailed by a knowledge base of definite clauses\n* **Backward chaining** - if one of q's premises is true, q is true\n* **Sound** - can only derive entailed sentences\n* **Completeness of inference algo** - it can derive all entailed sentences\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": 5670
        },
        "id": "T3cm1WV542_a",
        "outputId": "b7579803-c7aa-4a33-b9fc-c430154d6d72"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nAI is defined by two dimensions: human vs. rational and thought vs. behavior. Human actions are tested by Turing test. It passes if the human interrogator cannot tell the response is from a machine or a human. A total Turing test furter requires it to interact with people The computers needs nlp, knowledge representation automatied reasoning, ml, cv and robotics to pass a total Turing test. The rational action approach requires the development of an rational agent A rational agent approach is the prevailing one since it more general than thought approaches and it is more amenable Beyond the technical aspect, machine must not misbehave only for achieving their designated goals to be beneficial to humans. \n\n## AIMA Chapter 27.1 The Limits of AI\n \nThe capability of AI has been questioned in 3 aspects: informality of human behaviours; disability and mathematical unanswerable questions But Turing argued that since humans cannot do this either in certain scenarios, a behavioral test might be better for measuring AI. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nThe question can machine think itself is hard to answer because consciousness is ill-defined. In this sense, human can always behave better with their subjective apparatus in certain tasks than intelligent machines.\n\n\n## AIMA 2.1 Agents and Environments\n\nAn agent perceive its environment and act accordingly. The environment can be anything that we care about when designing the agent. It can be mathematically defined as an agent function that maps percepts to actions. An agent program is the practical implementation of an agent function\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nA rational agent maximize the expected performance measuring. Rationality doesn't require omniscience because it's not possible, but it will gather information from environments and learn in action.\n\n\n## AIMA 2.3 The Nature of Environments\n Task environment has multiple properties based on how the world changes when agents acts\n\n## AIMA 2.4 The Structure of Agents\n Agent are designed in different ways to act based on percepts, history, goals or utilities \n\n## Module 1 Lecture Notes\n\nagent = architecture + program problem solving agents plan ahead\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Environment** - anything we care about when designing an agent\n* **Rational agent** - an agent that yields the best expected outcome\n* **Percept** - what agents perceives from environment\n* **Percept sequence** - complete history of percepts\n* **Sensor, actuator** - percept, action media, respectively\n* **Agent function** - mathematical abstraction that maps percepts to actions\n* **Agent program** - physical implementation of agent function\n* **Omniscience** - maximize actual outcome\n* **Task environment** - the target problem with PEAS\n* **Peas** - performance, environment, sensors, actuators\n* **Fully observable** - agents can always see the complete state of environment\n* **Deterministic** - previous state and agent action completely determines next state\n* **Episodic** - percept then act, atomic and independent\n* **Sequential** - action affects further\n* **Static** - not changing environment\n* **Known** - outcomes are given\n* **Simple reflex agent** - only acts to the current percept\n* **Internal state** - reflects aspects of current state and depends on percept history\n* **Transition model** - encodes changes in world to update internal states\n* **Utility** - measures how good a situation is for the agent\n* **Utility function** - internal performance measure\n* **Atomic representation** - no internal structure in states\n* **Factored** - divided by avariables\n* **Structured** - relationships between objects in states\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nPython uses strong and dynamic typing. \n\nPrefix with r means raw (no escape) \n\nSlicing: [start:end:step] \n\ndictionary keys must be immutable \n\nPython doesn't allow overloading \n\n*args for non-keyward and *kwargs (dict) for keywords passing \n\n [expression for _ in iterable if condition ] \n\n\n\n## Module 2 Definitions\n* **Mutability** - internal element cannot be changed\n* **Strong typing** - object has fixed type and incompatible operations won't be allowed\n* **Dynamic typing** - variables only given type at runtime\n* **Static typing** - variable can only be declared type\n* **Duck typing** - no need for interface for methods like __len__\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nWhen the environment is fully observable, deterministic, known, the solution is fixed sequence of actions. A search problem is defined by state space, initial state, goal state, action, transition model and action cost To formulate a problem, abstraction is necessary to remove redundant details.\n\n\n## AIMA Chapter 3.2 Example Problems\n Examples of standardized problems \n\n## AIMA Chapter 3.3 Search Algorithms\n \nSearch algorithms takes in a search problem and return a solution. It has a tree structure. Best-first search choose node with optimal evaluation function. Graph search checks redundant paths but tree search doesn't. Tree use less memory but examines redundant paths thus runs slower. Search algorithms need to consider completeness, optimality, time and space complexity.   \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS, IDDFS, Bidirectional search and uniform-cost search are complete and optimal. Goal is examined when expanding node in uc search so optimality is guaranteed. IDDFS is preferred over BFS when depth of solution is unknown. UC search can be seen as best-first search of path cost as eval function.\n\n\n## Module 3 Lecture Notes\n \nBFS time space complexity: both O(b^d) \n\nDFS time O(b^m), space O(bm) \n\nIDDFS time O(b^d), space O(bd) \n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - percepts are ignored\n* **Standardized problems** - problems for illustrating or exercising solving methods\n* **Branching factor** - number of actions to be considered at a node\n* **Uninformed** - only have access to problem definition\n* **Bidirectional search** - two frontiers are maintained, on from initial one from goal\n* **Depth d** - depth of shallowest goal node\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy best-first search expands nodes with lowest h(n), A* expands g(n)+h(n) GBFS complete in finite state space; A* complete with admissible h(n). Consistency ensures admissibility, but not vice versa. When, suboptimal solutions can be accepted, there are multiple ways to reduce computation by using weighted A*, etc. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe quality of heuristic function greatly influences the performance of heuristic search algorithms. A good heuristic can be constructed by methods like relaxing problem, precomputing solution costs of subproblems or learning through experience\n\n\n## Module 4 Lecture Notes\n\nCost of optimal solution to relaxed problem is admissible h(n) for original.\n\n\n## Module 4 Definitions\n* **Heuristic** - estimate cost from current node to goal\n* **Admissible** - never overestimating\n* **Consistency** - $$cost(action)+ h(child) \\geq h(parent)$$\n* **Optimally efficient** - all other search must expand the expanded nodes in the current search scheme\n* **Satisficing search** - A* with inadmissible h(n)\n* **Speedy search** - gbfs with h(n)=# of actions\n* **Effective branching factor** - N+1 = sum(b*^d)\n* **Relaxed problem** - few constraints on action\n* **Frontier** - set of legal states for next action\n* **Dominance** - h2>h1 for all n\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nViewing adversary as economy, part of environment and adversiarial game-tree search makes up of the 3 stances on modeling adversarial games. It solves perfect information, zero-sum games\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nOptimal play of max assumes opponent plays optimally, but minimax may not be best when facing suboptimal opponents. Alliance can be a natural consequence of optimal moves. Optimizing search sequence can improve alpha-beta pruning. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo cut down the need of computation power that minimax might pose, methods like h-minimax, forward pruning and late move reduction may be applied to cut-off search. Actions found these way may not be optimal. Lookup resources in database can also aid searching.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games introduce random factors like rolling a dice. The minimax search is replaced with expectimax to solve such problems. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nThe simplest decision making depends on the maximum expected utility principle. The decision making theory can be a start point, but cannot solve all AI problems.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nThe axioms of utility guarantees the existence of utility function. Utility function is not unique. In a deterministic game environment, only an ordinal utility function is necessary. Exact numbers are not vital\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nAlthough money values are often proportional to people's preference, it is often not a good utility measurement. Decision theory is normative in that it only models how rational agents behave. In real scenarios, people behave more different due to reasons of risk aversion, irrationality, certainty effect, etc.\n\n\n## Module 5 Lecture Notes\n\nValues should reflect average case not worst case in expectimax.\n\n\n## Module 5 Definitions\n* **Adversarial search problem** - multiple agents with competitive environment\n* **Zero-sum** - one lose one win\n* **Utility function** - evaluates how desirable a state is\n* **H-minimax** - use heuristic eval as expected utility to use minimax\n* **Singular extension** - only do moves clearly better at a position\n* **Quiescence search** - avoid positions with possibly bad moves\n* **Horizon effect** - agents choose to delay inevitable moves it cant see\n* **Expectimax** - weighted sum of minimax value of children as node value\n* **Expect utility** - average utility of outcomes\n* **Ordinal utility function** - number for ranking preferences of agent\n* **Normalized utilities** - value from 0 to 1\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nVariables, domains and constraints together formulate CSPs. Constraints can be n-nary or global. n-nary constraints have been proved to be equivalent to binary ones given enough intermediate variables. Global constraints are preferred than binary ones for constructing solutions. There are other factors like preference constraints in real-world scenarios that introduces constraint optimization problems.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nOne way to solve CSP is through constraint propagation. The key idea is to enforce local consistency. AC-3 is a popular method for enforcing arc consistency. Strong k-consistency means k, k-1,...,1 consistent. Other constraints like global constraints and resource constraint will involve other strategies in constraint propagation.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nConstraint propagation may still run into conditions that multiple possible value assignments exist. To completely solve the problem, backtracking search stands out. Due to commutativity, order of inference can be optimized by mrv heuristics and degree heuristics. To avoid bad situations of failure, forward checking and backjumping during search will also help. Moreover, in backjumping, to avoid running into similar situations, constraint learning can be applied. \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search can solve many CSPs, popular algorithms are min-conflict heuristics and constraint weighting. Local search is also effective because it can solve online problems when problems setting change.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nCSPs can be solved by decomposing the constraint graph to independent subgraphs. One popular method is make the graph tree like since CSP tree solver can solve it in linear time to number of variables. Another way is tree decomposition. \n\n## Module 6 Lecture Notes\n\nAC-3 time complexity O(cd^3) worst case. c is number of arcs and d is domain size maximum. Tree csp O(nd^2)\n\n\n## Module 6 Definitions\n* **Csp** - find values for variables satisfying all constraints\n* **Node consistency** - unary consistency\n* **Arc consistency** - binary consistency\n* **Path consistency** - 3 consistency\n* **Commutative** - order of action doesn't matter\n* **Mrv heuristic** - minimum-remainig-values\n* **Degree heuristic** - most constraining value\n* **Conflict set** - a set of values of other variables conflicting the current variable\n* **Constraint learning** - find the minimum subset causing the conflict sets\n* **Min-conflicts** - randomly adjust illegal variables to position with fewest conflicts\n* **Constraint weighting** - change value with lowest total weight of violated constraints\n* **Tree width** - size of largest node in tree decomposition - 1\n* **Topological sort** - child after parent in tree\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-based agents maintains a knowledge base as a set of assertions of the world. Agent designers can TELL the agent by adding new assertions to the KB and ASK it by designing a way to ASK the agent. Inferences can be derived from known assertions in the KB. KB agents are amenable to descriptions at its knowledge level. Currently Knowledge base are constructed by a combination of declarative and procedural approaches.\n\n\n## AIMA Chapter 7.2 The Wumpus World\nAn example of wumpus game\n\n## AIMA Chapter 7.3 Logic\nInference algorithms should not make things up and preserve truths. It should also be able to derive all entailed sentences. To make KB system feasible, we need to ensure that KB is true in the real world, but not merely in agents world.\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Atomic sentences are given by propositional symbols standing for statements (boolean). Complex sentences are combination of simpler ones by parentheses and logical connectives. A simple KB can be constructed this way.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nInference rules help to prove logical problems. If every sentence of propositional logic is CNF, it can lead to a complete inference procedure. Resolution algorithms can be applied to CNF clauses to form a KB.\n\n\n## Module 7 Lecture Notes\n\ncommutativity, associativity \n\na implies b == not b implies not a == not a or b (Contraposition, implication elimination) \n\na <=> b = ((a =>b) and (b=>a)) (Biconditional elimination) \n\nnot (a and b) == (not a or not b) (De Morgan) \n\nnot (a or b) == (not a and not b) (De Morgan) \n\n((a and b) or c) == ((a and b) or (a and c)) (Distributivity of and over or) \n\n((a or b) and c) == ((a or b) and (a or c)) (Distributivity of or over and) \n\nresolution algorithm: CNF->resolve every pair with complementary literal->add new clause if not present ->end if no new clause(KB not entail a) or empty clauses yielded (KB entails a)\n\n\n## Module 7 Definitions\n* **Axiom** - assertion without being derived from other assertions\n* **Knowledge level** - the extent to which things we need to tell the agent\n* **Implementation level** - how the knowledge are programed\n* **Declarative** - sentence one by one\n* **Procedural** - construct from code\n* **Syntax** - well-formed representation language\n* **Semantics** - definition of truths in all possible worlds\n* **|=** - entailment, M(a) is subset of M(b) if a|=b\n* **Kb|-i a** - i derives a from KB, i is the inference algorithm\n* **Logical connectives** - and, or, not, implies, iff\n* **Validity** - true in all models\n* **Satisfiablity** - true in some model\n* **Cnf** - expressed in a conjunction of clauses\n* **Clause** - disjunction of literals\n* **Definitive clause** - exactly one literal is positive\n* **Horn clauses** - at most one literal is positive\n* **Forward chaining** - if queried propositional symbol is entailed by a knowledge base of definite clauses\n* **Backward chaining** - if one of q's premises is true, q is true\n* **Sound** - can only derive entailed sentences\n* **Completeness of inference algo** - it can derive all entailed sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}