{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.6+"
    }
  },
  "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": [
        "\n",
        "# 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": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "b91e964a-f4d4-4918-a8eb-2e984519bfa8"
      },
      "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": null,
      "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": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "e207a912-22a8-4fdb-832c-acfb8822642f"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "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",
        "  ML is a sub-field of AI;\\n\n",
        "  Four dimensions: human vs. rational and thought vs. behavior;\\n\n",
        "  \\n\n",
        "  ACT HUMANLY\\n\n",
        "  Turing test: whether the response comes from a person or machine: NLP, knowledge representation, \\n\n",
        "  automated reasoning, ML; physical person simulation unnecessary \\n\n",
        "  Total turing test: interaction with person and objects; computer vision (percepts), robotics to manipulate;\\n\n",
        "  \\n\n",
        "  THINK HUMANLY\\n\n",
        "  Three ways to learn about human thoughts: introspection, psych experiment (observing), brain imaging (MRI)\\n\n",
        "  \\n\n",
        "  THINK RATIONALLY\\n\n",
        "  Syllogisms: Socrates is a man and all men are mortal and concludes that Socrates is mortal.\\n\n",
        "  Initiate the field of logic. \\n\n",
        "\\n\n",
        "  ACT RATIONALLY\\n\n",
        "  Agent: something that acts; \\n\n",
        "  Rational agent acts to achieve the best expected outcome; \\n\n",
        "  Two advantages over other approaches: \\n\n",
        "  1. more general than the law of thought because correct inference is just one of many\\n\n",
        "  mechanisms for achieving rationality;\\n\n",
        "  2. more amenable to scientific development \\n\n",
        "\\n\n",
        "  AI -- focus on the study and construction of agents that do the right thing (rational agents)\\n\n",
        "\\n\n",
        "  Perfect rationality -- always make the right choice -- is not feasible in complex environments; computational demand too high;\\n\n",
        "  good starting point for theoretical analysis\\n\n",
        "\\n\n",
        "  Limited rationality -- act appropriately when there's not enough time to do all computations\\n\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",
        "weak AI: machine act as if they are intelligent; \\n\n",
        "strong AI: machines are actually consciously thinking, not just simulating == human_level AI, general AI;\\n\n",
        "Embodied cognition: need to study system as a whole, robotics, visions, and sensors are central, not peripheral;\\n\n",
        "Gödel sentence: Lucas cannot consistently assert that this sentence is true. If Lucas assert, contradiction; if cannot consistently assert, then True\\n\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Searle, Chinese room, merely translation and delivery of the message;\\n\n",
        "The technical term for the intrinsic nature of experiences is qualia, can machines have qualia?\n",
        "According to what we have called the standard model, AI is concerned mainly with rational action. \n",
        "An ideal intelligent agent takes the best possible action in a situation. \n",
        "\\n\n",
        "Two refinements to this simple idea are needed: first, the ability of any agent, \n",
        "human or otherwise, to choose rational actions is limited by the computational intractability of doing so; \n",
        "second, the concept of a machine that pursues a definite objective needs to be replaced with that of \n",
        "a machine pursuing objectives to benefit humans, but uncertain as to what those objectives are.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "Agents perceive through sensors, act through actuators;\\n\n",
        "The agent function is an abstract mathematical description; \n",
        "the agent program is a concrete implementation, running within some physical system.\n",
        "the agent function for an artificial agent will be implemented by an agent program\\n\n",
        "\\n\n",
        "As a general rule, it is better to design performance measures according to \n",
        "what one actually wants to be achieved in the environment, \n",
        "rather than according to how one thinks the agent should behave.\n",
        "\\n\n",
        "omniscience agent knows the actual outcome of its actions and can act accordingly; \n",
        "but impossible in reality\n",
        "\\n\n",
        "A rational agent should be autonomous -- it should learn what it can to compensate for partial or incorrect prior knowledge\n",
        "rather than on the prior knowledge of designer\n",
        "\\n\n",
        "The agent program implements the agent function\n",
        "\n",
        "rational agent not guaranteed to find optimal solution. \n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "PEAS (Performance, Environment, Actuators, Sensors)  of task environment;\n",
        "\n",
        "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE (unobservable if no sensors at all)\n",
        "\n",
        "SINGLE-AGENT VS. MULTIAGENT (taxi, cooperative multiagent; chess, competitive multiagent);\n",
        "\n",
        "Deterministic vs. nondeterministic. \n",
        "  determinisitc: If the next state of the environment is completely determined \n",
        "  by the current state and the action executed by the agent(s)\n",
        "  taxi, nondeterministic\n",
        "stochastic: explicitly deals with probabilities\n",
        "\n",
        "EPISODIC VS. SEQUENTIAL: episoci: atomic, receives a percept and then performs a single action, \n",
        "next does not depend on the previous; sequential: current decision might affect future\n",
        "\n",
        "STATIC VS. DYNAMIC\n",
        "\n",
        "DISCREATE VS. CONTINUOUS\n",
        "\n",
        "KNOWN VS. UNKNOWN: respective to agent's knowledge. The outcomes are all given in known environment\n",
        "\n",
        "The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "Essential to agent program: take the current percept as input from the sensors and return an action to the actuators\n",
        "\n",
        "Simple reflex agents: select actions based on current percept, ignore history\n",
        "condition–action rule, if... then..., simple but limited intelligence, only if environment fullly observable\n",
        "A randomized simple reflex agent might outperform a deterministic simple reflex agent.\n",
        "\n",
        "Model-based reflex agents: keep track of the world\n",
        "Updating this internal state information require transition model and sensor model \n",
        "A transition model, which describes what each action does.\n",
        "\n",
        "Goal-based agents: search and planning, involved consideration of the future. more flexible \n",
        "\n",
        "Utility-based agents: internalization of performance measure, pro in flexiblility\n",
        "two kinds of cases, utility > goal: conflicting foals, several goals\n",
        "maximize expected utility\n",
        "\n",
        "search and game-playing -- atomic representation\n",
        "two different factored states can share some attributes and not others, CSP, propositional logic\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "    \"AI\" : \"not just understanding, but also building intelligent entities \",\n",
        "    \"agent\" : \"anything that can perceive and act in an environment\",\n",
        "    \"percept\" : \"the content perceived by an agent’s sensors\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "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": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "468557ed-efe0-4b16-9ae0-7f948232487a"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n  ML is a sub-field of AI;\n\n  Four dimensions: human vs. rational and thought vs. behavior;\n\n  \n\n  ACT HUMANLY\n\n  Turing test: whether the response comes from a person or machine: NLP, knowledge representation, \n\n  automated reasoning, ML; physical person simulation unnecessary \n\n  Total turing test: interaction with person and objects; computer vision (percepts), robotics to manipulate;\n\n  \n\n  THINK HUMANLY\n\n  Three ways to learn about human thoughts: introspection, psych experiment (observing), brain imaging (MRI)\n\n  \n\n  THINK RATIONALLY\n\n  Syllogisms: Socrates is a man and all men are mortal and concludes that Socrates is mortal.\n\n  Initiate the field of logic. \n\n\n\n  ACT RATIONALLY\n\n  Agent: something that acts; \n\n  Rational agent acts to achieve the best expected outcome; \n\n  Two advantages over other approaches: \n\n  1. more general than the law of thought because correct inference is just one of many\n\n  mechanisms for achieving rationality;\n\n  2. more amenable to scientific development \n\n\n\n  AI -- focus on the study and construction of agents that do the right thing (rational agents)\n\n\n\n  Perfect rationality -- always make the right choice -- is not feasible in complex environments; computational demand too high;\n\n  good starting point for theoretical analysis\n\n\n\n  Limited rationality -- act appropriately when there's not enough time to do all computations\n\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak AI: machine act as if they are intelligent; \n\nstrong AI: machines are actually consciously thinking, not just simulating == human_level AI, general AI;\n\nEmbodied cognition: need to study system as a whole, robotics, visions, and sensors are central, not peripheral;\n\nGödel sentence: Lucas cannot consistently assert that this sentence is true. If Lucas assert, contradiction; if cannot consistently assert, then True\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nSearle, Chinese room, merely translation and delivery of the message;\n\nThe technical term for the intrinsic nature of experiences is qualia, can machines have qualia?\nAccording to what we have called the standard model, AI is concerned mainly with rational action. \nAn ideal intelligent agent takes the best possible action in a situation. \n\n\nTwo refinements to this simple idea are needed: first, the ability of any agent, \nhuman or otherwise, to choose rational actions is limited by the computational intractability of doing so; \nsecond, the concept of a machine that pursues a definite objective needs to be replaced with that of \na machine pursuing objectives to benefit humans, but uncertain as to what those objectives are.\n\n \n\n## AIMA 2.1 Agents and Environments\n\nAgents perceive through sensors, act through actuators;\n\nThe agent function is an abstract mathematical description; \nthe agent program is a concrete implementation, running within some physical system.\nthe agent function for an artificial agent will be implemented by an agent program\n\n\n\nAs a general rule, it is better to design performance measures according to \nwhat one actually wants to be achieved in the environment, \nrather than according to how one thinks the agent should behave.\n\n\nomniscience agent knows the actual outcome of its actions and can act accordingly; \nbut impossible in reality\n\n\nA rational agent should be autonomous -- it should learn what it can to compensate for partial or incorrect prior knowledge\nrather than on the prior knowledge of designer\n\n\nThe agent program implements the agent function\n\nrational agent not guaranteed to find optimal solution. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n\nPEAS (Performance, Environment, Actuators, Sensors)  of task environment;\n\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE (unobservable if no sensors at all)\n\nSINGLE-AGENT VS. MULTIAGENT (taxi, cooperative multiagent; chess, competitive multiagent);\n\nDeterministic vs. nondeterministic. \n  determinisitc: If the next state of the environment is completely determined \n  by the current state and the action executed by the agent(s)\n  taxi, nondeterministic\nstochastic: explicitly deals with probabilities\n\nEPISODIC VS. SEQUENTIAL: episoci: atomic, receives a percept and then performs a single action, \nnext does not depend on the previous; sequential: current decision might affect future\n\nSTATIC VS. DYNAMIC\n\nDISCREATE VS. CONTINUOUS\n\nKNOWN VS. UNKNOWN: respective to agent's knowledge. The outcomes are all given in known environment\n\nThe hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n\nEssential to agent program: take the current percept as input from the sensors and return an action to the actuators\n\nSimple reflex agents: select actions based on current percept, ignore history\ncondition–action rule, if... then..., simple but limited intelligence, only if environment fullly observable\nA randomized simple reflex agent might outperform a deterministic simple reflex agent.\n\nModel-based reflex agents: keep track of the world\nUpdating this internal state information require transition model and sensor model \nA transition model, which describes what each action does.\n\nGoal-based agents: search and planning, involved consideration of the future. more flexible \n\nUtility-based agents: internalization of performance measure, pro in flexiblility\ntwo kinds of cases, utility > goal: conflicting foals, several goals\nmaximize expected utility\n\nsearch and game-playing -- atomic representation\ntwo different factored states can share some attributes and not others, CSP, propositional logic\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Ai** - not just understanding, but also building intelligent entities \n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content perceived by an agent’s sensors\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "id": "ydOK__lwWgdp",
        "outputId": "4ba24d11-6511-4f96-92c3-3148ac309df1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "Problem-solving agents use atomic representations, planning agents use factored or structured representations\n",
        "\n",
        "A standardized problem is intended to illustrate or exercise various problem- solving methods\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "best-first search: we choose a node n, with minimum value of some evaluation function f(n)\n",
        "\n",
        "To be complete, a search algorithm must be systematic in the way it explores an infinite state space\n",
        "\n",
        "BFS: Then the total number of nodes generated is O(b^d)\n",
        "\n",
        "Uniform-cost search is complete and is cost-optimal. Expand node with lowest path cost. \n",
        "uniform-cost search can explore large trees of actions with low costs before exploring useful path with high cost. \n",
        "C* = cost of optimal solution. e = lower bound on the cost of each action (e >0). O(b^(1+C*/e)), can be much greater than b^d. \n",
        "\n",
        "DFS: Depth-first search is not cost-optimal. For finite state spaces that are trees it is efficient and complete.\n",
        "but in infinite space, incomplete.\n",
        "depth-first search has much smaller needs for memory.\n",
        "memory complexity of only O(bm),  m is the maximum depth of the tree.\n",
        "Return first solution, even may not be cheapest. \n",
        "\n",
        "depth limited search: The time complexity is O(b^l), space complexity is O(bl). -- avoid infinite search space. \n",
        "\n",
        "Iterative deepening: memory requirements O(bd), or O(bm) on finite state spaces with no solution\n",
        "time complexity is O(b^d) when solution, O(b^m) when none.\n",
        "\n",
        "backtracking search, one node at a time. Remember partially expanded nodes. Memory O(m). \n",
        "Use set to check for cycle in O(1). \n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Djistra: uniform cost search without a goal.\n",
        "\n",
        "In general, iterative deepening is the preferred uninformed search method \n",
        "when the search state space is larger than can fit in memory and the depth of the solution is not known.\n",
        "\n",
        "bidirectoinal best first search: When the evaluation function is the path cost, \n",
        "we know that the first solution found will be an optimal solution, \n",
        "but with different evaluation functions that is not necessarily true. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 789
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "b1109415-3650-44bc-e2f9-1d70fa24d699"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nProblem-solving agents use atomic representations, planning agents use factored or structured representations\n\nA standardized problem is intended to illustrate or exercise various problem- solving methods\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n\nbest-first search: we choose a node n, with minimum value of some evaluation function f(n)\n\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space\n\nBFS: Then the total number of nodes generated is O(b^d)\n\nUniform-cost search is complete and is cost-optimal. Expand node with lowest path cost. \nuniform-cost search can explore large trees of actions with low costs before exploring useful path with high cost. \nC* = cost of optimal solution. e = lower bound on the cost of each action (e >0). O(b^(1+C*/e)), can be much greater than b^d. \n\nDFS: Depth-first search is not cost-optimal. For finite state spaces that are trees it is efficient and complete.\nbut in infinite space, incomplete.\ndepth-first search has much smaller needs for memory.\nmemory complexity of only O(bm),  m is the maximum depth of the tree.\nReturn first solution, even may not be cheapest. \n\ndepth limited search: The time complexity is O(b^l), space complexity is O(bl). -- avoid infinite search space. \n\nIterative deepening: memory requirements O(bd), or O(bm) on finite state spaces with no solution\ntime complexity is O(b^d) when solution, O(b^m) when none.\n\nbacktracking search, one node at a time. Remember partially expanded nodes. Memory O(m). \nUse set to check for cycle in O(1). \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nDjistra: uniform cost search without a goal.\n\nIn general, iterative deepening is the preferred uninformed search method \nwhen the search state space is larger than can fit in memory and the depth of the solution is not known.\n\nbidirectoinal best first search: When the evaluation function is the path cost, \nwe know that the first solution found will be an optimal solution, \nbut with different evaluation functions that is not necessarily true. \n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "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 is a form of best-first search that expands first the node with the lowest h(n) value. \n",
        "f(n) = h(n) -- cloest to the goal\n",
        "\n",
        "Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. \n",
        "The worst-case time and space complexity is O(|V|). With a good heuristic function O(bm).\n",
        "\n",
        "Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n",
        "\n",
        "A* search: f(n) = g(n) + h(n), path cost from initial state to n + heuristic.\n",
        "A* is complete. Heuristic consistency: for every node n and every successor n' of n generated by an action a we have:\n",
        "h(n) <= c(n, a, n') + h(n') -- heuristic of n is less than cost from n to n' + heuristic of n'.\n",
        "Memory O(b^d)\n",
        "\n",
        "path’s cost will be monotonically increasing iff heurisitc is consistent\n",
        "\n",
        "weighted A* search: where we weight the heuristic value more heavily, giving us the evaluation function \n",
        "f(n) = g(n) + h(n) * W, for some W > 1.\n",
        "If optimal solution cost C*, weighted A* finds solution between C* and WC*\n",
        "\n",
        "RBFS is optimal if the heuristic function is admissible. Space complexity linear in depth of the deepest optimal solution. \n",
        "\n",
        "bidirectional A*: no guarantee that this would lead to an optimal-cost solution. \n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "A well-designed heuristic would have a value of close to 1\n",
        "\n",
        "Hence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "# \"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 551
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "ea644d3b-d4be-42b7-c7b1-7fbe8a365ad1"
      },
      "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\", module3_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": null,
      "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 is a form of best-first search that expands first the node with the lowest h(n) value. \nf(n) = h(n) -- cloest to the goal\n\nGreedy best-first graph search is complete in finite state spaces, but not in infinite ones. \nThe worst-case time and space complexity is O(|V|). With a good heuristic function O(bm).\n\nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n\nA* search: f(n) = g(n) + h(n), path cost from initial state to n + heuristic.\nA* is complete. Heuristic consistency: for every node n and every successor n' of n generated by an action a we have:\nh(n) <= c(n, a, n') + h(n') -- heuristic of n is less than cost from n to n' + heuristic of n'.\nMemory O(b^d)\n\npath’s cost will be monotonically increasing iff heurisitc is consistent\n\nweighted A* search: where we weight the heuristic value more heavily, giving us the evaluation function \nf(n) = g(n) + h(n) * W, for some W > 1.\nIf optimal solution cost C*, weighted A* finds solution between C* and WC*\n\nRBFS is optimal if the heuristic function is admissible. Space complexity linear in depth of the deepest optimal solution. \n\nbidirectional A*: no guarantee that this would lead to an optimal-cost solution. \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nA well-designed heuristic would have a value of close to 1\n\nHence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\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",
        "deterministic, two-player, turn-taking, fully observable, zero-sum games.\n",
        "\n",
        "transition model: take action a in the state s\n",
        "\n",
        "If the maximum depth of the tree is m and there are b legal moves (branching factor) at each point, \n",
        "then the time complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) if all nodes\n",
        "expand at once or O(m) if generate one action at a time\n",
        "\n",
        "Ordering affect running time. alpha–beta would need to examine only O(b^(m/2))nodes to pick the best move, instead of O(b^m) for minimax. \n",
        "Put another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\n",
        "With random move ordering, the total number of nodes examined will be roughly O(b^(3m/4))for moderate . \n",
        "\n",
        "Claude Shannon: Type A strategy considers all possible moves to a certain depth in the search tree, \n",
        "and then uses a heuristic evaluation function to estimate the utility of states at that depth. \n",
        "It explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, \n",
        "and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n",
        "\n",
        "forward pruning: there is no guarantee that the best move will not be pruned away.\n",
        "\n",
        "expectiminimax is also considering all the possible dice-roll sequences, it will take (b^m n^m), where n is the number of distinct rolls.\n",
        "\n",
        "If the program knew in advance all the dice rolls that would occur for the rest of the game, \n",
        "solving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time\n",
        "\n",
        "In games where the branching factor for chance nodes is high, you may want to consider forward pruning \n",
        "that samples a smaller number of the possible chance branches. Or you may want to avoid using an evaluation function altogether, \n",
        "and opt for Monte Carlo tree search instead, where each playout includes random dice rolls.\n",
        "\"\"\"\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",
        "Maximum Expected Utility (MEU): a rational agent should choose the action that maximizes the agent’s expected utility\n",
        "\n",
        "Decision theory, in its simplest form, deals with choosing among actions based on the\n",
        "desirability of their immediate outcomes; that is, the environment is assumed to be episodic\n",
        "\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, \n",
        "then the agent will achieve the highest possible performance score (averaged over all the possible environments).\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "MEU not the only rational way\n",
        "\n",
        "axioms of utility theory/ six constraints that we require any reasonable preference relation to obey: \n",
        "ORDERABILITY -- a rational agent must either prefer one or else rate them as equally preferable\n",
        "TRANSITIVITY -- if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
        "CONTINUITY -- if B between A and C, an agent should either accept B, or A with probability p, or C with probability 1-p\n",
        "SUBSTITUTABILITY -- If an agent is indifferent between two lotteries and , then the agent is indifferent between two more complex lotteries that are the same except that\n",
        "is substituted for in one of them.\n",
        "MONOTONICITY -- If prefer A to B, must prefer lottery that has higher probability for A\n",
        "DECOMPOSABILITY -- Compound lotteries can be reduced to simpler ones using the laws of probability\n",
        "\n",
        "a utility function exists for any rational agent\n",
        "\n",
        "the existence of a utility function that describes an agent’s preference behavior does not necessarily mean \n",
        "that the agent is explicitly maximizing that utility function in its own deliberations\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Probability theory describes what an agent should believe on the basis of evidence,\n",
        "utility theory describes what an agent wants, and decision theory puts the two together\n",
        "to describe what an agent should do.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "4d7ce6d0-5154-433b-fd1c-555509c2ada0"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\ndeterministic, two-player, turn-taking, fully observable, zero-sum games.\n\ntransition model: take action a in the state s\n\nIf the maximum depth of the tree is m and there are b legal moves (branching factor) at each point, \nthen the time complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) if all nodes\nexpand at once or O(m) if generate one action at a time\n\nOrdering affect running time. alpha–beta would need to examine only O(b^(m/2))nodes to pick the best move, instead of O(b^m) for minimax. \nPut another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\nWith random move ordering, the total number of nodes examined will be roughly O(b^(3m/4))for moderate . \n\nClaude Shannon: Type A strategy considers all possible moves to a certain depth in the search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth. \nIt explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, \nand follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\nforward pruning: there is no guarantee that the best move will not be pruned away.\n\nexpectiminimax is also considering all the possible dice-roll sequences, it will take (b^m n^m), where n is the number of distinct rolls.\n\nIf the program knew in advance all the dice rolls that would occur for the rest of the game, \nsolving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time\n\nIn games where the branching factor for chance nodes is high, you may want to consider forward pruning \nthat samples a smaller number of the possible chance branches. Or you may want to avoid using an evaluation function altogether, \nand opt for Monte Carlo tree search instead, where each playout includes random dice rolls.\n\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\nMaximum Expected Utility (MEU): a rational agent should choose the action that maximizes the agent’s expected utility\n\nDecision theory, in its simplest form, deals with choosing among actions based on the\ndesirability of their immediate outcomes; that is, the environment is assumed to be episodic\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, \nthen the agent will achieve the highest possible performance score (averaged over all the possible environments).\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMEU not the only rational way\n\naxioms of utility theory/ six constraints that we require any reasonable preference relation to obey: \nORDERABILITY -- a rational agent must either prefer one or else rate them as equally preferable\nTRANSITIVITY -- if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\nCONTINUITY -- if B between A and C, an agent should either accept B, or A with probability p, or C with probability 1-p\nSUBSTITUTABILITY -- If an agent is indifferent between two lotteries and , then the agent is indifferent between two more complex lotteries that are the same except that\nis substituted for in one of them.\nMONOTONICITY -- If prefer A to B, must prefer lottery that has higher probability for A\nDECOMPOSABILITY -- Compound lotteries can be reduced to simpler ones using the laws of probability\n\na utility function exists for any rational agent\n\nthe existence of a utility function that describes an agent’s preference behavior does not necessarily mean \nthat the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nProbability theory describes what an agent should believe on the basis of evidence,\nutility theory describes what an agent wants, and decision theory puts the two together\nto describe what an agent should do.\n\n\n\n## Module 5 Lecture Notes\n Your summary here \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 = \"\"\"\n",
        "Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can be solved very efficiently.\n",
        "\n",
        "simplest kind of CSP involves variables that have discrete, finite domains (Map- coloring problems and scheduling with time limits)\n",
        "\n",
        "A discrete domain can be infinite (job scheduling without deadline)\n",
        "\n",
        "no algorithm exists for solving general nonlinear constraints on integer variables\n",
        "\n",
        "Linear programming problems can be solved in time polynomial in the number of variables\n",
        "\n",
        "The simplest type is the unary constraint (SA = green), which restricts the value of a single variable. \n",
        "A binary constraint relates two variables. SA != NSW.\n",
        "A constraint involving an arbitrary number of variables is called a global constraint (arbitrary number, need not involve all variables)\n",
        "\n",
        "every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced. \n",
        "This means that we could transform any CSP into one with only binary constraints\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "node-consistent (a single variable) if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
        "\n",
        "arc-consistent1 if every value in its domain satisfies the variable’s binary constraints\n",
        "\n",
        "If Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure\n",
        "\n",
        "Checking consistency of an arc can be done in O(d^2) time, so we get total worst-case O(cd^3) time. c = arcs\n",
        "\n",
        " A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \n",
        " a consistent value can always be assigned to any kth variable.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "minimum-remaining-values (MRV) heuristic -- choosing the variable with the fewest “legal” values/most constrained variable\n",
        "\n",
        "degree heuristic -- the variable that is involved in the largest number of constraints on other unassigned variables.'\n",
        "\n",
        "least-constraining-value heuristic -- It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
        "trying to leave the maximum flexibility for subsequent variable assignments\n",
        "\n",
        "Although forward checking detects many inconsistencies, it does not detect all of them.\n",
        "\n",
        "Maintaining Arc Consistency (MAC) detects inconsistencies like this. \n",
        "\n",
        "conflict-directed backjumping\n",
        "\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Local search algorithms, min-conflicts heuristic\n",
        "\n",
        "n-queens: if you don’t count the initial placement of queens, the run time of min-conflicts is roughly independent of problem size\n",
        "\n",
        "constraint weighting aims to concentrate the search on the important constraints\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Independence can be ascertained simply by finding connected components of the constraint graph. Each component corresponds to a subproblem\n",
        "\n",
        "Suppose each CSP_i has c variables from the total of n variables. Then there are n/c subproblems, \n",
        "each of which takes at most d^c work to solve, where d is the size of the domain. \n",
        "Hence, the total work is O(d^c n*c), which is linear in n (assume c is constant); \n",
        "without the decomposition, the total work is O(d^n), which is exponential in n\n",
        "\n",
        "dividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time \n",
        "from the lifetime of the universe down to less than a second.\n",
        "\n",
        "any tree-structured CSP can be solved in time linear in the number of variables. \n",
        "\n",
        "Any tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps.\n",
        "each compares up to d possible domain values for two variables, for a total time of O(nd^2)\n",
        "\n",
        "reduce constraint graph to a tree: assigning values to some variables so that the remaining variables form a tree. \n",
        "Assign value to SA, the rest become a tree. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "9ed3773f-ae47-49e7-a21e-ca247109dbd1"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nSolving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can be solved very efficiently.\n\nsimplest kind of CSP involves variables that have discrete, finite domains (Map- coloring problems and scheduling with time limits)\n\nA discrete domain can be infinite (job scheduling without deadline)\n\nno algorithm exists for solving general nonlinear constraints on integer variables\n\nLinear programming problems can be solved in time polynomial in the number of variables\n\nThe simplest type is the unary constraint (SA = green), which restricts the value of a single variable. \nA binary constraint relates two variables. SA != NSW.\nA constraint involving an arbitrary number of variables is called a global constraint (arbitrary number, need not involve all variables)\n\nevery finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced. \nThis means that we could transform any CSP into one with only binary constraints\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nnode-consistent (a single variable) if all the values in the variable’s domain satisfy the variable’s unary constraints.\n\narc-consistent1 if every value in its domain satisfies the variable’s binary constraints\n\nIf Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure\n\nChecking consistency of an arc can be done in O(d^2) time, so we get total worst-case O(cd^3) time. c = arcs\n\n A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \n a consistent value can always be assigned to any kth variable.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nminimum-remaining-values (MRV) heuristic -- choosing the variable with the fewest “legal” values/most constrained variable\n\ndegree heuristic -- the variable that is involved in the largest number of constraints on other unassigned variables.'\n\nleast-constraining-value heuristic -- It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\ntrying to leave the maximum flexibility for subsequent variable assignments\n\nAlthough forward checking detects many inconsistencies, it does not detect all of them.\n\nMaintaining Arc Consistency (MAC) detects inconsistencies like this. \n\nconflict-directed backjumping\n\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search algorithms, min-conflicts heuristic\n\nn-queens: if you don’t count the initial placement of queens, the run time of min-conflicts is roughly independent of problem size\n\nconstraint weighting aims to concentrate the search on the important constraints\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nIndependence can be ascertained simply by finding connected components of the constraint graph. Each component corresponds to a subproblem\n\nSuppose each CSP_i has c variables from the total of n variables. Then there are n/c subproblems, \neach of which takes at most d^c work to solve, where d is the size of the domain. \nHence, the total work is O(d^c n*c), which is linear in n (assume c is constant); \nwithout the decomposition, the total work is O(d^n), which is exponential in n\n\ndividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time \nfrom the lifetime of the universe down to less than a second.\n\nany tree-structured CSP can be solved in time linear in the number of variables. \n\nAny tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps.\neach compares up to d possible domain values for two variables, for a total time of O(nd^2)\n\nreduce constraint graph to a tree: assigning values to some variables so that the remaining variables form a tree. \nAssign value to SA, the rest become a tree. \n\n\n## Module 6 Lecture Notes\n Your summary here \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 = \"\"\"\n",
        "Axiom: when a sentence is taken without being derived from other sentences\n",
        "\n",
        "when agent program is called: 1) tell the KB what it perceives/MAKE PERCEPT SENTENCE 2) ask the KB what action to perform/MAKE ACTION QUERY 3) tell KB the action chosen (for execution)/MAKE ACTION SENTENCE\n",
        "\n",
        "declarative vs procedural: declarative: empty KB, tell sentences one by one until agent knows how to operate; procedual: encode desired behaviors directly\n",
        "successful agent combines both, declarative can be compiled into more efficient procedual\n",
        "\n",
        "learning agent can be fully autonomous\n",
        "\n",
        "PEAS: performance measure, environment, actuators, sensors\n",
        "\n",
        "wumpus word: deterministic, discrete, static, single agent, sequential, partially observable\n",
        "\n",
        "fundamental property of logical reasoning: conclusion is guaranteed to be correct if the available info is correct\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "semantics defines the truth of each sentence with respect to each possible world\n",
        "\n",
        "a entails b iff in every model in which a is true, b is also true. a is a stronger assertion than b; a rues out more possible worlds; a is a subset of b\n",
        "\n",
        "two properties of inference algo: sound and complete; \n",
        "unsound -- make things up. Model checking is a sound procedure. Model checking only works in the space of model is finite (wumpus world). x + y = 4 is infinite model space. \n",
        "complete: if it can derive any sentence that is entailed\n",
        "\n",
        "if KB is true, then any sentence alpha derived from KB by a sound inference is also true\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "If KB and alpha contain n symbols in all, then there are 2^n models. Time complexity is O(2^n) and space complexity is O(n).\n",
        "\n",
        "Every known inference algo for  propositional logic has a worst-case complexity that is exponential in the size of the input\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "finding a proof can be more efficient because the proof can ignore irrelevant propositions no matter how many of them they are\n",
        "\n",
        "resolution algo: proof by contradiction. To show KB entails a, show that KB and not a is unsatisfiable. \n",
        "First, convert (KB and not a) into CNF. Each pair that contains complementary literal is resolved to produce a new clause which is added to the set if it is not already present. the process continues until one of the two things happens: 1) there are no new clause that can be added -- KB does not entails A; 2) two clauses resolve to yield the empty clause -- KB entails A\n",
        "\n",
        "resolution closure is finite. always terminate. If a set of clauses is unsatisfiable, then the resolution closure contains the empty clause. \n",
        "\n",
        "definite clause: disjunction of literals of which EXACTLY ONE IS POSITIVE. (not A and not B and C). \n",
        "1) every definite clause can be weitten as an implication whose premise is a conjunct of positive literals and whose conclusion is a single positive literal\n",
        "2) inference with horn clauses can be down through forward/backward chaining. \n",
        "3) deciding entailment with horn clauses can be down in time that is linear in the size of the KB\n",
        "\n",
        "Horn clause: more general. AT MOST ONE IS POSITIVE. all definite clauses are horn clauses. If you resolve two horn clauses, you get back a horn clause. \n",
        "\n",
        "Forward chaining: if all premises of an implication are known, then its conclusion is added to the set of known facts. Process continues until the query q is added or until no further inferences can be made. \n",
        "\n",
        "backward chaining: goal-directed reasoning, finds implications whose conclusion is q. if all premises can be proven true, then q is true. \n",
        "\n",
        "forward chaining is data-driven\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "91e0590e-b1d7-43a7-a689-1a3f1237b8a5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nAxiom: when a sentence is taken without being derived from other sentences\n\nwhen agent program is called: 1) tell the KB what it perceives/MAKE PERCEPT SENTENCE 2) ask the KB what action to perform/MAKE ACTION QUERY 3) tell KB the action chosen (for execution)/MAKE ACTION SENTENCE\n\ndeclarative vs procedural: declarative: empty KB, tell sentences one by one until agent knows how to operate; procedual: encode desired behaviors directly\nsuccessful agent combines both, declarative can be compiled into more efficient procedual\n\nlearning agent can be fully autonomous\n\nPEAS: performance measure, environment, actuators, sensors\n\nwumpus word: deterministic, discrete, static, single agent, sequential, partially observable\n\nfundamental property of logical reasoning: conclusion is guaranteed to be correct if the available info is correct\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n\nsemantics defines the truth of each sentence with respect to each possible world\n\na entails b iff in every model in which a is true, b is also true. a is a stronger assertion than b; a rues out more possible worlds; a is a subset of b\n\ntwo properties of inference algo: sound and complete; \nunsound -- make things up. Model checking is a sound procedure. Model checking only works in the space of model is finite (wumpus world). x + y = 4 is infinite model space. \ncomplete: if it can derive any sentence that is entailed\n\nif KB is true, then any sentence alpha derived from KB by a sound inference is also true\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nIf KB and alpha contain n symbols in all, then there are 2^n models. Time complexity is O(2^n) and space complexity is O(n).\n\nEvery known inference algo for  propositional logic has a worst-case complexity that is exponential in the size of the input\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nfinding a proof can be more efficient because the proof can ignore irrelevant propositions no matter how many of them they are\n\nresolution algo: proof by contradiction. To show KB entails a, show that KB and not a is unsatisfiable. \nFirst, convert (KB and not a) into CNF. Each pair that contains complementary literal is resolved to produce a new clause which is added to the set if it is not already present. the process continues until one of the two things happens: 1) there are no new clause that can be added -- KB does not entails A; 2) two clauses resolve to yield the empty clause -- KB entails A\n\nresolution closure is finite. always terminate. If a set of clauses is unsatisfiable, then the resolution closure contains the empty clause. \n\ndefinite clause: disjunction of literals of which EXACTLY ONE IS POSITIVE. (not A and not B and C). \n1) every definite clause can be weitten as an implication whose premise is a conjunct of positive literals and whose conclusion is a single positive literal\n2) inference with horn clauses can be down through forward/backward chaining. \n3) deciding entailment with horn clauses can be down in time that is linear in the size of the KB\n\nHorn clause: more general. AT MOST ONE IS POSITIVE. all definite clauses are horn clauses. If you resolve two horn clauses, you get back a horn clause. \n\nForward chaining: if all premises of an implication are known, then its conclusion is added to the set of known facts. Process continues until the query q is added or until no further inferences can be made. \n\nbackward chaining: goal-directed reasoning, finds implications whose conclusion is q. if all premises can be proven true, then q is true. \n\nforward chaining is data-driven\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "dd373dd0-4246-4d1c-8cf0-c81b6e2436d4"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n  ML is a sub-field of AI;\n\n  Four dimensions: human vs. rational and thought vs. behavior;\n\n  \n\n  ACT HUMANLY\n\n  Turing test: whether the response comes from a person or machine: NLP, knowledge representation, \n\n  automated reasoning, ML; physical person simulation unnecessary \n\n  Total turing test: interaction with person and objects; computer vision (percepts), robotics to manipulate;\n\n  \n\n  THINK HUMANLY\n\n  Three ways to learn about human thoughts: introspection, psych experiment (observing), brain imaging (MRI)\n\n  \n\n  THINK RATIONALLY\n\n  Syllogisms: Socrates is a man and all men are mortal and concludes that Socrates is mortal.\n\n  Initiate the field of logic. \n\n\n\n  ACT RATIONALLY\n\n  Agent: something that acts; \n\n  Rational agent acts to achieve the best expected outcome; \n\n  Two advantages over other approaches: \n\n  1. more general than the law of thought because correct inference is just one of many\n\n  mechanisms for achieving rationality;\n\n  2. more amenable to scientific development \n\n\n\n  AI -- focus on the study and construction of agents that do the right thing (rational agents)\n\n\n\n  Perfect rationality -- always make the right choice -- is not feasible in complex environments; computational demand too high;\n\n  good starting point for theoretical analysis\n\n\n\n  Limited rationality -- act appropriately when there's not enough time to do all computations\n\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak AI: machine act as if they are intelligent; \n\nstrong AI: machines are actually consciously thinking, not just simulating == human_level AI, general AI;\n\nEmbodied cognition: need to study system as a whole, robotics, visions, and sensors are central, not peripheral;\n\nGödel sentence: Lucas cannot consistently assert that this sentence is true. If Lucas assert, contradiction; if cannot consistently assert, then True\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nSearle, Chinese room, merely translation and delivery of the message;\n\nThe technical term for the intrinsic nature of experiences is qualia, can machines have qualia?\nAccording to what we have called the standard model, AI is concerned mainly with rational action. \nAn ideal intelligent agent takes the best possible action in a situation. \n\n\nTwo refinements to this simple idea are needed: first, the ability of any agent, \nhuman or otherwise, to choose rational actions is limited by the computational intractability of doing so; \nsecond, the concept of a machine that pursues a definite objective needs to be replaced with that of \na machine pursuing objectives to benefit humans, but uncertain as to what those objectives are.\n\n \n\n## AIMA 2.1 Agents and Environments\n\nAgents perceive through sensors, act through actuators;\n\nThe agent function is an abstract mathematical description; \nthe agent program is a concrete implementation, running within some physical system.\nthe agent function for an artificial agent will be implemented by an agent program\n\n\n\nAs a general rule, it is better to design performance measures according to \nwhat one actually wants to be achieved in the environment, \nrather than according to how one thinks the agent should behave.\n\n\nomniscience agent knows the actual outcome of its actions and can act accordingly; \nbut impossible in reality\n\n\nA rational agent should be autonomous -- it should learn what it can to compensate for partial or incorrect prior knowledge\nrather than on the prior knowledge of designer\n\n\nThe agent program implements the agent function\n\nrational agent not guaranteed to find optimal solution. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n\nPEAS (Performance, Environment, Actuators, Sensors)  of task environment;\n\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE (unobservable if no sensors at all)\n\nSINGLE-AGENT VS. MULTIAGENT (taxi, cooperative multiagent; chess, competitive multiagent);\n\nDeterministic vs. nondeterministic. \n  determinisitc: If the next state of the environment is completely determined \n  by the current state and the action executed by the agent(s)\n  taxi, nondeterministic\nstochastic: explicitly deals with probabilities\n\nEPISODIC VS. SEQUENTIAL: episoci: atomic, receives a percept and then performs a single action, \nnext does not depend on the previous; sequential: current decision might affect future\n\nSTATIC VS. DYNAMIC\n\nDISCREATE VS. CONTINUOUS\n\nKNOWN VS. UNKNOWN: respective to agent's knowledge. The outcomes are all given in known environment\n\nThe hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n\nEssential to agent program: take the current percept as input from the sensors and return an action to the actuators\n\nSimple reflex agents: select actions based on current percept, ignore history\ncondition–action rule, if... then..., simple but limited intelligence, only if environment fullly observable\nA randomized simple reflex agent might outperform a deterministic simple reflex agent.\n\nModel-based reflex agents: keep track of the world\nUpdating this internal state information require transition model and sensor model \nA transition model, which describes what each action does.\n\nGoal-based agents: search and planning, involved consideration of the future. more flexible \n\nUtility-based agents: internalization of performance measure, pro in flexiblility\ntwo kinds of cases, utility > goal: conflicting foals, several goals\nmaximize expected utility\n\nsearch and game-playing -- atomic representation\ntwo different factored states can share some attributes and not others, CSP, propositional logic\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Ai** - not just understanding, but also building intelligent entities \n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content perceived by an agent’s sensors\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nProblem-solving agents use atomic representations, planning agents use factored or structured representations\n\nA standardized problem is intended to illustrate or exercise various problem- solving methods\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n\nbest-first search: we choose a node n, with minimum value of some evaluation function f(n)\n\nTo be complete, a search algorithm must be systematic in the way it explores an infinite state space\n\nBFS: Then the total number of nodes generated is O(b^d)\n\nUniform-cost search is complete and is cost-optimal. Expand node with lowest path cost. \nuniform-cost search can explore large trees of actions with low costs before exploring useful path with high cost. \nC* = cost of optimal solution. e = lower bound on the cost of each action (e >0). O(b^(1+C*/e)), can be much greater than b^d. \n\nDFS: Depth-first search is not cost-optimal. For finite state spaces that are trees it is efficient and complete.\nbut in infinite space, incomplete.\ndepth-first search has much smaller needs for memory.\nmemory complexity of only O(bm),  m is the maximum depth of the tree.\nReturn first solution, even may not be cheapest. \n\ndepth limited search: The time complexity is O(b^l), space complexity is O(bl). -- avoid infinite search space. \n\nIterative deepening: memory requirements O(bd), or O(bm) on finite state spaces with no solution\ntime complexity is O(b^d) when solution, O(b^m) when none.\n\nbacktracking search, one node at a time. Remember partially expanded nodes. Memory O(m). \nUse set to check for cycle in O(1). \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nDjistra: uniform cost search without a goal.\n\nIn general, iterative deepening is the preferred uninformed search method \nwhen the search state space is larger than can fit in memory and the depth of the solution is not known.\n\nbidirectoinal best first search: When the evaluation function is the path cost, \nwe know that the first solution found will be an optimal solution, \nbut with different evaluation functions that is not necessarily true. \n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy best-first search is a form of best-first search that expands first the node with the lowest h(n) value. \nf(n) = h(n) -- cloest to the goal\n\nGreedy best-first graph search is complete in finite state spaces, but not in infinite ones. \nThe worst-case time and space complexity is O(|V|). With a good heuristic function O(bm).\n\nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n\nA* search: f(n) = g(n) + h(n), path cost from initial state to n + heuristic.\nA* is complete. Heuristic consistency: for every node n and every successor n' of n generated by an action a we have:\nh(n) <= c(n, a, n') + h(n') -- heuristic of n is less than cost from n to n' + heuristic of n'.\nMemory O(b^d)\n\npath’s cost will be monotonically increasing iff heurisitc is consistent\n\nweighted A* search: where we weight the heuristic value more heavily, giving us the evaluation function \nf(n) = g(n) + h(n) * W, for some W > 1.\nIf optimal solution cost C*, weighted A* finds solution between C* and WC*\n\nRBFS is optimal if the heuristic function is admissible. Space complexity linear in depth of the deepest optimal solution. \n\nbidirectional A*: no guarantee that this would lead to an optimal-cost solution. \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nA well-designed heuristic would have a value of close to 1\n\nHence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\ndeterministic, two-player, turn-taking, fully observable, zero-sum games.\n\ntransition model: take action a in the state s\n\nIf the maximum depth of the tree is m and there are b legal moves (branching factor) at each point, \nthen the time complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) if all nodes\nexpand at once or O(m) if generate one action at a time\n\nOrdering affect running time. alpha–beta would need to examine only O(b^(m/2))nodes to pick the best move, instead of O(b^m) for minimax. \nPut another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\nWith random move ordering, the total number of nodes examined will be roughly O(b^(3m/4))for moderate . \n\nClaude Shannon: Type A strategy considers all possible moves to a certain depth in the search tree, \nand then uses a heuristic evaluation function to estimate the utility of states at that depth. \nIt explores a wide but shallow portion of the tree. A Type B strategy ignores moves that look bad, \nand follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\nforward pruning: there is no guarantee that the best move will not be pruned away.\n\nexpectiminimax is also considering all the possible dice-roll sequences, it will take (b^m n^m), where n is the number of distinct rolls.\n\nIf the program knew in advance all the dice rolls that would occur for the rest of the game, \nsolving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time\n\nIn games where the branching factor for chance nodes is high, you may want to consider forward pruning \nthat samples a smaller number of the possible chance branches. Or you may want to avoid using an evaluation function altogether, \nand opt for Monte Carlo tree search instead, where each playout includes random dice rolls.\n\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\nMaximum Expected Utility (MEU): a rational agent should choose the action that maximizes the agent’s expected utility\n\nDecision theory, in its simplest form, deals with choosing among actions based on the\ndesirability of their immediate outcomes; that is, the environment is assumed to be episodic\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, \nthen the agent will achieve the highest possible performance score (averaged over all the possible environments).\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMEU not the only rational way\n\naxioms of utility theory/ six constraints that we require any reasonable preference relation to obey: \nORDERABILITY -- a rational agent must either prefer one or else rate them as equally preferable\nTRANSITIVITY -- if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\nCONTINUITY -- if B between A and C, an agent should either accept B, or A with probability p, or C with probability 1-p\nSUBSTITUTABILITY -- If an agent is indifferent between two lotteries and , then the agent is indifferent between two more complex lotteries that are the same except that\nis substituted for in one of them.\nMONOTONICITY -- If prefer A to B, must prefer lottery that has higher probability for A\nDECOMPOSABILITY -- Compound lotteries can be reduced to simpler ones using the laws of probability\n\na utility function exists for any rational agent\n\nthe existence of a utility function that describes an agent’s preference behavior does not necessarily mean \nthat the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nProbability theory describes what an agent should believe on the basis of evidence,\nutility theory describes what an agent wants, and decision theory puts the two together\nto describe what an agent should do.\n\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nSolving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can be solved very efficiently.\n\nsimplest kind of CSP involves variables that have discrete, finite domains (Map- coloring problems and scheduling with time limits)\n\nA discrete domain can be infinite (job scheduling without deadline)\n\nno algorithm exists for solving general nonlinear constraints on integer variables\n\nLinear programming problems can be solved in time polynomial in the number of variables\n\nThe simplest type is the unary constraint (SA = green), which restricts the value of a single variable. \nA binary constraint relates two variables. SA != NSW.\nA constraint involving an arbitrary number of variables is called a global constraint (arbitrary number, need not involve all variables)\n\nevery finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced. \nThis means that we could transform any CSP into one with only binary constraints\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nnode-consistent (a single variable) if all the values in the variable’s domain satisfy the variable’s unary constraints.\n\narc-consistent1 if every value in its domain satisfies the variable’s binary constraints\n\nIf Di is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure\n\nChecking consistency of an arc can be done in O(d^2) time, so we get total worst-case O(cd^3) time. c = arcs\n\n A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, \n a consistent value can always be assigned to any kth variable.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nminimum-remaining-values (MRV) heuristic -- choosing the variable with the fewest “legal” values/most constrained variable\n\ndegree heuristic -- the variable that is involved in the largest number of constraints on other unassigned variables.'\n\nleast-constraining-value heuristic -- It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.\ntrying to leave the maximum flexibility for subsequent variable assignments\n\nAlthough forward checking detects many inconsistencies, it does not detect all of them.\n\nMaintaining Arc Consistency (MAC) detects inconsistencies like this. \n\nconflict-directed backjumping\n\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search algorithms, min-conflicts heuristic\n\nn-queens: if you don’t count the initial placement of queens, the run time of min-conflicts is roughly independent of problem size\n\nconstraint weighting aims to concentrate the search on the important constraints\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nIndependence can be ascertained simply by finding connected components of the constraint graph. Each component corresponds to a subproblem\n\nSuppose each CSP_i has c variables from the total of n variables. Then there are n/c subproblems, \neach of which takes at most d^c work to solve, where d is the size of the domain. \nHence, the total work is O(d^c n*c), which is linear in n (assume c is constant); \nwithout the decomposition, the total work is O(d^n), which is exponential in n\n\ndividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time \nfrom the lifetime of the universe down to less than a second.\n\nany tree-structured CSP can be solved in time linear in the number of variables. \n\nAny tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps.\neach compares up to d possible domain values for two variables, for a total time of O(nd^2)\n\nreduce constraint graph to a tree: assigning values to some variables so that the remaining variables form a tree. \nAssign value to SA, the rest become a tree. \n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nAxiom: when a sentence is taken without being derived from other sentences\n\nwhen agent program is called: 1) tell the KB what it perceives/MAKE PERCEPT SENTENCE 2) ask the KB what action to perform/MAKE ACTION QUERY 3) tell KB the action chosen (for execution)/MAKE ACTION SENTENCE\n\ndeclarative vs procedural: declarative: empty KB, tell sentences one by one until agent knows how to operate; procedual: encode desired behaviors directly\nsuccessful agent combines both, declarative can be compiled into more efficient procedual\n\nlearning agent can be fully autonomous\n\nPEAS: performance measure, environment, actuators, sensors\n\nwumpus word: deterministic, discrete, static, single agent, sequential, partially observable\n\nfundamental property of logical reasoning: conclusion is guaranteed to be correct if the available info is correct\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n\nsemantics defines the truth of each sentence with respect to each possible world\n\na entails b iff in every model in which a is true, b is also true. a is a stronger assertion than b; a rues out more possible worlds; a is a subset of b\n\ntwo properties of inference algo: sound and complete; \nunsound -- make things up. Model checking is a sound procedure. Model checking only works in the space of model is finite (wumpus world). x + y = 4 is infinite model space. \ncomplete: if it can derive any sentence that is entailed\n\nif KB is true, then any sentence alpha derived from KB by a sound inference is also true\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nIf KB and alpha contain n symbols in all, then there are 2^n models. Time complexity is O(2^n) and space complexity is O(n).\n\nEvery known inference algo for  propositional logic has a worst-case complexity that is exponential in the size of the input\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nfinding a proof can be more efficient because the proof can ignore irrelevant propositions no matter how many of them they are\n\nresolution algo: proof by contradiction. To show KB entails a, show that KB and not a is unsatisfiable. \nFirst, convert (KB and not a) into CNF. Each pair that contains complementary literal is resolved to produce a new clause which is added to the set if it is not already present. the process continues until one of the two things happens: 1) there are no new clause that can be added -- KB does not entails A; 2) two clauses resolve to yield the empty clause -- KB entails A\n\nresolution closure is finite. always terminate. If a set of clauses is unsatisfiable, then the resolution closure contains the empty clause. \n\ndefinite clause: disjunction of literals of which EXACTLY ONE IS POSITIVE. (not A and not B and C). \n1) every definite clause can be weitten as an implication whose premise is a conjunct of positive literals and whose conclusion is a single positive literal\n2) inference with horn clauses can be down through forward/backward chaining. \n3) deciding entailment with horn clauses can be down in time that is linear in the size of the KB\n\nHorn clause: more general. AT MOST ONE IS POSITIVE. all definite clauses are horn clauses. If you resolve two horn clauses, you get back a horn clause. \n\nForward chaining: if all premises of an implication are known, then its conclusion is added to the set of known facts. Process continues until the query q is added or until no further inferences can be made. \n\nbackward chaining: goal-directed reasoning, finds implications whose conclusion is q. if all premises can be proven true, then q is true. \n\nforward chaining is data-driven\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}