{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS 521 Midterm Notes",
      "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": "f3841b10-ee95-4028-87e7-724cbce8170b"
      },
      "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": 26,
      "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": "aa4dda26-1af3-4edf-9a23-93aee64b4703"
      },
      "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": 27,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 28,
      "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 = \"\"\"Intelligence can be considered as an internal characterization of thought processes or reasoning, or external as behavior.\n",
        "Four possible combinations with human vs rational dimensions. Turing Test determines if a machine can think if a human interrogator, after\n",
        "posing questions, cannot tell if responses were human or computer. Needs (1) natural language processing (2) knowledge representation (3)\n",
        "automated reasoning (4) machine learning. Total Turing Test requires interaction with object/people. Needs (1) computer vision (2) robotics.\n",
        "Can learn about human thought through (1) introspection (2) psych. experiments (3) brain imaging. Combining neuroimaging methods + ML techniques\n",
        "can lead to reading minds/understanding human cognition. Thinking Rationally: syllogisms laws of thought govern the operation of mind: logic. \n",
        "Logic requires knowledge of world that is certain, with probability flling this gap. Acting Rationally: computer agents expected to operate by\n",
        "itself, perceive surroundings, persist over time, adapt to change, set goals. All skills needed for Turing test allow agent to act rationally. \n",
        "Rational agent approach is more general and more adaptable to scientific development. AI focuses on study and construction of agents that do the \n",
        "right thing- standard model. However, always taking optimal action is not feasible. As we move into real word, it is not that easy to specify\n",
        "objective completely and accurately. Example of value alignment problem: chess machine can act beyond confines to achieve winning, the sole goal. \n",
        "Need to tell machine to pursue our objectives, but make it uncertain so machine will act more cautiously- provably beneficial to humans.\"\"\" \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 = \"\"\"Strong AI has shifted to be called human-level AI or general AI, programs that can solve variety of tasks just like a human can. \n",
        "Argument from informality of behavior states that humans use informal guidelines far too complex to be captured by rules to be codified in a program. \n",
        "Probabilistic reasoning appropriate for open-ended domains. Need to study cognition->body->environment system as a whole. The argument from disability \n",
        "makes the claim that a machine can never do X. Godel's axiomatic theorem states that for any axiomatic framework F that can do arithmetic, can construct\n",
        "a Godel sentence G(F) such that (1) G(F) is sentence of F, but cannot be proved within F (2) if F is consistent, G(F) is true. \"\"\"\n",
        "\n",
        "chapter27_2 = \"\"\"Turing notes that we never have any direct evidence about the mental state of other humans. Should instead have polite convention that \n",
        "everyone thinks. Chinese room is a system that takes input in form of Chinese sentences and generates Chinese responses, with no understanding by human, rule \n",
        "book or paper of Chinese. Since doing the same thing a computer would, computers generate no understanding. Consciousness remains ill-defined. Behaving intelligently \n",
        "requires awareness which differs from task to task. Tasks involving human interactino requires model of human subjective experience. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"An agent's choice of action at any given instant depends on built-in knowledge and percept sequence observed to date.\"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\"Humans have desires and preferences, unlike machines, so success is measured in choosing actions that produce sequences \n",
        "of states that desirable from their POV, versus machines performance measured wrt to designer/users of machine. In general, should design \n",
        "performance measures according to what should be achieved in environment, rather than how an agent should behave (ex: amount of dirt cleaned \n",
        "vs clean floor). Rationality at any given time depends on (1) performance measure (2) agent's prior knowledge of environment (3) actions agent \n",
        "can perform (4) agent's percept sequence to date. Rationality (max. expected performance) not same as perfection (max. actual performance). \n",
        "Agent lacks autonomy if relies on prior knowledge of designer rather that its own percepts/learning. Incorporation of learning allows a single \n",
        "rational agent to be designed that can suceed in various environments.\"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\"Kinds of task environments (1) fully vs partially observable (2) single-agent vs multiagent (communication is a rational behavior)\n",
        "(3) deterministic vs nondeterministic (4) episodic vs sequential (5) static vs dynamic (6) discrete vs continuous (7) known vs unknown.\n",
        "Hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continous, unknown\"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\"Simple reflex agents will work only if correct decision can be made on the basis of just the current precept (fully observable environment).\n",
        "Infinite loops are unavoidable for SRA in partially observable environments-> can randomize actions. Goal-based agents appear less efficient, but more flexible \n",
        "because knowledge that supports its decisions is represented explicitly and can be modified. Utility based agent is advantageous: (1) when there are conflicting \n",
        "goals, utility function specifies appropriate tradeoff (2) when several goals that agent can aim for, utility provides a way such that success chance can be weighed \n",
        "against goal importance. Any type of agent can be built as a learning agent. Learning allows agents to operate in initially unknown environments and to become more \n",
        "competent that its initial knowledge alone. Improving model components of a model-based agent so that they conform better with reality is a good idea. Performance \n",
        "standard distinguishes part of incoming percept as a reward or penalty which provides feedback on agent's behavior quality. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\"\"\"\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",
        "\"rationality\": \"abstract formal definition of intelligence- doing the right thing\",\n",
        "\"natural language processing\": \"communicate successfully in human language\",\n",
        "\"knowledge representation\": \"store everything knows/hears\",\n",
        "\"automated reasoning\": \"answer questions and draw conclusions based on existing knowledge\",\n",
        "\"machine learning\": \"adapt to new situations, detect/extract/extrapolate patterns\",\n",
        "\"introspection\": \"looking into our own individual thoughts\",\n",
        "\"psychological experiments\": \"observing person's behaviors/actions\",\n",
        "\"brain imaging\": \"observing brain in action\",\n",
        "\"cognitive science:\": \"computer AI models + psychology experiements = theories of human mind\",\n",
        "\"syllogisms\": \"patterns for arguments that result in correct conclusions from correct premises\",\n",
        "\"agent\" : \"anything that can perceive through sensors and act in an environment through actuators\",\n",
        "\"rational agent\": \"agent that acts to achieve best (expected) outcome; does the right thing, given percept sequence & built-in knowledge\",\n",
        "\"limited rationality\": \"acting appropriately when not enough time to do all necessary computations\",\n",
        "\"weak AI\": \"machines could act as if they were intelligent\",\n",
        "\"strong AI\": \"machines that act intelligent are actually consciously, not simulating, thinking\",\n",
        "\"qualification problem\": \"difficult to capture every contingency of appropriate behavior in set of logical rules\",\n",
        "\"embodied cognition\": \"cannot consider brain separately; cognition takes place within body within environment\",\n",
        "\"biological naturalism\": \"mental states are high-level emergent features caused by low-level neuron physical processes\",\n",
        "\"consciousness\": \"awareness of outside world, self, subjective experience of living\",\n",
        "\"qualia\": \"intrinsic nature of experiences\",\n",
        "\"percept\": \"content the agent's sensors are perceiving\",\n",
        "\"percept sequence\": \"history of everything that agent has ever perceived\",\n",
        "\"agent function\": \"maps any given percept sequence to an action\",\n",
        "\"agent program\": \"agent function for an artificial agent implemented by this, running within physical system\",\n",
        "\"consequentialism\": \"evaluate an agent's behavior by its consequences\",\n",
        "\"performance measure\": \"evaluates any given sequence of environment states; criterion for agent's behavior success\",\n",
        "\"omniscience\": \"such an agent knows actual outcome of actions & acts accordingly, not realistic\",\n",
        "\"information gathering\": \"doing actions in order to modify future percepts\",\n",
        "\"autonomy\": \"such an agent should learn what it can to compensate for partial or incorrect prior knowledge\",\n",
        "\"task environment\": \"the problems to which the rational agents are the solutions\",\n",
        "\"PEAS\": \"Performance, Environment, Actuators, Sensors\",\n",
        "\"fully observable\": \"agent's sensors give access to complete state of environment at each point in time\",\n",
        "\"partially observable\": \"noisy & inaccurate sensors; parts of state missing from sensor data\",\n",
        "\"unobservable\": \"if an agent has no sensors at all\",\n",
        "\"competitive multiagent\": \"B trying to maximize performance measure minimizes A's performance measure\",\n",
        "\"partially cooperative multiagent\": \"taking actions that maximize performance measure of all agents (ex: taxi collisions)\",\n",
        "\"deterministic\": \"next state of environment fully determined by current state + action taken, else nondeterministic\",\n",
        "\"stochastic\": \"if a model of the environment deals with probabilities, else if not quantified then nondeterminsitic\",\n",
        "\"episodic\": \"next episode does not depend on actions taken in previous episodes\",\n",
        "\"sequential\": \"current decision could affect all future decisions (chess and taxi driving)\",\n",
        "\"dynamic\": \"if environment can change while an agent is deliberating, else static\",\n",
        "\"known\": \"environment in which outcomes (outcome probabilities) for all actions are given, else unknown\",\n",
        "\"agent architecture\": \"agent = architecture + program\",\n",
        "\"simple reflex agent\": \"select actions on basis of current percept ignoring rest of percept history\",\n",
        "\"condition-action rule\": \"ex: if car-in-front-is-braking then initiate-braking\",\n",
        "\"internal state\": \"maintained by agent to handle partial observability and keep track of unobservable aspects of current state\",\n",
        "\"transition model\": \"knowledge about how the world works\",\n",
        "\"sensor model\": \"information about how the state of the world is reflected in agent's percepts\",\n",
        "\"model-based agent\": \"use both transitional model and sensor model to keep track of state of the world\",\n",
        "\"goal-based agent\": \"use goal information that describes desirable situations along with the model to achieve the goal\",\n",
        "\"search and planning\": \"subfields of AI devoted to finding action sequences that achieve agent's goals\",\n",
        "\"utility function\": \"an agent's internalization of the performance measure\",\n",
        "\"expected utility\": \"utility agent expects to derive on average, given probabilities & utilities of each outcome\",\n",
        "\"model-free agent\": \"agent that can learn what action is best in a particular situation w/o learning how action affects environment\",\n",
        "\"learning element\": \"responsible for making improvements; uses feedback from critic to see how performance element should be modified\",\n",
        "\"performance element\": \"responsible for selecting external actions\",\n",
        "\"critic\": \"tells the learning element how well the agent is doing with wrt to a fixed performance standard\",\n",
        "\"problem generator\": \"suggests exploratory actions; allows agent to do some suboptimal actions in short run and discover better ones for long run\",\n",
        "\"atomic representation\": \"each state of the world is indivisible- no internal structure\",\n",
        "\"factored representation\": \"splits up each state into fixed set of variables or attributes, each of which has a value\",\n",
        "\"structured representation\": \"objects and their various, varying relationship can be described explicitly\",\n",
        "\"expressiveness\": \"more expressive language is more concise, captures at least as much as less expressive ones; learning more complex\",\n",
        "\"localist representation\": \"one-to-one mapping between concepts and memory locations (computer, brain)\",\n",
        "\"distributed representation\": \"representation of a concept is spread over many memory locations, each used for representation of multiple diff. concepts\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 29,
      "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": "c4f052fc-c46f-4d84-f2cb-8502ca982f72"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nIntelligence can be considered as an internal characterization of thought processes or reasoning, or external as behavior.\nFour possible combinations with human vs rational dimensions. Turing Test determines if a machine can think if a human interrogator, after\nposing questions, cannot tell if responses were human or computer. Needs (1) natural language processing (2) knowledge representation (3)\nautomated reasoning (4) machine learning. Total Turing Test requires interaction with object/people. Needs (1) computer vision (2) robotics.\nCan learn about human thought through (1) introspection (2) psych. experiments (3) brain imaging. Combining neuroimaging methods + ML techniques\ncan lead to reading minds/understanding human cognition. Thinking Rationally: syllogisms laws of thought govern the operation of mind: logic. \nLogic requires knowledge of world that is certain, with probability flling this gap. Acting Rationally: computer agents expected to operate by\nitself, perceive surroundings, persist over time, adapt to change, set goals. All skills needed for Turing test allow agent to act rationally. \nRational agent approach is more general and more adaptable to scientific development. AI focuses on study and construction of agents that do the \nright thing- standard model. However, always taking optimal action is not feasible. As we move into real word, it is not that easy to specify\nobjective completely and accurately. Example of value alignment problem: chess machine can act beyond confines to achieve winning, the sole goal. \nNeed to tell machine to pursue our objectives, but make it uncertain so machine will act more cautiously- provably beneficial to humans.\n\n## AIMA Chapter 27.1 The Limits of AI\nStrong AI has shifted to be called human-level AI or general AI, programs that can solve variety of tasks just like a human can. \nArgument from informality of behavior states that humans use informal guidelines far too complex to be captured by rules to be codified in a program. \nProbabilistic reasoning appropriate for open-ended domains. Need to study cognition->body->environment system as a whole. The argument from disability \nmakes the claim that a machine can never do X. Godel's axiomatic theorem states that for any axiomatic framework F that can do arithmetic, can construct\na Godel sentence G(F) such that (1) G(F) is sentence of F, but cannot be proved within F (2) if F is consistent, G(F) is true. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\nTuring notes that we never have any direct evidence about the mental state of other humans. Should instead have polite convention that \neveryone thinks. Chinese room is a system that takes input in form of Chinese sentences and generates Chinese responses, with no understanding by human, rule \nbook or paper of Chinese. Since doing the same thing a computer would, computers generate no understanding. Consciousness remains ill-defined. Behaving intelligently \nrequires awareness which differs from task to task. Tasks involving human interactino requires model of human subjective experience. \n\n## AIMA 2.1 Agents and Environments\nAn agent's choice of action at any given instant depends on built-in knowledge and percept sequence observed to date.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nHumans have desires and preferences, unlike machines, so success is measured in choosing actions that produce sequences \nof states that desirable from their POV, versus machines performance measured wrt to designer/users of machine. In general, should design \nperformance measures according to what should be achieved in environment, rather than how an agent should behave (ex: amount of dirt cleaned \nvs clean floor). Rationality at any given time depends on (1) performance measure (2) agent's prior knowledge of environment (3) actions agent \ncan perform (4) agent's percept sequence to date. Rationality (max. expected performance) not same as perfection (max. actual performance). \nAgent lacks autonomy if relies on prior knowledge of designer rather that its own percepts/learning. Incorporation of learning allows a single \nrational agent to be designed that can suceed in various environments.\n\n## AIMA 2.3 The Nature of Environments\nKinds of task environments (1) fully vs partially observable (2) single-agent vs multiagent (communication is a rational behavior)\n(3) deterministic vs nondeterministic (4) episodic vs sequential (5) static vs dynamic (6) discrete vs continuous (7) known vs unknown.\nHardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continous, unknown\n\n## AIMA 2.4 The Structure of Agents\nSimple reflex agents will work only if correct decision can be made on the basis of just the current precept (fully observable environment).\nInfinite loops are unavoidable for SRA in partially observable environments-> can randomize actions. Goal-based agents appear less efficient, but more flexible \nbecause knowledge that supports its decisions is represented explicitly and can be modified. Utility based agent is advantageous: (1) when there are conflicting \ngoals, utility function specifies appropriate tradeoff (2) when several goals that agent can aim for, utility provides a way such that success chance can be weighed \nagainst goal importance. Any type of agent can be built as a learning agent. Learning allows agents to operate in initially unknown environments and to become more \ncompetent that its initial knowledge alone. Improving model components of a model-based agent so that they conform better with reality is a good idea. Performance \nstandard distinguishes part of incoming percept as a reward or penalty which provides feedback on agent's behavior quality. \n\n## Module 1 Lecture Notes\n\n\n## Module 1 Definitions\n* **Rationality** - abstract formal definition of intelligence- doing the right thing\n* **Natural language processing** - communicate successfully in human language\n* **Knowledge representation** - store everything knows/hears\n* **Automated reasoning** - answer questions and draw conclusions based on existing knowledge\n* **Machine learning** - adapt to new situations, detect/extract/extrapolate patterns\n* **Introspection** - looking into our own individual thoughts\n* **Psychological experiments** - observing person's behaviors/actions\n* **Brain imaging** - observing brain in action\n* **Cognitive science:** - computer AI models + psychology experiements = theories of human mind\n* **Syllogisms** - patterns for arguments that result in correct conclusions from correct premises\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Rational agent** - agent that acts to achieve best (expected) outcome; does the right thing, given percept sequence & built-in knowledge\n* **Limited rationality** - acting appropriately when not enough time to do all necessary computations\n* **Weak ai** - machines could act as if they were intelligent\n* **Strong ai** - machines that act intelligent are actually consciously, not simulating, thinking\n* **Qualification problem** - difficult to capture every contingency of appropriate behavior in set of logical rules\n* **Embodied cognition** - cannot consider brain separately; cognition takes place within body within environment\n* **Biological naturalism** - mental states are high-level emergent features caused by low-level neuron physical processes\n* **Consciousness** - awareness of outside world, self, subjective experience of living\n* **Qualia** - intrinsic nature of experiences\n* **Percept** - content the agent's sensors are perceiving\n* **Percept sequence** - history of everything that agent has ever perceived\n* **Agent function** - maps any given percept sequence to an action\n* **Agent program** - agent function for an artificial agent implemented by this, running within physical system\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluates any given sequence of environment states; criterion for agent's behavior success\n* **Omniscience** - such an agent knows actual outcome of actions & acts accordingly, not realistic\n* **Information gathering** - doing actions in order to modify future percepts\n* **Autonomy** - such an agent should learn what it can to compensate for partial or incorrect prior knowledge\n* **Task environment** - the problems to which the rational agents are the solutions\n* **Peas** - Performance, Environment, Actuators, Sensors\n* **Fully observable** - agent's sensors give access to complete state of environment at each point in time\n* **Partially observable** - noisy & inaccurate sensors; parts of state missing from sensor data\n* **Unobservable** - if an agent has no sensors at all\n* **Competitive multiagent** - B trying to maximize performance measure minimizes A's performance measure\n* **Partially cooperative multiagent** - taking actions that maximize performance measure of all agents (ex: taxi collisions)\n* **Deterministic** - next state of environment fully determined by current state + action taken, else nondeterministic\n* **Stochastic** - if a model of the environment deals with probabilities, else if not quantified then nondeterminsitic\n* **Episodic** - next episode does not depend on actions taken in previous episodes\n* **Sequential** - current decision could affect all future decisions (chess and taxi driving)\n* **Dynamic** - if environment can change while an agent is deliberating, else static\n* **Known** - environment in which outcomes (outcome probabilities) for all actions are given, else unknown\n* **Agent architecture** - agent = architecture + program\n* **Simple reflex agent** - select actions on basis of current percept ignoring rest of percept history\n* **Condition-action rule** - ex: if car-in-front-is-braking then initiate-braking\n* **Internal state** - maintained by agent to handle partial observability and keep track of unobservable aspects of current state\n* **Transition model** - knowledge about how the world works\n* **Sensor model** - information about how the state of the world is reflected in agent's percepts\n* **Model-based agent** - use both transitional model and sensor model to keep track of state of the world\n* **Goal-based agent** - use goal information that describes desirable situations along with the model to achieve the goal\n* **Search and planning** - subfields of AI devoted to finding action sequences that achieve agent's goals\n* **Utility function** - an agent's internalization of the performance measure\n* **Expected utility** - utility agent expects to derive on average, given probabilities & utilities of each outcome\n* **Model-free agent** - agent that can learn what action is best in a particular situation w/o learning how action affects environment\n* **Learning element** - responsible for making improvements; uses feedback from critic to see how performance element should be modified\n* **Performance element** - responsible for selecting external actions\n* **Critic** - tells the learning element how well the agent is doing with wrt to a fixed performance standard\n* **Problem generator** - suggests exploratory actions; allows agent to do some suboptimal actions in short run and discover better ones for long run\n* **Atomic representation** - each state of the world is indivisible- no internal structure\n* **Factored representation** - splits up each state into fixed set of variables or attributes, each of which has a value\n* **Structured representation** - objects and their various, varying relationship can be described explicitly\n* **Expressiveness** - more expressive language is more concise, captures at least as much as less expressive ones; learning more complex\n* **Localist representation** - one-to-one mapping between concepts and memory locations (computer, brain)\n* **Distributed representation** - representation of a concept is spread over many memory locations, each used for representation of multiple diff. concepts\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 same value. 'is' checks whether variables \n",
        "point to the same object. Lists are mutable. Use y = x[:] to get a shallow copy of any sequence (a new object of the same value). \n",
        "Slicing examples: t[1:4] ends before last index, t[1:-1] ends before last element, t[1:-1:2] selection of every nth item, t[:2] copy from beginning\n",
        "of sequence, t[2:] copy to very end of sequence. List .reverse() reverses in place/modifies, .sort() sorts the list in place, .sort(function) sorts in place\n",
        "using user-defined comparions, sorted(li) returns a *copy* sorted. Can get KeyError with dictionaries if key does not exist. Dictionary methods: .keys() returns \n",
        "list of current keys, .values() returns list of current values, .items() returns list of item tuples, defaultdict automatically initializes nonexistent dictionary values \n",
        "like empty string while Counter initializes to 0. Python doesn't allow function overloading like Java does, operator overloading is possible. *args allows to accept a \n",
        "variable number of non-keyword arguments to a function and **kwards allows to accept a varialbe number of keyword arguments to function-> def myfun(positional, *args, **kwargs). \n",
        "Default parameters values are evaluated only when the def statement they belong to is first execution (ex: fibonacci). To define a subclass, put name of superclass in () after the \n",
        "subclass's name on first line of definition. To be iterable, must have __iter__ method, to be iterator must have __next__ method. \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"strong typing\" : \"every object has a fixed type, interpreter doesn't allow things incompatible with that type ('foo' + 2)\",\n",
        "\"static typing\": \"variables can only refer to objects of a declared type, use type signatures (Java)\",\n",
        "\"dynamic typing\": \"variables come into existence when first assigned; type(var) can be updated- Python\",\n",
        "\"tuple\": \"simple immutable ordered sequence of items; can be of mixed types, including collection types\",\n",
        "\"strings\": \"immutable; unicode and use 2-byte characters\",\n",
        "\"list\": \"mutable ordered sequence of items of mixed types\",\n",
        "\"slicing\": \"return copy of a subsequence\",\n",
        "\"dictionaries\": \"unordered & work by hashing, so keys must be immutable; constant average time add, lookup, update\",\n",
        "\"magic methods\": \"allow user-defined classes to behave like built-in types (__init__, __len__, __add__)\",\n",
        "\"duck typing\": \"establishes suitability of an object by determining presence of methods, call len() on any class with __len__\",\n",
        "\"list comprehension\": \"[expression for name in list]\",\n",
        "\"filtered list comprehension\": \"[expression for name in list if filter]\",\n",
        "\"iterator objects\": \"can be used in for loop because have __iter__ magic method, do not have hasnext() -> StopIteration exception\",\n",
        "\"generators\": \"functions that contain yield keyword automatically return a generator when called\",\n",
        "}"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 583
        },
        "outputId": "a08d20db-3d9a-41bc-fbce-c5e521cf6167"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nStrings are immutable. == checks whether variables point to objects of same value. 'is' checks whether variables \npoint to the same object. Lists are mutable. Use y = x[:] to get a shallow copy of any sequence (a new object of the same value). \nSlicing examples: t[1:4] ends before last index, t[1:-1] ends before last element, t[1:-1:2] selection of every nth item, t[:2] copy from beginning\nof sequence, t[2:] copy to very end of sequence. List .reverse() reverses in place/modifies, .sort() sorts the list in place, .sort(function) sorts in place\nusing user-defined comparions, sorted(li) returns a *copy* sorted. Can get KeyError with dictionaries if key does not exist. Dictionary methods: .keys() returns \nlist of current keys, .values() returns list of current values, .items() returns list of item tuples, defaultdict automatically initializes nonexistent dictionary values \nlike empty string while Counter initializes to 0. Python doesn't allow function overloading like Java does, operator overloading is possible. *args allows to accept a \nvariable number of non-keyword arguments to a function and **kwards allows to accept a varialbe number of keyword arguments to function-> def myfun(positional, *args, **kwargs). \nDefault parameters values are evaluated only when the def statement they belong to is first execution (ex: fibonacci). To define a subclass, put name of superclass in () after the \nsubclass's name on first line of definition. To be iterable, must have __iter__ method, to be iterator must have __next__ method. \n\n## Module 2 Definitions\n* **Strong typing** - every object has a fixed type, interpreter doesn't allow things incompatible with that type ('foo' + 2)\n* **Static typing** - variables can only refer to objects of a declared type, use type signatures (Java)\n* **Dynamic typing** - variables come into existence when first assigned; type(var) can be updated- Python\n* **Tuple** - simple immutable ordered sequence of items; can be of mixed types, including collection types\n* **Strings** - immutable; unicode and use 2-byte characters\n* **List** - mutable ordered sequence of items of mixed types\n* **Slicing** - return copy of a subsequence\n* **Dictionaries** - unordered & work by hashing, so keys must be immutable; constant average time add, lookup, update\n* **Magic methods** - allow user-defined classes to behave like built-in types (__init__, __len__, __add__)\n* **Duck typing** - establishes suitability of an object by determining presence of methods, call len() on any class with __len__\n* **List comprehension** - [expression for name in list]\n* **Filtered list comprehension** - [expression for name in list if filter]\n* **Iterator objects** - can be used in for loop because have __iter__ magic method, do not have hasnext() -> StopIteration exception\n* **Generators** - functions that contain yield keyword automatically return a generator when called\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 = \"\"\"Problem solving agents use atomic representations. Four phase problem solving process: (1) goal formulation\n",
        "(2) problem formulation (3) search (4) execution. In any fully observable, deterministic, known environment, the solution to\n",
        "any problem is a fixed sequence of actions. Search problem defined by (1) state space (2) initial state (3) goal states (4) actions\n",
        "(5) transition model (6) action cost function. Choice of good abstraction involves removing as much detail as possible while retaining\n",
        "validity and ensuring abstract actions are easy to carry out. Grid world example: a vacuum environment with n cells has n*2^n states. \n",
        "Example of infinite state spaces: sequence of square root, floor, and factorial operations can reach any desired positive integer\"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\"Standardized Problems\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\"State space describes possibly infinite set of states in world and actions that allow transitions from one state to another,\n",
        "while search tree describes paths between these states, reaching towards the goal. Best first search algorithm: on each iteration choose a node\n",
        "on the frontier with minimum f(n) value, return if goal, else apply EXPAND to generate child nodes. Each child node added to frontier if not yet \n",
        "reached or reached with path with lower cost than before. Returns either failure or node that represents path to goal. Even if state space is finite,\n",
        "the complete search tree is infinite because no limit how much traverse a loop/cycle/redundant path. Can check for cycles during a search algorith, by \n",
        "following up chain of parent pointers to check if state has been seen before (no need for additional memory). Evaluate an algorithm by (1) completeness\n",
        "(2) cost optimality (3) time complexity (4) space complexity\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\"Uninformed search algorithm is given no clue about how close a state is to the goal. For BFS, FIFO queue faster than a priority queue and gives\n",
        "correct order of nodes; reached can be set of states. BFS is cost optimal for problems where all actions have the same cost. Both space and time compexity are O(b^d).\n",
        "Uniform cost search spreads out in waves of uniform path cost. Worst case time and space complexity is $O(b^{1+frac{C*, e}})$. UCS can explore large trees of actions with low\n",
        "costs before exploring paths with high-cost and maybe useful action. Depth first search proceeds to deepest level of tree, then backs up to next deepest node that still has\n",
        "unexpanded successors. Not cost optimal. For infinite state spaces, DFS can get stuck going down infinite path even if no cycles, thus incomplete. Memory is much smaller in DFS- O(bm)\n",
        "Backtracking has O(m) memory requirement. Depth limited search has time complexity of O(b^l) and space O(bl). IDS has memory req of O(bd) if solution, else O(bm) on finite state space. \n",
        "Time complexity O(b^d) with solution, else O(b^m). In bidirectional search, if cost of optimal path is C*, no node with cost > C*/2 is expanded\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"If fully observable, deterministic, known environment, solution is always fixed sequence of actions. Else if partially observable or nondeterministic,\n",
        "solution must recommend different future actions depending on what percepts received (branching strategy). Search problem needs states, initial state, actions, transition model, path cost, \n",
        "and goal. Uniform action cost means all actions are equal cost. Path cost is the sum of all action costs along a path. An abstract state is an equivalence class of real-world states. An abstract \n",
        "action is an equivalence class of combinations of real-world actions. Generalized tree search enumerates in some order all possible paths from initial state- strategy used to choose leaf node for \n",
        "expansion determines the search process. Failure to detect repeated states can turn linear problem into exponential one. Graph search VS Tree Search: graph search checks to see if node has been \n",
        "visited before adding to search queue. Unnformed search is when all non-goal nodes in frontier look equally good, vs in informed, some can be ranked above others. In BFS, node inserted into queue \n",
        "only after testing to see if it is a goal state. \"\"\"\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 plan ahead, considering sequence of actions that form path to goal state\",    \n",
        "\"planning agents\": \"agents that use factored or structured representations of states\",\n",
        "\"solution\": \"sequence of actions (path) that reaches the goal\",\n",
        "\"open-loop\": \"ignoring the percepts breaks the loop between agent & environment; simply execute actions\",\n",
        "\"closed-loop\": \"monitors percepts in case model incorrect or environment is nondeterministic\",\n",
        "\"state space\": \"set of possible states that the environment can be in\",\n",
        "\"applicable\": \"an action that can be executed on a state\",\n",
        "\"transition model\": \"describes what each actions does; returns state from doing action on a state\",\n",
        "\"action cost function\": \"ACTION-COST(s, a, s') is cost of applying action a in state s to reach state s'\",\n",
        "\"optimal solution\": \"has the lowest path cost among all solutions\",\n",
        "\"graph\": \"way to represent state space; vertices are states and directed edges are actions\",\n",
        "\"search tree\": \"way of representing paths a search algorithm has explored. Initial state is root, and leaves are successor states\",\n",
        "\"abstraction\": \"process of removing detail from a representation\",\n",
        "\"standardized problem\": \"illustrates various problem solving methods; given concise, exact description; can use to measure algorithmic performance\",\n",
        "\"real-world problem\": \"solutions people actually use, formulation is idiosyncratic, not standardized\",\n",
        "\"grid world problem\": \"two-dimensional rectangular array of square cells in which agents can move from cell to cell\",\n",
        "\"egocentric actions\": \"actions defined relative to the viewpoint of the agent vs absolute actions\",\n",
        "\"sokoban puzzle\": \"agents goal is to push a number of boxes, scattered on grid, to designated storage locations\",\n",
        "\"sliding-tile puzzle\": \"number of tiles arranged in grid with one or more blank spaces to tiles can slide around (8-puzzle example)\",\n",
        "\"touring problem\": \"describes set of locations that must be visited, rather than a single goal destination\",\n",
        "\"traveling salesperson problem (TSP)\": \"touring problem in which every city on a map must be visited\",\n",
        "\"VLSI layout problem\": \"requires positioning millions of components and connections on chip to minimize area, circuit delays, etc..\",\n",
        "\"robot navigation\": \"generalization of route-solving problem, however robot can roam around creating its own paths\",\n",
        "\"automatic assembly sequencing\": \"of complex objects; find a feasible assembly sequence and then work to optimize the process (amino acids->proteins)\",\n",
        "\"search algorithm\": \"takes a search problem as input and returns a sollution, or indication of failure\",\n",
        "\"node\": \"in search tree, corresponds to state in state space, edges correspond to actions; root node = initial state\",\n",
        "\"reached\": \"any state that has had a node generated for it\",\n",
        "\"frontier\": \"separates two regions of the state-space graph: interior region where every state has been expanded vs exterior region\",\n",
        "\"best-first search\": \"choose a node n with minimum value of some evaluation function f(n)\",\n",
        "\"priority queue\": \"first pops the node with minimum cost according to evaluation function, f; used in best first search\",\n",
        "\"FIFO queue\": \"first-in-first-out queue first pops node that was added to queue first; used in BFS\",\n",
        "\"LIFO queue\": \"last-in-first-out queue (stack) pops first the most recently added node; used in DFS\",\n",
        "\"graph search\": \"a search algorithm that checks for redundant paths, else tree-like search\",\n",
        "\"systematic\": \"search algorithm must explore infinite state space by ensuring it can eventaually reach any state connected to initial\",\n",
        "\"depth\": \"d or the number of actions in an optimal solution\",\n",
        "\"m\": \"maximum number of actions in any path/maximum length of any path (potentially infinity)\",\n",
        "\"branching factor\": \"b or the number of successors of a node that must be considered\",\n",
        "\"breadth-first search\": \"root node expanded first, all successors of root expanded, then their successors, etc- FIFO frontier\",\n",
        "\"early goal test\": \"checking whether a node is solution as soon as it is generated vs late goal test (used in best first)\",\n",
        "\"uniform-cost search\": \"best-first search where the evaluation function is the cost of the path from root to current node; complete & cost-optimal\",\n",
        "\"depth-first search\": \"always expands the deepest node in the frontier first- LIFO frontier\",\n",
        "\"backtracking search\": \"only one successor generated at a time rather than all successors; generated by modifying current state rather than new memory\",\n",
        "\"depth-limited search\": \"version of DFS in which depth limit is supplied and treat all nodes at this limit as if no successors\",\n",
        "\"diameter\": \"number of steps necessary to travel from any one state to another state\",\n",
        "\"iterative deepening search\": \"tries all values of l (0, 1, 2, etc...) until either a solution is found or DLS returns failure\",\n",
        "\"bidirectional search\": \"algorithm that simultaneously searches forward from initial state and backward from goal state, solution when two frontiers collide\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d2ed9e06-5a83-447b-aff6-373e2a86949f"
      },
      "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": 34,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem solving agents use atomic representations. Four phase problem solving process: (1) goal formulation\n(2) problem formulation (3) search (4) execution. In any fully observable, deterministic, known environment, the solution to\nany problem is a fixed sequence of actions. Search problem defined by (1) state space (2) initial state (3) goal states (4) actions\n(5) transition model (6) action cost function. Choice of good abstraction involves removing as much detail as possible while retaining\nvalidity and ensuring abstract actions are easy to carry out. Grid world example: a vacuum environment with n cells has n*2^n states. \nExample of infinite state spaces: sequence of square root, floor, and factorial operations can reach any desired positive integer\n\n## AIMA Chapter 3.2 Example Problems\nStandardized Problems\n\n## AIMA Chapter 3.3 Search Algorithms\nState space describes possibly infinite set of states in world and actions that allow transitions from one state to another,\nwhile search tree describes paths between these states, reaching towards the goal. Best first search algorithm: on each iteration choose a node\non the frontier with minimum f(n) value, return if goal, else apply EXPAND to generate child nodes. Each child node added to frontier if not yet \nreached or reached with path with lower cost than before. Returns either failure or node that represents path to goal. Even if state space is finite,\nthe complete search tree is infinite because no limit how much traverse a loop/cycle/redundant path. Can check for cycles during a search algorith, by \nfollowing up chain of parent pointers to check if state has been seen before (no need for additional memory). Evaluate an algorithm by (1) completeness\n(2) cost optimality (3) time complexity (4) space complexity\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search algorithm is given no clue about how close a state is to the goal. For BFS, FIFO queue faster than a priority queue and gives\ncorrect order of nodes; reached can be set of states. BFS is cost optimal for problems where all actions have the same cost. Both space and time compexity are O(b^d).\nUniform cost search spreads out in waves of uniform path cost. Worst case time and space complexity is $O(b^{1+frac{C*, e}})$. UCS can explore large trees of actions with low\ncosts before exploring paths with high-cost and maybe useful action. Depth first search proceeds to deepest level of tree, then backs up to next deepest node that still has\nunexpanded successors. Not cost optimal. For infinite state spaces, DFS can get stuck going down infinite path even if no cycles, thus incomplete. Memory is much smaller in DFS- O(bm)\nBacktracking has O(m) memory requirement. Depth limited search has time complexity of O(b^l) and space O(bl). IDS has memory req of O(bd) if solution, else O(bm) on finite state space. \nTime complexity O(b^d) with solution, else O(b^m). In bidirectional search, if cost of optimal path is C*, no node with cost > C*/2 is expanded\n\n## Module 3 Lecture Notes\nIf fully observable, deterministic, known environment, solution is always fixed sequence of actions. Else if partially observable or nondeterministic,\nsolution must recommend different future actions depending on what percepts received (branching strategy). Search problem needs states, initial state, actions, transition model, path cost, \nand goal. Uniform action cost means all actions are equal cost. Path cost is the sum of all action costs along a path. An abstract state is an equivalence class of real-world states. An abstract \naction is an equivalence class of combinations of real-world actions. Generalized tree search enumerates in some order all possible paths from initial state- strategy used to choose leaf node for \nexpansion determines the search process. Failure to detect repeated states can turn linear problem into exponential one. Graph search VS Tree Search: graph search checks to see if node has been \nvisited before adding to search queue. Unnformed search is when all non-goal nodes in frontier look equally good, vs in informed, some can be ranked above others. In BFS, node inserted into queue \nonly after testing to see if it is a goal state. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that plan ahead, considering sequence of actions that form path to goal state\n* **Planning agents** - agents that use factored or structured representations of states\n* **Solution** - sequence of actions (path) that reaches the goal\n* **Open-loop** - ignoring the percepts breaks the loop between agent & environment; simply execute actions\n* **Closed-loop** - monitors percepts in case model incorrect or environment is nondeterministic\n* **State space** - set of possible states that the environment can be in\n* **Applicable** - an action that can be executed on a state\n* **Transition model** - describes what each actions does; returns state from doing action on a state\n* **Action cost function** - ACTION-COST(s, a, s') is cost of applying action a in state s to reach state s'\n* **Optimal solution** - has the lowest path cost among all solutions\n* **Graph** - way to represent state space; vertices are states and directed edges are actions\n* **Search tree** - way of representing paths a search algorithm has explored. Initial state is root, and leaves are successor states\n* **Abstraction** - process of removing detail from a representation\n* **Standardized problem** - illustrates various problem solving methods; given concise, exact description; can use to measure algorithmic performance\n* **Real-world problem** - solutions people actually use, formulation is idiosyncratic, not standardized\n* **Grid world problem** - two-dimensional rectangular array of square cells in which agents can move from cell to cell\n* **Egocentric actions** - actions defined relative to the viewpoint of the agent vs absolute actions\n* **Sokoban puzzle** - agents goal is to push a number of boxes, scattered on grid, to designated storage locations\n* **Sliding-tile puzzle** - number of tiles arranged in grid with one or more blank spaces to tiles can slide around (8-puzzle example)\n* **Touring problem** - describes set of locations that must be visited, rather than a single goal destination\n* **Traveling salesperson problem (tsp)** - touring problem in which every city on a map must be visited\n* **Vlsi layout problem** - requires positioning millions of components and connections on chip to minimize area, circuit delays, etc..\n* **Robot navigation** - generalization of route-solving problem, however robot can roam around creating its own paths\n* **Automatic assembly sequencing** - of complex objects; find a feasible assembly sequence and then work to optimize the process (amino acids->proteins)\n* **Search algorithm** - takes a search problem as input and returns a sollution, or indication of failure\n* **Node** - in search tree, corresponds to state in state space, edges correspond to actions; root node = initial state\n* **Reached** - any state that has had a node generated for it\n* **Frontier** - separates two regions of the state-space graph: interior region where every state has been expanded vs exterior region\n* **Best-first search** - choose a node n with minimum value of some evaluation function f(n)\n* **Priority queue** - first pops the node with minimum cost according to evaluation function, f; used in best first search\n* **Fifo queue** - first-in-first-out queue first pops node that was added to queue first; used in BFS\n* **Lifo queue** - last-in-first-out queue (stack) pops first the most recently added node; used in DFS\n* **Graph search** - a search algorithm that checks for redundant paths, else tree-like search\n* **Systematic** - search algorithm must explore infinite state space by ensuring it can eventaually reach any state connected to initial\n* **Depth** - d or the number of actions in an optimal solution\n* **M** - maximum number of actions in any path/maximum length of any path (potentially infinity)\n* **Branching factor** - b or the number of successors of a node that must be considered\n* **Breadth-first search** - root node expanded first, all successors of root expanded, then their successors, etc- FIFO frontier\n* **Early goal test** - checking whether a node is solution as soon as it is generated vs late goal test (used in best first)\n* **Uniform-cost search** - best-first search where the evaluation function is the cost of the path from root to current node; complete & cost-optimal\n* **Depth-first search** - always expands the deepest node in the frontier first- LIFO frontier\n* **Backtracking search** - only one successor generated at a time rather than all successors; generated by modifying current state rather than new memory\n* **Depth-limited search** - version of DFS in which depth limit is supplied and treat all nodes at this limit as if no successors\n* **Diameter** - number of steps necessary to travel from any one state to another state\n* **Iterative deepening search** - tries all values of l (0, 1, 2, etc...) until either a solution is found or DLS returns failure\n* **Bidirectional search** - algorithm that simultaneously searches forward from initial state and backward from goal state, solution when two frontiers collide\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 = \"\"\"Every consistent heuristic is admissible, but not vice versa. With consistent heuristic,\n",
        "A* is cost-optimal. With UCS, contours were of g-cost, not g + h, circular contours spreading out equally in all \n",
        "directions vs A* good heuristic, g + h bands will stretch towards a goal state/narrowly focused around optimal path.\n",
        "A* is complete, cost-optimal, optimally efficient among all such algorithms, but number of nodes expanded can be \n",
        "exponential in length of solution. Weighted A* search finds slightly costlier solution, but faster search time. Fewer \n",
        "states are explored, but if optimal path strays outside of weighted search's contour, optimal path not found. Can use the \n",
        "separation properly and prohibition of U-turn actions to eliminate the reached table. In iterative deepening A* search, if \n",
        "optimal solution has cost C*, there can be no more than C* iterations. When SMA* drops the worst leaf node, this value is \n",
        "backed up to its parent- so when all other paths shown to look worse than forgotten path, this subtree is regenerated. SMA* \n",
        "is complete if any reachable solution (depth of shallowest goal is < memory size); optimal if optimal solution is reachable. \n",
        "SMA* sometimes switches back and forth among many candidate paths, only small set can fit in memory (thrashing).\n",
        "Bidirectional best-first search with f(n) = g(n) + h(n) is not necessarily optimal. \"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"Well designed heuristic would have a value of b* close to 1, allowing large problems to be solved at reasonable \n",
        "computational cost. A* pruning with heuristic h reduces the effective depth by constant k_h, so search cost is O(b^(d-k_h)). \n",
        "Generally better to use a heuristic function with higher values. Any optimal solution in original problem is solution to relaxed problem, but\n",
        "relaxed may have better solutions if added edges provide shortcuts. Cost of an optimal solutin to relaxed problem is admissible heuristic for original \n",
        "problem. Admissible heuristics can be derived from solution cost of a subproblem of a given problem. Pattern database constructed by searching back from \n",
        "the goal and recording the cost of each new pattern. Given stored C* tables, can create heuristic: minimum over all landmarks of cost of getting from node\n",
        "to landmark then to goal. A path in the metalevel state space such that each state on path is an object-level search tree. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Uniform cost search used for traversing/searching weighted tree. UCS expands node with the lowest path cost, so frontier is PQ ordered by g(n). \n",
        "Tests if goal state when it is selected for expansion, not when added to frontier. Cost contours vs smooth contours in BFS. Best-first search selects node for expansion \n",
        "based on f(n) that includes some h(n). Greedy best first search ignores g(n), just uses f(n) = h(n). A* algorithm uses f(n) = g(n) + h(n). A heuristic h(n) is admissible \n",
        "if it never overestimates the cost to reach the goal. THEOREM: if h(n) is admissible, A* using Tree search is optimal. If h2 dominates h1, h2 is more accurate than h1 and \n",
        "is better for search. Inadmissble heuristics break optimality by pushing good plans too far back on frontier (never expanded) vs admissible (optimistic) heuristics slow down \n",
        "bad plans but never outweight true costs. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"one that uses domain-specific hints about the location of goals\",\n",
        "\"heuristic function\": \"estimated cost of the cheapest path from the state at node n to a goal state\",\n",
        "\"greedy best-first search\": \"form of best-first search that expands first the node with the lowest h(n) value\",\n",
        "\"A* search\": \"best-first search that uses the evaluation function f(n)=g(n)+h(n), where g(n) is path cost from initial to n\",\n",
        "\"admissible heuristic\": \"one that never overestimates the cost to a goal (optimisitic)\",\n",
        "\"consistency\": \"heuristic h(n) consistent if for a node n and successor n' by action a, then h(n)<=c(n,a,n')+h(n')\",\n",
        "\"triange inequality\": \"side of a triangle cannot be longer than the sum of the other two sides\",\n",
        "\"contours\": \"nodes inside a given contour have f = g + h costs <= the contour value\",\n",
        "\"monotonic\": \"the path cost always increases as you go along a path, because action costs are always positive\",\n",
        "\"surely expanded nodes\": \"A* expands all nodes that can be reached from initial state on a path where node on path has f(n)<C*\",\n",
        "\"pruning\": \"eliminating possibilities from consideration without having to examine them\",\n",
        "\"satisficing solutions\": \"willing to accept solutions that are suboptimal, but good enough\",\n",
        "\"weighted A* search\": \"weight the heuristic value more heavily; f(n) = g(n) + W * h(n)\",\n",
        "\"bounded suboptimal search\": \"look for a solution that is guaranteed to be within constant factor W of optimal cost (weighted A*)\",\n",
        "\"bounded-cost search\": \"look for a solution whose cost is less than some constant C\",\n",
        "\"unbounded-cost search\": 'accept a solution of any cost as long as we can find it quickly',\n",
        "\"speedy search\": \"type of unbounded cost search that uses heuristic as estimated # of actions to reach goal, regardless of costs\",\n",
        "\"reference counts\": \"number of times state has been reached; remove it from reached table when no more ways to reach it\",\n",
        "\"beam search\": \"limits size of frontier, keep only k nodes with best f-scores; executes fast even though incomplete & suboptimal\",\n",
        "\"iterative-deepening A* search\": \"gives benefits of A* without requirements to keep all reached states in memory, cutoff is f-cost\",\n",
        "\"recursive best-first search\": \"resembles recursive DFS, but uses f_limit to keep track of f-value of best alternative path from ancestor, can unwind back\",\n",
        "\"SMA* (simplified memory-bounded (MA*))\": \"expands like A*, expanding best leaf until full memory. Always drops worst leaf node (highest f-value)\",\n",
        "\"bidirectional heuristic search\": \"uses evaluation function f2(n) = max(2g(n), g)n) + h(n))- does not expand node with g(n) > C*/2; complete/optimal\",\n",
        "\"front-to-end search\": \"hF heuristic estimates distance to goal & hB estimates distance to the start\",\n",
        "\"front-to-front search\": \"attempts to estimate the distance to the other frontier\",\n",
        "\"city-block or Manhattan distance\": \"sum of the horizontal and vertical distances\",\n",
        "\"effective branching factor b*\": \"branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\",\n",
        "\"dominates\": \"for any node n, h2(n)>=h1(n), so h2 dominates h1; A* with h2 will never expand more nodes than with h1\",\n",
        "\"relaxed problem\": \"problem with fewer restrictions on the actions; state space graph is supergraph of original state space graph\",\n",
        "\"pattern databases\": \"store the exact solution costs for every possible subproblem instances\",\n",
        "\"disjoin pattern databases\": \"record cost of solving elements in subproblem ONLY, the sum of these costs is lower bound on entire cost\",\n",
        "\"precomputation\": \"of optimal path costs; time-consuming, but only done once, and then amortized over billions of requests\",\n",
        "\"landmark points\": \"for each landmark L and each vertex v in the graph, compute and store C*(v, L) and C*(L, v)\",\n",
        "\"differential heuristic\": \"hDH(n) = max (l in landmarks) |C*(n, L) - C*(goal, L)|\",\n",
        "\"metalevel state space\": \"each state in metalevel state space captures internal state of a program searching in ordinary state space\",\n",
        "\"metalevel learning\": \"such an algorithm can learn from missteps experiences to avoid exploring unpromising subtrees\",\n",
        "\"features\": \"of a state that are relevant to predicting state's heuristic value; h(n) = c1x1(n) + c2x2(n)\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 35,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7b0e3dc8-1b7b-49d7-97cb-ce67835c5c18"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nEvery consistent heuristic is admissible, but not vice versa. With consistent heuristic,\nA* is cost-optimal. With UCS, contours were of g-cost, not g + h, circular contours spreading out equally in all \ndirections vs A* good heuristic, g + h bands will stretch towards a goal state/narrowly focused around optimal path.\nA* is complete, cost-optimal, optimally efficient among all such algorithms, but number of nodes expanded can be \nexponential in length of solution. Weighted A* search finds slightly costlier solution, but faster search time. Fewer \nstates are explored, but if optimal path strays outside of weighted search's contour, optimal path not found. Can use the \nseparation properly and prohibition of U-turn actions to eliminate the reached table. In iterative deepening A* search, if \noptimal solution has cost C*, there can be no more than C* iterations. When SMA* drops the worst leaf node, this value is \nbacked up to its parent- so when all other paths shown to look worse than forgotten path, this subtree is regenerated. SMA* \nis complete if any reachable solution (depth of shallowest goal is < memory size); optimal if optimal solution is reachable. \nSMA* sometimes switches back and forth among many candidate paths, only small set can fit in memory (thrashing).\nBidirectional best-first search with f(n) = g(n) + h(n) is not necessarily optimal. \n\n## AIMA Chapter 3.6 Heuristic Functions\nWell designed heuristic would have a value of b* close to 1, allowing large problems to be solved at reasonable \ncomputational cost. A* pruning with heuristic h reduces the effective depth by constant k_h, so search cost is O(b^(d-k_h)). \nGenerally better to use a heuristic function with higher values. Any optimal solution in original problem is solution to relaxed problem, but\nrelaxed may have better solutions if added edges provide shortcuts. Cost of an optimal solutin to relaxed problem is admissible heuristic for original \nproblem. Admissible heuristics can be derived from solution cost of a subproblem of a given problem. Pattern database constructed by searching back from \nthe goal and recording the cost of each new pattern. Given stored C* tables, can create heuristic: minimum over all landmarks of cost of getting from node\nto landmark then to goal. A path in the metalevel state space such that each state on path is an object-level search tree. \n\n## Module 4 Lecture Notes\nUniform cost search used for traversing/searching weighted tree. UCS expands node with the lowest path cost, so frontier is PQ ordered by g(n). \nTests if goal state when it is selected for expansion, not when added to frontier. Cost contours vs smooth contours in BFS. Best-first search selects node for expansion \nbased on f(n) that includes some h(n). Greedy best first search ignores g(n), just uses f(n) = h(n). A* algorithm uses f(n) = g(n) + h(n). A heuristic h(n) is admissible \nif it never overestimates the cost to reach the goal. THEOREM: if h(n) is admissible, A* using Tree search is optimal. If h2 dominates h1, h2 is more accurate than h1 and \nis better for search. Inadmissble heuristics break optimality by pushing good plans too far back on frontier (never expanded) vs admissible (optimistic) heuristics slow down \nbad plans but never outweight true costs. \n\n## Module 4 Definitions\n* **Informed search** - one that uses domain-specific hints about the location of goals\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Greedy best-first search** - form of best-first search that expands first the node with the lowest h(n) value\n* **A* search** - best-first search that uses the evaluation function f(n)=g(n)+h(n), where g(n) is path cost from initial to n\n* **Admissible heuristic** - one that never overestimates the cost to a goal (optimisitic)\n* **Consistency** - heuristic h(n) consistent if for a node n and successor n' by action a, then h(n)<=c(n,a,n')+h(n')\n* **Triange inequality** - side of a triangle cannot be longer than the sum of the other two sides\n* **Contours** - nodes inside a given contour have f = g + h costs <= the contour value\n* **Monotonic** - the path cost always increases as you go along a path, because action costs are always positive\n* **Surely expanded nodes** - A* expands all nodes that can be reached from initial state on a path where node on path has f(n)<C*\n* **Pruning** - eliminating possibilities from consideration without having to examine them\n* **Satisficing solutions** - willing to accept solutions that are suboptimal, but good enough\n* **Weighted a* search** - weight the heuristic value more heavily; f(n) = g(n) + W * h(n)\n* **Bounded suboptimal search** - look for a solution that is guaranteed to be within constant factor W of optimal cost (weighted A*)\n* **Bounded-cost search** - look for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accept a solution of any cost as long as we can find it quickly\n* **Speedy search** - type of unbounded cost search that uses heuristic as estimated # of actions to reach goal, regardless of costs\n* **Reference counts** - number of times state has been reached; remove it from reached table when no more ways to reach it\n* **Beam search** - limits size of frontier, keep only k nodes with best f-scores; executes fast even though incomplete & suboptimal\n* **Iterative-deepening a* search** - gives benefits of A* without requirements to keep all reached states in memory, cutoff is f-cost\n* **Recursive best-first search** - resembles recursive DFS, but uses f_limit to keep track of f-value of best alternative path from ancestor, can unwind back\n* **Sma* (simplified memory-bounded (ma*))** - expands like A*, expanding best leaf until full memory. Always drops worst leaf node (highest f-value)\n* **Bidirectional heuristic search** - uses evaluation function f2(n) = max(2g(n), g)n) + h(n))- does not expand node with g(n) > C*/2; complete/optimal\n* **Front-to-end search** - hF heuristic estimates distance to goal & hB estimates distance to the start\n* **Front-to-front search** - attempts to estimate the distance to the other frontier\n* **City-block or manhattan distance** - sum of the horizontal and vertical distances\n* **Effective branching factor b*** - branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\n* **Dominates** - for any node n, h2(n)>=h1(n), so h2 dominates h1; A* with h2 will never expand more nodes than with h1\n* **Relaxed problem** - problem with fewer restrictions on the actions; state space graph is supergraph of original state space graph\n* **Pattern databases** - store the exact solution costs for every possible subproblem instances\n* **Disjoin pattern databases** - record cost of solving elements in subproblem ONLY, the sum of these costs is lower bound on entire cost\n* **Precomputation** - of optimal path costs; time-consuming, but only done once, and then amortized over billions of requests\n* **Landmark points** - for each landmark L and each vertex v in the graph, compute and store C*(v, L) and C*(L, v)\n* **Differential heuristic** - hDH(n) = max (l in landmarks) |C*(n, L) - C*(goal, L)|\n* **Metalevel state space** - each state in metalevel state space captures internal state of a program searching in ordinary state space\n* **Metalevel learning** - such an algorithm can learn from missteps experiences to avoid exploring unpromising subtrees\n* **Features** - of a state that are relevant to predicting state's heuristic value; h(n) = c1x1(n) + c2x2(n)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Two-Player Zero-Sum Games; MAX and MIN. Game tree may be infinite if the state space is unbounded or if \n",
        "the rules of the game allow for infinitely repeating positions.\"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\"If MIN does not play optimally, MAX will do at least as well as against an optimal player. Minimax search \n",
        "algorithm is recursive algorithm that proceeds all the way down to leaves of tree than backs up minimax values through tree \n",
        "as recursion unwinds. Time complexity is O(b^m), space complexity is O(bm) or O(m). The backed-up value of a node n is the utility \n",
        "vector of the successor state with the highest value for the player choosing at n. Players must balance the immediate advantage of \n",
        "breaking an alliance against long-term disadvantage of being perceived as untrustworthy. Consider a node n in tree such that player has \n",
        "a choice of moving to n. If player has a better choice either at same level or any point higher up in tree, player will never move to n.\n",
        "If done perfectly, alpha-beta only needs to examine O(b^m/2) notes to pick best move. Adding dynamic move-ordering schemas brings us quite \n",
        "close to the theoretical limit. \"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\"A heuristic evaluation function EVAL(s, p) returns estimate of expected utility of state s to player p. Evaluation functions work \n",
        "by calculating various features of state, which together define categories or equivalence classes of states; Any given categoy will contain \n",
        "some states that lead to wins, draws, or losses. Adding up values of features involves assumption that contribution of each feature is independent \n",
        "of value of the other features, so programs use nonlinear comibinations of features. Probabilistic cut algorithm is forward-pruning version of alpha-beta \n",
        "search that uses stats from prior experience to lessen chance best move is pruned. Many game-playing programs use table lookup rather than search for opening \n",
        "and ending of games.\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\"Since expectiminimax considering all possible dice-roll sequences, takes O(b^mn^m), where n is number of distinct rolls. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Decision theory deals with choosing among actions based on the desirability of their immediate outcomes (episodic). If an agent \n",
        "acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance, \n",
        "averaged over all the possible environments.\"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\"Axioms of utility theory: (1) orderability (2) transitivity (3) continuity\n",
        "(4) substitability (5) monotonicity (6) decomposability\"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\"Utility is not directly proportional to monetary value. Utility of money was almost exactly proportional to the \n",
        "logarithm of the amount- most likely that people have a utility function concave for positive wealth. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"competitive environments\" : \"two or more agents have conflicting goals -> adverserial search problems\",\n",
        "\"economy\": \"very large number of agents, consider them aggregated, predict demand, etc without predicting individual agent action\",\n",
        "\"pruning\": \"makes search more efficient by ignoring portions of search tree that make no difference to the optimal move\",\n",
        "\"perfect information, zero-sum games\": \"fully observable, zero-sum\",\n",
        "\"utility function\": \"UTILITY(s, p) is final numeric value to player p when game ends in terminal state s\",\n",
        "\"game tree\": \"search tree that follows every sequence of moves all the way to a terminal state\",\n",
        "\"minimax search\": \"a general algorithm for games with multiple outcome scores\",\n",
        "\"minimax value\": \"utility (for MAX) of being in that state, assuming both players play optimally from there to end of game\",\n",
        "\"alpha\": \"value of the best (highest) choice we have so far at any choice point along path for MAX; at least\",\n",
        "\"beta\": \"value of the best/lowest choice we have so far at any choice point along path for MIN; at most\",\n",
        "\"killer moves\": \"the best move; to try them first is called killer move heuristic\",\n",
        "\"transpositions\": \"different permutations of the move sequence that end up in the same position\",\n",
        "\"transposition table\": \"Caches the heuristic values of states\",\n",
        "\"type A strategy\": \"considers all possible moves to certain depth; uses heuristic EF to estimate utility at those depths; wide but shallow\",\n",
        "\"type B strategy\": \"ignores moves that look bad, follows promising lines as far as possible, deep but narrow\",\n",
        "\"cutoff test\": \"returns true for terminal states, free to decide when to cut off search based on depth and state properties\",\n",
        "\"expected value\": \"a single value that estimates the proportion of states with each outcome; can be determined for each catogory\",\n",
        "\"material value\": \"such feature values are simply added up to obtain the evaluation of a position\",\n",
        "\"weighted linear function\": \"EVAL(s) = w1f1(S) + w2f2(s) + ... + wnfn(s)\",\n",
        "\"quiescent\": \"position in which no pending move would wildly swing the evaluation; IS_CUTOFF returns false for nonquiescent positions\",\n",
        "\"quiescence search\": \"search continues until quiescent position reached; restricted to capture moves that will resolve uncertainties in position\",\n",
        "\"horizon effect\": \"when program is facing an opponent's move that causes serious damage/unavoidable, can be temporarily avoided by delaying\",\n",
        "\"singular extensions\": \"moves that are clearly better than all others in given position even when search normally be cutoff at that point\",\n",
        "\"forward pruning\": \"prunes moves that appear to be poor moves, but might be good ones; saves computation time at risk of errors\",\n",
        "\"beam search\": \"on each ply, consider only beam of n best moves, rather than all possible moves\",\n",
        "\"late move reduction\": \"works under assumption that move ordering done well, so later moves in list are less likely to be good moves\",\n",
        "\"policy\": \"mapping from every possible state to the best move in that state; computer can play by looking up right move\",\n",
        "\"retrograde\": \"table is constructed by retrograde minimax search\",\n",
        "\"stochastic games\": \"bring us closer to unpredictability of real life by including a random element\",\n",
        "\"chance nodes\": \"in addition to MAX and MIN nodes; branche from chance node labeled with outcome and its probability\",\n",
        "\"expected value\": \"of a position: the average over all possible outcomes of the chance nodes\",\n",
        "\"expectiminimax value\": \"for games with chance nodes, a generalization of the minimax value for deterministic games\",\n",
        "\"utility function\": \"U(s) assigns a single number to express the desirability of a state\",\n",
        "\"expected utility\": \"of an action EU(a), is just average utility of outcomes weighted by probability that outcome occurs\",\n",
        "\"maximum expected utility (MEU)\": \"a rational agent should choose action that maximizes agent's expected utility\",\n",
        "\"lottery\" : \"set of outcomes for each action- each action is a ticket\",\n",
        "\"orderability\": \"given any two lotteries, rational agent must either prefor one or else rate them as equally preferable\",\n",
        "\"transitivity\": \"given any three lotteries, if agent prefers A to B and B to C, must prefer A to C\",\n",
        "\"continuity\": \"if B between A and C, prob.p s.t. indifferent between B 100% vs A with p & C with 1-p\",\n",
        "\"substituability\": \"if agent indifferent between A/B, agent is indifferent between complex lotteries that are same except for B sub with A\",\n",
        "\"monotonicity\": \"if two lotteries have same outcomes, A&B, if agent prefers A to B, must prefer higher A probability lottery\",\n",
        "\"decomposability\": \"compound lotteries can be reduced to simpler ones using the laws of probability\",\n",
        "\"existence of utility function\": \"if agent's preferences obey axiomos, function U such that U(A) > U(B) if A > B\",\n",
        "\"expected utility of a lottery\": \"utility of lottery is sum of probability of each outcome * utility of that outcome\",\n",
        "\"value or ordinal utility function\": \"in a deterministic environment, agent needs only a preference ranking on states\",\n",
        "\"preference elicitation\": \"presenting choices to human and using observed preferences to pin down underlying utility function\",\n",
        "\"value of a statistical life\": \"used to determine costs and benefits of regulations and interventions\",\n",
        "\"micromort\": \"a one in a million chance of death\",\n",
        "\"QALY\": \"quality-adjusted life year\",\n",
        "\"monotonic preference\": \"agent exhibits this for more money\",\n",
        "\"risk-averse\": \"U(L) < U(Seml(L)); prefer sure thing with payoff less than expected monetary value of a gamble\",\n",
        "\"certainty equivalent\": \"the value an agnet will accept in lieu of a lottery\",\n",
        "\"insurance premium\": \"the difference between the EMV of a lottery and its certainty equivalent\",\n",
        "\"risk-neutral\": \"an agent that has a linear curve for wealth\",\n",
        "\"unbiased\": \"expected value of the error between estimate and its expected value is zero\",\n",
        "\"optimizer's curse\": \"tendency for the estimated expected utility of the best choice to be too high\",\n",
        "\"normative theory\": \"describes how a rational agent should act\",\n",
        "\"descriptive theory\": \"describes how actual agents really do act\",\n",
        "\"certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"ambiguity aversion\": \"people elect the known probabability rather than the unknown unknowns\",\n",
        "\"framing effect\": \"exact wording of a decision problem can have a big impact on the agent's choices\",\n",
        "\"anchoring effect\": \"people feel more comfortable making relative utility judgements rather than absolute ones\",\n",
        "\"evolutionary psychology\": \"our brain's decision-making mechanisms did not evolve to solve word problems with probabilites/decimals\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "93fb01ad-8034-4ab8-9e98-dc1b93a173d4"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nTwo-Player Zero-Sum Games; MAX and MIN. Game tree may be infinite if the state space is unbounded or if \nthe rules of the game allow for infinitely repeating positions.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nIf MIN does not play optimally, MAX will do at least as well as against an optimal player. Minimax search \nalgorithm is recursive algorithm that proceeds all the way down to leaves of tree than backs up minimax values through tree \nas recursion unwinds. Time complexity is O(b^m), space complexity is O(bm) or O(m). The backed-up value of a node n is the utility \nvector of the successor state with the highest value for the player choosing at n. Players must balance the immediate advantage of \nbreaking an alliance against long-term disadvantage of being perceived as untrustworthy. Consider a node n in tree such that player has \na choice of moving to n. If player has a better choice either at same level or any point higher up in tree, player will never move to n.\nIf done perfectly, alpha-beta only needs to examine O(b^m/2) notes to pick best move. Adding dynamic move-ordering schemas brings us quite \nclose to the theoretical limit. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nA heuristic evaluation function EVAL(s, p) returns estimate of expected utility of state s to player p. Evaluation functions work \nby calculating various features of state, which together define categories or equivalence classes of states; Any given categoy will contain \nsome states that lead to wins, draws, or losses. Adding up values of features involves assumption that contribution of each feature is independent \nof value of the other features, so programs use nonlinear comibinations of features. Probabilistic cut algorithm is forward-pruning version of alpha-beta \nsearch that uses stats from prior experience to lessen chance best move is pruned. Many game-playing programs use table lookup rather than search for opening \nand ending of games.\n\n## AIMA Chapter 5.5 Stochastic Games\nSince expectiminimax considering all possible dice-roll sequences, takes O(b^mn^m), where n is number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory deals with choosing among actions based on the desirability of their immediate outcomes (episodic). If an agent \nacts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance, \naveraged over all the possible environments.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nAxioms of utility theory: (1) orderability (2) transitivity (3) continuity\n(4) substitability (5) monotonicity (6) decomposability\n\n## AIMA Chapter 16.3 Utility Functions\nUtility is not directly proportional to monetary value. Utility of money was almost exactly proportional to the \nlogarithm of the amount- most likely that people have a utility function concave for positive wealth. \n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Competitive environments** - two or more agents have conflicting goals -> adverserial search problems\n* **Economy** - very large number of agents, consider them aggregated, predict demand, etc without predicting individual agent action\n* **Pruning** - makes search more efficient by ignoring portions of search tree that make no difference to the optimal move\n* **Perfect information, zero-sum games** - fully observable, zero-sum\n* **Utility function** - U(s) assigns a single number to express the desirability of a state\n* **Game tree** - search tree that follows every sequence of moves all the way to a terminal state\n* **Minimax search** - a general algorithm for games with multiple outcome scores\n* **Minimax value** - utility (for MAX) of being in that state, assuming both players play optimally from there to end of game\n* **Alpha** - value of the best (highest) choice we have so far at any choice point along path for MAX; at least\n* **Beta** - value of the best/lowest choice we have so far at any choice point along path for MIN; at most\n* **Killer moves** - the best move; to try them first is called killer move heuristic\n* **Transpositions** - different permutations of the move sequence that end up in the same position\n* **Transposition table** - Caches the heuristic values of states\n* **Type a strategy** - considers all possible moves to certain depth; uses heuristic EF to estimate utility at those depths; wide but shallow\n* **Type b strategy** - ignores moves that look bad, follows promising lines as far as possible, deep but narrow\n* **Cutoff test** - returns true for terminal states, free to decide when to cut off search based on depth and state properties\n* **Expected value** - of a position: the average over all possible outcomes of the chance nodes\n* **Material value** - such feature values are simply added up to obtain the evaluation of a position\n* **Weighted linear function** - EVAL(s) = w1f1(S) + w2f2(s) + ... + wnfn(s)\n* **Quiescent** - position in which no pending move would wildly swing the evaluation; IS_CUTOFF returns false for nonquiescent positions\n* **Quiescence search** - search continues until quiescent position reached; restricted to capture moves that will resolve uncertainties in position\n* **Horizon effect** - when program is facing an opponent's move that causes serious damage/unavoidable, can be temporarily avoided by delaying\n* **Singular extensions** - moves that are clearly better than all others in given position even when search normally be cutoff at that point\n* **Forward pruning** - prunes moves that appear to be poor moves, but might be good ones; saves computation time at risk of errors\n* **Beam search** - on each ply, consider only beam of n best moves, rather than all possible moves\n* **Late move reduction** - works under assumption that move ordering done well, so later moves in list are less likely to be good moves\n* **Policy** - mapping from every possible state to the best move in that state; computer can play by looking up right move\n* **Retrograde** - table is constructed by retrograde minimax search\n* **Stochastic games** - bring us closer to unpredictability of real life by including a random element\n* **Chance nodes** - in addition to MAX and MIN nodes; branche from chance node labeled with outcome and its probability\n* **Expectiminimax value** - for games with chance nodes, a generalization of the minimax value for deterministic games\n* **Expected utility** - of an action EU(a), is just average utility of outcomes weighted by probability that outcome occurs\n* **Maximum expected utility (meu)** - a rational agent should choose action that maximizes agent's expected utility\n* **Lottery** - set of outcomes for each action- each action is a ticket\n* **Orderability** - given any two lotteries, rational agent must either prefor one or else rate them as equally preferable\n* **Transitivity** - given any three lotteries, if agent prefers A to B and B to C, must prefer A to C\n* **Continuity** - if B between A and C, prob.p s.t. indifferent between B 100% vs A with p & C with 1-p\n* **Substituability** - if agent indifferent between A/B, agent is indifferent between complex lotteries that are same except for B sub with A\n* **Monotonicity** - if two lotteries have same outcomes, A&B, if agent prefers A to B, must prefer higher A probability lottery\n* **Decomposability** - compound lotteries can be reduced to simpler ones using the laws of probability\n* **Existence of utility function** - if agent's preferences obey axiomos, function U such that U(A) > U(B) if A > B\n* **Expected utility of a lottery** - utility of lottery is sum of probability of each outcome * utility of that outcome\n* **Value or ordinal utility function** - in a deterministic environment, agent needs only a preference ranking on states\n* **Preference elicitation** - presenting choices to human and using observed preferences to pin down underlying utility function\n* **Value of a statistical life** - used to determine costs and benefits of regulations and interventions\n* **Micromort** - a one in a million chance of death\n* **Qaly** - quality-adjusted life year\n* **Monotonic preference** - agent exhibits this for more money\n* **Risk-averse** - U(L) < U(Seml(L)); prefer sure thing with payoff less than expected monetary value of a gamble\n* **Certainty equivalent** - the value an agnet will accept in lieu of a lottery\n* **Insurance premium** - the difference between the EMV of a lottery and its certainty equivalent\n* **Risk-neutral** - an agent that has a linear curve for wealth\n* **Unbiased** - expected value of the error between estimate and its expected value is zero\n* **Optimizer's curse** - tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - people elect the known probabability rather than the unknown unknowns\n* **Framing effect** - exact wording of a decision problem can have a big impact on the agent's choices\n* **Anchoring effect** - people feel more comfortable making relative utility judgements rather than absolute ones\n* **Evolutionary psychology** - our brain's decision-making mechanisms did not evolve to solve word problems with probabilites/decimals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "13c95146-1c04-4e1a-d701-2a8197836e53"
      },
      "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": 40,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n 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 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "19fb4602-e360-4504-bec4-302450b5bacd"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n 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": "3f2c11a8-603c-4aab-fcb8-bbf442f44a25"
      },
      "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": 43,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nIntelligence can be considered as an internal characterization of thought processes or reasoning, or external as behavior.\nFour possible combinations with human vs rational dimensions. Turing Test determines if a machine can think if a human interrogator, after\nposing questions, cannot tell if responses were human or computer. Needs (1) natural language processing (2) knowledge representation (3)\nautomated reasoning (4) machine learning. Total Turing Test requires interaction with object/people. Needs (1) computer vision (2) robotics.\nCan learn about human thought through (1) introspection (2) psych. experiments (3) brain imaging. Combining neuroimaging methods + ML techniques\ncan lead to reading minds/understanding human cognition. Thinking Rationally: syllogisms laws of thought govern the operation of mind: logic. \nLogic requires knowledge of world that is certain, with probability flling this gap. Acting Rationally: computer agents expected to operate by\nitself, perceive surroundings, persist over time, adapt to change, set goals. All skills needed for Turing test allow agent to act rationally. \nRational agent approach is more general and more adaptable to scientific development. AI focuses on study and construction of agents that do the \nright thing- standard model. However, always taking optimal action is not feasible. As we move into real word, it is not that easy to specify\nobjective completely and accurately. Example of value alignment problem: chess machine can act beyond confines to achieve winning, the sole goal. \nNeed to tell machine to pursue our objectives, but make it uncertain so machine will act more cautiously- provably beneficial to humans.\n\n## AIMA Chapter 27.1 The Limits of AI\nStrong AI has shifted to be called human-level AI or general AI, programs that can solve variety of tasks just like a human can. \nArgument from informality of behavior states that humans use informal guidelines far too complex to be captured by rules to be codified in a program. \nProbabilistic reasoning appropriate for open-ended domains. Need to study cognition->body->environment system as a whole. The argument from disability \nmakes the claim that a machine can never do X. Godel's axiomatic theorem states that for any axiomatic framework F that can do arithmetic, can construct\na Godel sentence G(F) such that (1) G(F) is sentence of F, but cannot be proved within F (2) if F is consistent, G(F) is true. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\nTuring notes that we never have any direct evidence about the mental state of other humans. Should instead have polite convention that \neveryone thinks. Chinese room is a system that takes input in form of Chinese sentences and generates Chinese responses, with no understanding by human, rule \nbook or paper of Chinese. Since doing the same thing a computer would, computers generate no understanding. Consciousness remains ill-defined. Behaving intelligently \nrequires awareness which differs from task to task. Tasks involving human interactino requires model of human subjective experience. \n\n## AIMA 2.1 Agents and Environments\nAn agent's choice of action at any given instant depends on built-in knowledge and percept sequence observed to date.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nHumans have desires and preferences, unlike machines, so success is measured in choosing actions that produce sequences \nof states that desirable from their POV, versus machines performance measured wrt to designer/users of machine. In general, should design \nperformance measures according to what should be achieved in environment, rather than how an agent should behave (ex: amount of dirt cleaned \nvs clean floor). Rationality at any given time depends on (1) performance measure (2) agent's prior knowledge of environment (3) actions agent \ncan perform (4) agent's percept sequence to date. Rationality (max. expected performance) not same as perfection (max. actual performance). \nAgent lacks autonomy if relies on prior knowledge of designer rather that its own percepts/learning. Incorporation of learning allows a single \nrational agent to be designed that can suceed in various environments.\n\n## AIMA 2.3 The Nature of Environments\nKinds of task environments (1) fully vs partially observable (2) single-agent vs multiagent (communication is a rational behavior)\n(3) deterministic vs nondeterministic (4) episodic vs sequential (5) static vs dynamic (6) discrete vs continuous (7) known vs unknown.\nHardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continous, unknown\n\n## AIMA 2.4 The Structure of Agents\nSimple reflex agents will work only if correct decision can be made on the basis of just the current precept (fully observable environment).\nInfinite loops are unavoidable for SRA in partially observable environments-> can randomize actions. Goal-based agents appear less efficient, but more flexible \nbecause knowledge that supports its decisions is represented explicitly and can be modified. Utility based agent is advantageous: (1) when there are conflicting \ngoals, utility function specifies appropriate tradeoff (2) when several goals that agent can aim for, utility provides a way such that success chance can be weighed \nagainst goal importance. Any type of agent can be built as a learning agent. Learning allows agents to operate in initially unknown environments and to become more \ncompetent that its initial knowledge alone. Improving model components of a model-based agent so that they conform better with reality is a good idea. Performance \nstandard distinguishes part of incoming percept as a reward or penalty which provides feedback on agent's behavior quality. \n\n## Module 1 Lecture Notes\n\n\n## Module 1 Definitions\n* **Rationality** - abstract formal definition of intelligence- doing the right thing\n* **Natural language processing** - communicate successfully in human language\n* **Knowledge representation** - store everything knows/hears\n* **Automated reasoning** - answer questions and draw conclusions based on existing knowledge\n* **Machine learning** - adapt to new situations, detect/extract/extrapolate patterns\n* **Introspection** - looking into our own individual thoughts\n* **Psychological experiments** - observing person's behaviors/actions\n* **Brain imaging** - observing brain in action\n* **Cognitive science:** - computer AI models + psychology experiements = theories of human mind\n* **Syllogisms** - patterns for arguments that result in correct conclusions from correct premises\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Rational agent** - agent that acts to achieve best (expected) outcome; does the right thing, given percept sequence & built-in knowledge\n* **Limited rationality** - acting appropriately when not enough time to do all necessary computations\n* **Weak ai** - machines could act as if they were intelligent\n* **Strong ai** - machines that act intelligent are actually consciously, not simulating, thinking\n* **Qualification problem** - difficult to capture every contingency of appropriate behavior in set of logical rules\n* **Embodied cognition** - cannot consider brain separately; cognition takes place within body within environment\n* **Biological naturalism** - mental states are high-level emergent features caused by low-level neuron physical processes\n* **Consciousness** - awareness of outside world, self, subjective experience of living\n* **Qualia** - intrinsic nature of experiences\n* **Percept** - content the agent's sensors are perceiving\n* **Percept sequence** - history of everything that agent has ever perceived\n* **Agent function** - maps any given percept sequence to an action\n* **Agent program** - agent function for an artificial agent implemented by this, running within physical system\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluates any given sequence of environment states; criterion for agent's behavior success\n* **Omniscience** - such an agent knows actual outcome of actions & acts accordingly, not realistic\n* **Information gathering** - doing actions in order to modify future percepts\n* **Autonomy** - such an agent should learn what it can to compensate for partial or incorrect prior knowledge\n* **Task environment** - the problems to which the rational agents are the solutions\n* **Peas** - Performance, Environment, Actuators, Sensors\n* **Fully observable** - agent's sensors give access to complete state of environment at each point in time\n* **Partially observable** - noisy & inaccurate sensors; parts of state missing from sensor data\n* **Unobservable** - if an agent has no sensors at all\n* **Competitive multiagent** - B trying to maximize performance measure minimizes A's performance measure\n* **Partially cooperative multiagent** - taking actions that maximize performance measure of all agents (ex: taxi collisions)\n* **Deterministic** - next state of environment fully determined by current state + action taken, else nondeterministic\n* **Stochastic** - if a model of the environment deals with probabilities, else if not quantified then nondeterminsitic\n* **Episodic** - next episode does not depend on actions taken in previous episodes\n* **Sequential** - current decision could affect all future decisions (chess and taxi driving)\n* **Dynamic** - if environment can change while an agent is deliberating, else static\n* **Known** - environment in which outcomes (outcome probabilities) for all actions are given, else unknown\n* **Agent architecture** - agent = architecture + program\n* **Simple reflex agent** - select actions on basis of current percept ignoring rest of percept history\n* **Condition-action rule** - ex: if car-in-front-is-braking then initiate-braking\n* **Internal state** - maintained by agent to handle partial observability and keep track of unobservable aspects of current state\n* **Transition model** - knowledge about how the world works\n* **Sensor model** - information about how the state of the world is reflected in agent's percepts\n* **Model-based agent** - use both transitional model and sensor model to keep track of state of the world\n* **Goal-based agent** - use goal information that describes desirable situations along with the model to achieve the goal\n* **Search and planning** - subfields of AI devoted to finding action sequences that achieve agent's goals\n* **Utility function** - an agent's internalization of the performance measure\n* **Expected utility** - utility agent expects to derive on average, given probabilities & utilities of each outcome\n* **Model-free agent** - agent that can learn what action is best in a particular situation w/o learning how action affects environment\n* **Learning element** - responsible for making improvements; uses feedback from critic to see how performance element should be modified\n* **Performance element** - responsible for selecting external actions\n* **Critic** - tells the learning element how well the agent is doing with wrt to a fixed performance standard\n* **Problem generator** - suggests exploratory actions; allows agent to do some suboptimal actions in short run and discover better ones for long run\n* **Atomic representation** - each state of the world is indivisible- no internal structure\n* **Factored representation** - splits up each state into fixed set of variables or attributes, each of which has a value\n* **Structured representation** - objects and their various, varying relationship can be described explicitly\n* **Expressiveness** - more expressive language is more concise, captures at least as much as less expressive ones; learning more complex\n* **Localist representation** - one-to-one mapping between concepts and memory locations (computer, brain)\n* **Distributed representation** - representation of a concept is spread over many memory locations, each used for representation of multiple diff. concepts\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nStrings are immutable. == checks whether variables point to objects of same value. 'is' checks whether variables \npoint to the same object. Lists are mutable. Use y = x[:] to get a shallow copy of any sequence (a new object of the same value). \nSlicing examples: t[1:4] ends before last index, t[1:-1] ends before last element, t[1:-1:2] selection of every nth item, t[:2] copy from beginning\nof sequence, t[2:] copy to very end of sequence. List .reverse() reverses in place/modifies, .sort() sorts the list in place, .sort(function) sorts in place\nusing user-defined comparions, sorted(li) returns a *copy* sorted. Can get KeyError with dictionaries if key does not exist. Dictionary methods: .keys() returns \nlist of current keys, .values() returns list of current values, .items() returns list of item tuples, defaultdict automatically initializes nonexistent dictionary values \nlike empty string while Counter initializes to 0. Python doesn't allow function overloading like Java does, operator overloading is possible. *args allows to accept a \nvariable number of non-keyword arguments to a function and **kwards allows to accept a varialbe number of keyword arguments to function-> def myfun(positional, *args, **kwargs). \nDefault parameters values are evaluated only when the def statement they belong to is first execution (ex: fibonacci). To define a subclass, put name of superclass in () after the \nsubclass's name on first line of definition. To be iterable, must have __iter__ method, to be iterator must have __next__ method. \n\n## Module 2 Definitions\n* **Strong typing** - every object has a fixed type, interpreter doesn't allow things incompatible with that type ('foo' + 2)\n* **Static typing** - variables can only refer to objects of a declared type, use type signatures (Java)\n* **Dynamic typing** - variables come into existence when first assigned; type(var) can be updated- Python\n* **Tuple** - simple immutable ordered sequence of items; can be of mixed types, including collection types\n* **Strings** - immutable; unicode and use 2-byte characters\n* **List** - mutable ordered sequence of items of mixed types\n* **Slicing** - return copy of a subsequence\n* **Dictionaries** - unordered & work by hashing, so keys must be immutable; constant average time add, lookup, update\n* **Magic methods** - allow user-defined classes to behave like built-in types (__init__, __len__, __add__)\n* **Duck typing** - establishes suitability of an object by determining presence of methods, call len() on any class with __len__\n* **List comprehension** - [expression for name in list]\n* **Filtered list comprehension** - [expression for name in list if filter]\n* **Iterator objects** - can be used in for loop because have __iter__ magic method, do not have hasnext() -> StopIteration exception\n* **Generators** - functions that contain yield keyword automatically return a generator when called\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem solving agents use atomic representations. Four phase problem solving process: (1) goal formulation\n(2) problem formulation (3) search (4) execution. In any fully observable, deterministic, known environment, the solution to\nany problem is a fixed sequence of actions. Search problem defined by (1) state space (2) initial state (3) goal states (4) actions\n(5) transition model (6) action cost function. Choice of good abstraction involves removing as much detail as possible while retaining\nvalidity and ensuring abstract actions are easy to carry out. Grid world example: a vacuum environment with n cells has n*2^n states. \nExample of infinite state spaces: sequence of square root, floor, and factorial operations can reach any desired positive integer\n\n## AIMA Chapter 3.2 Example Problems\nStandardized Problems\n\n## AIMA Chapter 3.3 Search Algorithms\nState space describes possibly infinite set of states in world and actions that allow transitions from one state to another,\nwhile search tree describes paths between these states, reaching towards the goal. Best first search algorithm: on each iteration choose a node\non the frontier with minimum f(n) value, return if goal, else apply EXPAND to generate child nodes. Each child node added to frontier if not yet \nreached or reached with path with lower cost than before. Returns either failure or node that represents path to goal. Even if state space is finite,\nthe complete search tree is infinite because no limit how much traverse a loop/cycle/redundant path. Can check for cycles during a search algorith, by \nfollowing up chain of parent pointers to check if state has been seen before (no need for additional memory). Evaluate an algorithm by (1) completeness\n(2) cost optimality (3) time complexity (4) space complexity\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search algorithm is given no clue about how close a state is to the goal. For BFS, FIFO queue faster than a priority queue and gives\ncorrect order of nodes; reached can be set of states. BFS is cost optimal for problems where all actions have the same cost. Both space and time compexity are O(b^d).\nUniform cost search spreads out in waves of uniform path cost. Worst case time and space complexity is $O(b^{1+frac{C*, e}})$. UCS can explore large trees of actions with low\ncosts before exploring paths with high-cost and maybe useful action. Depth first search proceeds to deepest level of tree, then backs up to next deepest node that still has\nunexpanded successors. Not cost optimal. For infinite state spaces, DFS can get stuck going down infinite path even if no cycles, thus incomplete. Memory is much smaller in DFS- O(bm)\nBacktracking has O(m) memory requirement. Depth limited search has time complexity of O(b^l) and space O(bl). IDS has memory req of O(bd) if solution, else O(bm) on finite state space. \nTime complexity O(b^d) with solution, else O(b^m). In bidirectional search, if cost of optimal path is C*, no node with cost > C*/2 is expanded\n\n## Module 3 Lecture Notes\nIf fully observable, deterministic, known environment, solution is always fixed sequence of actions. Else if partially observable or nondeterministic,\nsolution must recommend different future actions depending on what percepts received (branching strategy). Search problem needs states, initial state, actions, transition model, path cost, \nand goal. Uniform action cost means all actions are equal cost. Path cost is the sum of all action costs along a path. An abstract state is an equivalence class of real-world states. An abstract \naction is an equivalence class of combinations of real-world actions. Generalized tree search enumerates in some order all possible paths from initial state- strategy used to choose leaf node for \nexpansion determines the search process. Failure to detect repeated states can turn linear problem into exponential one. Graph search VS Tree Search: graph search checks to see if node has been \nvisited before adding to search queue. Unnformed search is when all non-goal nodes in frontier look equally good, vs in informed, some can be ranked above others. In BFS, node inserted into queue \nonly after testing to see if it is a goal state. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that plan ahead, considering sequence of actions that form path to goal state\n* **Planning agents** - agents that use factored or structured representations of states\n* **Solution** - sequence of actions (path) that reaches the goal\n* **Open-loop** - ignoring the percepts breaks the loop between agent & environment; simply execute actions\n* **Closed-loop** - monitors percepts in case model incorrect or environment is nondeterministic\n* **State space** - set of possible states that the environment can be in\n* **Applicable** - an action that can be executed on a state\n* **Transition model** - describes what each actions does; returns state from doing action on a state\n* **Action cost function** - ACTION-COST(s, a, s') is cost of applying action a in state s to reach state s'\n* **Optimal solution** - has the lowest path cost among all solutions\n* **Graph** - way to represent state space; vertices are states and directed edges are actions\n* **Search tree** - way of representing paths a search algorithm has explored. Initial state is root, and leaves are successor states\n* **Abstraction** - process of removing detail from a representation\n* **Standardized problem** - illustrates various problem solving methods; given concise, exact description; can use to measure algorithmic performance\n* **Real-world problem** - solutions people actually use, formulation is idiosyncratic, not standardized\n* **Grid world problem** - two-dimensional rectangular array of square cells in which agents can move from cell to cell\n* **Egocentric actions** - actions defined relative to the viewpoint of the agent vs absolute actions\n* **Sokoban puzzle** - agents goal is to push a number of boxes, scattered on grid, to designated storage locations\n* **Sliding-tile puzzle** - number of tiles arranged in grid with one or more blank spaces to tiles can slide around (8-puzzle example)\n* **Touring problem** - describes set of locations that must be visited, rather than a single goal destination\n* **Traveling salesperson problem (tsp)** - touring problem in which every city on a map must be visited\n* **Vlsi layout problem** - requires positioning millions of components and connections on chip to minimize area, circuit delays, etc..\n* **Robot navigation** - generalization of route-solving problem, however robot can roam around creating its own paths\n* **Automatic assembly sequencing** - of complex objects; find a feasible assembly sequence and then work to optimize the process (amino acids->proteins)\n* **Search algorithm** - takes a search problem as input and returns a sollution, or indication of failure\n* **Node** - in search tree, corresponds to state in state space, edges correspond to actions; root node = initial state\n* **Reached** - any state that has had a node generated for it\n* **Frontier** - separates two regions of the state-space graph: interior region where every state has been expanded vs exterior region\n* **Best-first search** - choose a node n with minimum value of some evaluation function f(n)\n* **Priority queue** - first pops the node with minimum cost according to evaluation function, f; used in best first search\n* **Fifo queue** - first-in-first-out queue first pops node that was added to queue first; used in BFS\n* **Lifo queue** - last-in-first-out queue (stack) pops first the most recently added node; used in DFS\n* **Graph search** - a search algorithm that checks for redundant paths, else tree-like search\n* **Systematic** - search algorithm must explore infinite state space by ensuring it can eventaually reach any state connected to initial\n* **Depth** - d or the number of actions in an optimal solution\n* **M** - maximum number of actions in any path/maximum length of any path (potentially infinity)\n* **Branching factor** - b or the number of successors of a node that must be considered\n* **Breadth-first search** - root node expanded first, all successors of root expanded, then their successors, etc- FIFO frontier\n* **Early goal test** - checking whether a node is solution as soon as it is generated vs late goal test (used in best first)\n* **Uniform-cost search** - best-first search where the evaluation function is the cost of the path from root to current node; complete & cost-optimal\n* **Depth-first search** - always expands the deepest node in the frontier first- LIFO frontier\n* **Backtracking search** - only one successor generated at a time rather than all successors; generated by modifying current state rather than new memory\n* **Depth-limited search** - version of DFS in which depth limit is supplied and treat all nodes at this limit as if no successors\n* **Diameter** - number of steps necessary to travel from any one state to another state\n* **Iterative deepening search** - tries all values of l (0, 1, 2, etc...) until either a solution is found or DLS returns failure\n* **Bidirectional search** - algorithm that simultaneously searches forward from initial state and backward from goal state, solution when two frontiers collide\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nEvery consistent heuristic is admissible, but not vice versa. With consistent heuristic,\nA* is cost-optimal. With UCS, contours were of g-cost, not g + h, circular contours spreading out equally in all \ndirections vs A* good heuristic, g + h bands will stretch towards a goal state/narrowly focused around optimal path.\nA* is complete, cost-optimal, optimally efficient among all such algorithms, but number of nodes expanded can be \nexponential in length of solution. Weighted A* search finds slightly costlier solution, but faster search time. Fewer \nstates are explored, but if optimal path strays outside of weighted search's contour, optimal path not found. Can use the \nseparation properly and prohibition of U-turn actions to eliminate the reached table. In iterative deepening A* search, if \noptimal solution has cost C*, there can be no more than C* iterations. When SMA* drops the worst leaf node, this value is \nbacked up to its parent- so when all other paths shown to look worse than forgotten path, this subtree is regenerated. SMA* \nis complete if any reachable solution (depth of shallowest goal is < memory size); optimal if optimal solution is reachable. \nSMA* sometimes switches back and forth among many candidate paths, only small set can fit in memory (thrashing).\nBidirectional best-first search with f(n) = g(n) + h(n) is not necessarily optimal. \n\n## AIMA Chapter 3.6 Heuristic Functions\nWell designed heuristic would have a value of b* close to 1, allowing large problems to be solved at reasonable \ncomputational cost. A* pruning with heuristic h reduces the effective depth by constant k_h, so search cost is O(b^(d-k_h)). \nGenerally better to use a heuristic function with higher values. Any optimal solution in original problem is solution to relaxed problem, but\nrelaxed may have better solutions if added edges provide shortcuts. Cost of an optimal solutin to relaxed problem is admissible heuristic for original \nproblem. Admissible heuristics can be derived from solution cost of a subproblem of a given problem. Pattern database constructed by searching back from \nthe goal and recording the cost of each new pattern. Given stored C* tables, can create heuristic: minimum over all landmarks of cost of getting from node\nto landmark then to goal. A path in the metalevel state space such that each state on path is an object-level search tree. \n\n## Module 4 Lecture Notes\nUniform cost search used for traversing/searching weighted tree. UCS expands node with the lowest path cost, so frontier is PQ ordered by g(n). \nTests if goal state when it is selected for expansion, not when added to frontier. Cost contours vs smooth contours in BFS. Best-first search selects node for expansion \nbased on f(n) that includes some h(n). Greedy best first search ignores g(n), just uses f(n) = h(n). A* algorithm uses f(n) = g(n) + h(n). A heuristic h(n) is admissible \nif it never overestimates the cost to reach the goal. THEOREM: if h(n) is admissible, A* using Tree search is optimal. If h2 dominates h1, h2 is more accurate than h1 and \nis better for search. Inadmissble heuristics break optimality by pushing good plans too far back on frontier (never expanded) vs admissible (optimistic) heuristics slow down \nbad plans but never outweight true costs. \n\n## Module 4 Definitions\n* **Informed search** - one that uses domain-specific hints about the location of goals\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Greedy best-first search** - form of best-first search that expands first the node with the lowest h(n) value\n* **A* search** - best-first search that uses the evaluation function f(n)=g(n)+h(n), where g(n) is path cost from initial to n\n* **Admissible heuristic** - one that never overestimates the cost to a goal (optimisitic)\n* **Consistency** - heuristic h(n) consistent if for a node n and successor n' by action a, then h(n)<=c(n,a,n')+h(n')\n* **Triange inequality** - side of a triangle cannot be longer than the sum of the other two sides\n* **Contours** - nodes inside a given contour have f = g + h costs <= the contour value\n* **Monotonic** - the path cost always increases as you go along a path, because action costs are always positive\n* **Surely expanded nodes** - A* expands all nodes that can be reached from initial state on a path where node on path has f(n)<C*\n* **Pruning** - eliminating possibilities from consideration without having to examine them\n* **Satisficing solutions** - willing to accept solutions that are suboptimal, but good enough\n* **Weighted a* search** - weight the heuristic value more heavily; f(n) = g(n) + W * h(n)\n* **Bounded suboptimal search** - look for a solution that is guaranteed to be within constant factor W of optimal cost (weighted A*)\n* **Bounded-cost search** - look for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accept a solution of any cost as long as we can find it quickly\n* **Speedy search** - type of unbounded cost search that uses heuristic as estimated # of actions to reach goal, regardless of costs\n* **Reference counts** - number of times state has been reached; remove it from reached table when no more ways to reach it\n* **Beam search** - limits size of frontier, keep only k nodes with best f-scores; executes fast even though incomplete & suboptimal\n* **Iterative-deepening a* search** - gives benefits of A* without requirements to keep all reached states in memory, cutoff is f-cost\n* **Recursive best-first search** - resembles recursive DFS, but uses f_limit to keep track of f-value of best alternative path from ancestor, can unwind back\n* **Sma* (simplified memory-bounded (ma*))** - expands like A*, expanding best leaf until full memory. Always drops worst leaf node (highest f-value)\n* **Bidirectional heuristic search** - uses evaluation function f2(n) = max(2g(n), g)n) + h(n))- does not expand node with g(n) > C*/2; complete/optimal\n* **Front-to-end search** - hF heuristic estimates distance to goal & hB estimates distance to the start\n* **Front-to-front search** - attempts to estimate the distance to the other frontier\n* **City-block or manhattan distance** - sum of the horizontal and vertical distances\n* **Effective branching factor b*** - branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\n* **Dominates** - for any node n, h2(n)>=h1(n), so h2 dominates h1; A* with h2 will never expand more nodes than with h1\n* **Relaxed problem** - problem with fewer restrictions on the actions; state space graph is supergraph of original state space graph\n* **Pattern databases** - store the exact solution costs for every possible subproblem instances\n* **Disjoin pattern databases** - record cost of solving elements in subproblem ONLY, the sum of these costs is lower bound on entire cost\n* **Precomputation** - of optimal path costs; time-consuming, but only done once, and then amortized over billions of requests\n* **Landmark points** - for each landmark L and each vertex v in the graph, compute and store C*(v, L) and C*(L, v)\n* **Differential heuristic** - hDH(n) = max (l in landmarks) |C*(n, L) - C*(goal, L)|\n* **Metalevel state space** - each state in metalevel state space captures internal state of a program searching in ordinary state space\n* **Metalevel learning** - such an algorithm can learn from missteps experiences to avoid exploring unpromising subtrees\n* **Features** - of a state that are relevant to predicting state's heuristic value; h(n) = c1x1(n) + c2x2(n)\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nTwo-Player Zero-Sum Games; MAX and MIN. Game tree may be infinite if the state space is unbounded or if \nthe rules of the game allow for infinitely repeating positions.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nIf MIN does not play optimally, MAX will do at least as well as against an optimal player. Minimax search \nalgorithm is recursive algorithm that proceeds all the way down to leaves of tree than backs up minimax values through tree \nas recursion unwinds. Time complexity is O(b^m), space complexity is O(bm) or O(m). The backed-up value of a node n is the utility \nvector of the successor state with the highest value for the player choosing at n. Players must balance the immediate advantage of \nbreaking an alliance against long-term disadvantage of being perceived as untrustworthy. Consider a node n in tree such that player has \na choice of moving to n. If player has a better choice either at same level or any point higher up in tree, player will never move to n.\nIf done perfectly, alpha-beta only needs to examine O(b^m/2) notes to pick best move. Adding dynamic move-ordering schemas brings us quite \nclose to the theoretical limit. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nA heuristic evaluation function EVAL(s, p) returns estimate of expected utility of state s to player p. Evaluation functions work \nby calculating various features of state, which together define categories or equivalence classes of states; Any given categoy will contain \nsome states that lead to wins, draws, or losses. Adding up values of features involves assumption that contribution of each feature is independent \nof value of the other features, so programs use nonlinear comibinations of features. Probabilistic cut algorithm is forward-pruning version of alpha-beta \nsearch that uses stats from prior experience to lessen chance best move is pruned. Many game-playing programs use table lookup rather than search for opening \nand ending of games.\n\n## AIMA Chapter 5.5 Stochastic Games\nSince expectiminimax considering all possible dice-roll sequences, takes O(b^mn^m), where n is number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory deals with choosing among actions based on the desirability of their immediate outcomes (episodic). If an agent \nacts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance, \naveraged over all the possible environments.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nAxioms of utility theory: (1) orderability (2) transitivity (3) continuity\n(4) substitability (5) monotonicity (6) decomposability\n\n## AIMA Chapter 16.3 Utility Functions\nUtility is not directly proportional to monetary value. Utility of money was almost exactly proportional to the \nlogarithm of the amount- most likely that people have a utility function concave for positive wealth. \n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Competitive environments** - two or more agents have conflicting goals -> adverserial search problems\n* **Economy** - very large number of agents, consider them aggregated, predict demand, etc without predicting individual agent action\n* **Pruning** - makes search more efficient by ignoring portions of search tree that make no difference to the optimal move\n* **Perfect information, zero-sum games** - fully observable, zero-sum\n* **Utility function** - U(s) assigns a single number to express the desirability of a state\n* **Game tree** - search tree that follows every sequence of moves all the way to a terminal state\n* **Minimax search** - a general algorithm for games with multiple outcome scores\n* **Minimax value** - utility (for MAX) of being in that state, assuming both players play optimally from there to end of game\n* **Alpha** - value of the best (highest) choice we have so far at any choice point along path for MAX; at least\n* **Beta** - value of the best/lowest choice we have so far at any choice point along path for MIN; at most\n* **Killer moves** - the best move; to try them first is called killer move heuristic\n* **Transpositions** - different permutations of the move sequence that end up in the same position\n* **Transposition table** - Caches the heuristic values of states\n* **Type a strategy** - considers all possible moves to certain depth; uses heuristic EF to estimate utility at those depths; wide but shallow\n* **Type b strategy** - ignores moves that look bad, follows promising lines as far as possible, deep but narrow\n* **Cutoff test** - returns true for terminal states, free to decide when to cut off search based on depth and state properties\n* **Expected value** - of a position: the average over all possible outcomes of the chance nodes\n* **Material value** - such feature values are simply added up to obtain the evaluation of a position\n* **Weighted linear function** - EVAL(s) = w1f1(S) + w2f2(s) + ... + wnfn(s)\n* **Quiescent** - position in which no pending move would wildly swing the evaluation; IS_CUTOFF returns false for nonquiescent positions\n* **Quiescence search** - search continues until quiescent position reached; restricted to capture moves that will resolve uncertainties in position\n* **Horizon effect** - when program is facing an opponent's move that causes serious damage/unavoidable, can be temporarily avoided by delaying\n* **Singular extensions** - moves that are clearly better than all others in given position even when search normally be cutoff at that point\n* **Forward pruning** - prunes moves that appear to be poor moves, but might be good ones; saves computation time at risk of errors\n* **Beam search** - on each ply, consider only beam of n best moves, rather than all possible moves\n* **Late move reduction** - works under assumption that move ordering done well, so later moves in list are less likely to be good moves\n* **Policy** - mapping from every possible state to the best move in that state; computer can play by looking up right move\n* **Retrograde** - table is constructed by retrograde minimax search\n* **Stochastic games** - bring us closer to unpredictability of real life by including a random element\n* **Chance nodes** - in addition to MAX and MIN nodes; branche from chance node labeled with outcome and its probability\n* **Expectiminimax value** - for games with chance nodes, a generalization of the minimax value for deterministic games\n* **Expected utility** - of an action EU(a), is just average utility of outcomes weighted by probability that outcome occurs\n* **Maximum expected utility (meu)** - a rational agent should choose action that maximizes agent's expected utility\n* **Lottery** - set of outcomes for each action- each action is a ticket\n* **Orderability** - given any two lotteries, rational agent must either prefor one or else rate them as equally preferable\n* **Transitivity** - given any three lotteries, if agent prefers A to B and B to C, must prefer A to C\n* **Continuity** - if B between A and C, prob.p s.t. indifferent between B 100% vs A with p & C with 1-p\n* **Substituability** - if agent indifferent between A/B, agent is indifferent between complex lotteries that are same except for B sub with A\n* **Monotonicity** - if two lotteries have same outcomes, A&B, if agent prefers A to B, must prefer higher A probability lottery\n* **Decomposability** - compound lotteries can be reduced to simpler ones using the laws of probability\n* **Existence of utility function** - if agent's preferences obey axiomos, function U such that U(A) > U(B) if A > B\n* **Expected utility of a lottery** - utility of lottery is sum of probability of each outcome * utility of that outcome\n* **Value or ordinal utility function** - in a deterministic environment, agent needs only a preference ranking on states\n* **Preference elicitation** - presenting choices to human and using observed preferences to pin down underlying utility function\n* **Value of a statistical life** - used to determine costs and benefits of regulations and interventions\n* **Micromort** - a one in a million chance of death\n* **Qaly** - quality-adjusted life year\n* **Monotonic preference** - agent exhibits this for more money\n* **Risk-averse** - U(L) < U(Seml(L)); prefer sure thing with payoff less than expected monetary value of a gamble\n* **Certainty equivalent** - the value an agnet will accept in lieu of a lottery\n* **Insurance premium** - the difference between the EMV of a lottery and its certainty equivalent\n* **Risk-neutral** - an agent that has a linear curve for wealth\n* **Unbiased** - expected value of the error between estimate and its expected value is zero\n* **Optimizer's curse** - tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - people elect the known probabability rather than the unknown unknowns\n* **Framing effect** - exact wording of a decision problem can have a big impact on the agent's choices\n* **Anchoring effect** - people feel more comfortable making relative utility judgements rather than absolute ones\n* **Evolutionary psychology** - our brain's decision-making mechanisms did not evolve to solve word problems with probabilites/decimals\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n 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 Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xSD718ktxC7J"
      },
      "source": [
        ""
      ],
      "execution_count": 43,
      "outputs": []
    }
  ]
}