{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c769d182-8b12-46b3-9dbb-5ea0d59133ae"
      },
      "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": 39,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "59c54a58-5a6d-465a-e19b-33ec02467c52"
      },
      "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": 40,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 23,
      "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 = \"\"\"The Turing test requires agents to have NLP, knowledge, automated reasoning and ML capabilities. The total Turing test requires computer vision and robotics.\n",
        "An agent is something that acts. A rational agent is one that achieves best expected outcome. Does not need to involve inference(recoiling). limited rationality due to complex env and computational constraints.\n",
        "value alignment problem:achieving agreement between our true preferences and the objectives.\"\"\" \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 = \"\"\" weakAI: simulated thinking. strongAI: true consciousness. The qualification problem is to capture every contingency of appropriate behavior in a\n",
        "set of necessary and sufficient logical rules; The embodied cognition approach considers brain inseparable from a body, robotics, vision and other sensors thus become central.\"\"\"\n",
        "chapter27_2 = \"\"\"qualia - intrinsic nature of experiences\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and\n",
        "acting upon that environment through actuators. Percept refers to the content an agent’s sensors are perceiving. An agent’s\n",
        "percept sequence is the complete history of everything the agent has ever perceived. An agent’s behavior is described by the agent function that maps any given percept\n",
        "sequence to an action. the agent function for an artificial agent will be implemented by an agent program. The\n",
        "agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\"\"\"\n",
        "chapter2_2 = \"\"\" consequentialism: we evaluate an agent’s behavior by its consequences. When an agent is plunked down in an environment, it generates a\n",
        "sequence of actions according to the percepts it receives. This sequence of actions causes\n",
        "the environment to go through a sequence of states. If the sequence is desirable, then the\n",
        "agent has performed well. This notion of desirability is captured by a performance measure\n",
        "that evaluates any given sequence of environment states.What is rational at any given time depends on four things:\n",
        "The performance measure that defines the criterion of success.\n",
        "The agent’s prior knowledge of the environment.\n",
        "The actions that the agent can perform.\n",
        "The agent’s percept sequence to date.\n",
        "definition of a rational agent:\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has. An omniscient\n",
        "agent knows the actual outcome of its actions and can act accordingly; but omniscience is\n",
        "impossible in reality.Rationality maximizes\n",
        "expected performance, while perfection maximizes actual performance. Our definition of rationality does not require omniscience, then, because the rational choice\n",
        "depends only on the percept sequence to date. Need to ensure that \n",
        "the agent does not inadvertently engage in decidedly underintelligent activities (irrational) would not be rational to cross the road given this uninformative percept sequence. Doing actions in order to modify future percepts—\n",
        "sometimes called information gathering—is an important part of rationality -exploration\"\"\"\n",
        "chapter2_3 = \"\"\" task environments, which are essentially the “problems” to which rational agents are the “solutions.” PEAS (Performance, Environment, Actuators, Sensors) description. If an agent’s sensors give it access\n",
        "to the complete state of the environment at each point in time, then we say that the task environment is fully observable (all aspects that are relevant to the choice of action depending on the performance measure.agent need not maintain any internal state to keep track of the world. An\n",
        "environment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data. If the agent has no sensors at all\n",
        "then the environment is unobservable, the agent’s goals, however, may still be achievable. competitive multiagent environment: the opponent entity maximizes its performance measure,\n",
        "which minimizes agent ’s performance measure.If the next state of the environment is completely\n",
        "determined by the current state and the action executed by the agent(s), then we say the\n",
        "environment is deterministic; otherwise, it is nondeterministic. a model of the environment\n",
        "is stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain\n",
        "tomorrow”) and “nondeterministic” if the possibilities are listed without being quantified. In an episodic task environment, the agent’s experience is\n",
        "divided into atomic episodes. In each episode the agent receives a percept and then\n",
        "performs a single action. Crucially, the next episode does not depend on the actions taken in\n",
        "previous episodes. Many classification tasks are episodic. For example, an agent that has to\n",
        "spot defective parts on an assembly line bases each decision on the current part, regardless\n",
        "of previous decisions; moreover, the current decision doesn’t affect whether the next part is\n",
        "defective. In sequential environments, on the other hand, the current decision could affect\n",
        "all future decisions. If the environment can change while an agent is deliberating, then\n",
        "we say the environment is dynamic for that agent; otherwise, it is static.if the environment itself does not change with the\n",
        "passage of time but the agent’s performance score does, then we say the environment is\n",
        "semidynamic.In a known environment, the outcomes (or outcome probabilities if the\n",
        "environment is nondeterministic) for all actions are given\"\"\"\n",
        "chapter2_4 = \"\"\"a rational utility-based agent\n",
        "chooses the action that maximizes the expected utility of the action outcomes.a model-free agent can learn what action is best in a particular situation\n",
        "without ever learning exactly how that action changes the environment.In an atomic representation each state of the world is indivisible—it has no internal\n",
        "structure.A factored representation splits up each state into a fixed set of variables or attributes,\n",
        "each of which can have a value.Many important areas of AI are based on factored representations,\n",
        "including constraint satisfaction algorithms (Chapter 6 ), propositional logic (Chapter 7 ),\n",
        "planning (Chapter 11 ), Bayesian networks (Chapters 12 –16 ), and various machine\n",
        "learning algorithms.structured representation, in which objects such as cows and\n",
        "trucks and their various and varying relationships can be described explicitly. the axis along which atomic, factored, and structured\n",
        "representations lie is the axis of increasing expressiveness. Simple reflex agents respond directly to percepts, whereas model-based reflex agents\n",
        "maintain internal state to track aspects of the world that are not evident in the current\n",
        "percept. Goal-based agents act to achieve their goals, and utility-based agents try to\n",
        "maximize their own expected “happiness.”\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" An agent is anything that perceives\n",
        "its environment through sensors\n",
        "and can act on its environment\n",
        "through actuators\n",
        "A percept is the agent’s perceptual\n",
        "inputs at any given instance. An agent is specified by an agent function f:P® a that maps a\n",
        "sequence of percept vectors P to an action a from a set A:The agent program runs on the physical architecture to produce f\n",
        "• agent = architecture + program\n",
        "A rational agent is an agent that perceives its environment and and behaves rationally\n",
        "Rational behavior: doing the right thing -  performance measure:\n",
        "• An objective criterion for success of an agent's behavior\n",
        "• given the evidence provided by the percept sequence.\n",
        "Rational Agent:\n",
        "• For each possible percept sequence P\n",
        "• a rational agent selects an action a\n",
        "• to maximize its expected value of performance measure (computational limitations make complete rationality unachievable)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "17b99b9a-dc90-4950-cc16-de198b8ba621"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nThe Turing test requires agents to have NLP, knowledge, automated reasoning and ML capabilities. The total Turing test requires computer vision and robotics.\nAn agent is something that acts. A rational agent is one that achieves best expected outcome. Does not need to involve inference(recoiling). limited rationality due to complex env and computational constraints.\nvalue alignment problem:achieving agreement between our true preferences and the objectives.\n\n## AIMA Chapter 27.1 The Limits of AI\n weakAI: simulated thinking. strongAI: true consciousness. The qualification problem is to capture every contingency of appropriate behavior in a\nset of necessary and sufficient logical rules; The embodied cognition approach considers brain inseparable from a body, robotics, vision and other sensors thus become central.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nqualia - intrinsic nature of experiences\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators. Percept refers to the content an agent’s sensors are perceiving. An agent’s\npercept sequence is the complete history of everything the agent has ever perceived. An agent’s behavior is described by the agent function that maps any given percept\nsequence to an action. the agent function for an artificial agent will be implemented by an agent program. The\nagent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n consequentialism: we evaluate an agent’s behavior by its consequences. When an agent is plunked down in an environment, it generates a\nsequence of actions according to the percepts it receives. This sequence of actions causes\nthe environment to go through a sequence of states. If the sequence is desirable, then the\nagent has performed well. This notion of desirability is captured by a performance measure\nthat evaluates any given sequence of environment states.What is rational at any given time depends on four things:\nThe performance measure that defines the criterion of success.\nThe agent’s prior knowledge of the environment.\nThe actions that the agent can perform.\nThe agent’s percept sequence to date.\ndefinition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has. An omniscient\nagent knows the actual outcome of its actions and can act accordingly; but omniscience is\nimpossible in reality.Rationality maximizes\nexpected performance, while perfection maximizes actual performance. Our definition of rationality does not require omniscience, then, because the rational choice\ndepends only on the percept sequence to date. Need to ensure that \nthe agent does not inadvertently engage in decidedly underintelligent activities (irrational) would not be rational to cross the road given this uninformative percept sequence. Doing actions in order to modify future percepts—\nsometimes called information gathering—is an important part of rationality -exploration\n\n## AIMA 2.3 The Nature of Environments\n task environments, which are essentially the “problems” to which rational agents are the “solutions.” PEAS (Performance, Environment, Actuators, Sensors) description. If an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task environment is fully observable (all aspects that are relevant to the choice of action depending on the performance measure.agent need not maintain any internal state to keep track of the world. An\nenvironment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data. If the agent has no sensors at all\nthen the environment is unobservable, the agent’s goals, however, may still be achievable. competitive multiagent environment: the opponent entity maximizes its performance measure,\nwhich minimizes agent ’s performance measure.If the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic. a model of the environment\nis stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain\ntomorrow”) and “nondeterministic” if the possibilities are listed without being quantified. In an episodic task environment, the agent’s experience is\ndivided into atomic episodes. In each episode the agent receives a percept and then\nperforms a single action. Crucially, the next episode does not depend on the actions taken in\nprevious episodes. Many classification tasks are episodic. For example, an agent that has to\nspot defective parts on an assembly line bases each decision on the current part, regardless\nof previous decisions; moreover, the current decision doesn’t affect whether the next part is\ndefective. In sequential environments, on the other hand, the current decision could affect\nall future decisions. If the environment can change while an agent is deliberating, then\nwe say the environment is dynamic for that agent; otherwise, it is static.if the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.In a known environment, the outcomes (or outcome probabilities if the\nenvironment is nondeterministic) for all actions are given\n\n## AIMA 2.4 The Structure of Agents\na rational utility-based agent\nchooses the action that maximizes the expected utility of the action outcomes.a model-free agent can learn what action is best in a particular situation\nwithout ever learning exactly how that action changes the environment.In an atomic representation each state of the world is indivisible—it has no internal\nstructure.A factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value.Many important areas of AI are based on factored representations,\nincluding constraint satisfaction algorithms (Chapter 6 ), propositional logic (Chapter 7 ),\nplanning (Chapter 11 ), Bayesian networks (Chapters 12 –16 ), and various machine\nlearning algorithms.structured representation, in which objects such as cows and\ntrucks and their various and varying relationships can be described explicitly. the axis along which atomic, factored, and structured\nrepresentations lie is the axis of increasing expressiveness. Simple reflex agents respond directly to percepts, whereas model-based reflex agents\nmaintain internal state to track aspects of the world that are not evident in the current\npercept. Goal-based agents act to achieve their goals, and utility-based agents try to\nmaximize their own expected “happiness.”\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"strings are immutable, == checks whether variables point to objects of the same value\n",
        "o is checks whether variables point to the\n",
        "same object. lists are mutable, use y = x[:] to get a (shallow) copy of any\n",
        "sequence, ie. a new object of the same value (does not work on list of list). Non-default argument should always precede default arguments; otherwise, it\n",
        "reports SyntaxError. Functions can be called with arguments out of order\n",
        "o These arguments are specified in the call\n",
        "o Keyword arguments can be used after all other arguments\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        },
        "outputId": "6c8f3895-d66a-4f4a-cd0b-677b422e8a6d"
      },
      "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": 27,
      "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 = \"\"\" A search problem is defined by a set of possible states that the environment can be in, initial state, goal states and actions available to the agent, transition model RESULT returns the state\n",
        "that results from doing action in state, action cost function.\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" An uninformed search algorithm is given no clue about how close a state is to the goal(s).When all actions have the same cost, an appropriate strategy is breadth-first search,both time and space complexity are O(b^d).When actions have different costs, an obvious choice is to use best-first search where the\n",
        "evaluation function is the cost of the path from the root to the current node - Dijkstra’s algorithm(uniform-cost search).Uniform-cost search is complete and is cost-optimal, because the first solution it finds will\n",
        "have a cost that is at least as low as the cost of any other node in the frontier. Depth-first search is not cost-optimal, but it is complete for finite state spaces. For a finite tree, depth-first tree-like\n",
        "search takes time proportional to the number of states, and has memory complexity of only O(bm) where m is the branching factor and is the maximum depth of the tree. A variant of depth-first search called backtracking search uses even less memory, O(m). To keep depth-first search from wandering down an infinite path, we can use depth-limited\n",
        "search, with time complexity of O(b^l), space complexity of O(bl). Poor choice of l makes it incomplete. Iterative deepening search solves the problem of picking a good value for by trying all\n",
        "values. Similar space complexity as DFS, O(bd). optimal for problems where all actions have the same cost,\n",
        "and is complete on finite acyclic state spaces. An alternative approach called bidirectional search\n",
        "simultaneously searches forward from the initial state and backwards from the goal state(s), with O(b^(d/2))+O(b^(d/2)) smaller\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"A solution is a sequence of actions from the initial state to a goal\n",
        "state.\n",
        "Optimal Solution: A solution is optimal if no solution has a lower\n",
        "path cost. BFS is complete and optimal (when cost=1 per step), DFS is not complete (trapped in inf depth) and not optimal. BFS O(b^d) for both. DFS O(b^m) bad if m >>d but space O(bm) linear. Depth-limited search:Depth-First search but with depth limit l. O(b^l), O(bl). • If l < d then incomplete ☹\n",
        "• If l > d then not optimal. Iterative deepening search. O(b^d), O(bd), complete and optimal if cost is 1. \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 641
        },
        "outputId": "663fdae1-3193-4cb8-d08f-144ba1eaa2ca"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A search problem is defined by a set of possible states that the environment can be in, initial state, goal states and actions available to the agent, transition model RESULT returns the state\nthat results from doing action in state, action cost function.\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n An uninformed search algorithm is given no clue about how close a state is to the goal(s).When all actions have the same cost, an appropriate strategy is breadth-first search,both time and space complexity are O(b^d).When actions have different costs, an obvious choice is to use best-first search where the\nevaluation function is the cost of the path from the root to the current node - Dijkstra’s algorithm(uniform-cost search).Uniform-cost search is complete and is cost-optimal, because the first solution it finds will\nhave a cost that is at least as low as the cost of any other node in the frontier. Depth-first search is not cost-optimal, but it is complete for finite state spaces. For a finite tree, depth-first tree-like\nsearch takes time proportional to the number of states, and has memory complexity of only O(bm) where m is the branching factor and is the maximum depth of the tree. A variant of depth-first search called backtracking search uses even less memory, O(m). To keep depth-first search from wandering down an infinite path, we can use depth-limited\nsearch, with time complexity of O(b^l), space complexity of O(bl). Poor choice of l makes it incomplete. Iterative deepening search solves the problem of picking a good value for by trying all\nvalues. Similar space complexity as DFS, O(bd). optimal for problems where all actions have the same cost,\nand is complete on finite acyclic state spaces. An alternative approach called bidirectional search\nsimultaneously searches forward from the initial state and backwards from the goal state(s), with O(b^(d/2))+O(b^(d/2)) smaller\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed (Heuristic) Search Strategies use domain-specific hints. Greedy best-first search is a form of best-first search that expands first the node with the\n",
        "lowest h(n) value—the node that appears to be closest to the goal. Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. It is also not optimal. The\n",
        "worst-case time and space complexity is O(|V|). With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching O(bm). A star is complete and is cost optimal with an admissible heuristic (never overestimates the cost to reach a goal, optimistic). A slightly stronger property is called consistency (triangle inequality). We say that A* with a consistent heuristic is optimally efficient in the sense that any\n",
        "algorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A*, it prunes away search tree nodes that are not necessary for finding\n",
        "an optimal solution.\"\"\"\n",
        "chapter3_6 = \"\"\" the quality of a heuristic - effective branching factor. well-designed heuristic would have a value of b close to 1.\n",
        "have a value. Domination translates directly into efficiency. A* using a consistently larger heuristic h1 will\n",
        "never expand more nodes than h2\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 458
        },
        "cellView": "form",
        "outputId": "b1c41e48-280e-435e-de0f-22478bfa693f"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) Search Strategies use domain-specific hints. Greedy best-first search is a form of best-first search that expands first the node with the\nlowest h(n) value—the node that appears to be closest to the goal. Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. It is also not optimal. The\nworst-case time and space complexity is O(|V|). With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching O(bm). A star is complete and is cost optimal with an admissible heuristic (never overestimates the cost to reach a goal, optimistic). A slightly stronger property is called consistency (triangle inequality). We say that A* with a consistent heuristic is optimally efficient in the sense that any\nalgorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A*, it prunes away search tree nodes that are not necessary for finding\nan optimal solution.\n\n## AIMA Chapter 3.6 Heuristic Functions\n the quality of a heuristic - effective branching factor. well-designed heuristic would have a value of b close to 1.\nhave a value. Domination translates directly into efficiency. A* using a consistently larger heuristic h1 will\nnever expand more nodes than h2\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" deterministic, two-player, turn-taking, perfect information, zero-sum games. \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 669
        },
        "outputId": "92381a9a-687e-486b-8233-0de2bf4c9071"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" search algorithm, each state is atomic, or\n",
        "indivisible—a black box with no internal structure, need domainspecific\n",
        "code to describe the transitions between states. Constraint Satisfaction Problems open the black box with a factored representation for each\n",
        "state: a set of variables, each of which has a value. A constraint satisfaction problem consists of three components, X (X1,..., Xn, set of vars), D(set of domains, one for each var)C(a set of constraints that specify allowable combinations of values). CSPs deal with assignments of values to variables. An assignment\n",
        "that does not violate any constraints is called a consistent or legal assignment. A complete\n",
        "assignment is one in which every variable is assigned a value, and a solution to a CSP is a\n",
        "consistent, complete assignment. A partial assignment is one that leaves some variables\n",
        "unassigned, and a partial solution is a partial assignment that is consistent.Solving a CSP is\n",
        "an NP-complete problem in general. A binary CSP is one with only unary and binary constraints, it can be represented as a\n",
        "constraint graph. CSPs with preferences can\n",
        "be solved with optimization search methods, either path-based or local. We call such a\n",
        "problem a constrained optimization problem. \"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propagation may be intertwined with search, or it may be done as a\n",
        "preprocessing step, before search starts. Sometimes this preprocessing can solve the whole\n",
        "problem, so no search is required at all. A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\n",
        "values in the variable’s domain satisfy the variable’s unary constraints. a graph is node-consistent if every variable in the graph is node-consistent. A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\n",
        "binary constraints.AC-3 enforcing arc consistency. AC-3 algorithm maintains a queue which initially contains all the arcs in the CSP. (Each binary constraint\n",
        "becomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (A,B) from the queue and makes A arc-consistent with respect to B. If this leaves domain of A unchanged, the\n",
        "algorithm just moves on to the next arc. If the domain of A changes, all arcs (X, A) need to be added back to the queue. because the change in Da might enable further reductions in Dx, even if we have previously\n",
        "considered Dx. If any domain is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure. Otherwise, we keep checking,\n",
        "trying to remove values from the domains of variables until no more arcs are in the queue.\n",
        "At that point, we are left with a CSP that is equivalent to the original CSP—they both have\n",
        "the same solutions—but the arc-consistent CSP will be faster to search because its variables\n",
        "have smaller domains. The complexity of AC-3: Assume a CSP with variables, each\n",
        "with domain size at most , and with binary constraints (arcs). Each arc can be\n",
        "inserted in the queue only d times because Xi has at most values to delete. Checking\n",
        "consistency of an arc can be done in time O(d^2), so we get O(cd^3) total worst-case time. A CSP is strongly k-consistent if it is k-1-consistent, k-2-consistent,..., all the way down to 1-consistent. any\n",
        "algorithm for establishing -consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in .\"\"\"\n",
        "chapter6_3 = \"\"\" Sometimes we can finish the constraint propagation process and still have variables with\n",
        "multiple possible values. In that case we have to search for a solution.It repeatedly chooses an\n",
        "unassigned variable, and then tries all values in the domain of that variable in turn, trying to each one into a solution via a recursive call. If the call succeeds, the solution is\n",
        "returned, and if it fails, the assignment is restored to the previous state, and we try the next value. If no value works then we return failure. choosing the variable with the fewest “legal” values—is called the\n",
        "minimum-remaining-values (MRV) heuristic. It also has been called the “most constrained\n",
        "variable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to\n",
        "cause a failure soon, thereby pruning the search tree. The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,\n",
        "because initially every region has three legal colors. In this case, the degree heuristic comes\n",
        "in handy. It attempts to reduce the branching factor on future choices by selecting the\n",
        "variable that is involved in the largest number of constraints on other unassigned variables. Once a variable has been selected, the algorithm must decide on the order in which to\n",
        "examine its values. The least-constraining-value heuristic is effective for this. It prefers the\n",
        "value that rules out the fewest choices for the neighboring variables in the constraint graph. every time we make a\n",
        "choice of a value for a variable, we have a brand-new opportunity to infer new domain\n",
        "reductions on the neighboring variables. One of the simplest forms of inference is called forward checking. Whenever a variable is\n",
        "assigned, the forward-checking process establishes arc consistency for it: for each\n",
        "unassigned variable that is connected to by a constraint, delete from ’s domain any\n",
        "value that is inconsistent with the value chosen for. Although forward checking detects many inconsistencies, it does not detect all of them. The\n",
        "problem is that it doesn’t look ahead far enough. The algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like\n",
        "this. forward checking does the same thing\n",
        "as MAC on the initial arcs in MAC’s queue but unlike MAC, forward checking does not\n",
        "recursively propagate constraints when changes are made to the domains of variables.\"\"\"\n",
        "chapter6_4 = \"\"\" Completely independent subproblems are delicious (independent\n",
        "subproblems decomposition O(d^cn/c) linear in n instead of exponential), then, but rare. any tree-structured CSP can\n",
        "be solved in time linear in the number of variables. A CSP is defined to be directional arc-consistent\n",
        "under an ordering of variables  X1,..., Xn if and only if every Xi is arc-consistent with\n",
        "each Xj for j>i.To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\n",
        "an ordering of the variables such that each variable appears after its parent in the tree. Such\n",
        "an ordering is called a topological sort. The first way to reduce a constraint graph to a tree involves assigning values to some\n",
        "variables so that the remaining variables form a tree. Choose a subset S of the CSP’s variables such that the constraint graph becomes a\n",
        "tree after removal of S. S is called a cycle cutset. If the cycle cutset has size c, then the total run time is O(d^c(n-c)d^2) \"\"\"\n",
        "chapter6_5 = \"\"\" The second way to reduce a constraint graph to a tree is based on constructing a tree\n",
        "decomposition of the constraint graph, a transformation of the original graph into a tree\n",
        "where each node in the tree consists of a set of variables.Every variable in the original problem appears in at least one of the tree nodes.\n",
        "If two variables are connected by a constraint in the original problem, they must appear\n",
        "together (along with the constraint) in at least one of the tree nodes.\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the\n",
        "path connecting those nodes. Once we have a tree-structured graph, we can apply TREE-CSP-SOLVER to get a solution in\n",
        "O(nd^2) time, where is the number of tree nodes and is the size of the largest domain. The tree width of a tree decomposition of a graph is\n",
        "one less than the size of the largest node; the tree width of the graph itself is defined to be\n",
        "the minimum width among all its tree decompositions. If a graph has tree width then the\n",
        "problem can be solved in O(nd^(w+1))time given the corresponding tree decomposition. Hence, CSPs with constraint graphs of bounded tiree width are solvable in polynomal time.the cutset decomposition with\n",
        "time , or the tree decomposition with time ? Whenever you have a\n",
        "cycle-cutset of size c, there is also a tree width of size w<c+1, and it may be far smaller in\n",
        "some cases. So time consideration favors tree decomposition, but the advantage of the\n",
        "cycle-cutset approach is that it can be executed in linear memory, while tree decomposition\n",
        "requires memory exponential in the tree width of the constraint\n",
        "graph.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "480a0783-d1c9-4d6c-a193-b9c075420d5b"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n search algorithm, each state is atomic, or\nindivisible—a black box with no internal structure, need domainspecific\ncode to describe the transitions between states. Constraint Satisfaction Problems open the black box with a factored representation for each\nstate: a set of variables, each of which has a value. A constraint satisfaction problem consists of three components, X (X1,..., Xn, set of vars), D(set of domains, one for each var)C(a set of constraints that specify allowable combinations of values). CSPs deal with assignments of values to variables. An assignment\nthat does not violate any constraints is called a consistent or legal assignment. A complete\nassignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. A partial assignment is one that leaves some variables\nunassigned, and a partial solution is a partial assignment that is consistent.Solving a CSP is\nan NP-complete problem in general. A binary CSP is one with only unary and binary constraints, it can be represented as a\nconstraint graph. CSPs with preferences can\nbe solved with optimization search methods, either path-based or local. We call such a\nproblem a constrained optimization problem. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation may be intertwined with search, or it may be done as a\npreprocessing step, before search starts. Sometimes this preprocessing can solve the whole\nproblem, so no search is required at all. A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints. a graph is node-consistent if every variable in the graph is node-consistent. A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints.AC-3 enforcing arc consistency. AC-3 algorithm maintains a queue which initially contains all the arcs in the CSP. (Each binary constraint\nbecomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (A,B) from the queue and makes A arc-consistent with respect to B. If this leaves domain of A unchanged, the\nalgorithm just moves on to the next arc. If the domain of A changes, all arcs (X, A) need to be added back to the queue. because the change in Da might enable further reductions in Dx, even if we have previously\nconsidered Dx. If any domain is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure. Otherwise, we keep checking,\ntrying to remove values from the domains of variables until no more arcs are in the queue.\nAt that point, we are left with a CSP that is equivalent to the original CSP—they both have\nthe same solutions—but the arc-consistent CSP will be faster to search because its variables\nhave smaller domains. The complexity of AC-3: Assume a CSP with variables, each\nwith domain size at most , and with binary constraints (arcs). Each arc can be\ninserted in the queue only d times because Xi has at most values to delete. Checking\nconsistency of an arc can be done in time O(d^2), so we get O(cd^3) total worst-case time. A CSP is strongly k-consistent if it is k-1-consistent, k-2-consistent,..., all the way down to 1-consistent. any\nalgorithm for establishing -consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in .\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Sometimes we can finish the constraint propagation process and still have variables with\nmultiple possible values. In that case we have to search for a solution.It repeatedly chooses an\nunassigned variable, and then tries all values in the domain of that variable in turn, trying to each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, and if it fails, the assignment is restored to the previous state, and we try the next value. If no value works then we return failure. choosing the variable with the fewest “legal” values—is called the\nminimum-remaining-values (MRV) heuristic. It also has been called the “most constrained\nvariable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to\ncause a failure soon, thereby pruning the search tree. The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,\nbecause initially every region has three legal colors. In this case, the degree heuristic comes\nin handy. It attempts to reduce the branching factor on future choices by selecting the\nvariable that is involved in the largest number of constraints on other unassigned variables. Once a variable has been selected, the algorithm must decide on the order in which to\nexamine its values. The least-constraining-value heuristic is effective for this. It prefers the\nvalue that rules out the fewest choices for the neighboring variables in the constraint graph. every time we make a\nchoice of a value for a variable, we have a brand-new opportunity to infer new domain\nreductions on the neighboring variables. One of the simplest forms of inference is called forward checking. Whenever a variable is\nassigned, the forward-checking process establishes arc consistency for it: for each\nunassigned variable that is connected to by a constraint, delete from ’s domain any\nvalue that is inconsistent with the value chosen for. Although forward checking detects many inconsistencies, it does not detect all of them. The\nproblem is that it doesn’t look ahead far enough. The algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like\nthis. forward checking does the same thing\nas MAC on the initial arcs in MAC’s queue but unlike MAC, forward checking does not\nrecursively propagate constraints when changes are made to the domains of variables.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Completely independent subproblems are delicious (independent\nsubproblems decomposition O(d^cn/c) linear in n instead of exponential), then, but rare. any tree-structured CSP can\nbe solved in time linear in the number of variables. A CSP is defined to be directional arc-consistent\nunder an ordering of variables  X1,..., Xn if and only if every Xi is arc-consistent with\neach Xj for j>i.To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\nan ordering of the variables such that each variable appears after its parent in the tree. Such\nan ordering is called a topological sort. The first way to reduce a constraint graph to a tree involves assigning values to some\nvariables so that the remaining variables form a tree. Choose a subset S of the CSP’s variables such that the constraint graph becomes a\ntree after removal of S. S is called a cycle cutset. If the cycle cutset has size c, then the total run time is O(d^c(n-c)d^2) \n\n## AIMA Chapter 6.5 The Structure of Problems\n The second way to reduce a constraint graph to a tree is based on constructing a tree\ndecomposition of the constraint graph, a transformation of the original graph into a tree\nwhere each node in the tree consists of a set of variables.Every variable in the original problem appears in at least one of the tree nodes.\nIf two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\nIf a variable appears in two nodes in the tree, it must appear in every node along the\npath connecting those nodes. Once we have a tree-structured graph, we can apply TREE-CSP-SOLVER to get a solution in\nO(nd^2) time, where is the number of tree nodes and is the size of the largest domain. The tree width of a tree decomposition of a graph is\none less than the size of the largest node; the tree width of the graph itself is defined to be\nthe minimum width among all its tree decompositions. If a graph has tree width then the\nproblem can be solved in O(nd^(w+1))time given the corresponding tree decomposition. Hence, CSPs with constraint graphs of bounded tiree width are solvable in polynomal time.the cutset decomposition with\ntime , or the tree decomposition with time ? Whenever you have a\ncycle-cutset of size c, there is also a tree width of size w<c+1, and it may be far smaller in\nsome cases. So time consideration favors tree decomposition, but the advantage of the\ncycle-cutset approach is that it can be executed in linear memory, while tree decomposition\nrequires memory exponential in the tree width of the constraint\ngraph.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" entailment is\n",
        "this: if and only if, in every model in which a is true, b is also true. a is a stronger assertion than b \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\"Having specified the syntax of propositional logic, we now specify its semantics. The\n",
        "semantics defines the rules for determining the truth of a sentence with respect to a\n",
        "particular model. In propositional logic, a model simply sets the truth value—true or false—\n",
        "for every proposition symbol. With three proposition symbols, there are 2^3 possible models. The semantics for propositional logic must specify how to compute the truth value of any\n",
        "sentence, given a model. two sentences and are logically equivalent if they are true in the same set of models. or any two sentences and\n",
        "are equivalent if and only if each of them entails the other.A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. tautologies—they\n",
        "are necessarily true. every valid sentence is\n",
        "logically equivalent to True.A sentence is satisfiable if it is true in, or satisfied by, some model. Satisfiability can be checked by enumerating the possible models\n",
        "until one is found that satisfies the sentence.The problem of determining the satisfiability of\n",
        "sentences in propositional logic—the SAT problem—was the first problem proved to be NPcomplete. a is valid iff a is unsatisfiable;\n",
        "contrapositively, a is satisfiable iff a is not valid.Proving a  from by checking the unsatisfiability of a and not b. It is also called proof by refutation or proof by contradiction. One assumes\n",
        "a sentence to be false and shows that this leads to a contradiction with known axioms .\n",
        "This contradiction is exactly what is meant by saying that the sentence is\n",
        "unsatisfiable.\n",
        "Reductio\"\"\"\n",
        "chapter7_5 = \"\"\"inference rule: Modus Ponens, And-Elimination, \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 36,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 690
        },
        "outputId": "b8e0d066-f33b-4c59-8800-3fb46368c9bb"
      },
      "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": 37,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n entailment is\nthis: if and only if, in every model in which a is true, b is also true. a is a stronger assertion than b \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nHaving specified the syntax of propositional logic, we now specify its semantics. The\nsemantics defines the rules for determining the truth of a sentence with respect to a\nparticular model. In propositional logic, a model simply sets the truth value—true or false—\nfor every proposition symbol. With three proposition symbols, there are 2^3 possible models. The semantics for propositional logic must specify how to compute the truth value of any\nsentence, given a model. two sentences and are logically equivalent if they are true in the same set of models. or any two sentences and\nare equivalent if and only if each of them entails the other.A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. tautologies—they\nare necessarily true. every valid sentence is\nlogically equivalent to True.A sentence is satisfiable if it is true in, or satisfied by, some model. Satisfiability can be checked by enumerating the possible models\nuntil one is found that satisfies the sentence.The problem of determining the satisfiability of\nsentences in propositional logic—the SAT problem—was the first problem proved to be NPcomplete. a is valid iff a is unsatisfiable;\ncontrapositively, a is satisfiable iff a is not valid.Proving a  from by checking the unsatisfiability of a and not b. It is also called proof by refutation or proof by contradiction. One assumes\na sentence to be false and shows that this leads to a contradiction with known axioms .\nThis contradiction is exactly what is meant by saying that the sentence is\nunsatisfiable.\nReductio\n\n## AIMA 7.5 Propositional Theorem Proving\ninference rule: Modus Ponens, And-Elimination, \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "afb58b2e-e8de-4247-8265-cdd15dd13ec2"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nThe Turing test requires agents to have NLP, knowledge, automated reasoning and ML capabilities. The total Turing test requires computer vision and robotics.\nAn agent is something that acts. A rational agent is one that achieves best expected outcome. Does not need to involve inference(recoiling). limited rationality due to complex env and computational constraints.\nvalue alignment problem:achieving agreement between our true preferences and the objectives.\n\n## AIMA Chapter 27.1 The Limits of AI\n weakAI: simulated thinking. strongAI: true consciousness. The qualification problem is to capture every contingency of appropriate behavior in a\nset of necessary and sufficient logical rules; The embodied cognition approach considers brain inseparable from a body, robotics, vision and other sensors thus become central.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nqualia - intrinsic nature of experiences\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators. Percept refers to the content an agent’s sensors are perceiving. An agent’s\npercept sequence is the complete history of everything the agent has ever perceived. An agent’s behavior is described by the agent function that maps any given percept\nsequence to an action. the agent function for an artificial agent will be implemented by an agent program. The\nagent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n consequentialism: we evaluate an agent’s behavior by its consequences. When an agent is plunked down in an environment, it generates a\nsequence of actions according to the percepts it receives. This sequence of actions causes\nthe environment to go through a sequence of states. If the sequence is desirable, then the\nagent has performed well. This notion of desirability is captured by a performance measure\nthat evaluates any given sequence of environment states.What is rational at any given time depends on four things:\nThe performance measure that defines the criterion of success.\nThe agent’s prior knowledge of the environment.\nThe actions that the agent can perform.\nThe agent’s percept sequence to date.\ndefinition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has. An omniscient\nagent knows the actual outcome of its actions and can act accordingly; but omniscience is\nimpossible in reality.Rationality maximizes\nexpected performance, while perfection maximizes actual performance. Our definition of rationality does not require omniscience, then, because the rational choice\ndepends only on the percept sequence to date. Need to ensure that \nthe agent does not inadvertently engage in decidedly underintelligent activities (irrational) would not be rational to cross the road given this uninformative percept sequence. Doing actions in order to modify future percepts—\nsometimes called information gathering—is an important part of rationality -exploration\n\n## AIMA 2.3 The Nature of Environments\n task environments, which are essentially the “problems” to which rational agents are the “solutions.” PEAS (Performance, Environment, Actuators, Sensors) description. If an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task environment is fully observable (all aspects that are relevant to the choice of action depending on the performance measure.agent need not maintain any internal state to keep track of the world. An\nenvironment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data. If the agent has no sensors at all\nthen the environment is unobservable, the agent’s goals, however, may still be achievable. competitive multiagent environment: the opponent entity maximizes its performance measure,\nwhich minimizes agent ’s performance measure.If the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic. a model of the environment\nis stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain\ntomorrow”) and “nondeterministic” if the possibilities are listed without being quantified. In an episodic task environment, the agent’s experience is\ndivided into atomic episodes. In each episode the agent receives a percept and then\nperforms a single action. Crucially, the next episode does not depend on the actions taken in\nprevious episodes. Many classification tasks are episodic. For example, an agent that has to\nspot defective parts on an assembly line bases each decision on the current part, regardless\nof previous decisions; moreover, the current decision doesn’t affect whether the next part is\ndefective. In sequential environments, on the other hand, the current decision could affect\nall future decisions. If the environment can change while an agent is deliberating, then\nwe say the environment is dynamic for that agent; otherwise, it is static.if the environment itself does not change with the\npassage of time but the agent’s performance score does, then we say the environment is\nsemidynamic.In a known environment, the outcomes (or outcome probabilities if the\nenvironment is nondeterministic) for all actions are given\n\n## AIMA 2.4 The Structure of Agents\na rational utility-based agent\nchooses the action that maximizes the expected utility of the action outcomes.a model-free agent can learn what action is best in a particular situation\nwithout ever learning exactly how that action changes the environment.In an atomic representation each state of the world is indivisible—it has no internal\nstructure.A factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value.Many important areas of AI are based on factored representations,\nincluding constraint satisfaction algorithms (Chapter 6 ), propositional logic (Chapter 7 ),\nplanning (Chapter 11 ), Bayesian networks (Chapters 12 –16 ), and various machine\nlearning algorithms.structured representation, in which objects such as cows and\ntrucks and their various and varying relationships can be described explicitly. the axis along which atomic, factored, and structured\nrepresentations lie is the axis of increasing expressiveness. Simple reflex agents respond directly to percepts, whereas model-based reflex agents\nmaintain internal state to track aspects of the world that are not evident in the current\npercept. Goal-based agents act to achieve their goals, and utility-based agents try to\nmaximize their own expected “happiness.”\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n 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 A search problem is defined by a set of possible states that the environment can be in, initial state, goal states and actions available to the agent, transition model RESULT returns the state\nthat results from doing action in state, action cost function.\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n An uninformed search algorithm is given no clue about how close a state is to the goal(s).When all actions have the same cost, an appropriate strategy is breadth-first search,both time and space complexity are O(b^d).When actions have different costs, an obvious choice is to use best-first search where the\nevaluation function is the cost of the path from the root to the current node - Dijkstra’s algorithm(uniform-cost search).Uniform-cost search is complete and is cost-optimal, because the first solution it finds will\nhave a cost that is at least as low as the cost of any other node in the frontier. Depth-first search is not cost-optimal, but it is complete for finite state spaces. For a finite tree, depth-first tree-like\nsearch takes time proportional to the number of states, and has memory complexity of only O(bm) where m is the branching factor and is the maximum depth of the tree. A variant of depth-first search called backtracking search uses even less memory, O(m). To keep depth-first search from wandering down an infinite path, we can use depth-limited\nsearch, with time complexity of O(b^l), space complexity of O(bl). Poor choice of l makes it incomplete. Iterative deepening search solves the problem of picking a good value for by trying all\nvalues. Similar space complexity as DFS, O(bd). optimal for problems where all actions have the same cost,\nand is complete on finite acyclic state spaces. An alternative approach called bidirectional search\nsimultaneously searches forward from the initial state and backwards from the goal state(s), with O(b^(d/2))+O(b^(d/2)) smaller\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) Search Strategies use domain-specific hints. Greedy best-first search is a form of best-first search that expands first the node with the\nlowest h(n) value—the node that appears to be closest to the goal. Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. It is also not optimal. The\nworst-case time and space complexity is O(|V|). With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching O(bm). A star is complete and is cost optimal with an admissible heuristic (never overestimates the cost to reach a goal, optimistic). A slightly stronger property is called consistency (triangle inequality). We say that A* with a consistent heuristic is optimally efficient in the sense that any\nalgorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A*, it prunes away search tree nodes that are not necessary for finding\nan optimal solution.\n\n## AIMA Chapter 3.6 Heuristic Functions\n the quality of a heuristic - effective branching factor. well-designed heuristic would have a value of b close to 1.\nhave a value. Domination translates directly into efficiency. A* using a consistently larger heuristic h1 will\nnever expand more nodes than h2\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n search algorithm, each state is atomic, or\nindivisible—a black box with no internal structure, need domainspecific\ncode to describe the transitions between states. Constraint Satisfaction Problems open the black box with a factored representation for each\nstate: a set of variables, each of which has a value. A constraint satisfaction problem consists of three components, X (X1,..., Xn, set of vars), D(set of domains, one for each var)C(a set of constraints that specify allowable combinations of values). CSPs deal with assignments of values to variables. An assignment\nthat does not violate any constraints is called a consistent or legal assignment. A complete\nassignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. A partial assignment is one that leaves some variables\nunassigned, and a partial solution is a partial assignment that is consistent.Solving a CSP is\nan NP-complete problem in general. A binary CSP is one with only unary and binary constraints, it can be represented as a\nconstraint graph. CSPs with preferences can\nbe solved with optimization search methods, either path-based or local. We call such a\nproblem a constrained optimization problem. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation may be intertwined with search, or it may be done as a\npreprocessing step, before search starts. Sometimes this preprocessing can solve the whole\nproblem, so no search is required at all. A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints. a graph is node-consistent if every variable in the graph is node-consistent. A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints.AC-3 enforcing arc consistency. AC-3 algorithm maintains a queue which initially contains all the arcs in the CSP. (Each binary constraint\nbecomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (A,B) from the queue and makes A arc-consistent with respect to B. If this leaves domain of A unchanged, the\nalgorithm just moves on to the next arc. If the domain of A changes, all arcs (X, A) need to be added back to the queue. because the change in Da might enable further reductions in Dx, even if we have previously\nconsidered Dx. If any domain is revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure. Otherwise, we keep checking,\ntrying to remove values from the domains of variables until no more arcs are in the queue.\nAt that point, we are left with a CSP that is equivalent to the original CSP—they both have\nthe same solutions—but the arc-consistent CSP will be faster to search because its variables\nhave smaller domains. The complexity of AC-3: Assume a CSP with variables, each\nwith domain size at most , and with binary constraints (arcs). Each arc can be\ninserted in the queue only d times because Xi has at most values to delete. Checking\nconsistency of an arc can be done in time O(d^2), so we get O(cd^3) total worst-case time. A CSP is strongly k-consistent if it is k-1-consistent, k-2-consistent,..., all the way down to 1-consistent. any\nalgorithm for establishing -consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in .\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Sometimes we can finish the constraint propagation process and still have variables with\nmultiple possible values. In that case we have to search for a solution.It repeatedly chooses an\nunassigned variable, and then tries all values in the domain of that variable in turn, trying to each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, and if it fails, the assignment is restored to the previous state, and we try the next value. If no value works then we return failure. choosing the variable with the fewest “legal” values—is called the\nminimum-remaining-values (MRV) heuristic. It also has been called the “most constrained\nvariable” or “fail-first” heuristic, the latter because it picks a variable that is most likely to\ncause a failure soon, thereby pruning the search tree. The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,\nbecause initially every region has three legal colors. In this case, the degree heuristic comes\nin handy. It attempts to reduce the branching factor on future choices by selecting the\nvariable that is involved in the largest number of constraints on other unassigned variables. Once a variable has been selected, the algorithm must decide on the order in which to\nexamine its values. The least-constraining-value heuristic is effective for this. It prefers the\nvalue that rules out the fewest choices for the neighboring variables in the constraint graph. every time we make a\nchoice of a value for a variable, we have a brand-new opportunity to infer new domain\nreductions on the neighboring variables. One of the simplest forms of inference is called forward checking. Whenever a variable is\nassigned, the forward-checking process establishes arc consistency for it: for each\nunassigned variable that is connected to by a constraint, delete from ’s domain any\nvalue that is inconsistent with the value chosen for. Although forward checking detects many inconsistencies, it does not detect all of them. The\nproblem is that it doesn’t look ahead far enough. The algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like\nthis. forward checking does the same thing\nas MAC on the initial arcs in MAC’s queue but unlike MAC, forward checking does not\nrecursively propagate constraints when changes are made to the domains of variables.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Completely independent subproblems are delicious (independent\nsubproblems decomposition O(d^cn/c) linear in n instead of exponential), then, but rare. any tree-structured CSP can\nbe solved in time linear in the number of variables. A CSP is defined to be directional arc-consistent\nunder an ordering of variables  X1,..., Xn if and only if every Xi is arc-consistent with\neach Xj for j>i.To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\nan ordering of the variables such that each variable appears after its parent in the tree. Such\nan ordering is called a topological sort. The first way to reduce a constraint graph to a tree involves assigning values to some\nvariables so that the remaining variables form a tree. Choose a subset S of the CSP’s variables such that the constraint graph becomes a\ntree after removal of S. S is called a cycle cutset. If the cycle cutset has size c, then the total run time is O(d^c(n-c)d^2) \n\n## AIMA Chapter 6.5 The Structure of Problems\n The second way to reduce a constraint graph to a tree is based on constructing a tree\ndecomposition of the constraint graph, a transformation of the original graph into a tree\nwhere each node in the tree consists of a set of variables.Every variable in the original problem appears in at least one of the tree nodes.\nIf two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\nIf a variable appears in two nodes in the tree, it must appear in every node along the\npath connecting those nodes. Once we have a tree-structured graph, we can apply TREE-CSP-SOLVER to get a solution in\nO(nd^2) time, where is the number of tree nodes and is the size of the largest domain. The tree width of a tree decomposition of a graph is\none less than the size of the largest node; the tree width of the graph itself is defined to be\nthe minimum width among all its tree decompositions. If a graph has tree width then the\nproblem can be solved in O(nd^(w+1))time given the corresponding tree decomposition. Hence, CSPs with constraint graphs of bounded tiree width are solvable in polynomal time.the cutset decomposition with\ntime , or the tree decomposition with time ? Whenever you have a\ncycle-cutset of size c, there is also a tree width of size w<c+1, and it may be far smaller in\nsome cases. So time consideration favors tree decomposition, but the advantage of the\ncycle-cutset approach is that it can be executed in linear memory, while tree decomposition\nrequires memory exponential in the tree width of the constraint\ngraph.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n entailment is\nthis: if and only if, in every model in which a is true, b is also true. a is a stronger assertion than b \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nHaving specified the syntax of propositional logic, we now specify its semantics. The\nsemantics defines the rules for determining the truth of a sentence with respect to a\nparticular model. In propositional logic, a model simply sets the truth value—true or false—\nfor every proposition symbol. With three proposition symbols, there are 2^3 possible models. The semantics for propositional logic must specify how to compute the truth value of any\nsentence, given a model. two sentences and are logically equivalent if they are true in the same set of models. or any two sentences and\nare equivalent if and only if each of them entails the other.A sentence is valid if it is true in all models.Valid sentences are also known as tautologies. tautologies—they\nare necessarily true. every valid sentence is\nlogically equivalent to True.A sentence is satisfiable if it is true in, or satisfied by, some model. Satisfiability can be checked by enumerating the possible models\nuntil one is found that satisfies the sentence.The problem of determining the satisfiability of\nsentences in propositional logic—the SAT problem—was the first problem proved to be NPcomplete. a is valid iff a is unsatisfiable;\ncontrapositively, a is satisfiable iff a is not valid.Proving a  from by checking the unsatisfiability of a and not b. It is also called proof by refutation or proof by contradiction. One assumes\na sentence to be false and shows that this leads to a contradiction with known axioms .\nThis contradiction is exactly what is meant by saying that the sentence is\nunsatisfiable.\nReductio\n\n## AIMA 7.5 Propositional Theorem Proving\ninference rule: Modus Ponens, And-Elimination, \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}