{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "bdbe5051-3071-478b-c053-fd262f9aee8d"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "9c150fc6-22d0-483e-fa4a-0d7108ca5219"
      },
      "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": 43,
      "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": 44,
      "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 = \"\"\" Rationality - doing the \"right thing.\" \n",
        "\\n The Turing Test: Can a machine think? NLP, Knowledge Representation, Automated Reasoning, Machine Learning (adapt to new circumstances and to detect and extrapolate patterns) \n",
        "\\n To pass a (TOTAL) Turing test, robot needs ${computer vision}$ and speech recog to perceive the world and ${robotics}$ to manipulate objects and move about.\n",
        "\\n A rational agent is one that acts to acheive the best (expected) outcome.\n",
        "\\n Value alignment problem: values or objectives put into machine must be aligned with human. We want agents that are 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 = \"\"\" Weak AI - the idea that machines could act as if they were intelligent\n",
        "\\n Strong AI - assertion that machines that do so are actually consciously thinking (not just simulating thinking)\n",
        "\\n 'Argument from informality of behavior' - human behavior is far too complex to be captured by any formal set of rules \n",
        "\\n Human smust be using some informal guidelines that could never be captured in a formal set of rules and thus coudl never be codified in a computer program.\n",
        "\\n Alan Turing - instead of asking whether machines can think, ask whether machines can pass a behavioral test (Turing Test)\n",
        "\\n  \"\"\"\n",
        "chapter27_2 = \"\"\" brain in a vat  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can perceive its environment thru sensors and acting on that environment thru actuators.\n",
        "\\n Percept refers to content that an agent's sensors are perceiving. Percept sequence is complete history of everything agent has perceived. \n",
        "\\n In general, agent's choice of action depends on built-in knowledge and entire percept sequence but not on anything it hasn't perceived.\n",
        "\\n Agent's behavior is described by agent function that maps any given percept sequence to an action.\n",
        "\\n Agent function will be implemented by agent program. Tabulating agent function for most agents would be almost infinite unless we place bound on length of percept sequences considered. \"\"\"\n",
        "chapter2_2 = \"\"\" Rational agent does the right thing, but what is the right thing?\n",
        "\\n Consequentialism: evaluate agent behavior by its consequences. When agent is in an environment, it generates a sequence of actions according to percepts it recieves. This seq of actions causes environment to go thru seq of states. \n",
        "\\n If seq is desirable, then agent has performed well (desirability -> performance measure that evaluates any given seq of env states). Machines dont have preferences on its own, so it is within designer of machine. \n",
        "\\n It is better to design general performance measures according to what one actually wants to be achieved in the env, rather than according to how one thinks the agent should behave. \n",
        "\\n What is rational: (1) performance measure that defines success criterion (2) agent's prior knowledge of env (3) actions that agent can perform (4) agent's percept seq to date\n",
        "\\n Rationality vs omniscience: omnicient agent knows actual outcome of actions, but impossible in reality. Rationality maximizes expected performance. \n",
        "\\n Information gathering: doing actions in order to modify future percepts\n",
        "\\n Autonomy - learn what it can to compensate for partial or incorrect prior knowledge\"\"\"\n",
        "chapter2_3 = \"\"\" Task environments: problems to which rational agents are the solutions. \n",
        "\\n PEAS: (Performance, Environment, Actuators, Sensors). When designing an agent, 1st step is always to specify task env as fully as possible. \n",
        "\\n Fully Observable: agent's sensors give access to complete state of env at each point in time. Effectively fully observable if sensors detect all aspects relevant to choice of action\n",
        "\\n Partially Observable: partial bc of noisy, inaccurate sensors or parts of state are missing from sensor data.\n",
        "\\n Unobservable: if no sensors at all \n",
        "\\n Single Agent vs Multiagent. Entities are not agents (is B maximizing a performance measure? if not, not an agent).\n",
        "\\n Deterministic: if next state of environment is completely determined by curr state and action executed by the agents\n",
        "\\n Agent does not need to wrory about uncertainty in fully observable, deterministic environment. \n",
        "\\n If env is partially observable, it could ${appear}$ to be nondeterministic. \n",
        "\\n Most real situations are so complex, impossible to track of all unobserved aspects so practically treated as nondeterministic (e.g. taxi driving).\n",
        "\\n Stochastic is used as synonym for nondeterministic - distinction: stochastic if explicitly deals with probabilities, nondeterministic if possibilities are listed without being quantified (e.g. chance of rain tmr). \n",
        "\\n Episodic task env: agent experience is divided into atomic episodes. each episode agent receives percept and performs single action (next ep does not depend on actions in prev episodes. many classification tasks are episodic).\n",
        "\\n Sequential envs: curr decision could affect all future decisions (e.g. chess, taxi driving)\n",
        "\\n Dynamic environment if env can change during agent deliberating, else static\n",
        "\\n If env itself does not change with passage of time but agent's performance score does, then env is semidynamic\n",
        "\\n Discrete/continuous applies to state of environment, to way time is handled, to the percepts and actions of agent. \n",
        "\\n Known/unknown refers to agent's state of knowledge about laws of physics of environment, not to env itself. In a known env, outcomes for all actions given. If env is unknown, agent has to learn how it works to make good decisions.\n",
        "\\n Possible for known env to be partially observable (in card games, know rules but unable to see cards that have not yet been turned over) and unkown env to be fully observable (new video game, screen shows entire game state but still dont know what buttons do until tried)\n",
        "\\n Agent may learn more about perfromance measure based on further interactions with designer or user (task env is viewed as multiagent env).\n",
        "\\n Hardest case: partially observable, multiagent, nondeterministics, sequential, dynamic, continuou, unknown\"\"\"\n",
        "chapter2_4 = \"\"\" Job of AI: design agent program that implements agent function (map percepts -> actions).\n",
        "\\n Agent program takes current percept as input, agent function depends on entire percept history.\n",
        "\\n Agent program has no choice but to take jsut current percept as input bc nothing more is available from environment\n",
        "\\n If agent actions depend on entire percept sequence, agent will need to remember percepts.\n",
        "\\n Key challenge for AI: find out how to write programs that produce rational behavior from smallish program rather than vast table (too big!)\n",
        "\\n 4 basic kinds of agent programs: simple reflex agents, model-based reflex agents, goal-based agents, utility-based agents\n",
        "\\n Simplest agent: simple reflex agent. select actions on basis of current percept, ignoring rest. \n",
        "\\n Condition-action rule: some process triggers some established connection in agent program (e.g. if car in front breaks, then break)\n",
        "\\n simple reflex agent works only if correct decision can be made on basis of just current percept (i.e. only if env is fully observable)\n",
        "\\n Escape from infinite loops is possible if agent can radnomize actions (randomized behavior can be rational in some multiagent env.)\n",
        "\\n Most effective way to handle partial observability: agent keeps track of part of world it cant see now (maintain internal state depends on percept history, thus reflects at least some unobserved aspects of curr state).\n",
        "\\n Updating such internal state info requires 2 kinds of knowledge encoded in agent program: (1) info about how world changes over time (transition model)\n",
        "\\n (2) info about how state of world is reflected in agent percepts (sensor model).\n",
        "\\n Goal-based agents: Agent program can combine this with the model to choose actions that achieve this goal\n",
        "\\n ^may appear less efficient, more flexible because knowledge that supports its decisions is represented explicitly and can be modified. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Goals alone are not enough to generate high-quality behavior in most environments. Goals just provide a binary distinction btw happy and unhappy states\n",
        "\\n Agent's utility function is essentially internalization of performance measure. An Agent that chooses actions to maximize its utility will be rational according to external performance measure\n",
        "\\n Like goal-based agents, utility-based agent has many advantages in terms of flexibility and learning. Utility provides a way for probability of success to be weighed against importance of goals\n",
        "\\n Rational utility-based agent chooses action that maximized expected utility of action outcomes. Any rational agent must behave as if it possesses a utility function whose expected value it tries to maximize\n",
        "\\n Agent that possesses an explicit utility function can make rational decisions w general-purpose algorithm that does not depend on the specific utility function being maximized\n",
        "\\n Model-free agents can learn what action is best in a particular situation without learning exactly how that action changes the env\n",
        "\\n All agents can improve their performance thru learning \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"intelligent agent\": \"takes best possible action in a situation\",\n",
        "\"agent function\": \"specifies the action taken by the agent in response to any percept sequence\",\n",
        "\"percept\": \"content that an agent's sensors are perceiving\",\n",
        "\"Agent Architecture\": \"agent = architecture + program\",\n",
        "\"Model-based agent\" : \"Transition model + sensor model allow agent to track world state to extent possible given limits of agent sensors\",\n",
        "\"Goal-based Agents\" : \"agent needs some sort of goal info that describes situations that are desirable.\",\n",
        "\"transition model\": \"Knowledge of how world works\",\n",
        "\"deterministic\":\"action has clear outcome/circumstance. state of world determined by recent choice of agent\",\n",
        "\"stochastic\":\"probabilistic\",\n",
        "\"episodic\":\"type of env. agent perceives env and performs *single* action. action choice not reliant on prev action\",\n",
        "\"sequential\":\"current decision affects all future actions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 45,
      "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": 2475
        },
        "cellView": "form",
        "outputId": "a6cf3d1f-0d99-491e-ce3d-88154448a9fc"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Rationality - doing the \"right thing.\" \n\n The Turing Test: Can a machine think? NLP, Knowledge Representation, Automated Reasoning, Machine Learning (adapt to new circumstances and to detect and extrapolate patterns) \n\n To pass a (TOTAL) Turing test, robot needs ${computer vision}$ and speech recog to perceive the world and ${robotics}$ to manipulate objects and move about.\n\n A rational agent is one that acts to acheive the best (expected) outcome.\n\n Value alignment problem: values or objectives put into machine must be aligned with human. We want agents that are provably beneficial to humans. \n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI - the idea that machines could act as if they were intelligent\n\n Strong AI - assertion that machines that do so are actually consciously thinking (not just simulating thinking)\n\n 'Argument from informality of behavior' - human behavior is far too complex to be captured by any formal set of rules \n\n Human smust be using some informal guidelines that could never be captured in a formal set of rules and thus coudl never be codified in a computer program.\n\n Alan Turing - instead of asking whether machines can think, ask whether machines can pass a behavioral test (Turing Test)\n\n  \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n brain in a vat  \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can perceive its environment thru sensors and acting on that environment thru actuators.\n\n Percept refers to content that an agent's sensors are perceiving. Percept sequence is complete history of everything agent has perceived. \n\n In general, agent's choice of action depends on built-in knowledge and entire percept sequence but not on anything it hasn't perceived.\n\n Agent's behavior is described by agent function that maps any given percept sequence to an action.\n\n Agent function will be implemented by agent program. Tabulating agent function for most agents would be almost infinite unless we place bound on length of percept sequences considered. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational agent does the right thing, but what is the right thing?\n\n Consequentialism: evaluate agent behavior by its consequences. When agent is in an environment, it generates a sequence of actions according to percepts it recieves. This seq of actions causes environment to go thru seq of states. \n\n If seq is desirable, then agent has performed well (desirability -> performance measure that evaluates any given seq of env states). Machines dont have preferences on its own, so it is within designer of machine. \n\n It is better to design general performance measures according to what one actually wants to be achieved in the env, rather than according to how one thinks the agent should behave. \n\n What is rational: (1) performance measure that defines success criterion (2) agent's prior knowledge of env (3) actions that agent can perform (4) agent's percept seq to date\n\n Rationality vs omniscience: omnicient agent knows actual outcome of actions, but impossible in reality. Rationality maximizes expected performance. \n\n Information gathering: doing actions in order to modify future percepts\n\n Autonomy - learn what it can to compensate for partial or incorrect prior knowledge\n\n## AIMA 2.3 The Nature of Environments\n Task environments: problems to which rational agents are the solutions. \n\n PEAS: (Performance, Environment, Actuators, Sensors). When designing an agent, 1st step is always to specify task env as fully as possible. \n\n Fully Observable: agent's sensors give access to complete state of env at each point in time. Effectively fully observable if sensors detect all aspects relevant to choice of action\n\n Partially Observable: partial bc of noisy, inaccurate sensors or parts of state are missing from sensor data.\n\n Unobservable: if no sensors at all \n\n Single Agent vs Multiagent. Entities are not agents (is B maximizing a performance measure? if not, not an agent).\n\n Deterministic: if next state of environment is completely determined by curr state and action executed by the agents\n\n Agent does not need to wrory about uncertainty in fully observable, deterministic environment. \n\n If env is partially observable, it could ${appear}$ to be nondeterministic. \n\n Most real situations are so complex, impossible to track of all unobserved aspects so practically treated as nondeterministic (e.g. taxi driving).\n\n Stochastic is used as synonym for nondeterministic - distinction: stochastic if explicitly deals with probabilities, nondeterministic if possibilities are listed without being quantified (e.g. chance of rain tmr). \n\n Episodic task env: agent experience is divided into atomic episodes. each episode agent receives percept and performs single action (next ep does not depend on actions in prev episodes. many classification tasks are episodic).\n\n Sequential envs: curr decision could affect all future decisions (e.g. chess, taxi driving)\n\n Dynamic environment if env can change during agent deliberating, else static\n\n If env itself does not change with passage of time but agent's performance score does, then env is semidynamic\n\n Discrete/continuous applies to state of environment, to way time is handled, to the percepts and actions of agent. \n\n Known/unknown refers to agent's state of knowledge about laws of physics of environment, not to env itself. In a known env, outcomes for all actions given. If env is unknown, agent has to learn how it works to make good decisions.\n\n Possible for known env to be partially observable (in card games, know rules but unable to see cards that have not yet been turned over) and unkown env to be fully observable (new video game, screen shows entire game state but still dont know what buttons do until tried)\n\n Agent may learn more about perfromance measure based on further interactions with designer or user (task env is viewed as multiagent env).\n\n Hardest case: partially observable, multiagent, nondeterministics, sequential, dynamic, continuou, unknown\n\n## AIMA 2.4 The Structure of Agents\n Job of AI: design agent program that implements agent function (map percepts -> actions).\n\n Agent program takes current percept as input, agent function depends on entire percept history.\n\n Agent program has no choice but to take jsut current percept as input bc nothing more is available from environment\n\n If agent actions depend on entire percept sequence, agent will need to remember percepts.\n\n Key challenge for AI: find out how to write programs that produce rational behavior from smallish program rather than vast table (too big!)\n\n 4 basic kinds of agent programs: simple reflex agents, model-based reflex agents, goal-based agents, utility-based agents\n\n Simplest agent: simple reflex agent. select actions on basis of current percept, ignoring rest. \n\n Condition-action rule: some process triggers some established connection in agent program (e.g. if car in front breaks, then break)\n\n simple reflex agent works only if correct decision can be made on basis of just current percept (i.e. only if env is fully observable)\n\n Escape from infinite loops is possible if agent can radnomize actions (randomized behavior can be rational in some multiagent env.)\n\n Most effective way to handle partial observability: agent keeps track of part of world it cant see now (maintain internal state depends on percept history, thus reflects at least some unobserved aspects of curr state).\n\n Updating such internal state info requires 2 kinds of knowledge encoded in agent program: (1) info about how world changes over time (transition model)\n\n (2) info about how state of world is reflected in agent percepts (sensor model).\n\n Goal-based agents: Agent program can combine this with the model to choose actions that achieve this goal\n\n ^may appear less efficient, more flexible because knowledge that supports its decisions is represented explicitly and can be modified. \n\n## Module 1 Lecture Notes\n Goals alone are not enough to generate high-quality behavior in most environments. Goals just provide a binary distinction btw happy and unhappy states\n\n Agent's utility function is essentially internalization of performance measure. An Agent that chooses actions to maximize its utility will be rational according to external performance measure\n\n Like goal-based agents, utility-based agent has many advantages in terms of flexibility and learning. Utility provides a way for probability of success to be weighed against importance of goals\n\n Rational utility-based agent chooses action that maximized expected utility of action outcomes. Any rational agent must behave as if it possesses a utility function whose expected value it tries to maximize\n\n Agent that possesses an explicit utility function can make rational decisions w general-purpose algorithm that does not depend on the specific utility function being maximized\n\n Model-free agents can learn what action is best in a particular situation without learning exactly how that action changes the env\n\n All agents can improve their performance thru learning \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Intelligent agent** - takes best possible action in a situation\n* **Agent function** - specifies the action taken by the agent in response to any percept sequence\n* **Percept** - content that an agent's sensors are perceiving\n* **Agent architecture** - agent = architecture + program\n* **Model-based agent** - Transition model + sensor model allow agent to track world state to extent possible given limits of agent sensors\n* **Goal-based agents** - agent needs some sort of goal info that describes situations that are desirable.\n* **Transition model** - Knowledge of how world works\n* **Deterministic** - action has clear outcome/circumstance. state of world determined by recent choice of agent\n* **Stochastic** - probabilistic\n* **Episodic** - type of env. agent perceives env and performs *single* action. action choice not reliant on prev action\n* **Sequential** - current decision affects all future actions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "bd7e2c76-27db-4319-95ed-b6f30639a499"
      },
      "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": 48,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Goal Formulation, Problem Formulation (devise description of states and actions to reach goal), Search (agent simulates sequences of actions in its model until finds seq of actions to reach goal (seq is solution)), Execution (agent can execute the actions in the solution one at a time)\n",
        "\\n If model is correct, then once found a solution, it can ignore percepts while executing the actions (open-loop system).\n",
        "\\n If chance model is incorrect or env is nondeterministic, agent is safer using closed-loop approach that monitors percepts\n",
        "\\n Search Problem: (0.) Problem (2) State Space (3) Initial State (4) Goal States (5) Actions (6) Transition Model (describes what each action does) (7) Action Cost Function \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized Problem: intended to illustrate or exercise various problem solving methods. can be consise, exact description.\n",
        "\\n Real-world problem: solutions people actually used \n",
        "\\n Robot navigation - generalization of route-finding problem. instead of following distinct paths, robot can roam around to make own paths\"\"\"\n",
        "chapter3_3 = \"\"\" Search Algorithm: takes search problem as input and outputs solution (or failure indicator)\n",
        "\\n In search tree over state-space graph, each node corresponds to state and edges are actions. root is initial state \n",
        "\\n Best First Search (how do we decide which node from frontier to expand next?) Choose node n with min val from evalutation function (graph search algorithm)\n",
        "\\n Node in tree has State, Parent, Action (applied to parent state to generate this node), Path-Cost\n",
        "\\n To be complete, search alg must be systematic in way it explores an infinite state space making sure it can eventually reach any state connected to initial state\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" BFS = 1  + b + b^2 +...+b^d = O(b^d), total nodes generated, b=branching factor\n",
        "\\n DFS is O(bm), m is max depth of tree. Variant is backtracking search. DFS is not cost-optimal, returns 1st sol it finds even if not cheapest\n",
        "\\n Use DFS for problems where a tree-like search is feasible (less need for memory, no need for reached table and frontier is small) \n",
        "\\n Depth-limited search, supply DFS with depth limit and treat nodes at depth l as if no successors. O(b^l) runtime, space O(bl)\n",
        "\\n Iterative deepening search solves problem of picking good value for l by trying all values until a solution is found or depth limited search returns failure. O(bd) w sol or O(bm) memory on finite state spaces w no solution\n",
        "\\n like BFS, iterative deepening is optimal for problems where all actions have same cost, complete on finite acyclic state spaces, or on any finite state space when check nodes for cycles all up the path \n",
        "\\n Iterative deepening is O(b^d) when solution, O(b^m) when not\n",
        "\\n Bidirectional search: def below - motivation is that 2*b^(d/2) < b^d \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" to make DFS complete, limit depth to avoid infinite paths\n",
        "\\n Procedure for solving search: Goal Formulation, Problem Formulation, Search, Execution \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"grid world\": \"2d array of square cells where agents can move cell to cell\",\n",
        "\"completeness\": \"algorithm guarenteed to report a solution\",\n",
        "\"cost optimality\":\"find sol w lowest path cost of all solutions\",\n",
        "\"early-goal test\":\"check whether a node is solution as soon as it is generated (vs late goal test best-first search)\",\n",
        "\"uniform-cost search\": \"g(n) | W=0 , by AI community, Dijkstra's by CS community\",\n",
        "\"bidirectional search\": \"simult. searches forward from initial state and backwards from goal state hoping that they meet\",\n",
        "\"path\":\"sequence of actions\",\n",
        "\"strategy\":\"order of tree expansion evailabted on completeness, optimality, time+space complexity\",\n",
        "\"reflex agent\": \"selects action based on current percept\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 49,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1086
        },
        "outputId": "c9a32c88-0039-4535-bc6b-d1dd0902bfc6"
      },
      "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": 50,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Goal Formulation, Problem Formulation (devise description of states and actions to reach goal), Search (agent simulates sequences of actions in its model until finds seq of actions to reach goal (seq is solution)), Execution (agent can execute the actions in the solution one at a time)\n\n If model is correct, then once found a solution, it can ignore percepts while executing the actions (open-loop system).\n\n If chance model is incorrect or env is nondeterministic, agent is safer using closed-loop approach that monitors percepts\n\n Search Problem: (0.) Problem (2) State Space (3) Initial State (4) Goal States (5) Actions (6) Transition Model (describes what each action does) (7) Action Cost Function \n\n## AIMA Chapter 3.2 Example Problems\n Standardized Problem: intended to illustrate or exercise various problem solving methods. can be consise, exact description.\n\n Real-world problem: solutions people actually used \n\n Robot navigation - generalization of route-finding problem. instead of following distinct paths, robot can roam around to make own paths\n\n## AIMA Chapter 3.3 Search Algorithms\n Search Algorithm: takes search problem as input and outputs solution (or failure indicator)\n\n In search tree over state-space graph, each node corresponds to state and edges are actions. root is initial state \n\n Best First Search (how do we decide which node from frontier to expand next?) Choose node n with min val from evalutation function (graph search algorithm)\n\n Node in tree has State, Parent, Action (applied to parent state to generate this node), Path-Cost\n\n To be complete, search alg must be systematic in way it explores an infinite state space making sure it can eventually reach any state connected to initial state\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS = 1  + b + b^2 +...+b^d = O(b^d), total nodes generated, b=branching factor\n\n DFS is O(bm), m is max depth of tree. Variant is backtracking search. DFS is not cost-optimal, returns 1st sol it finds even if not cheapest\n\n Use DFS for problems where a tree-like search is feasible (less need for memory, no need for reached table and frontier is small) \n\n Depth-limited search, supply DFS with depth limit and treat nodes at depth l as if no successors. O(b^l) runtime, space O(bl)\n\n Iterative deepening search solves problem of picking good value for l by trying all values until a solution is found or depth limited search returns failure. O(bd) w sol or O(bm) memory on finite state spaces w no solution\n\n like BFS, iterative deepening is optimal for problems where all actions have same cost, complete on finite acyclic state spaces, or on any finite state space when check nodes for cycles all up the path \n\n Iterative deepening is O(b^d) when solution, O(b^m) when not\n\n Bidirectional search: def below - motivation is that 2*b^(d/2) < b^d \n\n## Module 3 Lecture Notes\n to make DFS complete, limit depth to avoid infinite paths\n\n Procedure for solving search: Goal Formulation, Problem Formulation, Search, Execution \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Grid world** - 2d array of square cells where agents can move cell to cell\n* **Completeness** - algorithm guarenteed to report a solution\n* **Cost optimality** - find sol w lowest path cost of all solutions\n* **Early-goal test** - check whether a node is solution as soon as it is generated (vs late goal test best-first search)\n* **Uniform-cost search** - g(n) | W=0 , by AI community, Dijkstra's by CS community\n* **Bidirectional search** - simult. searches forward from initial state and backwards from goal state hoping that they meet\n* **Path** - sequence of actions\n* **Strategy** - order of tree expansion evailabted on completeness, optimality, time+space complexity\n* **Reflex agent** - selects action based on current percept\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 = \"\"\" Greedy best first search expands on node that appears closest to goal, so evaluation function f(n) = h(n). Time + space complexity is O(|V|)\n",
        "\\n w good heuristic function above, time complexity can be O(bm)\n",
        "\\n A* search is best first search w eval function f(n) = g(n) + h(n), g(n) is path cost from initial state to node . f(n) estimated cost of best path from n to goal\n",
        "\\n w/ admissible heuristic, A* is cost optimal. \n",
        "\\n A* is efficient bc it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
        "\\n A* s complete, cost optimal, and optimally efficient, but not answer for all searching. For many problems, num nodes expanded can be exponential in length of solution\n",
        "\\n Recursive best first search is optimal if h(n) is admissible. space complexity is linear in depth of deepest optimal soln, but time complexity is difficult to characterize. depends both on h(n) accuracy and how often best path changes as nodes are expanded. expands nodes in order of increasing f-score, even if f is nonmonotonic\n",
        "\\n IDA*, RBFS use too little memory. forget most of what is done, so many reexplore states many times\n",
        "\\n Bidirectional best first search, could try f(n) = g(n) + h(n) but no guarentee to lead to optimal cosst solution\n",
        "\\n heuristic dominates if overestimates more than other, but still admissible so its better\"\"\"\n",
        "chapter3_6 = \"\"\" One way to characterize quality of heuristic if effective branching factor b8. N = total num of nodes generated by A*. soln depth=d. b* is branching factor that uniform tree w depth d would have to have in order to contain N+1 nodes. N+1 = 1+b* + (b*)^2+...+(b*)^d \n",
        "\\n Cost of optimal soln to relaxed problem is an admissible heuristic for original problem\n",
        "\\n perfromance of heuristic search algorithms depends on quality of heuristic function, which can be constructed by relaxing prob definitionby storing precomputed solution costs for subproblems in a pattern database,\n",
        "by defining landmarks, or by learning from experience with the problem class\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" local beam search alg keeps track of k states rather than just one \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"greedy best first search\" : \"h(n), W=infinity, expands first the node w lowest h(n) value to try to get to solution quickly\",    \n",
        "\"admissible heuristic\": \"one that never overestimated cost to reach a goal (thereby optimistic)\",\n",
        "\"consistency\": \"h(n) is consistent if for every node n and every successor n' by action a, $h(n) \\leq c(n,a,n') + h(n')$\",\n",
        "\"A* search\":\"g(n) + h(n), W=1, main issue is use of memory (remove states from reached when prove no longer needed)\",\n",
        "\"weighted A* search\": \"f(n) = g(n) + W*h(n) | infinity > W > 1\",\n",
        "\"bounded suboptimal search\":\" look for soln guarenteed within constant factor W of optimal cost\",\n",
        "\"unbounded cost search\": \"acccept soln of any cost as long as can find quickly\",\n",
        "\"reference counts\": \"num times a state has been reached\",\n",
        "\"beam search\":\"limits size of frontier, keep k nodes with best f scores (incomplete+suboptimal, fast w fewer nodes)\",\n",
        "\"iterative-deepening A* search\":\"benefits of A* without requirement to keep all reach states in mem, w cost of revisiting states\",\n",
        "\"recursive best first search\": \"attempt to mimic best first search w linear space. more efficient than IDA* but suffers excessive node regen\",\n",
        "\"relaxed problem\":\"problem w fewer restrictions on actions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 51,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 853
        },
        "cellView": "form",
        "outputId": "d19d7d5d-32dc-4b74-bc47-5533ffd351d6"
      },
      "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": 52,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best first search expands on node that appears closest to goal, so evaluation function f(n) = h(n). Time + space complexity is O(|V|)\n\n w good heuristic function above, time complexity can be O(bm)\n\n A* search is best first search w eval function f(n) = g(n) + h(n), g(n) is path cost from initial state to node . f(n) estimated cost of best path from n to goal\n\n w/ admissible heuristic, A* is cost optimal. \n\n A* is efficient bc it prunes away search tree nodes that are not necessary for finding an optimal solution.\n\n A* s complete, cost optimal, and optimally efficient, but not answer for all searching. For many problems, num nodes expanded can be exponential in length of solution\n\n Recursive best first search is optimal if h(n) is admissible. space complexity is linear in depth of deepest optimal soln, but time complexity is difficult to characterize. depends both on h(n) accuracy and how often best path changes as nodes are expanded. expands nodes in order of increasing f-score, even if f is nonmonotonic\n\n IDA*, RBFS use too little memory. forget most of what is done, so many reexplore states many times\n\n Bidirectional best first search, could try f(n) = g(n) + h(n) but no guarentee to lead to optimal cosst solution\n\n heuristic dominates if overestimates more than other, but still admissible so its better\n\n## AIMA Chapter 3.6 Heuristic Functions\n One way to characterize quality of heuristic if effective branching factor b8. N = total num of nodes generated by A*. soln depth=d. b* is branching factor that uniform tree w depth d would have to have in order to contain N+1 nodes. N+1 = 1+b* + (b*)^2+...+(b*)^d \n\n Cost of optimal soln to relaxed problem is an admissible heuristic for original problem\n\n perfromance of heuristic search algorithms depends on quality of heuristic function, which can be constructed by relaxing prob definitionby storing precomputed solution costs for subproblems in a pattern database,\nby defining landmarks, or by learning from experience with the problem class\n\n## Module 4 Lecture Notes\n local beam search alg keeps track of k states rather than just one \n\n## Module 4 Definitions\n* **Greedy best first search** - h(n), W=infinity, expands first the node w lowest h(n) value to try to get to solution quickly\n* **Admissible heuristic** - one that never overestimated cost to reach a goal (thereby optimistic)\n* **Consistency** - h(n) is consistent if for every node n and every successor n' by action a, $h(n) \\leq c(n,a,n') + h(n')$\n* **A* search** - g(n) + h(n), W=1, main issue is use of memory (remove states from reached when prove no longer needed)\n* **Weighted a* search** - f(n) = g(n) + W*h(n) | infinity > W > 1\n* **Bounded suboptimal search** -  look for soln guarenteed within constant factor W of optimal cost\n* **Unbounded cost search** - acccept soln of any cost as long as can find quickly\n* **Reference counts** - num times a state has been reached\n* **Beam search** - limits size of frontier, keep k nodes with best f scores (incomplete+suboptimal, fast w fewer nodes)\n* **Iterative-deepening a* search** - benefits of A* without requirement to keep all reach states in mem, w cost of revisiting states\n* **Recursive best first search** - attempt to mimic best first search w linear space. more efficient than IDA* but suffers excessive node regen\n* **Relaxed problem** - problem w fewer restrictions on actions\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 = \"\"\" Most commonly studied games and 2 player turn taking perfect info, zero sum games. \n",
        "\\n Perfect info = fully observable \n",
        "\\n Game tree may be infinite if state space is unbounded or if rules of game allow for infinitely repeating positions\n",
        "\\n Minimax search assumes both plaers play optimally\n",
        "\\n Minimax alg performs complete depth-first exploration of game tree. \n",
        "\\n m=max depth, b=legal moves at each point, time complexity=O(b^m) and space is O(bm)\n",
        "\\n Alpha-beta pruning can be applied to trees of any depth\n",
        "\\n $utility(loss,p) \\leq eval(s,p) \\leq utility(win,p)$\n",
        "\\n evaluation function should be applied only to positions that are quiescent\n",
        "\\n alpha-beta pruning prunes branches of the tree that can have no effect on final evaluation\n",
        "\\n forward pruning prunes moves that appear to be poor mnoves but might possibly be good ones (saves computation time)\n",
        "\\n beam search (one forward pruning) considers a beam of best n moves but approach is dangerous bc cannot guarentee best move is not pruned away\n",
        "\\n Modern Go programs have abandoned alpha-beta search and use Monte Carlo tree search (MCTS) no h(n) but value of state is estimated as the avg utility over a num of simulations of complete games starting from the state\"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" stochastic games bring closer to real life by including random element\n",
        "\\n game tree must include chance nodes in addition to MAX and MIN nodes \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Making Simple Decisions\n",
        "\\n How Utility Theory combines with probability theory to yield decision-theoretic agent - agent that can make rational decisions based on what it believes and what it wants.\n",
        "\\n Such agents canmake decisions in contexts in which uncertainty and conflicting goals leave a logical agent with no way to decide. \n",
        "\\n Goal-based agent has a binary distinction good (goal) and bad (non-goal) states.\n",
        "\\n Decision-theoretic agent assigns continuous range of values to states and thus can easily choose a better state when no best state is available. \n",
        "\\n Basic principle of decision theory: maximization of expected utility. \n",
        "\\n Decision theory deals with choosing among actions based on desirability of immediate outcomes.\"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\"Basis of Utility Theory.\n",
        "\\n Maximum Expected Utility, seems a reasonable way to make decisions, but not the only rational way \n",
        "\\n Primary issue for utility theory is to understand how preferences between complex lotteries are related to preferences between underlying states in those lotteries\n",
        "\\n 6 Constraints any Reasonable Preference Relation to Obey:\n",
        "\\n (1) Orderability: given 2 lotteries. rational agent must either prefer one or rate equal (cannot avoid deciding)\n",
        "\\n (2) Transitivity If agent prefers A to B, and B to C, then prefers A to C\n",
        "\\n (3) Continuity If some lottery B is between A and C in preference, then some probability p for which rational agent will be indifferent between getting B for sure and the lottery that yields A w probability p and C with probability 1 - p \n",
        "\\n (4) Substitutability If agent is indifferent between 2 lotteries A and B, then agent is indifferent between 2 or more complex lotteries that are the same except that B is substituted for A in one of them (holds regardless of the probabilities and the other outcomes in the lotteries)\n",
        "\\n (5) Monotonocity: 2 lotteries with same 2 possible outcomes, A and B. if agent prefers A to B, then agent must prefer the lottery that has a higher probability for A\n",
        "\\n (6) Decompososability: Compound lotteries can reduced to simpler ones using probability. \n",
        "\\n Constraints are known as axioms of utility theory (preference). \n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Decision theory is a normative theory - describes how a rational agent should act\n",
        "\\n Descriptive theory describes how actual agents (e.g. humans) really act\n",
        "\\n Certainty Effect: ppl are strongly attracted to gains that are certain \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"Minimax runtime = $O(b^m)$, DFS on game tree. \n",
        "\\n ALPHA-BETA PRUNING: \n",
        "\\n If curr player has better choice at (1) same level (2) any point higher in the tree, player never moves to that state/node so prune it\n",
        "\\n MAX is at least alpha. MIN is at most beta\n",
        "\\n PRUNING GUIDELINES:\n",
        "\\n - MAX: when v >= beta is backed up, MIN never selects that MAX node bc Beta is MIN's upper bound\n",
        "\\n - MIN: when v <= alpha '', MAX never selects that MIN bc alpha is MAX's upper bound\n",
        "\\n done well. alphabeta is $O(b^(m/2))$ rather than minimax $O(b^m)$. effective branch factor is $sqrt(b)$\n",
        "\\n Expectimax: instead of MAX and MIN, has MAX and chance nodes (min nodes but outcome uncertain. expected util) \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"terminal state\" : \"states where game has ended\",\n",
        "\"game tree\": \"search tree that follows every sequence of moves all the way to a terminal state.\",\n",
        "\"killer moves\": \"best moves, and to try them first is killer move heuristic\",\n",
        "\"cutoff test\": \"return true terminal states, otherwise free to decide when to cut off search based on depth and others\",\n",
        "\"quicient\": \"positions in which there is no pending move that would wildly swing the evaluation\",\n",
        "\"utility function\":\"how agent's preferences are captured which assigns a single number to express desirability of a state\",\n",
        "\"expected utility\": \"average utility value of outcomes weighted by probability outcome occurs\",\n",
        "\"value function or original utility function\": \"in deterministic env, an agent needs only a preference ranking on states\",\n",
        "\"preference elicitation\": 'involves presenting choices to the human and using observed preferences to pin down underlying utility function'\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 53,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1787
        },
        "outputId": "70b6e2f0-ae7c-4ed2-f65a-e4e4b30a570e"
      },
      "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": 54,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Most commonly studied games and 2 player turn taking perfect info, zero sum games. \n\n Perfect info = fully observable \n\n Game tree may be infinite if state space is unbounded or if rules of game allow for infinitely repeating positions\n\n Minimax search assumes both plaers play optimally\n\n Minimax alg performs complete depth-first exploration of game tree. \n\n m=max depth, b=legal moves at each point, time complexity=O(b^m) and space is O(bm)\n\n Alpha-beta pruning can be applied to trees of any depth\n\n $utility(loss,p) \\leq eval(s,p) \\leq utility(win,p)$\n\n evaluation function should be applied only to positions that are quiescent\n\n alpha-beta pruning prunes branches of the tree that can have no effect on final evaluation\n\n forward pruning prunes moves that appear to be poor mnoves but might possibly be good ones (saves computation time)\n\n beam search (one forward pruning) considers a beam of best n moves but approach is dangerous bc cannot guarentee best move is not pruned away\n\n Modern Go programs have abandoned alpha-beta search and use Monte Carlo tree search (MCTS) no h(n) but value of state is estimated as the avg utility over a num of simulations of complete games starting from the state\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n stochastic games bring closer to real life by including random element\n\n game tree must include chance nodes in addition to MAX and MIN nodes \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Making Simple Decisions\n\n How Utility Theory combines with probability theory to yield decision-theoretic agent - agent that can make rational decisions based on what it believes and what it wants.\n\n Such agents canmake decisions in contexts in which uncertainty and conflicting goals leave a logical agent with no way to decide. \n\n Goal-based agent has a binary distinction good (goal) and bad (non-goal) states.\n\n Decision-theoretic agent assigns continuous range of values to states and thus can easily choose a better state when no best state is available. \n\n Basic principle of decision theory: maximization of expected utility. \n\n Decision theory deals with choosing among actions based on desirability of immediate outcomes.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nBasis of Utility Theory.\n\n Maximum Expected Utility, seems a reasonable way to make decisions, but not the only rational way \n\n Primary issue for utility theory is to understand how preferences between complex lotteries are related to preferences between underlying states in those lotteries\n\n 6 Constraints any Reasonable Preference Relation to Obey:\n\n (1) Orderability: given 2 lotteries. rational agent must either prefer one or rate equal (cannot avoid deciding)\n\n (2) Transitivity If agent prefers A to B, and B to C, then prefers A to C\n\n (3) Continuity If some lottery B is between A and C in preference, then some probability p for which rational agent will be indifferent between getting B for sure and the lottery that yields A w probability p and C with probability 1 - p \n\n (4) Substitutability If agent is indifferent between 2 lotteries A and B, then agent is indifferent between 2 or more complex lotteries that are the same except that B is substituted for A in one of them (holds regardless of the probabilities and the other outcomes in the lotteries)\n\n (5) Monotonocity: 2 lotteries with same 2 possible outcomes, A and B. if agent prefers A to B, then agent must prefer the lottery that has a higher probability for A\n\n (6) Decompososability: Compound lotteries can reduced to simpler ones using probability. \n\n Constraints are known as axioms of utility theory (preference). \n\n\n## AIMA Chapter 16.3 Utility Functions\n Decision theory is a normative theory - describes how a rational agent should act\n\n Descriptive theory describes how actual agents (e.g. humans) really act\n\n Certainty Effect: ppl are strongly attracted to gains that are certain \n\n## Module 5 Lecture Notes\nMinimax runtime = $O(b^m)$, DFS on game tree. \n\n ALPHA-BETA PRUNING: \n\n If curr player has better choice at (1) same level (2) any point higher in the tree, player never moves to that state/node so prune it\n\n MAX is at least alpha. MIN is at most beta\n\n PRUNING GUIDELINES:\n\n - MAX: when v >= beta is backed up, MIN never selects that MAX node bc Beta is MIN's upper bound\n\n - MIN: when v <= alpha '', MAX never selects that MIN bc alpha is MAX's upper bound\n\n done well. alphabeta is $O(b^(m/2))$ rather than minimax $O(b^m)$. effective branch factor is $sqrt(b)$\n\n Expectimax: instead of MAX and MIN, has MAX and chance nodes (min nodes but outcome uncertain. expected util) \n\n## Module 5 Definitions\n* **Terminal state** - states where game has ended\n* **Game tree** - search tree that follows every sequence of moves all the way to a terminal state.\n* **Killer moves** - best moves, and to try them first is killer move heuristic\n* **Cutoff test** - return true terminal states, otherwise free to decide when to cut off search based on depth and others\n* **Quicient** - positions in which there is no pending move that would wildly swing the evaluation\n* **Utility function** - how agent's preferences are captured which assigns a single number to express desirability of a state\n* **Expected utility** - average utility value of outcomes weighted by probability outcome occurs\n* **Value function or original utility function** - in deterministic env, an agent needs only a preference ranking on states\n* **Preference elicitation** - involves presenting choices to the human and using observed preferences to pin down underlying utility function\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 = \"\"\" CSP search algs take advantage of the structure of states and use general rather than domain-specific heuristics to enable the soln of complex problems\n",
        "\\n main idea: eliminate large portions of search space at once by identifying variable/value combinations that violate the constraints\n",
        "\\n CSPs have additional advant: actions and transition model can be deduced from problem description\n",
        "\\n CSP: $X$ is set of variables $set(X_{1},...,X_{n})$. $D$ is set of domains... one for each variable. $C$ is set of constraints that specfify allowable combinations of values.\n",
        "\\n Each $C_{j}$ consists of pair $<scope, relation>$. \n",
        "\\n Different variables can have diff domains of different sizes. A Boolean variable would have domain $set(true, false)$.\n",
        "\\n CSPs deal w assignments of values to variables. Assignment that does not violate any constriants is called $consistent$ or legal assignment.\n",
        "\\n solving CSP is NP-complete in general\n",
        "\\n Why CSPs? (1) CSPs yield a natural representation for a wide variety of problems, so easy to formulate prob as CSP\n",
        "\\n Simplest CSPs involve variables that have discrete, finite domains. Discrete domain can be infinite, such as set of integers or strings\n",
        "\\n CSP w continuous domains are common in real world, best known category of continuous domain CSPs is that of linear programming problems\n",
        "\\n Simplest constrain is unary\n",
        "\\n Preference constraints can often be encoded as costs on individual variable assignments. w this, CSPs w preferences can be solved w optimization search methods (path based or local) - contraint optimization problem (aka COP, e.g. linear programs)\"\"\"\n",
        "chapter6_2 = \"\"\" Atomic state-space search alg makes progress by expanding a node to visit the successors. CSP alg has choices - generate successors by choosing new variable assignment or can do specific typ eof inference called constraint propagation (using constraints to reduce num of legal moves for a var, which can reduce the same for another var...)\n",
        "\\n Constriant propagation may be interrwined  w search or done as preprocessing (sometimes that can solve the whole problem itself)\n",
        "\\n key idea: local consistency-treat each variable as a node in a graph and each binary constraint as an edge, process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated thruout graph\n",
        "\\n Most popular alg to enforce arc consistency is AC-3 (maintains q of arcs to consider - initially q contains all arcs, but one is popped (Xi, Xj) and Xi is made arc consistent w respect to Xj. If this leaves Di unchanged, the alg moves on to nex arc, otherwise must add to q all arcs Xk, Xi where Xk is neighbor. If Di revised to nothing, then CSP has no consistent soln.\n",
        "\\n Arc consistent CSP isfaster to search bc its variables have smaller domains. Checking consistency of arc is worst case $O(cd^3)$ time, c=num binary constraints(arcs), d=domain size.\n",
        "\\n Path consistency tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables. \n",
        "\\n Stronger forms of propagation can be defined w k-consistency\n",
        "\\n CSP is bounds-consistent if for every var X, and for both the lower bound and upper bound values of X, there exists some val of Y that satisfies the constraint between X and Y for every var Y\n",
        "\\n Backtracking search keeps only a single representation of a state (assignment) and alters that representation rather than creating new ones. \n",
        "\\n Uninformed search algos could only be improved by supplying them w domain-specific heuristics\n",
        "\\n Backtracking search can be improved using domain-independent heuristics that take advantage of factored representation of CSPs\"\"\"\n",
        "chapter6_3 = \"\"\" CSPs are COMMUTATIVE - problem is comm. if order of application of any given set of actions does not matter\n",
        "\\n Simplest inference: forward checking - whenever a var X is assigned forward checking process establishes arc consistency for it \"\"\"\n",
        "chapter6_4 = \"\"\" LOCAL CONFLICTS\n",
        "\\n Constraint weighting: aims to concentrate the search on the important constraints\n",
        "\\n another advantage of local search is that it can be used in an online setting when the problem changes\"\"\"\n",
        "chapter6_5 = \"\"\" Directional arc consistency: CSP is if under an ordering of variables X1, X2..Xn, iff every Xi is arc consistenct with each Xj j>i (topo sort)\n",
        "\\n Any tree w n nodes has n-1 edges, can make this graph directed arc-consistent in $O(n)$ steps, each must compare up to $d$ possible domain values for a total time of $O(nd^2)$\n",
        "\\n Cutset conditioning: first way to reduce constraint graph to a tree involves assigning values to some variables so that remaining variables form a tree\n",
        "\\n Second way to reduce constraint graph to tree is constructing tree decomposition of the constraint graph: transformation of original graph into tree where each node in tree consists of set of variables\n",
        "\\n ^must satisfy 3 requirements: (1) every variable in the original problem appears in at least one of the tree nodes.\n",
        "(2) if two variables are connected by a constraint in the original problem, they must appear\n",
        "together (along with the constraint) in at least one of the tree nodes.\n",
        "(3) if a variable appears in two nodes in the tree, it must appear in every node along the\n",
        "path connecting those nodes.\n",
        "\\n Tree width of tree decomp of a graph is one less than the size of largest node. Problem solved in $O(nd^{w+1})$ time, so CSPs w constraint graphs of bounded tree width are solvable in polynomial time\n",
        "\n",
        "```\n",
        "{\n",
        "  dev AC3 (CSP) : return CSP (reduced dom)\n",
        "    inputs : csp, binary w var {X_{1}, ..., X_{n}}. \n",
        "    local vars : q of arcs, initially all arcs in CSP\n",
        "\n",
        "    while q not empty : \n",
        "      ($X_{i}$, $X_{j}$) = q.pop()\n",
        "      if REMOVE_INCONSISTENT_VALUES($X_{i}$, $X_{j}$) : \n",
        "        for each $X_{k}$ in (NEIGHBORS[$X_{i}$ - $X_{j}$] : \n",
        "          add ($X_{k}$, $X_{i}$)\n",
        "}\n",
        "{\n",
        "  def REMOVE_INCONSISTENT_VALUES($X_{i}$, $X_{j}$) : ret true iff removed value\n",
        "    removed = False\n",
        "    for each $x$ in DOMAIN[$X_{i}$] : \n",
        "      if no value $y$ in DOMAIN[$X_{j}$] allows $(x,y)$ to satisfy constaints between $X_{i}$ and $X_{j}$ : \n",
        "        delete $x$ from DOMAIN[$X_{i}$]\n",
        "        removed = True\n",
        "    return removed\n",
        "}\n",
        "```\n",
        "\\n each arc (i,j) inserted in q d times\n",
        "\\n $O(n^{2}d^{3})$. if no crossing edges(planar constraint graph), arc linear $O(nd^{3})$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP as a search problem:\n",
        "\\n initial state: empty\n",
        "\\n successor function, goal test, path cost\n",
        "\\n Order in assignment of vars doesnt matter\n",
        "\\n instead of $n!d^n$ leaves, can be $d^n$ leaves bc communicative for variable assignments\n",
        "\\n Improving backtracking:\n",
        "\\n (1) Next var assigned is most constrained variable (Minimum remaining values heuristic). if tie, most constraining var. (2). least constraining var (3) forward checking to detect failure ahead of time\n",
        "\\n Contraint propagation: repeatedly enforce constraints to locally rid of failures ahead of time\n",
        "\\n Local Consistency: Node consistent, arc consistent.\n",
        "\\n Arc consistency: for every val in Di, some value in Dj that satisfies binary constraint btw Xi and Xj\n",
        "\\n AC3: each iter, examine X where 1<= neighboar lost a val previously\n",
        "\\n removing val forom ail can only make head arc const to tail\n",
        "\\n if Xi loses val only bc of arc inconsistency w Y, dont check Y next\n",
        "\\n Solving arbitrary CSSP takes exponential time in num of vars\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent\" : \"assignment that does not violate any constriaints (aka legal assignment)\",\n",
        "\"partial soln\":\"partial assignment that is consistent\",\n",
        "\"global constraint\":\"constraint involving arbitrary num of vars (not all)\",\n",
        "\"preference constraints\":\"indicates which soln are prefered\",\n",
        "\"node consistent\":\"single variable is if all values in that domain satisfy var's unary constraints\",\n",
        "\"arc consistent\":\"every val in domain satisfies variable's binary constraints\",\n",
        "\"k-consistent\":\"any set of k-1 vars and any consistent assignment to those, consistent val can always be assigned to any kth-var\",\n",
        "\"strongly k consistent\":\"k const, k-1 const k-2 const...1-const\",\n",
        "\"constraint learning\":\"finding a mininum set of variables from conflict set that causes the problem\",\n",
        "\"value symmetry\" : \"would like to reduce search space by factor of d! by breaking symmetry in assignments -> symmetry-breaking constraint\",\n",
        "\"backmarking\":\"simple method-consistent and inconsistent pairwise assignmnets are saved and used to avoid rechecking constraints\",\n",
        "\"higher-order constraints\" : \"constraints w 2+ vars\",\n",
        "\"MAC\":\"maintaining arc consistency\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2404
        },
        "outputId": "fc33a748-7342-4f6a-feb5-0940d2d9594f"
      },
      "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": 56,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP search algs take advantage of the structure of states and use general rather than domain-specific heuristics to enable the soln of complex problems\n\n main idea: eliminate large portions of search space at once by identifying variable/value combinations that violate the constraints\n\n CSPs have additional advant: actions and transition model can be deduced from problem description\n\n CSP: $X$ is set of variables $set(X_{1},...,X_{n})$. $D$ is set of domains... one for each variable. $C$ is set of constraints that specfify allowable combinations of values.\n\n Each $C_{j}$ consists of pair $<scope, relation>$. \n\n Different variables can have diff domains of different sizes. A Boolean variable would have domain $set(true, false)$.\n\n CSPs deal w assignments of values to variables. Assignment that does not violate any constriants is called $consistent$ or legal assignment.\n\n solving CSP is NP-complete in general\n\n Why CSPs? (1) CSPs yield a natural representation for a wide variety of problems, so easy to formulate prob as CSP\n\n Simplest CSPs involve variables that have discrete, finite domains. Discrete domain can be infinite, such as set of integers or strings\n\n CSP w continuous domains are common in real world, best known category of continuous domain CSPs is that of linear programming problems\n\n Simplest constrain is unary\n\n Preference constraints can often be encoded as costs on individual variable assignments. w this, CSPs w preferences can be solved w optimization search methods (path based or local) - contraint optimization problem (aka COP, e.g. linear programs)\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Atomic state-space search alg makes progress by expanding a node to visit the successors. CSP alg has choices - generate successors by choosing new variable assignment or can do specific typ eof inference called constraint propagation (using constraints to reduce num of legal moves for a var, which can reduce the same for another var...)\n\n Constriant propagation may be interrwined  w search or done as preprocessing (sometimes that can solve the whole problem itself)\n\n key idea: local consistency-treat each variable as a node in a graph and each binary constraint as an edge, process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated thruout graph\n\n Most popular alg to enforce arc consistency is AC-3 (maintains q of arcs to consider - initially q contains all arcs, but one is popped (Xi, Xj) and Xi is made arc consistent w respect to Xj. If this leaves Di unchanged, the alg moves on to nex arc, otherwise must add to q all arcs Xk, Xi where Xk is neighbor. If Di revised to nothing, then CSP has no consistent soln.\n\n Arc consistent CSP isfaster to search bc its variables have smaller domains. Checking consistency of arc is worst case $O(cd^3)$ time, c=num binary constraints(arcs), d=domain size.\n\n Path consistency tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables. \n\n Stronger forms of propagation can be defined w k-consistency\n\n CSP is bounds-consistent if for every var X, and for both the lower bound and upper bound values of X, there exists some val of Y that satisfies the constraint between X and Y for every var Y\n\n Backtracking search keeps only a single representation of a state (assignment) and alters that representation rather than creating new ones. \n\n Uninformed search algos could only be improved by supplying them w domain-specific heuristics\n\n Backtracking search can be improved using domain-independent heuristics that take advantage of factored representation of CSPs\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n CSPs are COMMUTATIVE - problem is comm. if order of application of any given set of actions does not matter\n\n Simplest inference: forward checking - whenever a var X is assigned forward checking process establishes arc consistency for it \n\n## AIMA Chapter 6.4 Local Search for CSPs\n LOCAL CONFLICTS\n\n Constraint weighting: aims to concentrate the search on the important constraints\n\n another advantage of local search is that it can be used in an online setting when the problem changes\n\n## AIMA Chapter 6.5 The Structure of Problems\n Directional arc consistency: CSP is if under an ordering of variables X1, X2..Xn, iff every Xi is arc consistenct with each Xj j>i (topo sort)\n\n Any tree w n nodes has n-1 edges, can make this graph directed arc-consistent in $O(n)$ steps, each must compare up to $d$ possible domain values for a total time of $O(nd^2)$\n\n Cutset conditioning: first way to reduce constraint graph to a tree involves assigning values to some variables so that remaining variables form a tree\n\n Second way to reduce constraint graph to tree is constructing tree decomposition of the constraint graph: transformation of original graph into tree where each node in tree consists of set of variables\n\n ^must satisfy 3 requirements: (1) every variable in the original problem appears in at least one of the tree nodes.\n(2) if two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\n(3) if a variable appears in two nodes in the tree, it must appear in every node along the\npath connecting those nodes.\n\n Tree width of tree decomp of a graph is one less than the size of largest node. Problem solved in $O(nd^{w+1})$ time, so CSPs w constraint graphs of bounded tree width are solvable in polynomial time\n\n```\n{\n  dev AC3 (CSP) : return CSP (reduced dom)\n    inputs : csp, binary w var {X_{1}, ..., X_{n}}. \n    local vars : q of arcs, initially all arcs in CSP\n\n    while q not empty : \n      ($X_{i}$, $X_{j}$) = q.pop()\n      if REMOVE_INCONSISTENT_VALUES($X_{i}$, $X_{j}$) : \n        for each $X_{k}$ in (NEIGHBORS[$X_{i}$ - $X_{j}$] : \n          add ($X_{k}$, $X_{i}$)\n}\n{\n  def REMOVE_INCONSISTENT_VALUES($X_{i}$, $X_{j}$) : ret true iff removed value\n    removed = False\n    for each $x$ in DOMAIN[$X_{i}$] : \n      if no value $y$ in DOMAIN[$X_{j}$] allows $(x,y)$ to satisfy constaints between $X_{i}$ and $X_{j}$ : \n        delete $x$ from DOMAIN[$X_{i}$]\n        removed = True\n    return removed\n}\n```\n\n each arc (i,j) inserted in q d times\n\n $O(n^{2}d^{3})$. if no crossing edges(planar constraint graph), arc linear $O(nd^{3})$\n\n\n\n## Module 6 Lecture Notes\n CSP as a search problem:\n\n initial state: empty\n\n successor function, goal test, path cost\n\n Order in assignment of vars doesnt matter\n\n instead of $n!d^n$ leaves, can be $d^n$ leaves bc communicative for variable assignments\n\n Improving backtracking:\n\n (1) Next var assigned is most constrained variable (Minimum remaining values heuristic). if tie, most constraining var. (2). least constraining var (3) forward checking to detect failure ahead of time\n\n Contraint propagation: repeatedly enforce constraints to locally rid of failures ahead of time\n\n Local Consistency: Node consistent, arc consistent.\n\n Arc consistency: for every val in Di, some value in Dj that satisfies binary constraint btw Xi and Xj\n\n AC3: each iter, examine X where 1<= neighboar lost a val previously\n\n removing val forom ail can only make head arc const to tail\n\n if Xi loses val only bc of arc inconsistency w Y, dont check Y next\n\n Solving arbitrary CSSP takes exponential time in num of vars\n\n## Module 6 Definitions\n* **Consistent** - assignment that does not violate any constriaints (aka legal assignment)\n* **Partial soln** - partial assignment that is consistent\n* **Global constraint** - constraint involving arbitrary num of vars (not all)\n* **Preference constraints** - indicates which soln are prefered\n* **Node consistent** - single variable is if all values in that domain satisfy var's unary constraints\n* **Arc consistent** - every val in domain satisfies variable's binary constraints\n* **K-consistent** - any set of k-1 vars and any consistent assignment to those, consistent val can always be assigned to any kth-var\n* **Strongly k consistent** - k const, k-1 const k-2 const...1-const\n* **Constraint learning** - finding a mininum set of variables from conflict set that causes the problem\n* **Value symmetry** - would like to reduce search space by factor of d! by breaking symmetry in assignments -> symmetry-breaking constraint\n* **Backmarking** - simple method-consistent and inconsistent pairwise assignmnets are saved and used to avoid rechecking constraints\n* **Higher-order constraints** - constraints w 2+ vars\n* **Mac** - maintaining arc consistency\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 = \"\"\" so far, problem solving agents have performed a search over states in order to find a plan. the representation of states has been atomic\n",
        "\\n 2 kinds of sentences: axioms (sentence given) and derived sentences (new sentence derived from others sentences)\n",
        "\\n knowledge base can contain some background info about the world\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Logical reasoning involves entailment relation between sentence. entailment is the idea that a sentence follows logically from another. a|= b iff M(a) _c_ M(b) (a entails B iff model of a is subset of model b) \n",
        "\\n Entailment can be applied to derive conclusions (logical inference)\n",
        "\\n <=> (iff, not XOR)\n",
        "\\n Horn clauses are closed under resolution (if apply resolution to horn clause, get back a horn clause) \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" resolution alg is complete\n",
        "\\n forward chaining is a kind of data-driven reasoning. agent can start w known data adding premises as new percepts come in and then incrementally apply the forward chaning alg to derive new conclusions. doesnt have to have specific query in mind to do so\n",
        "\\n backward chaining works backwards from query. if query known to be true, no work needed. else alg finds implications in KB whose conclusions is the query. if all premises of one of those can be proved to be true (via backward chaining) then query is true \n",
        "\\n backward chaining is form of goal directed reasoning\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" how do agents reason about the world? \n",
        "\\n Cutset conditioning used to reduce general CSP to tree structured one\n",
        "\\n \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use process of reasoning over internal representation of knowledge to decide what actions to take\", \n",
        "\"knowledge base\" :\" set of sentences (forms complex representation of how the world works)\",\n",
        "\"sentence\":\"expressed in a language called knowledge representation language and represents some assertion of the world\",\n",
        "\"inference\": \"derive new sentences from old\",\n",
        "\"logic\": 'must define semantics or meaning of sentences',   \n",
        "'sound':'inference algorithm should only derive entailed sentences',\n",
        "'complete':'inference alg is complete if it can derive all sentences that are entailed',\n",
        "\"definite clause\":\"disjunction of literals where exactly one is positive\",\n",
        "\"horn clause\":'disjunction of literals where at least one is positive (includes definite clauses and ones w no pos literals',\n",
        "}\n",
        "\n"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 935
        },
        "outputId": "ce45c0c9-0a11-4b13-9240-ea1431a629e7"
      },
      "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": 58,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n so far, problem solving agents have performed a search over states in order to find a plan. the representation of states has been atomic\n\n 2 kinds of sentences: axioms (sentence given) and derived sentences (new sentence derived from others sentences)\n\n knowledge base can contain some background info about the world\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Logical reasoning involves entailment relation between sentence. entailment is the idea that a sentence follows logically from another. a|= b iff M(a) _c_ M(b) (a entails B iff model of a is subset of model b) \n\n Entailment can be applied to derive conclusions (logical inference)\n\n <=> (iff, not XOR)\n\n Horn clauses are closed under resolution (if apply resolution to horn clause, get back a horn clause) \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 resolution alg is complete\n\n forward chaining is a kind of data-driven reasoning. agent can start w known data adding premises as new percepts come in and then incrementally apply the forward chaning alg to derive new conclusions. doesnt have to have specific query in mind to do so\n\n backward chaining works backwards from query. if query known to be true, no work needed. else alg finds implications in KB whose conclusions is the query. if all premises of one of those can be proved to be true (via backward chaining) then query is true \n\n backward chaining is form of goal directed reasoning\n\n## Module 7 Lecture Notes\n how do agents reason about the world? \n\n Cutset conditioning used to reduce general CSP to tree structured one\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use process of reasoning over internal representation of knowledge to decide what actions to take\n* **Knowledge base** -  set of sentences (forms complex representation of how the world works)\n* **Sentence** - expressed in a language called knowledge representation language and represents some assertion of the world\n* **Inference** - derive new sentences from old\n* **Logic** - must define semantics or meaning of sentences\n* **Sound** - inference algorithm should only derive entailed sentences\n* **Complete** - inference alg is complete if it can derive all sentences that are entailed\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at least one is positive (includes definite clauses and ones w no pos literals\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": 0
        },
        "id": "T3cm1WV542_a",
        "outputId": "bf30a6ce-0ae0-45d6-8f97-454aa5bb005a"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 62,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n so far, problem solving agents have performed a search over states in order to find a plan. the representation of states has been atomic\n\n 2 kinds of sentences: axioms (sentence given) and derived sentences (new sentence derived from others sentences)\n\n knowledge base can contain some background info about the world\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Logical reasoning involves entailment relation between sentence. entailment is the idea that a sentence follows logically from another. a|= b iff M(a) _c_ M(b) (a entails B iff model of a is subset of model b) \n\n Entailment can be applied to derive conclusions (logical inference)\n\n <=> (iff, not XOR)\n\n Horn clauses are closed under resolution (if apply resolution to horn clause, get back a horn clause) \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 resolution alg is complete\n\n forward chaining is a kind of data-driven reasoning. agent can start w known data adding premises as new percepts come in and then incrementally apply the forward chaning alg to derive new conclusions. doesnt have to have specific query in mind to do so\n\n backward chaining works backwards from query. if query known to be true, no work needed. else alg finds implications in KB whose conclusions is the query. if all premises of one of those can be proved to be true (via backward chaining) then query is true \n\n backward chaining is form of goal directed reasoning\n\n## Module 7 Lecture Notes\n how do agents reason about the world? \n\n Cutset conditioning used to reduce general CSP to tree structured one\n\n \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use process of reasoning over internal representation of knowledge to decide what actions to take\n* **Knowledge base** -  set of sentences (forms complex representation of how the world works)\n* **Sentence** - expressed in a language called knowledge representation language and represents some assertion of the world\n* **Inference** - derive new sentences from old\n* **Logic** - must define semantics or meaning of sentences\n* **Sound** - inference algorithm should only derive entailed sentences\n* **Complete** - inference alg is complete if it can derive all sentences that are entailed\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at least one is positive (includes definite clauses and ones w no pos literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}