{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "3ab6096c-ecdb-40b8-80a3-f0b8bce57af4"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "e0c5798f-93b4-49c0-d139-92ad59acefb2"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 32,
      "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 = \"\"\" 1. Turing test by Alan Turing was designed as a thought experiment about \"Can a machine think?\" ...\n",
        "2. Six AI disciplines: NLP, Knowledge representation, Automated reasoning, ML, Total Turing Test, CV, Robotics  ...\n",
        "3. Rational agent advantages: more general than the \"laws of thought\" approach; more amenable to scientific development.\"\"\"\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 = \"\"\" Turing argument from informality of bahvior: human behavior too complex using formal set of rules(informal guideline that cannot be codify)...\n",
        "1. qualification problem: cannot capture behavior in a set of logiccal rules...\n",
        "2. embodied cognition: dont consider brain separately; cognition take place in body embedded in env; study system as whole...\n",
        "3. argument from disability: a machine never do X(be kind resourceful...) ...\n",
        "4. Incompleteness theorem: formal axiomatic framework f enough to do arithmetic, can construct Godel sentence G(F), a sentence of F but cannot be prove in F; if F is consistent, then G(F) is true...\n",
        "5. IT  show machine cannot establish truth of Godel...\n",
        "6. examination: 1. should not be ashamed if they cannot establish truth; Godel's IT applys to mathematics not computer; only to formal system that do arithmetic...\n",
        "7. Turing test: conversation for 5 mins, bahavioral test; pretend human and chat\"\"\"\n",
        "chapter27_2 = \"\"\" 1. Chinese room: argue no understanding...\n",
        "2. qualia: intrinsic nature of expression\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" 1. agents choice of action depend on its built-in knowledge and the entire percept sequence observed to date, not on anything hasn't...\n",
        "                  2. A function is abstract mathematical description; A program is concrete implementation with physical system\"\"\"\n",
        "chapter2_2 = \"\"\" 1. Rationality depends on: performane measure defined the criterion of success; agent's prior knowledge of the environment; actions of agent; agent's percept sequence to date...\n",
        "2. Rational and Omniscient : rationality maximizes expected performace; perfection maximize actual performance ...\n",
        "3. autonomy : the extend an agent relies on prior knowledge of its designer rather than on its percept and learning process means lack of autonomy\"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\"  1. Task environment: Performance, Environment, Actuators, Sensors...\n",
        "2. Fully observed: no need to maintain any internal state to keep track of the world...\n",
        "3. multi agent: B's behavior is described as maximizing a performance measure whose value depends on A's bahavior...\n",
        "4. stochastic/nondeterministic : stochastic if deals with probabilities; non if possibilities are listed without being quantified...\n",
        "5. episodic/ sequential: sequential(current decision affect all future decision); episodic(no need to think ahead) ...\n",
        "6. static/ dynamic: static(no need to keep looking the world); semidynamic(environment change by agent's performance score rather than the passage of time, chess played with clock)...\n",
        "7. discrete/continuous: state of environ; the way time is handled, and percepts and actions of agent....\n",
        "8. known/unknown: agent's state of knowledge about the \"laws of physics\" of the envir(known can be partially observed/unknown fully observed)\"\"\"\n",
        "chapter2_4 = \"\"\" 1. agent = architecture + program...\n",
        "2. agent problem skeleton : take current percept as input from the sensor and return action to actuator...\n",
        "3. simple reflex agent : select action on current percept, ignoring percept history;  only in fully observed env; infinite loop in partially observed(using randomized actions (may not be rational))...\n",
        "4. model-based reflex agent: (transition + sensor model)for partial observability by keeping track of internal state that depends on the percept history and reflect some part of current state...\n",
        "5. goal-based : using goal information; less efficient more flexible because knowledge supports its decision is explicit and can be modified...\n",
        "6. utility-based:  for high quality bahavior; rational decision when conflict goals; maximize the expected utility of the action...\n",
        "7. an agent that possesses an explicit utility function can make rational decisions with a general algo that does not depend on the specific utility being maximize...\n",
        "Learning Agent:\n",
        "1. any type of agent can be built as a learning agent(or not).\n",
        "2. Critic(how the agent is doing); Learning element(making improvements using feedback from critic); problem generator(suggenst actions); performance element(select external actions)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" All agents can improve performance through learning. \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment through sensors and acting through actuators\",\n",
        "\"computer agent\" : \"operate autonomously, perceive their environment, prsist over a prolonged time period, adapt to change, and create and pursue goals\",\n",
        "\"percept\" : \"content an agent's sensors are perceiving\",\n",
        "\"percept sequence\":\"the complete history of everything perceived\",\n",
        "\"standard model\" : \"213\",\n",
        "\"value alignment problem\": \"the values or objectives put into the machine must be aligned with those of human.\",\n",
        "\"agent function\" : \"describe the agent's behavior by maping any given percept sequence into action\",\n",
        "\"agent program\" : \"implement agent function for an artificial agent\",\n",
        "\"Consequentialism\" : \"evaluate an agent's behavior by it consequences\",\n",
        "\"Performance measure\" : \"evaluates given sequence of enviroment state\",\n",
        "\"rational agent\" : \"select an action that is expected to maximize its performance measure, given evidence from  percept sequence & built-in knowledge\",\n",
        "\"priori\" :\"geography of the environment\",\n",
        "\"omniscient\" : \"knows the actual outcome of its actions (impossible in reality)\",\n",
        "\"information gathering\":\"doing actions in order to modify future percepts (part of raionality)\",\n",
        "\"task environment\" : \"the problem to which rational agents are the solutions\",\n",
        "\"fully observed\" : \"agent's sensors give access to complete state of environment (sensor detect all that are relevant to choice of action)\",\n",
        "\"partially observed\" : \"noisy and inaccurate sensors or missing data (unobservable : no sensor)\",\n",
        "\"deterministic enviro\":\"next state of environment determined by current state and action by agent\",\n",
        "\"agent architecture\" : \"agent program run on some computing device with physical sensors and actuators\",\n",
        "\"transition model\" :\"the knowlegde about \\\"how the world changes\\\" - effects of the actions and how the world evolves independent of agent\",\n",
        "\"sensor model\" :\"how the state of the world is reflected in agent's sensor\",\n",
        "\"utility function\" : \"an internalization of the performance measure\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1729
        },
        "outputId": "0dca0e99-b07f-479d-ad07-985547435348"
      },
      "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": 34,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n 1. Turing test by Alan Turing was designed as a thought experiment about \"Can a machine think?\" ...\n2. Six AI disciplines: NLP, Knowledge representation, Automated reasoning, ML, Total Turing Test, CV, Robotics  ...\n3. Rational agent advantages: more general than the \"laws of thought\" approach; more amenable to scientific development.\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing argument from informality of bahvior: human behavior too complex using formal set of rules(informal guideline that cannot be codify)...\n1. qualification problem: cannot capture behavior in a set of logiccal rules...\n2. embodied cognition: dont consider brain separately; cognition take place in body embedded in env; study system as whole...\n3. argument from disability: a machine never do X(be kind resourceful...) ...\n4. Incompleteness theorem: formal axiomatic framework f enough to do arithmetic, can construct Godel sentence G(F), a sentence of F but cannot be prove in F; if F is consistent, then G(F) is true...\n5. IT  show machine cannot establish truth of Godel...\n6. examination: 1. should not be ashamed if they cannot establish truth; Godel's IT applys to mathematics not computer; only to formal system that do arithmetic...\n7. Turing test: conversation for 5 mins, bahavioral test; pretend human and chat\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n 1. Chinese room: argue no understanding...\n2. qualia: intrinsic nature of expression\n\n## AIMA 2.1 Agents and Environments\n 1. agents choice of action depend on its built-in knowledge and the entire percept sequence observed to date, not on anything hasn't...\n                  2. A function is abstract mathematical description; A program is concrete implementation with physical system\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n 1. Rationality depends on: performane measure defined the criterion of success; agent's prior knowledge of the environment; actions of agent; agent's percept sequence to date...\n2. Rational and Omniscient : rationality maximizes expected performace; perfection maximize actual performance ...\n3. autonomy : the extend an agent relies on prior knowledge of its designer rather than on its percept and learning process means lack of autonomy\n\n## AIMA 2.3 The Nature of Environments\n  1. Task environment: Performance, Environment, Actuators, Sensors...\n2. Fully observed: no need to maintain any internal state to keep track of the world...\n3. multi agent: B's behavior is described as maximizing a performance measure whose value depends on A's bahavior...\n4. stochastic/nondeterministic : stochastic if deals with probabilities; non if possibilities are listed without being quantified...\n5. episodic/ sequential: sequential(current decision affect all future decision); episodic(no need to think ahead) ...\n6. static/ dynamic: static(no need to keep looking the world); semidynamic(environment change by agent's performance score rather than the passage of time, chess played with clock)...\n7. discrete/continuous: state of environ; the way time is handled, and percepts and actions of agent....\n8. known/unknown: agent's state of knowledge about the \"laws of physics\" of the envir(known can be partially observed/unknown fully observed)\n\n## AIMA 2.4 The Structure of Agents\n 1. agent = architecture + program...\n2. agent problem skeleton : take current percept as input from the sensor and return action to actuator...\n3. simple reflex agent : select action on current percept, ignoring percept history;  only in fully observed env; infinite loop in partially observed(using randomized actions (may not be rational))...\n4. model-based reflex agent: (transition + sensor model)for partial observability by keeping track of internal state that depends on the percept history and reflect some part of current state...\n5. goal-based : using goal information; less efficient more flexible because knowledge supports its decision is explicit and can be modified...\n6. utility-based:  for high quality bahavior; rational decision when conflict goals; maximize the expected utility of the action...\n7. an agent that possesses an explicit utility function can make rational decisions with a general algo that does not depend on the specific utility being maximize...\nLearning Agent:\n1. any type of agent can be built as a learning agent(or not).\n2. Critic(how the agent is doing); Learning element(making improvements using feedback from critic); problem generator(suggenst actions); performance element(select external actions)\n\n\n## Module 1 Lecture Notes\n All agents can improve performance through learning. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment through sensors and acting through actuators\n* **Computer agent** - operate autonomously, perceive their environment, prsist over a prolonged time period, adapt to change, and create and pursue goals\n* **Percept** - content an agent's sensors are perceiving\n* **Percept sequence** - the complete history of everything perceived\n* **Standard model** - 213\n* **Value alignment problem** - the values or objectives put into the machine must be aligned with those of human.\n* **Agent function** - describe the agent's behavior by maping any given percept sequence into action\n* **Agent program** - implement agent function for an artificial agent\n* **Consequentialism** - evaluate an agent's behavior by it consequences\n* **Performance measure** - evaluates given sequence of enviroment state\n* **Rational agent** - select an action that is expected to maximize its performance measure, given evidence from  percept sequence & built-in knowledge\n* **Priori** - geography of the environment\n* **Omniscient** - knows the actual outcome of its actions (impossible in reality)\n* **Information gathering** - doing actions in order to modify future percepts (part of raionality)\n* **Task environment** - the problem to which rational agents are the solutions\n* **Fully observed** - agent's sensors give access to complete state of environment (sensor detect all that are relevant to choice of action)\n* **Partially observed** - noisy and inaccurate sensors or missing data (unobservable : no sensor)\n* **Deterministic enviro** - next state of environment determined by current state and action by agent\n* **Agent architecture** - agent program run on some computing device with physical sensors and actuators\n* **Transition model** - the knowlegde about \"how the world changes\" - effects of the actions and how the world evolves independent of agent\n* **Sensor model** - how the state of the world is reflected in agent's sensor\n* **Utility function** - an internalization of the performance measure\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": 35,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 210
        },
        "outputId": "a1bcc1ea-0b5b-46f1-9a2c-329e6767f05d"
      },
      "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": 36,
      "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 = \"\"\" 1. PS A use atomic representations...\n",
        "2. Search Problem: set of states; initial state; set of goal states; actions; transition model; action cost function  \n",
        "3. fully ob + deterministic + known = solution is fixed sequence of actions...\n",
        "4. partially ob + nondeter = solution recommend diff actions (branching stategy)...\n",
        "5. search algo treats states and actions atomic without internal structure \"\"\"\n",
        "chapter3_2 = \"\"\" 1. Standardized Problem: illustrate or exercise various problem solving method (grid world, sokoban, sliding-tile)...\n",
        "2. real-world: use solution (route finding, touring tsp, VLSI layout, robot navig, assembly sequencing protein design) \"\"\"\n",
        "chapter3_3 = \"\"\" 1. state space: set of states and actions; search tree: path between states, multiple path to a state but unque path to root...\n",
        "3. priority queue: first pop minimum cost; FIFO queue: first in first out; LIFO: stack...\n",
        "4. Best-First Search : choose minimum frontier with evaluation function f; graph search/tree search; ...\n",
        "5. solution if infinite loop: graph search: check redundant, check cycles ...\n",
        "6. evaluate algo: completeness; cost optimality; time complexity; space complexity;  \"\"\"\n",
        "chapter3_4 = \"\"\" 1. BFS: best-fs with f(n) is depth of the node; systematic search strategy, therefore complete; exponential space complexity\n",
        "2. Uniform-cost: f(n) = path cost; optimal...\n",
        "3. DFS : f(n) = negative depth; tree-like feasible; without reached; lower memory; variant: backtracking less mem(one successor atime); neither complete nor optimal...\n",
        "4. depth-limited(dfs): may cause cycle, use diameter(depth limit); optimal when same cost on actions; complete on finite acyclic\n",
        "5. Iterative-deepening: complete when full cycle check; optimal; linear space complexity.\n",
        "6. bidirectional: from initial and goal till frontier collide \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" DFS vs BFS:\n",
        "1. DFS if: restricted space; many possibles solutions with long paths, and wrong paths terminated quickly...\n",
        "2. BFS if: possible infinite paths; short path solution; quickly discard unlikely path. \"\"\"\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",
        "\"search problem\" : \"set of possible states that env can be, state space\",\n",
        "\"state vs node\":\"state is physical configuration; node is data structure part of search tree\",\n",
        "\"path\" : \"a sequence of actions\",\n",
        "\"solution\":\"path from initial to goal; optimal has lowest path cost\",\n",
        "\"model\":\"abstract mathematical description\",\n",
        "\"abstraction\":\"remove details from a representation, level of abstraction\",\n",
        "\"frontier\" : \"unexpanded node, separates interior(expanded) and exterior(unexpanded) nodes\",\n",
        "\"uninformed search\":\"use only information in problem definition, all non-goal nodes in frontier look equally good\",\n",
        "\"informed search\": \" some non-goal can be ranked above others, may have additional info such as pattern databases with solution costs\",\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 975
        },
        "outputId": "fe845bef-19c5-40a4-a257-19dabc266cef"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n 1. PS A use atomic representations...\n2. Search Problem: set of states; initial state; set of goal states; actions; transition model; action cost function  \n3. fully ob + deterministic + known = solution is fixed sequence of actions...\n4. partially ob + nondeter = solution recommend diff actions (branching stategy)...\n5. search algo treats states and actions atomic without internal structure \n\n## AIMA Chapter 3.2 Example Problems\n 1. Standardized Problem: illustrate or exercise various problem solving method (grid world, sokoban, sliding-tile)...\n2. real-world: use solution (route finding, touring tsp, VLSI layout, robot navig, assembly sequencing protein design) \n\n## AIMA Chapter 3.3 Search Algorithms\n 1. state space: set of states and actions; search tree: path between states, multiple path to a state but unque path to root...\n3. priority queue: first pop minimum cost; FIFO queue: first in first out; LIFO: stack...\n4. Best-First Search : choose minimum frontier with evaluation function f; graph search/tree search; ...\n5. solution if infinite loop: graph search: check redundant, check cycles ...\n6. evaluate algo: completeness; cost optimality; time complexity; space complexity;  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n 1. BFS: best-fs with f(n) is depth of the node; systematic search strategy, therefore complete; exponential space complexity\n2. Uniform-cost: f(n) = path cost; optimal...\n3. DFS : f(n) = negative depth; tree-like feasible; without reached; lower memory; variant: backtracking less mem(one successor atime); neither complete nor optimal...\n4. depth-limited(dfs): may cause cycle, use diameter(depth limit); optimal when same cost on actions; complete on finite acyclic\n5. Iterative-deepening: complete when full cycle check; optimal; linear space complexity.\n6. bidirectional: from initial and goal till frontier collide \n\n## Module 3 Lecture Notes\n DFS vs BFS:\n1. DFS if: restricted space; many possibles solutions with long paths, and wrong paths terminated quickly...\n2. BFS if: possible infinite paths; short path solution; quickly discard unlikely path. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search problem** - set of possible states that env can be, state space\n* **State vs node** - state is physical configuration; node is data structure part of search tree\n* **Path** - a sequence of actions\n* **Solution** - path from initial to goal; optimal has lowest path cost\n* **Model** - abstract mathematical description\n* **Abstraction** - remove details from a representation, level of abstraction\n* **Frontier** - unexpanded node, separates interior(expanded) and exterior(unexpanded) nodes\n* **Uninformed search** - use only information in problem definition, all non-goal nodes in frontier look equally good\n* **Informed search** -  some non-goal can be ranked above others, may have additional info such as pattern databases with solution costs\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 = \"\"\" 1. Greedy Best-first search: expand first node with lowest h(n), f(n) = h(n); not optimal but complete in finite state space but not in infinite ...\n",
        "2. A* search : complete and optimal; no reached; f(n) = g(n):path cost from ini to current +h(n) from current to goal/ estimated cost of the best path that continues from n to goal...\n",
        "3. heuristic: admissible; consistency(h(n) <= c(n, a,n')+h(n')); every consistent h is admissible(not vice versa); ...\n",
        "4. inconsistent: lead to multiple path, update successor to solve inconsistency ...\n",
        "5. inadmissible: may or may not be optimal(only one path)...\n",
        "6. suboptimal algo: bounded-cost(factor W of optimal); unbounded(speedy search quick)...\n",
        "7. weighted A*: weight the h more heavily, suboptimal solution...\n",
        "8. beam search: limit size of frontier; incomplete and suboptimal; fast...\n",
        "9. bidirectional heuristic search( not optimal) \"\"\"\n",
        "chapter3_6 = \"\"\" 1. effective branching factor b* to characterize the quality of h(n) ...\n",
        "2. N(total number of nodes generated): N+1 = 1+ b* + (b*)^2 + ..(b*)^d. ...\n",
        "3. good b* : close to 1. h2(n) >= h1(n) ==> h2 dominates h1, A* expands less node using h2 than h1. ...\n",
        "4. how admissible h: relaxed problem/ storing precomputed solution costs for subproblem in pattern db/ defining landmarks/ learn from experience. ...\n",
        "5. state-space graph of relaxed problem is supergraph of original with added edges. ...\n",
        "6. the cost of optimal solution in relaxed is admissible in original, also consistent. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"domain-specific information about the location of the goals inorder to find a solution more efficiently\",  \n",
        "\"admissible heuristic\":\" never overestimates the cost to goal, optimistic\" ,\n",
        "\"relaxed problem\" : \"fewer restriction on the action\" ,\n",
        "\"Bidirectional A*\":\"sometimes more efficient than A*\",\n",
        "\"IDA*\" :\"space complexity issue\",\n",
        "\"RBFS and SMA*\":\"robus, optimal with limited memory\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 690
        },
        "cellView": "form",
        "outputId": "8b81d65e-19f6-47f2-c4f4-9a9b52a4b8f4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n 1. Greedy Best-first search: expand first node with lowest h(n), f(n) = h(n); not optimal but complete in finite state space but not in infinite ...\n2. A* search : complete and optimal; no reached; f(n) = g(n):path cost from ini to current +h(n) from current to goal/ estimated cost of the best path that continues from n to goal...\n3. heuristic: admissible; consistency(h(n) <= c(n, a,n')+h(n')); every consistent h is admissible(not vice versa); ...\n4. inconsistent: lead to multiple path, update successor to solve inconsistency ...\n5. inadmissible: may or may not be optimal(only one path)...\n6. suboptimal algo: bounded-cost(factor W of optimal); unbounded(speedy search quick)...\n7. weighted A*: weight the h more heavily, suboptimal solution...\n8. beam search: limit size of frontier; incomplete and suboptimal; fast...\n9. bidirectional heuristic search( not optimal) \n\n## AIMA Chapter 3.6 Heuristic Functions\n 1. effective branching factor b* to characterize the quality of h(n) ...\n2. N(total number of nodes generated): N+1 = 1+ b* + (b*)^2 + ..(b*)^d. ...\n3. good b* : close to 1. h2(n) >= h1(n) ==> h2 dominates h1, A* expands less node using h2 than h1. ...\n4. how admissible h: relaxed problem/ storing precomputed solution costs for subproblem in pattern db/ defining landmarks/ learn from experience. ...\n5. state-space graph of relaxed problem is supergraph of original with added edges. ...\n6. the cost of optimal solution in relaxed is admissible in original, also consistent. \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - domain-specific information about the location of the goals inorder to find a solution more efficiently\n* **Admissible heuristic** -  never overestimates the cost to goal, optimistic\n* **Relaxed problem** - fewer restriction on the action\n* **Bidirectional a*** - sometimes more efficient than A*\n* **Ida*** - space complexity issue\n* **Rbfs and sma*** - robus, optimal with limited memory\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" 1. Minimax: (complete depth-first exploration)recursive algo that proceeds all the way down to the leaves of the tree and backs up the minimax val through tree as recursion unwind...\n",
        "2. node value: vector/ single val for two player, zero-sum...\n",
        "3. backup val of node n is utility vector of successor state with the highest val for the player choosing at n...\n",
        "4. collaboration might occur when not zero-sum ...\n",
        "5. alpha-beta pruning: alpha-at least for max, beta: at most for min ...\n",
        "6. ab pruning's effectiveness depends on the order in which the states are examined...\n",
        "7. transposition: diff permutations of moves leads to same position, transposition table to caches values\n",
        "8. Type A: all possible moves to a certain depth; Type B: ignore bad moves deep but narrow portion\"\"\"\n",
        "chapter5_3 = \"\"\" 1.  utility(loss) <= Eval <= utility(win) ...\n",
        "2. one Eval fun: weighted linear function w1f1(s)+w2f2(s)+...wnfn(s) f-feature, w-weight...\n",
        "3.  fixed depth limit lead to error due to approximation of eval function, only apply to quiescnet position...\n",
        "4. forward pruning:beam search(consider only one beam of n best moves rather all) probcut(using stats from prior experience to avoid pruning of best move)...\n",
        " - late move reduction(move ordering is good, later move not good)...\"\"\"\n",
        "chapter5_5 = \"\"\"  1. expectiminimax value: for stochastic game\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision Theory: maximization of expected utility...\n",
        " 1. decision theory: choosing among actions based on desirability of their immediate outcomes; env assumed to be episodic, cannot solve all but basic framework...\n",
        " 2. expected utility: average utility of outcomes weighted by the probability; guide actions...\n",
        " 3. maximum expected utility: perception for intelligent behavior\"\"\"\n",
        "chapter16_2 = \"\"\" Basis of utility theory...\n",
        "1. A > B prefer A; A ~ B indifferent; A >~ B prefer or indifferent...\n",
        "2. reasonable preference: orderability; transitivity; continuity: A>B>C , [p, A; 1-p, C]~B; substitutability: A~B => [p,A; 1-p, C]~[p,B; 1-p, C];monotonicity; frcomposability...\n",
        "3. existence of utility fun: A>B <-> U(A) > U(B); expected utility of lottery: utility of lottery = sum of utility*prob for each...\n",
        "4. value function/ordinal utility fun: preference ranking in deterministic env\"\"\"\n",
        "chapter16_3 = \"\"\"1. preference elicitation: using observed preference to pin down lying utility fun...\n",
        "2. best possible prize : u up = 1(normalized); worst possible catastrophe u down =0...\n",
        "3. Standard lottery [p, u down; (1-p) u up]...\n",
        "4. micromort: currency in medical and safety...\n",
        "5. QALY: quality-adjusted life year shorter life to avoid disability...\n",
        "6. utility of money: money is not utility fun, but monotonic preference for more money...\n",
        "7. normative theory: describe how rational agent acts(decision theory); descriptive theory: how actual agents do (people)...\n",
        "8. human irrational: reduce computational burden; distrust legitmacy of stated probability; emotional and financial state ...\n",
        "9. framing effect: exact wording of a decision problem impact choice...\n",
        "10. anchoring effect: restaurant 200$ wine and 55$ wines as bargain \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"adversarial search\" : \"competitive env, two or more agents conflict goals\",\n",
        "\"pruning\":\"ignoring portion of the search tree that make no diff to optimal move\",    \n",
        "\"perfect info\":\"fully observed\",    \n",
        "\"zero-sum\":\"no win-win, good for one bad for another\",    \n",
        "\"state space graph\":\"vertices-state, edge-moves, state might be reached by multi paths\",    \n",
        "\"game tree\":\"search tree that follows every sequence of moves all the way to terminal state, infinite if unbounded or repeating position\",    \n",
        "\"conditional plan\":\"strategy giving response to each min's possible move\",    \n",
        "\"ply\":\"one move by one player\",    \n",
        "\"minimax value\":\"utility of being that state, determinie the optimal strategy of game\",    \n",
        "\"cutoff test\":\"return true if terminal, else free to decide when to cut off based on depth and property(using depth)\",    \n",
        "\"EVAL\":\"expected utility of state s, as heuristic function distance to goal\",    \n",
        "\"quiescent position\":\"no pending move\",    \n",
        "\"horizon effct\":\"program facing opponent's move that causes unavoidable damage, temporarily avoid using delaying tactics, using singular extensions\",    \n",
        "\"singular extension\":\"mitigate horizon effect, moves that clearly better\",    \n",
        "\"forward pruning\":\"moves appear to be bad but might be good, save time at risk of error\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1537
        },
        "outputId": "7695fd8f-1ede-4de2-8fd7-3b1117005bbb"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n 1. Minimax: (complete depth-first exploration)recursive algo that proceeds all the way down to the leaves of the tree and backs up the minimax val through tree as recursion unwind...\n2. node value: vector/ single val for two player, zero-sum...\n3. backup val of node n is utility vector of successor state with the highest val for the player choosing at n...\n4. collaboration might occur when not zero-sum ...\n5. alpha-beta pruning: alpha-at least for max, beta: at most for min ...\n6. ab pruning's effectiveness depends on the order in which the states are examined...\n7. transposition: diff permutations of moves leads to same position, transposition table to caches values\n8. Type A: all possible moves to a certain depth; Type B: ignore bad moves deep but narrow portion\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n 1.  utility(loss) <= Eval <= utility(win) ...\n2. one Eval fun: weighted linear function w1f1(s)+w2f2(s)+...wnfn(s) f-feature, w-weight...\n3.  fixed depth limit lead to error due to approximation of eval function, only apply to quiescnet position...\n4. forward pruning:beam search(consider only one beam of n best moves rather all) probcut(using stats from prior experience to avoid pruning of best move)...\n - late move reduction(move ordering is good, later move not good)...\n\n## AIMA Chapter 5.5 Stochastic Games\n  1. expectiminimax value: for stochastic game\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision Theory: maximization of expected utility...\n 1. decision theory: choosing among actions based on desirability of their immediate outcomes; env assumed to be episodic, cannot solve all but basic framework...\n 2. expected utility: average utility of outcomes weighted by the probability; guide actions...\n 3. maximum expected utility: perception for intelligent behavior\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Basis of utility theory...\n1. A > B prefer A; A ~ B indifferent; A >~ B prefer or indifferent...\n2. reasonable preference: orderability; transitivity; continuity: A>B>C , [p, A; 1-p, C]~B; substitutability: A~B => [p,A; 1-p, C]~[p,B; 1-p, C];monotonicity; frcomposability...\n3. existence of utility fun: A>B <-> U(A) > U(B); expected utility of lottery: utility of lottery = sum of utility*prob for each...\n4. value function/ordinal utility fun: preference ranking in deterministic env\n\n## AIMA Chapter 16.3 Utility Functions\n1. preference elicitation: using observed preference to pin down lying utility fun...\n2. best possible prize : u up = 1(normalized); worst possible catastrophe u down =0...\n3. Standard lottery [p, u down; (1-p) u up]...\n4. micromort: currency in medical and safety...\n5. QALY: quality-adjusted life year shorter life to avoid disability...\n6. utility of money: money is not utility fun, but monotonic preference for more money...\n7. normative theory: describe how rational agent acts(decision theory); descriptive theory: how actual agents do (people)...\n8. human irrational: reduce computational burden; distrust legitmacy of stated probability; emotional and financial state ...\n9. framing effect: exact wording of a decision problem impact choice...\n10. anchoring effect: restaurant 200$ wine and 55$ wines as bargain \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Adversarial search** - competitive env, two or more agents conflict goals\n* **Pruning** - ignoring portion of the search tree that make no diff to optimal move\n* **Perfect info** - fully observed\n* **Zero-sum** - no win-win, good for one bad for another\n* **State space graph** - vertices-state, edge-moves, state might be reached by multi paths\n* **Game tree** - search tree that follows every sequence of moves all the way to terminal state, infinite if unbounded or repeating position\n* **Conditional plan** - strategy giving response to each min's possible move\n* **Ply** - one move by one player\n* **Minimax value** - utility of being that state, determinie the optimal strategy of game\n* **Cutoff test** - return true if terminal, else free to decide when to cut off based on depth and property(using depth)\n* **Eval** - expected utility of state s, as heuristic function distance to goal\n* **Quiescent position** - no pending move\n* **Horizon effct** - program facing opponent's move that causes unavoidable damage, temporarily avoid using delaying tactics, using singular extensions\n* **Singular extension** - mitigate horizon effect, moves that clearly better\n* **Forward pruning** - moves appear to be bad but might be good, save time at risk of error\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 = \"\"\" 1.  X variable sets, D domains for each X, C constraints ...\n",
        "2. why CSP: natural representation for wide variety og problem; solves fast efficient; quickly prune large swathes of search space that an atomic state-space cannot...\n",
        "3. variable types: discrete-finite domains: simplest; discrete-infinite: set of integers, need implicit linear contraints like t1+d <= t2(nonlinear con is undecidable); continuos domains: linear programming...\n",
        "4.  constraint types: unary: single val; binary: a <> b; global constraint: arbitrary number of variables, Alldiff: sudoku, cryptarithmetic...\n",
        "5. n-aray to binary: auxiliary var; dual graph: new graph where one var for each constraint in original graph and one binary constratint for each pair of constraint in original graph share variables...\n",
        "5. global constraint > binary constraint: easier and less error-prone; can use special-purpose inference more efficient...\n",
        "6. preference constraint: constrained optimization problem\"\"\"\n",
        "chapter6_2 = \"\"\" 1. CSP successor: choose new variable; constraint propagation: use constraint to reduce value\"\"\"\n",
        "chapter6_3 = \"\"\" 1. Backtracking search CSP : commutativity if the order of application of any set action does not matter...\n",
        "2. backtracking; forward checking\"\"\"\n",
        "chapter6_4 = \"\"\" 1. Local Search: min-conflicts ...\n",
        "2. Plateau search: allowing sideways moves to another state with the same score- help find its way off this plateau...\n",
        "3. constraint weighting: concentrate the search on important constraints : adds topology so possible to improve; adds learning...\n",
        "4. advantages of local search: online setting when problem changes; effective \"\"\"\n",
        "chapter6_5 = \"\"\" 1. independent subproblem: can be ascertained by finding connected components of the constraint graph...\n",
        "2. cutset conditioning: reduce a general CSP to tree-structured one, efficient if a small cutset found...\n",
        "- choose subset S of CSP's var such that constraint graph becomes a tree after removal of S(S is cycle cutset)...\n",
        "- for each assignment to var in S : remove from domains of remaining var any values that are inconsis with S and if remianing CSP has solution return...\n",
        "3. (reduce constraint graph) tree decomposition: transform CSP into tree subproblems, efficient when tree width is small, memory exponential ...\n",
        "- every var in original apears at least once; ...\n",
        "- two var connected, then appear together in at least one of the tree nodes; ...\n",
        "- one var in two nodes then in every node along the path connecting them...\n",
        "4. tree width : one less than size of the largetst node, defined to be minimum width among all decomposition\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP \" : \"factored representation for each state, variables with value, satisfied constrain\",    \n",
        "\"node consis\" : \"values in the domain satisfy the var's unary constraint, 1-consistency node\",    \n",
        "\"arc consis\" : \"binary constraint, AC-3,2-consistency node\",    \n",
        "\"path consis\" : \"tighten the binary constraints using implicit constraints inferred by looking at triples of var, 3-consistency node\",    \n",
        "\"k consis\" : \"if any set of k-1vars and for consis assignment to those, consist val can be assigned to any kth var.\",    \n",
        "\"strongly k consis\" : \"k consis, k-1 consis, .. 1-consis, NP-complete\",    \n",
        "\"resource constraint\" : \"higher-order constrint, atmost constraint\",    \n",
        "\"bounds consis\" : \"every X upper and lower bound, exists Y satisfied contraint between X and Y for every Y\",    \n",
        "\"minimum remaining values(MRV)\" : \"choosing vars with fewest moves\",    \n",
        "\"least constraint value\" : \"rules out the fewest choice for neighboring var\",    \n",
        "\"forward checking\" : \"form of inference, establishes arc consistency when assign X, for unassigned Y, delete from Y's domain inconsistent with Xval\",    \n",
        "\"Maintaining Arc Consi(MAC)\" : \"delete inconsis for assigning one leaving others only val that are not possible\",    \n",
        "\"chronological backtracking\" : \"back up to preceding var and try new one, most recent node is revisited\",    \n",
        "\"backjumping\" : \"back tracks to the most recent assignment in the conflict set(conflict-directed jumping), tell us how far to back up\",    \n",
        "\"min-conflicts\" : \"select val results in the minimum conflicts with others\",\n",
        "\"independent subproblems\":\"any solution for one combined with another yields a solution for the whole map\",\n",
        "\"directional arc consis\":\"under an ordering of X1 X2 .. if and only if every Xi is arc-consis wit Xj for j>i\",\n",
        "\"topological sort\":\"each vars appears after its parent in the tree\"\n",
        "}\n"
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1268
        },
        "outputId": "ee056931-fe7d-483e-ba8a-6cfdc6627e32"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n 1.  X variable sets, D domains for each X, C constraints ...\n2. why CSP: natural representation for wide variety og problem; solves fast efficient; quickly prune large swathes of search space that an atomic state-space cannot...\n3. variable types: discrete-finite domains: simplest; discrete-infinite: set of integers, need implicit linear contraints like t1+d <= t2(nonlinear con is undecidable); continuos domains: linear programming...\n4.  constraint types: unary: single val; binary: a <> b; global constraint: arbitrary number of variables, Alldiff: sudoku, cryptarithmetic...\n5. n-aray to binary: auxiliary var; dual graph: new graph where one var for each constraint in original graph and one binary constratint for each pair of constraint in original graph share variables...\n5. global constraint > binary constraint: easier and less error-prone; can use special-purpose inference more efficient...\n6. preference constraint: constrained optimization problem\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 1. CSP successor: choose new variable; constraint propagation: use constraint to reduce value\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n 1. Backtracking search CSP : commutativity if the order of application of any set action does not matter...\n2. backtracking; forward checking\n\n## AIMA Chapter 6.4 Local Search for CSPs\n 1. Local Search: min-conflicts ...\n2. Plateau search: allowing sideways moves to another state with the same score- help find its way off this plateau...\n3. constraint weighting: concentrate the search on important constraints : adds topology so possible to improve; adds learning...\n4. advantages of local search: online setting when problem changes; effective \n\n## AIMA Chapter 6.5 The Structure of Problems\n 1. independent subproblem: can be ascertained by finding connected components of the constraint graph...\n2. cutset conditioning: reduce a general CSP to tree-structured one, efficient if a small cutset found...\n- choose subset S of CSP's var such that constraint graph becomes a tree after removal of S(S is cycle cutset)...\n- for each assignment to var in S : remove from domains of remaining var any values that are inconsis with S and if remianing CSP has solution return...\n3. (reduce constraint graph) tree decomposition: transform CSP into tree subproblems, efficient when tree width is small, memory exponential ...\n- every var in original apears at least once; ...\n- two var connected, then appear together in at least one of the tree nodes; ...\n- one var in two nodes then in every node along the path connecting them...\n4. tree width : one less than size of the largetst node, defined to be minimum width among all decomposition\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp ** - factored representation for each state, variables with value, satisfied constrain\n* **Node consis** - values in the domain satisfy the var's unary constraint, 1-consistency node\n* **Arc consis** - binary constraint, AC-3,2-consistency node\n* **Path consis** - tighten the binary constraints using implicit constraints inferred by looking at triples of var, 3-consistency node\n* **K consis** - if any set of k-1vars and for consis assignment to those, consist val can be assigned to any kth var.\n* **Strongly k consis** - k consis, k-1 consis, .. 1-consis, NP-complete\n* **Resource constraint** - higher-order constrint, atmost constraint\n* **Bounds consis** - every X upper and lower bound, exists Y satisfied contraint between X and Y for every Y\n* **Minimum remaining values(mrv)** - choosing vars with fewest moves\n* **Least constraint value** - rules out the fewest choice for neighboring var\n* **Forward checking** - form of inference, establishes arc consistency when assign X, for unassigned Y, delete from Y's domain inconsistent with Xval\n* **Maintaining arc consi(mac)** - delete inconsis for assigning one leaving others only val that are not possible\n* **Chronological backtracking** - back up to preceding var and try new one, most recent node is revisited\n* **Backjumping** - back tracks to the most recent assignment in the conflict set(conflict-directed jumping), tell us how far to back up\n* **Min-conflicts** - select val results in the minimum conflicts with others\n* **Independent subproblems** - any solution for one combined with another yields a solution for the whole map\n* **Directional arc consis** - under an ordering of X1 X2 .. if and only if every Xi is arc-consis wit Xj for j>i\n* **Topological sort** - each vars appears after its parent in the tree\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Proposition logic: factored representation; less expressive than first-order logic(canonical structured representation)...\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" 1. logic: syntax; semantics(meaning); ...\n",
        "2. entailment, follows logically from another sentence |= ...\n",
        "3. KB|-i a a is derived from KB by i...\n",
        "4. inference : sound(truth preserving) ; completeness(derived any sentence that is entailed)\"\"\"\n",
        "chapter7_4 = \"\"\" 1. propositional logic...\n",
        "2. a|= b iff (a^-b) is not satisfiable\"\"\"\n",
        "chapter7_5 = \"\"\" 1. Modus Ponens: a=>b, a/ b...\n",
        "2, and-elimination: a^b/a...\n",
        "3. CNF  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"sentence\":\"expressed in knowledge representation language and represents assertions about the world\",\n",
        "\"axiom\" : \"sentence given without being derived from others\",    \n",
        "\"model checking\":\"inference algo, anumerates all possible models to check that a is true in all models in which KB is true\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 690
        },
        "outputId": "21f2fff0-b180-4300-edf8-b14a4a2087a1"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Proposition logic: factored representation; less expressive than first-order logic(canonical structured representation)...\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n 1. logic: syntax; semantics(meaning); ...\n2. entailment, follows logically from another sentence |= ...\n3. KB|-i a a is derived from KB by i...\n4. inference : sound(truth preserving) ; completeness(derived any sentence that is entailed)\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 1. propositional logic...\n2. a|= b iff (a^-b) is not satisfiable\n\n## AIMA 7.5 Propositional Theorem Proving\n 1. Modus Ponens: a=>b, a/ b...\n2, and-elimination: a^b/a...\n3. CNF  \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Sentence** - expressed in knowledge representation language and represents assertions about the world\n* **Axiom** - sentence given without being derived from others\n* **Model checking** - inference algo, anumerates all possible models to check that a is true in all models in which KB is true\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": 6960
        },
        "id": "T3cm1WV542_a",
        "outputId": "9d7ef879-a94b-4862-8402-0db845ff9420"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n 1. Turing test by Alan Turing was designed as a thought experiment about \"Can a machine think?\" ...\n2. Six AI disciplines: NLP, Knowledge representation, Automated reasoning, ML, Total Turing Test, CV, Robotics  ...\n3. Rational agent advantages: more general than the \"laws of thought\" approach; more amenable to scientific development.\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing argument from informality of bahvior: human behavior too complex using formal set of rules(informal guideline that cannot be codify)...\n1. qualification problem: cannot capture behavior in a set of logiccal rules...\n2. embodied cognition: dont consider brain separately; cognition take place in body embedded in env; study system as whole...\n3. argument from disability: a machine never do X(be kind resourceful...) ...\n4. Incompleteness theorem: formal axiomatic framework f enough to do arithmetic, can construct Godel sentence G(F), a sentence of F but cannot be prove in F; if F is consistent, then G(F) is true...\n5. IT  show machine cannot establish truth of Godel...\n6. examination: 1. should not be ashamed if they cannot establish truth; Godel's IT applys to mathematics not computer; only to formal system that do arithmetic...\n7. Turing test: conversation for 5 mins, bahavioral test; pretend human and chat\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n 1. Chinese room: argue no understanding...\n2. qualia: intrinsic nature of expression\n\n## AIMA 2.1 Agents and Environments\n 1. agents choice of action depend on its built-in knowledge and the entire percept sequence observed to date, not on anything hasn't...\n                  2. A function is abstract mathematical description; A program is concrete implementation with physical system\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n 1. Rationality depends on: performane measure defined the criterion of success; agent's prior knowledge of the environment; actions of agent; agent's percept sequence to date...\n2. Rational and Omniscient : rationality maximizes expected performace; perfection maximize actual performance ...\n3. autonomy : the extend an agent relies on prior knowledge of its designer rather than on its percept and learning process means lack of autonomy\n\n## AIMA 2.3 The Nature of Environments\n  1. Task environment: Performance, Environment, Actuators, Sensors...\n2. Fully observed: no need to maintain any internal state to keep track of the world...\n3. multi agent: B's behavior is described as maximizing a performance measure whose value depends on A's bahavior...\n4. stochastic/nondeterministic : stochastic if deals with probabilities; non if possibilities are listed without being quantified...\n5. episodic/ sequential: sequential(current decision affect all future decision); episodic(no need to think ahead) ...\n6. static/ dynamic: static(no need to keep looking the world); semidynamic(environment change by agent's performance score rather than the passage of time, chess played with clock)...\n7. discrete/continuous: state of environ; the way time is handled, and percepts and actions of agent....\n8. known/unknown: agent's state of knowledge about the \"laws of physics\" of the envir(known can be partially observed/unknown fully observed)\n\n## AIMA 2.4 The Structure of Agents\n 1. agent = architecture + program...\n2. agent problem skeleton : take current percept as input from the sensor and return action to actuator...\n3. simple reflex agent : select action on current percept, ignoring percept history;  only in fully observed env; infinite loop in partially observed(using randomized actions (may not be rational))...\n4. model-based reflex agent: (transition + sensor model)for partial observability by keeping track of internal state that depends on the percept history and reflect some part of current state...\n5. goal-based : using goal information; less efficient more flexible because knowledge supports its decision is explicit and can be modified...\n6. utility-based:  for high quality bahavior; rational decision when conflict goals; maximize the expected utility of the action...\n7. an agent that possesses an explicit utility function can make rational decisions with a general algo that does not depend on the specific utility being maximize...\nLearning Agent:\n1. any type of agent can be built as a learning agent(or not).\n2. Critic(how the agent is doing); Learning element(making improvements using feedback from critic); problem generator(suggenst actions); performance element(select external actions)\n\n\n## Module 1 Lecture Notes\n All agents can improve performance through learning. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment through sensors and acting through actuators\n* **Computer agent** - operate autonomously, perceive their environment, prsist over a prolonged time period, adapt to change, and create and pursue goals\n* **Percept** - content an agent's sensors are perceiving\n* **Percept sequence** - the complete history of everything perceived\n* **Standard model** - 213\n* **Value alignment problem** - the values or objectives put into the machine must be aligned with those of human.\n* **Agent function** - describe the agent's behavior by maping any given percept sequence into action\n* **Agent program** - implement agent function for an artificial agent\n* **Consequentialism** - evaluate an agent's behavior by it consequences\n* **Performance measure** - evaluates given sequence of enviroment state\n* **Rational agent** - select an action that is expected to maximize its performance measure, given evidence from  percept sequence & built-in knowledge\n* **Priori** - geography of the environment\n* **Omniscient** - knows the actual outcome of its actions (impossible in reality)\n* **Information gathering** - doing actions in order to modify future percepts (part of raionality)\n* **Task environment** - the problem to which rational agents are the solutions\n* **Fully observed** - agent's sensors give access to complete state of environment (sensor detect all that are relevant to choice of action)\n* **Partially observed** - noisy and inaccurate sensors or missing data (unobservable : no sensor)\n* **Deterministic enviro** - next state of environment determined by current state and action by agent\n* **Agent architecture** - agent program run on some computing device with physical sensors and actuators\n* **Transition model** - the knowlegde about \"how the world changes\" - effects of the actions and how the world evolves independent of agent\n* **Sensor model** - how the state of the world is reflected in agent's sensor\n* **Utility function** - an internalization of the performance measure\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 1. PS A use atomic representations...\n2. Search Problem: set of states; initial state; set of goal states; actions; transition model; action cost function  \n3. fully ob + deterministic + known = solution is fixed sequence of actions...\n4. partially ob + nondeter = solution recommend diff actions (branching stategy)...\n5. search algo treats states and actions atomic without internal structure \n\n## AIMA Chapter 3.2 Example Problems\n 1. Standardized Problem: illustrate or exercise various problem solving method (grid world, sokoban, sliding-tile)...\n2. real-world: use solution (route finding, touring tsp, VLSI layout, robot navig, assembly sequencing protein design) \n\n## AIMA Chapter 3.3 Search Algorithms\n 1. state space: set of states and actions; search tree: path between states, multiple path to a state but unque path to root...\n3. priority queue: first pop minimum cost; FIFO queue: first in first out; LIFO: stack...\n4. Best-First Search : choose minimum frontier with evaluation function f; graph search/tree search; ...\n5. solution if infinite loop: graph search: check redundant, check cycles ...\n6. evaluate algo: completeness; cost optimality; time complexity; space complexity;  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n 1. BFS: best-fs with f(n) is depth of the node; systematic search strategy, therefore complete; exponential space complexity\n2. Uniform-cost: f(n) = path cost; optimal...\n3. DFS : f(n) = negative depth; tree-like feasible; without reached; lower memory; variant: backtracking less mem(one successor atime); neither complete nor optimal...\n4. depth-limited(dfs): may cause cycle, use diameter(depth limit); optimal when same cost on actions; complete on finite acyclic\n5. Iterative-deepening: complete when full cycle check; optimal; linear space complexity.\n6. bidirectional: from initial and goal till frontier collide \n\n## Module 3 Lecture Notes\n DFS vs BFS:\n1. DFS if: restricted space; many possibles solutions with long paths, and wrong paths terminated quickly...\n2. BFS if: possible infinite paths; short path solution; quickly discard unlikely path. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search problem** - set of possible states that env can be, state space\n* **State vs node** - state is physical configuration; node is data structure part of search tree\n* **Path** - a sequence of actions\n* **Solution** - path from initial to goal; optimal has lowest path cost\n* **Model** - abstract mathematical description\n* **Abstraction** - remove details from a representation, level of abstraction\n* **Frontier** - unexpanded node, separates interior(expanded) and exterior(unexpanded) nodes\n* **Uninformed search** - use only information in problem definition, all non-goal nodes in frontier look equally good\n* **Informed search** -  some non-goal can be ranked above others, may have additional info such as pattern databases with solution costs\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n 1. Greedy Best-first search: expand first node with lowest h(n), f(n) = h(n); not optimal but complete in finite state space but not in infinite ...\n2. A* search : complete and optimal; no reached; f(n) = g(n):path cost from ini to current +h(n) from current to goal/ estimated cost of the best path that continues from n to goal...\n3. heuristic: admissible; consistency(h(n) <= c(n, a,n')+h(n')); every consistent h is admissible(not vice versa); ...\n4. inconsistent: lead to multiple path, update successor to solve inconsistency ...\n5. inadmissible: may or may not be optimal(only one path)...\n6. suboptimal algo: bounded-cost(factor W of optimal); unbounded(speedy search quick)...\n7. weighted A*: weight the h more heavily, suboptimal solution...\n8. beam search: limit size of frontier; incomplete and suboptimal; fast...\n9. bidirectional heuristic search( not optimal) \n\n## AIMA Chapter 3.6 Heuristic Functions\n 1. effective branching factor b* to characterize the quality of h(n) ...\n2. N(total number of nodes generated): N+1 = 1+ b* + (b*)^2 + ..(b*)^d. ...\n3. good b* : close to 1. h2(n) >= h1(n) ==> h2 dominates h1, A* expands less node using h2 than h1. ...\n4. how admissible h: relaxed problem/ storing precomputed solution costs for subproblem in pattern db/ defining landmarks/ learn from experience. ...\n5. state-space graph of relaxed problem is supergraph of original with added edges. ...\n6. the cost of optimal solution in relaxed is admissible in original, also consistent. \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - domain-specific information about the location of the goals inorder to find a solution more efficiently\n* **Admissible heuristic** -  never overestimates the cost to goal, optimistic\n* **Relaxed problem** - fewer restriction on the action\n* **Bidirectional a*** - sometimes more efficient than A*\n* **Ida*** - space complexity issue\n* **Rbfs and sma*** - robus, optimal with limited memory\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n 1. Minimax: (complete depth-first exploration)recursive algo that proceeds all the way down to the leaves of the tree and backs up the minimax val through tree as recursion unwind...\n2. node value: vector/ single val for two player, zero-sum...\n3. backup val of node n is utility vector of successor state with the highest val for the player choosing at n...\n4. collaboration might occur when not zero-sum ...\n5. alpha-beta pruning: alpha-at least for max, beta: at most for min ...\n6. ab pruning's effectiveness depends on the order in which the states are examined...\n7. transposition: diff permutations of moves leads to same position, transposition table to caches values\n8. Type A: all possible moves to a certain depth; Type B: ignore bad moves deep but narrow portion\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n 1.  utility(loss) <= Eval <= utility(win) ...\n2. one Eval fun: weighted linear function w1f1(s)+w2f2(s)+...wnfn(s) f-feature, w-weight...\n3.  fixed depth limit lead to error due to approximation of eval function, only apply to quiescnet position...\n4. forward pruning:beam search(consider only one beam of n best moves rather all) probcut(using stats from prior experience to avoid pruning of best move)...\n - late move reduction(move ordering is good, later move not good)...\n\n## AIMA Chapter 5.5 Stochastic Games\n  1. expectiminimax value: for stochastic game\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision Theory: maximization of expected utility...\n 1. decision theory: choosing among actions based on desirability of their immediate outcomes; env assumed to be episodic, cannot solve all but basic framework...\n 2. expected utility: average utility of outcomes weighted by the probability; guide actions...\n 3. maximum expected utility: perception for intelligent behavior\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Basis of utility theory...\n1. A > B prefer A; A ~ B indifferent; A >~ B prefer or indifferent...\n2. reasonable preference: orderability; transitivity; continuity: A>B>C , [p, A; 1-p, C]~B; substitutability: A~B => [p,A; 1-p, C]~[p,B; 1-p, C];monotonicity; frcomposability...\n3. existence of utility fun: A>B <-> U(A) > U(B); expected utility of lottery: utility of lottery = sum of utility*prob for each...\n4. value function/ordinal utility fun: preference ranking in deterministic env\n\n## AIMA Chapter 16.3 Utility Functions\n1. preference elicitation: using observed preference to pin down lying utility fun...\n2. best possible prize : u up = 1(normalized); worst possible catastrophe u down =0...\n3. Standard lottery [p, u down; (1-p) u up]...\n4. micromort: currency in medical and safety...\n5. QALY: quality-adjusted life year shorter life to avoid disability...\n6. utility of money: money is not utility fun, but monotonic preference for more money...\n7. normative theory: describe how rational agent acts(decision theory); descriptive theory: how actual agents do (people)...\n8. human irrational: reduce computational burden; distrust legitmacy of stated probability; emotional and financial state ...\n9. framing effect: exact wording of a decision problem impact choice...\n10. anchoring effect: restaurant 200$ wine and 55$ wines as bargain \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Adversarial search** - competitive env, two or more agents conflict goals\n* **Pruning** - ignoring portion of the search tree that make no diff to optimal move\n* **Perfect info** - fully observed\n* **Zero-sum** - no win-win, good for one bad for another\n* **State space graph** - vertices-state, edge-moves, state might be reached by multi paths\n* **Game tree** - search tree that follows every sequence of moves all the way to terminal state, infinite if unbounded or repeating position\n* **Conditional plan** - strategy giving response to each min's possible move\n* **Ply** - one move by one player\n* **Minimax value** - utility of being that state, determinie the optimal strategy of game\n* **Cutoff test** - return true if terminal, else free to decide when to cut off based on depth and property(using depth)\n* **Eval** - expected utility of state s, as heuristic function distance to goal\n* **Quiescent position** - no pending move\n* **Horizon effct** - program facing opponent's move that causes unavoidable damage, temporarily avoid using delaying tactics, using singular extensions\n* **Singular extension** - mitigate horizon effect, moves that clearly better\n* **Forward pruning** - moves appear to be bad but might be good, save time at risk of error\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n 1.  X variable sets, D domains for each X, C constraints ...\n2. why CSP: natural representation for wide variety og problem; solves fast efficient; quickly prune large swathes of search space that an atomic state-space cannot...\n3. variable types: discrete-finite domains: simplest; discrete-infinite: set of integers, need implicit linear contraints like t1+d <= t2(nonlinear con is undecidable); continuos domains: linear programming...\n4.  constraint types: unary: single val; binary: a <> b; global constraint: arbitrary number of variables, Alldiff: sudoku, cryptarithmetic...\n5. n-aray to binary: auxiliary var; dual graph: new graph where one var for each constraint in original graph and one binary constratint for each pair of constraint in original graph share variables...\n5. global constraint > binary constraint: easier and less error-prone; can use special-purpose inference more efficient...\n6. preference constraint: constrained optimization problem\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n 1. CSP successor: choose new variable; constraint propagation: use constraint to reduce value\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n 1. Backtracking search CSP : commutativity if the order of application of any set action does not matter...\n2. backtracking; forward checking\n\n## AIMA Chapter 6.4 Local Search for CSPs\n 1. Local Search: min-conflicts ...\n2. Plateau search: allowing sideways moves to another state with the same score- help find its way off this plateau...\n3. constraint weighting: concentrate the search on important constraints : adds topology so possible to improve; adds learning...\n4. advantages of local search: online setting when problem changes; effective \n\n## AIMA Chapter 6.5 The Structure of Problems\n 1. independent subproblem: can be ascertained by finding connected components of the constraint graph...\n2. cutset conditioning: reduce a general CSP to tree-structured one, efficient if a small cutset found...\n- choose subset S of CSP's var such that constraint graph becomes a tree after removal of S(S is cycle cutset)...\n- for each assignment to var in S : remove from domains of remaining var any values that are inconsis with S and if remianing CSP has solution return...\n3. (reduce constraint graph) tree decomposition: transform CSP into tree subproblems, efficient when tree width is small, memory exponential ...\n- every var in original apears at least once; ...\n- two var connected, then appear together in at least one of the tree nodes; ...\n- one var in two nodes then in every node along the path connecting them...\n4. tree width : one less than size of the largetst node, defined to be minimum width among all decomposition\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp ** - factored representation for each state, variables with value, satisfied constrain\n* **Node consis** - values in the domain satisfy the var's unary constraint, 1-consistency node\n* **Arc consis** - binary constraint, AC-3,2-consistency node\n* **Path consis** - tighten the binary constraints using implicit constraints inferred by looking at triples of var, 3-consistency node\n* **K consis** - if any set of k-1vars and for consis assignment to those, consist val can be assigned to any kth var.\n* **Strongly k consis** - k consis, k-1 consis, .. 1-consis, NP-complete\n* **Resource constraint** - higher-order constrint, atmost constraint\n* **Bounds consis** - every X upper and lower bound, exists Y satisfied contraint between X and Y for every Y\n* **Minimum remaining values(mrv)** - choosing vars with fewest moves\n* **Least constraint value** - rules out the fewest choice for neighboring var\n* **Forward checking** - form of inference, establishes arc consistency when assign X, for unassigned Y, delete from Y's domain inconsistent with Xval\n* **Maintaining arc consi(mac)** - delete inconsis for assigning one leaving others only val that are not possible\n* **Chronological backtracking** - back up to preceding var and try new one, most recent node is revisited\n* **Backjumping** - back tracks to the most recent assignment in the conflict set(conflict-directed jumping), tell us how far to back up\n* **Min-conflicts** - select val results in the minimum conflicts with others\n* **Independent subproblems** - any solution for one combined with another yields a solution for the whole map\n* **Directional arc consis** - under an ordering of X1 X2 .. if and only if every Xi is arc-consis wit Xj for j>i\n* **Topological sort** - each vars appears after its parent in the tree\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Proposition logic: factored representation; less expressive than first-order logic(canonical structured representation)...\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n 1. logic: syntax; semantics(meaning); ...\n2. entailment, follows logically from another sentence |= ...\n3. KB|-i a a is derived from KB by i...\n4. inference : sound(truth preserving) ; completeness(derived any sentence that is entailed)\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n 1. propositional logic...\n2. a|= b iff (a^-b) is not satisfiable\n\n## AIMA 7.5 Propositional Theorem Proving\n 1. Modus Ponens: a=>b, a/ b...\n2, and-elimination: a^b/a...\n3. CNF  \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Sentence** - expressed in knowledge representation language and represents assertions about the world\n* **Axiom** - sentence given without being derived from others\n* **Model checking** - inference algo, anumerates all possible models to check that a is true in all models in which KB is true\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}