{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "cw5IpDLCZa4W",
        "s3Uk9gQTevcj"
      ]
    },
    "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": "1799d289-8b74-4045-804e-b3bf356b7914"
      },
      "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": 146,
      "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": "4e9f4a68-70b1-4bfa-e4d4-fa509483fce0"
      },
      "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": 147,
      "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 = \"Zachary Hahn\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 148,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DmNbXD_MSRRm"
      },
      "source": [
        ""
      ],
      "execution_count": 148,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "- **Rationality**- making the right decision\n",
        "- Turing Test\n",
        "  - **Natural Language Processing**- ability to communicate with human\n",
        "  - **Knowledge representation**- remember information from before or during conversation\n",
        "  - **Automated reasoning**- Use remembered info to come to conclusions\n",
        "  - **Machine learning**- Adapt, recognize patterns and expand on them\n",
        "  - Total Turing Test\n",
        "    - **Computer vision**- in order to percieve\n",
        "    - **Robotics**- in order to move   \n",
        "- Thinking humanly\n",
        "  - **Cognitive Science** - Tries to figure out how the human mind works using tests\n",
        "- Thinking rationally\n",
        "  - Use logic to find a solution, if there is one\n",
        "- Actinng rationally: Rational Agent\n",
        "  - Acting perfectly rational is impossible in complex situations\n",
        "  - **Limited Rationality** - choosing the best option when not possible to do all calculations\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \n",
        "- **Weak AI**- act as intillegent\n",
        "- **Strong AI**- are intllegent (not simulating intellegennce)\n",
        "- **Qualification Problem**- hard to define all behaviours in a set of logical rules\n",
        "- **Embodied cognition**- study brain and body to gether, not seperately\n",
        "- **Good Old-Fashioned AI (GOFAI)**\n",
        "- **Qualification problem**- \n",
        "- **Anytime Algorithms**- Solution quality increases with time, so at any given time it has its best solution\n",
        "  - ex) iterative deepinging search\n",
        "- **Decision-theoretic metareasoning**- Computation values is dependent on the cost (time) and benefit (solution quality)\n",
        "  - Guarentees anytime property\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "- Chinese room- computers have no understanding\n",
        "- **Polite Convention**- assuming everyone thinks\n",
        "- Biological naturalism\n",
        "- **Conciousness**- awareness of the outside owrld\n",
        "- **Qualia**- nature of expereince\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "- **Agent** acts on environment through **effectors**, perceieves usning **sensors**\"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "- **Rational Agent**\n",
        "  - Correct action- action that leads to success \n",
        "  - **Performance Measure**- used to tell how succesful an agent is\n",
        "  - **Omniscient** agent knows actual outcomes of its actions (impossible) \n",
        "  - Rationality is concerned with expected success given what it has percieved\n",
        "  - Rationality depends on:<br>\n",
        "    1) Performance measure<br>\n",
        "    2) **Percept sequence**- history of what the agent has percieved<br>\n",
        "    3) What an agent knows<br>\n",
        "    4) Action that agent is capable of<br>\n",
        "  - **Ideal Rational Agent**- Performs action that maximizes performance measure (given precept history and knowledge)\n",
        "- **Mapping**- list of actions from precept sequences\n",
        "  - **Ideal mapping**\n",
        "- **Autonomy**- actions based on more than just built in knowledge \n",
        "  - Behaviour determined by its own experiences\n",
        "  - Should be able to operate in multiple environments  \"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- **Task Environments**- the area which rational agents can solve problems\n",
        "- Defining a task environemnt:\n",
        "  - **P**erformance (ex. safe, fuel efficient, minimize trip time, max profits)\n",
        "  - **E**nvironemnt (ex. traffic, pedestrians, highway)\n",
        "  - **A**ctuators (ex. accelerator, break, output display)\n",
        "  - **S**ensors (ex. camera, lidar, ultrasound)  \n",
        "- Environment Types:\n",
        "  - **Fully observable**- knowing the complete state of an environment\n",
        "  - **Partially observable**- Only know part of the state (innacurate sensors, missing data)\n",
        "  - **Unobservable**- no sensors\n",
        "- Agent Types:\n",
        "  - **Single agent**\n",
        "  - **Multiagent**- Another agent that is working to maximize its performance\n",
        "    - **Competitive**- Maximizing A success decreases B success (chess)\n",
        "    - **Cooperative**- work together to succeed (avoid car crash)\n",
        "- Deterministic\n",
        "  - **Deterministic**- state is completely influenced by the current state and the next action performed\n",
        "  - **Nondeterministic**- Not deterministic\n",
        "  - **Stochastic**- non-deterministic but specifically deals with percentages (ex. 25% chaince of rain)\n",
        "- Episodic\n",
        "  - **Episodic**- percieves situation, performs action with no future implication\n",
        "  - **Sequential**- decisions can effect future decisions (chess, driving)\n",
        "- Static\n",
        "  - **Static**- Environment remains same until action is taken (chess)\n",
        "  - **Dynamic**- Environment always changing (road while driving)\n",
        "  - **Semidynamic**- ex. Chess with a clock\n",
        "- Discrete\n",
        "  - **Discrete**- Limited states and actions (ex. Chess)\n",
        "  - **Continuous**- Unlimited states and actions (ex. Driving)\n",
        "- Known\n",
        "  - **Known**- Outcome of actions is known \n",
        "  - **Unknown**- Outcome of actions is unkown\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- **Agent Programs** implement an **Agent Function**\n",
        "- **Agent Architecture**- the physical sensors and actuators that make an agent\n",
        "  - Receive precepts, run the program, send actions to actuators\n",
        "agent = architecture + program\n",
        "-  **Agent Programs**\n",
        "  - Skeleton: input is precepts, return action\n",
        "  - Agent program only takes current precept, agent function depends on precept history\n",
        "  - Table driven agents are too large\n",
        "- **Simple Reflex Agents**- only take action on current precept\n",
        "  - **Condition-action rule**- condition triggers an action (ex. car infront breaking -> initiate break)\n",
        "    - A.k.a situation-action rules, productions, if-then rules\n",
        "  - infinite loops are a problem with such simplicity\n",
        "  - **Randomization**- makes a random choice if certain criteria is met\n",
        "    - This might be better than a deterministic agent\n",
        "- **Model-based reflex agents**\n",
        "  - **Internal State**- remembers past precepts\n",
        "  - Requires:\n",
        "    - **Transition Model**- how the agents world channges with time\n",
        "    - **Sensor Model**- how the agent percieves the world\n",
        "- **Goal-based agents**\n",
        "  - More flexible\n",
        "  - Agent makes an action in order to achieve a specific goal\n",
        "- **Utility based agents**\n",
        "  - **utility**- quality of the solution of the agent \n",
        "  - **utility function**- performance measure of utility\n",
        "  - **expected utility**- utility when there is uncertainty \n",
        "  - **model-free agent**- learns best action without knowing direct impact onn environemnt\n",
        "- **Learning Agent**\n",
        "  - **Learning element**- makes improvements\n",
        "    - uses feedback from **critic**\n",
        "  - **Performance element**- makes actions\n",
        "  - **Problem generator**- Suggests new action that are unfamiliar\n",
        "- **Atomic Representation**- each state is a \"black box\"\n",
        "- **Factored Representation**- states are represented as **variables**/**attributes** that are given a value.\n",
        "- **Structured Representation**- objects and relationships are defined explicitly.\n",
        "- **Localist Represenation**-  1:1 mapping of concept to a physical memory location\n",
        "- **Distributed Representation**- concepts are spread over memory locations (more robust)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 149,
      "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": 2844
        },
        "cellView": "form",
        "outputId": "d052cbff-b97b-4049-fd53-3850abb4f070"
      },
      "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": 150,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n- **Rationality**- making the right decision\n- Turing Test\n  - **Natural Language Processing**- ability to communicate with human\n  - **Knowledge representation**- remember information from before or during conversation\n  - **Automated reasoning**- Use remembered info to come to conclusions\n  - **Machine learning**- Adapt, recognize patterns and expand on them\n  - Total Turing Test\n    - **Computer vision**- in order to percieve\n    - **Robotics**- in order to move   \n- Thinking humanly\n  - **Cognitive Science** - Tries to figure out how the human mind works using tests\n- Thinking rationally\n  - Use logic to find a solution, if there is one\n- Actinng rationally: Rational Agent\n  - Acting perfectly rational is impossible in complex situations\n  - **Limited Rationality** - choosing the best option when not possible to do all calculations\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \n- **Weak AI**- act as intillegent\n- **Strong AI**- are intllegent (not simulating intellegennce)\n- **Qualification Problem**- hard to define all behaviours in a set of logical rules\n- **Embodied cognition**- study brain and body to gether, not seperately\n- **Good Old-Fashioned AI (GOFAI)**\n- **Qualification problem**- \n- **Anytime Algorithms**- Solution quality increases with time, so at any given time it has its best solution\n  - ex) iterative deepinging search\n- **Decision-theoretic metareasoning**- Computation values is dependent on the cost (time) and benefit (solution quality)\n  - Guarentees anytime property\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- Chinese room- computers have no understanding\n- **Polite Convention**- assuming everyone thinks\n- Biological naturalism\n- **Conciousness**- awareness of the outside owrld\n- **Qualia**- nature of expereince\n \n\n## AIMA 2.1 Agents and Environments\n \n- **Agent** acts on environment through **effectors**, perceieves usning **sensors**\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \n- **Rational Agent**\n  - Correct action- action that leads to success \n  - **Performance Measure**- used to tell how succesful an agent is\n  - **Omniscient** agent knows actual outcomes of its actions (impossible) \n  - Rationality is concerned with expected success given what it has percieved\n  - Rationality depends on:<br>\n    1) Performance measure<br>\n    2) **Percept sequence**- history of what the agent has percieved<br>\n    3) What an agent knows<br>\n    4) Action that agent is capable of<br>\n  - **Ideal Rational Agent**- Performs action that maximizes performance measure (given precept history and knowledge)\n- **Mapping**- list of actions from precept sequences\n  - **Ideal mapping**\n- **Autonomy**- actions based on more than just built in knowledge \n  - Behaviour determined by its own experiences\n  - Should be able to operate in multiple environments  \n\n## AIMA 2.3 The Nature of Environments\n\n- **Task Environments**- the area which rational agents can solve problems\n- Defining a task environemnt:\n  - **P**erformance (ex. safe, fuel efficient, minimize trip time, max profits)\n  - **E**nvironemnt (ex. traffic, pedestrians, highway)\n  - **A**ctuators (ex. accelerator, break, output display)\n  - **S**ensors (ex. camera, lidar, ultrasound)  \n- Environment Types:\n  - **Fully observable**- knowing the complete state of an environment\n  - **Partially observable**- Only know part of the state (innacurate sensors, missing data)\n  - **Unobservable**- no sensors\n- Agent Types:\n  - **Single agent**\n  - **Multiagent**- Another agent that is working to maximize its performance\n    - **Competitive**- Maximizing A success decreases B success (chess)\n    - **Cooperative**- work together to succeed (avoid car crash)\n- Deterministic\n  - **Deterministic**- state is completely influenced by the current state and the next action performed\n  - **Nondeterministic**- Not deterministic\n  - **Stochastic**- non-deterministic but specifically deals with percentages (ex. 25% chaince of rain)\n- Episodic\n  - **Episodic**- percieves situation, performs action with no future implication\n  - **Sequential**- decisions can effect future decisions (chess, driving)\n- Static\n  - **Static**- Environment remains same until action is taken (chess)\n  - **Dynamic**- Environment always changing (road while driving)\n  - **Semidynamic**- ex. Chess with a clock\n- Discrete\n  - **Discrete**- Limited states and actions (ex. Chess)\n  - **Continuous**- Unlimited states and actions (ex. Driving)\n- Known\n  - **Known**- Outcome of actions is known \n  - **Unknown**- Outcome of actions is unkown\n\n\n\n## AIMA 2.4 The Structure of Agents\n\n- **Agent Programs** implement an **Agent Function**\n- **Agent Architecture**- the physical sensors and actuators that make an agent\n  - Receive precepts, run the program, send actions to actuators\nagent = architecture + program\n-  **Agent Programs**\n  - Skeleton: input is precepts, return action\n  - Agent program only takes current precept, agent function depends on precept history\n  - Table driven agents are too large\n- **Simple Reflex Agents**- only take action on current precept\n  - **Condition-action rule**- condition triggers an action (ex. car infront breaking -> initiate break)\n    - A.k.a situation-action rules, productions, if-then rules\n  - infinite loops are a problem with such simplicity\n  - **Randomization**- makes a random choice if certain criteria is met\n    - This might be better than a deterministic agent\n- **Model-based reflex agents**\n  - **Internal State**- remembers past precepts\n  - Requires:\n    - **Transition Model**- how the agents world channges with time\n    - **Sensor Model**- how the agent percieves the world\n- **Goal-based agents**\n  - More flexible\n  - Agent makes an action in order to achieve a specific goal\n- **Utility based agents**\n  - **utility**- quality of the solution of the agent \n  - **utility function**- performance measure of utility\n  - **expected utility**- utility when there is uncertainty \n  - **model-free agent**- learns best action without knowing direct impact onn environemnt\n- **Learning Agent**\n  - **Learning element**- makes improvements\n    - uses feedback from **critic**\n  - **Performance element**- makes actions\n  - **Problem generator**- Suggests new action that are unfamiliar\n- **Atomic Representation**- each state is a \"black box\"\n- **Factored Representation**- states are represented as **variables**/**attributes** that are given a value.\n- **Structured Representation**- objects and relationships are defined explicitly.\n- **Localist Represenation**-  1:1 mapping of concept to a physical memory location\n- **Distributed Representation**- concepts are spread over memory locations (more robust)\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" 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": 151,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 207
        },
        "outputId": "91d698c7-4991-4fb2-ff68-687623d4e384"
      },
      "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": 152,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "**Problem-Solving Agents**\n",
        "- **Goal Formulation**- creating goals that then influence behaviour\n",
        "- **Problem Formulation**- the states and actions the agent considers\n",
        "- **Search**- Simulating sequences until one sequences accomplishes the goal (**solution**)\n",
        "- **Execution**- performing the action of the solution\n",
        "- **Open-loop**- agent ignores precepts on the way to solution\n",
        "- **Closed-loop**- agent possibly corrects itself on path (ex. used if environemtn is nondeterministic)\n",
        "- **Problem Definition**:\n",
        "  - States or State Space\n",
        "  - Initial State\n",
        "  - Goal States\n",
        "  - Actions\n",
        "  - Transisiton model- result of certain action\n",
        "  - Action cost function\n",
        "- **Path**- sequence of actions\n",
        "- **Optimal Solution**- lowest possible cost\n",
        "- **Model**- mathematical model\n",
        "- **Abstration**- removing detail from a problem representation\n",
        "  - valid if we can use the general solution in the more detailed world\n",
        "  - Ex. finding shortest way to Arad without worrying about roads or driver skill\n",
        "  \"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "- **Standardized Problems**\n",
        "  - ex) grid world, vacuum world\n",
        "  - **States**\n",
        "  - **Initial State**\n",
        "  - **Actions**- \n",
        "  - **Transition Model**\n",
        "  - **Goal States**\n",
        "  - **Action Cost**\n",
        "- **Real-world Problems**\n",
        "  - ex) route finding problem, VLSI layout (positioning components to minimize area on a chip)\n",
        "  - **States**\n",
        "  - **Initial State**\n",
        "  - **Actions**- \n",
        "  - **Transition Model**\n",
        "  - **Goal States**\n",
        "  - **Action Cost** \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "- **Search Algorithm**- solves a searhch problem\n",
        "- **node**- state in a **search tree**\n",
        "- **Search Tree** is different from a **State Space** because state space has all possible states and the actions while search tree has the paths between the states.\n",
        "- **Expand** a node by taking an action, thus **generating** a new node\n",
        "- **Frontier** seperates the region that has been explore and region that has yet to be explored\n",
        "- **Best First Search**- choose node with smallest value from evaluation function f(n)\n",
        "- Data stuctures\n",
        "  - Frontier\n",
        "    - **Queue**\n",
        "      - **Priority Queue**- pops node with lowes f(n)\n",
        "      - **FIFO**- pops node that was added to queue first\n",
        "      - **LIFO** (aka **stack**)- pops node was added to queue last (most recently)\n",
        "      - Reached states should be stored as a lookup table (dict)\n",
        "- **Redundant Paths**\n",
        "  - **Graph search**- checks for redundnat paths\n",
        "  - **Tree search**- does not check for redundant paths\n",
        "  - Check for cycles\n",
        "- Measuring problem-solving\n",
        "  - **Completeness**- returns solution if there is one, returns failure if none\n",
        "    - Algorithm must be **systematic**\n",
        "  - **Optimal**- returns solution with lowest path cost\n",
        "  - **Time complexity**- how long it takes to find solution\n",
        "  - **Space complexity**- how much memory is needed to find a solution\n",
        "- **depth**- d, m- maximum depth\n",
        "- **branching factor**- b, number of successors\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "- **Breadth-first Search**\n",
        "  - **early goal test**- check if node is a solution as soon as its generated\n",
        "  - **late goal test**- wait for node to be popped off queue\n",
        "  - Optimal if all actions have same cost, always complete\n",
        "  - Time and Space Complexity: O(b^d)\n",
        "- **Uniform-Cost Search**/**Djkstra's Algorithm**\n",
        "  - Check for goal when expanding\n",
        "  - Complete and optimal\n",
        "- **Depth-first Search**\n",
        "  - Not optimal, incmoplete\n",
        "  - Much smaller memory than breadth-first or best-first O(bm)\n",
        "  - **Backtracking Search**- uses less memory, one successor generated at a time\n",
        "- **Depth limited** and **Iterative Deepeninng**\n",
        "  - **Depth limited**\n",
        "    - depth limit l, if pick l badly than will fail\n",
        "    - **diameter**- known good value for depth limit l\n",
        "  - **Iterative Deepining**\n",
        "    - increases depth every iteration\n",
        "    - Optimal when all actions have same cost\n",
        "    - Complete\n",
        "- **Bidirectional Search**\n",
        "  - Searches from initial state and goal state\n",
        "\n",
        "   \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 153,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1976
        },
        "outputId": "53a3d684-92d0-4939-f9b8-6e0bfb77f32c"
      },
      "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": 154,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n**Problem-Solving Agents**\n- **Goal Formulation**- creating goals that then influence behaviour\n- **Problem Formulation**- the states and actions the agent considers\n- **Search**- Simulating sequences until one sequences accomplishes the goal (**solution**)\n- **Execution**- performing the action of the solution\n- **Open-loop**- agent ignores precepts on the way to solution\n- **Closed-loop**- agent possibly corrects itself on path (ex. used if environemtn is nondeterministic)\n- **Problem Definition**:\n  - States or State Space\n  - Initial State\n  - Goal States\n  - Actions\n  - Transisiton model- result of certain action\n  - Action cost function\n- **Path**- sequence of actions\n- **Optimal Solution**- lowest possible cost\n- **Model**- mathematical model\n- **Abstration**- removing detail from a problem representation\n  - valid if we can use the general solution in the more detailed world\n  - Ex. finding shortest way to Arad without worrying about roads or driver skill\n  \n\n## AIMA Chapter 3.2 Example Problems\n\n- **Standardized Problems**\n  - ex) grid world, vacuum world\n  - **States**\n  - **Initial State**\n  - **Actions**- \n  - **Transition Model**\n  - **Goal States**\n  - **Action Cost**\n- **Real-world Problems**\n  - ex) route finding problem, VLSI layout (positioning components to minimize area on a chip)\n  - **States**\n  - **Initial State**\n  - **Actions**- \n  - **Transition Model**\n  - **Goal States**\n  - **Action Cost** \n\n## AIMA Chapter 3.3 Search Algorithms\n\n- **Search Algorithm**- solves a searhch problem\n- **node**- state in a **search tree**\n- **Search Tree** is different from a **State Space** because state space has all possible states and the actions while search tree has the paths between the states.\n- **Expand** a node by taking an action, thus **generating** a new node\n- **Frontier** seperates the region that has been explore and region that has yet to be explored\n- **Best First Search**- choose node with smallest value from evaluation function f(n)\n- Data stuctures\n  - Frontier\n    - **Queue**\n      - **Priority Queue**- pops node with lowes f(n)\n      - **FIFO**- pops node that was added to queue first\n      - **LIFO** (aka **stack**)- pops node was added to queue last (most recently)\n      - Reached states should be stored as a lookup table (dict)\n- **Redundant Paths**\n  - **Graph search**- checks for redundnat paths\n  - **Tree search**- does not check for redundant paths\n  - Check for cycles\n- Measuring problem-solving\n  - **Completeness**- returns solution if there is one, returns failure if none\n    - Algorithm must be **systematic**\n  - **Optimal**- returns solution with lowest path cost\n  - **Time complexity**- how long it takes to find solution\n  - **Space complexity**- how much memory is needed to find a solution\n- **depth**- d, m- maximum depth\n- **branching factor**- b, number of successors\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- **Breadth-first Search**\n  - **early goal test**- check if node is a solution as soon as its generated\n  - **late goal test**- wait for node to be popped off queue\n  - Optimal if all actions have same cost, always complete\n  - Time and Space Complexity: O(b^d)\n- **Uniform-Cost Search**/**Djkstra's Algorithm**\n  - Check for goal when expanding\n  - Complete and optimal\n- **Depth-first Search**\n  - Not optimal, incmoplete\n  - Much smaller memory than breadth-first or best-first O(bm)\n  - **Backtracking Search**- uses less memory, one successor generated at a time\n- **Depth limited** and **Iterative Deepeninng**\n  - **Depth limited**\n    - depth limit l, if pick l badly than will fail\n    - **diameter**- known good value for depth limit l\n  - **Iterative Deepining**\n    - increases depth every iteration\n    - Optimal when all actions have same cost\n    - Complete\n- **Bidirectional Search**\n  - Searches from initial state and goal state\n\n   \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "- **Informed searches** use **hueritic functions**, h(n)\n",
        "- **Greedy best-first search**\n",
        "  - expands lowest h(n)\n",
        "  - complete in finite spaces\n",
        "- **A*search**\n",
        "  - f(n) = g(n) + h(n)\n",
        "  - **consistency**- concisisten if every node nn and successor of n, n' from action a satisfies: h(n) <= c(n, a, n') + h(n')\n",
        "    - form of **triangle inequality** (1 side of a triangle can't be longer than the sum of the other 2)\n",
        "  - g(n) is cost from initial state to current node\n",
        "  - **Admissable Huerisitc** never overestimates\n",
        "  - Optimal with consistent hueristic \n",
        "  - Can be optimal with inadmissable hueristic \n",
        "  - **monotomic**- path cost always increases as you move forward\n",
        "  - **Sureley expanded nodes**- nodes with f(n) < C*, C* is cost of optimal solution\n",
        "  - **Optimally efficient**- all search algorithms that epand from the initial state using the same hueristic with expand all nodes that were expanded by A*\n",
        "  - **Prunes**- remove nodes not neccessary for finding optimal solution\n",
        "  - Complete, optimal, and optimally efficient\n",
        "  - **Satisficing**- solutions that are **good enough**\n",
        "    - ex) using an inadmissable hueristic that is more accurate\n",
        "  - **Detour index**- multiplier on straight line distance to account for curves in the road\n",
        "  - **Weighted A* Search**- giving the huerisitc more weight than g(n)\n",
        "- **Bounded supotimal Search**- solution must be with in a factor, W, of the optimal cost\n",
        "- **Bounded-cost search**- cost of solution is less than a constant C\n",
        "- **Unbounded-cost search**- any solution as long as it is found quickly\n",
        "- **Memory-bounded Search**\n",
        "  - **Reference counts**- number of times a state has been reached\n",
        "  - Remove from table when reference count max has been hit\n",
        "  - **Beam search**- limits frontier size by only keeping k nodes with best f(n)\n",
        "    - Incomplete, suboptimal\n",
        "  - **Iterative Deepining A* Search** (IDA*)- cutoff is the f(n) cost\n",
        "  - **Recursive Best-First Search** (RBFS)- acts a recursive depth-first search. Keeps track of f-limit and when this number is exceed it backs up and continues down the path with the better f-value.\n",
        "    - more efficient than IDA*\n",
        "    - optimal if hueristic is admissable\n",
        "  - **MA*** (memory-bound A*)- \n",
        "  - **SMA*** (simplified MA*)- continues like A* until memory is full, then drops node with worst f-value\n",
        "    - If all lead nodes have same f-value, then the oldest node is deleted and newest is expanded\n",
        "    - If there is only one leaf than the node is forgotten like it had no successors\n",
        "    - Complete if memory allows\n",
        "- **Bidirection Hueristic Search**\n",
        "  - must consider pairs of nodes (from each frontier)\n",
        "  - **Front-to-end search**- h_f is hueristic from front, h_b is huerisitc from back\n",
        "  - **Front-to-front search**- uses huerisitc to estimate distance between frontiers\n",
        "  - Bidirection expands fewer nodes with an average huerisitc, with a very good huerisitic it does not add much\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "- **Manhattan Distance**/**City Block Distance**- min number of moves needed to get block to right location\n",
        "- **Effective Branching Factor** (b*)- want to be close to 1\n",
        "  - Equation: N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\n",
        "  - N- total nodes generates, d- solution depth\n",
        "- h2 **dominates** h1 if h2 is always better than h1\n",
        "- **Relaxed problem**- problem with less rules\n",
        "- **Subproblem**- finding optimal solution for a simpler problem than the actual problem\n",
        "  - ex) For 8 tile- Getting tiles 1,2,3,4 into correct location and other tiles dont matter\n",
        "- **Pattern Databses**- store solution for all subproblems\n",
        "- **Disjoint Pattern Databases**- Combining solutions from subproblems that dont overlap\n",
        "  - ex) Getting 1,2,3,4 into correct location and getting 5,6,7,8 into location but other tiles don't exisist\n",
        "- **Precomputation**- solving problem optimally once and then using\n",
        "- **Landmark Points**- solving C* for all landmark points and using them as part of the huerisitc \n",
        "- **Shortcuts**- artificial edges that describe an optimal path\n",
        "- **Defferential Huerisitc**- huerisitc that subtracts two values rather than adds them\n",
        "- Learning to Search Better\n",
        "  - **metalevel state space**- states in a metalelvel state space are the computation state of the program\n",
        "  - **metalevel learning**- learns from mistakes\n",
        "  - Goal of learning is to minimize **total cost**\n",
        "- Learning from experience\n",
        "  - Learning from doing the problem multiple times\n",
        "  - **Features**- descriptors of a state (ex. # of misplaced tiles)\n",
        "  - Linear combination equation:\n",
        "    - h(n) = c_1 * x_1(n) + c_2 * x_2(n)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 155,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1680
        },
        "cellView": "form",
        "outputId": "ea01fed6-91d7-48fa-9974-41bbb72efeff"
      },
      "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": 156,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 3.5 Informed (Heuristic) Search Strategies' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n- **Informed searches** use **hueritic functions**, h(n)\n- **Greedy best-first search**\n  - expands lowest h(n)\n  - complete in finite spaces\n- **A*search**\n  - f(n) = g(n) + h(n)\n  - **consistency**- concisisten if every node nn and successor of n, n' from action a satisfies: h(n) <= c(n, a, n') + h(n')\n    - form of **triangle inequality** (1 side of a triangle can't be longer than the sum of the other 2)\n  - g(n) is cost from initial state to current node\n  - **Admissable Huerisitc** never overestimates\n  - Optimal with consistent hueristic \n  - Can be optimal with inadmissable hueristic \n  - **monotomic**- path cost always increases as you move forward\n  - **Sureley expanded nodes**- nodes with f(n) < C*, C* is cost of optimal solution\n  - **Optimally efficient**- all search algorithms that epand from the initial state using the same hueristic with expand all nodes that were expanded by A*\n  - **Prunes**- remove nodes not neccessary for finding optimal solution\n  - Complete, optimal, and optimally efficient\n  - **Satisficing**- solutions that are **good enough**\n    - ex) using an inadmissable hueristic that is more accurate\n  - **Detour index**- multiplier on straight line distance to account for curves in the road\n  - **Weighted A* Search**- giving the huerisitc more weight than g(n)\n- **Bounded supotimal Search**- solution must be with in a factor, W, of the optimal cost\n- **Bounded-cost search**- cost of solution is less than a constant C\n- **Unbounded-cost search**- any solution as long as it is found quickly\n- **Memory-bounded Search**\n  - **Reference counts**- number of times a state has been reached\n  - Remove from table when reference count max has been hit\n  - **Beam search**- limits frontier size by only keeping k nodes with best f(n)\n    - Incomplete, suboptimal\n  - **Iterative Deepining A* Search** (IDA*)- cutoff is the f(n) cost\n  - **Recursive Best-First Search** (RBFS)- acts a recursive depth-first search. Keeps track of f-limit and when this number is exceed it backs up and continues down the path with the better f-value.\n    - more efficient than IDA*\n    - optimal if hueristic is admissable\n  - **MA*** (memory-bound A*)- \n  - **SMA*** (simplified MA*)- continues like A* until memory is full, then drops node with worst f-value\n    - If all lead nodes have same f-value, then the oldest node is deleted and newest is expanded\n    - If there is only one leaf than the node is forgotten like it had no successors\n    - Complete if memory allows\n- **Bidirection Hueristic Search**\n  - must consider pairs of nodes (from each frontier)\n  - **Front-to-end search**- h_f is hueristic from front, h_b is huerisitc from back\n  - **Front-to-front search**- uses huerisitc to estimate distance between frontiers\n  - Bidirection expands fewer nodes with an average huerisitc, with a very good huerisitic it does not add much\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- **Manhattan Distance**/**City Block Distance**- min number of moves needed to get block to right location\n- **Effective Branching Factor** (b*)- want to be close to 1\n  - Equation: N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\n  - N- total nodes generates, d- solution depth\n- h2 **dominates** h1 if h2 is always better than h1\n- **Relaxed problem**- problem with less rules\n- **Subproblem**- finding optimal solution for a simpler problem than the actual problem\n  - ex) For 8 tile- Getting tiles 1,2,3,4 into correct location and other tiles dont matter\n- **Pattern Databses**- store solution for all subproblems\n- **Disjoint Pattern Databases**- Combining solutions from subproblems that dont overlap\n  - ex) Getting 1,2,3,4 into correct location and getting 5,6,7,8 into location but other tiles don't exisist\n- **Precomputation**- solving problem optimally once and then using\n- **Landmark Points**- solving C* for all landmark points and using them as part of the huerisitc \n- **Shortcuts**- artificial edges that describe an optimal path\n- **Defferential Huerisitc**- huerisitc that subtracts two values rather than adds them\n- Learning to Search Better\n  - **metalevel state space**- states in a metalelvel state space are the computation state of the program\n  - **metalevel learning**- learns from mistakes\n  - Goal of learning is to minimize **total cost**\n- Learning from experience\n  - Learning from doing the problem multiple times\n  - **Features**- descriptors of a state (ex. # of misplaced tiles)\n  - Linear combination equation:\n    - h(n) = c_1 * x_1(n) + c_2 * x_2(n)\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "- **economy**- price increases as demand increases, don't have to predict action of an agent\n",
        "- **Evaluation Function**- estimates who is winning based off features of the game/state\n",
        "- Two Player, Zero Sum Games\n",
        "  - **Perfect Infomration** == **Fully Observable**\n",
        "  - **Zero-Sum**- something that is good for one player can not also be good for the other\n",
        "  - **move** == **action**\n",
        "  - **position** == **state**\n",
        "  - Defined using:\n",
        "    - Initial State, S_0\n",
        "    - To-Move- players whose it is\n",
        "    - Actions- legal moves\n",
        "    - Result- **transisition model** is used to solve for the resulting state from the action\n",
        "    - Is-Terminal- **terminal test** is used to see if game is over (or in **terminal state**)\n",
        "    - Utility- **utility function** solves if player has won, lost or tied\n",
        "  - **Game Tree**- search tree for every sequence of moves until the game is over\n",
        "    - Can be infinite\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "- **Minimax Search**\n",
        "  - Depth-first\n",
        "  - **ply**- single player has moved, one more level deeper in the game tree\n",
        "  - **Minimax value**- value of the utility, assumes both players play perfectly\n",
        "  - **Minimax Decision**- decision made using the minimax value\n",
        "  - Time Complexity: O(b^m), m- maximum depth of tree, b- # of legal moves\n",
        "  - Space Complexity: O(bm)\n",
        "- Multiplayer Games\n",
        "  - Must replace single value of each node with a vector of values. This vector gives the utility of the state from each player’s viewpoint. (In two-player, zero-sum games, the two-element vector can be reduced to a single value because the values are always opposite.)\n",
        "  - Multiplayer games contain **alliances**\n",
        "- **Alpha-Beta Pruning**\n",
        "  - Alpha- the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. Think: “at least.”\n",
        "  - Beta- the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. Think: “at most.”\n",
        "  - Effictivenes depends on order states are examined\n",
        "- Move ordering\n",
        "  - If done perfectly, alpha-beta effective branching factor becomes sqrt(b)\n",
        "  - Dynamic move ordering- trying moves that had been the best in the past\n",
        "  - **killer moves**- best move\n",
        "  - **transposition**- repeated states due to different move order leading to the same state\n",
        "  - **transposition table**- stores huerisitc values of states\n",
        "  - Chess Computer:\n",
        "    - **Type A strategy**- consider all moves to a certain depth, uses huerisitic to estimate the quality of the states at this depth. Wide but shallw.\n",
        "    - **Type B strategy**- ignore moves that look bad and follow only good ones. Deep but narrow.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "- To use time more efficiently:\n",
        "  - Apply huerisitc **evaluation function** to states, treating noterminal nodes as terminal\n",
        "  - Replace terminal test with **cutoff test**\n",
        "    - Cuts off at terminal states or at other cut off points seach certain depth\n",
        "- Huerisitc evaluation function- returns estimate of the expected utility of a state to a player\n",
        "  - For non terminal states, the eval must be between a win and a loss\n",
        "  - Calculate **features** (ex. pawns on the board)\n",
        "  - **Expected Value** = sum(chance * value)\n",
        "  - **Weighted Linear Function**- weighted sum of all features\n",
        "    - Assumes each feature is independent\n",
        "  - Function should only be applied to **Quiescent** positions- positions with no next move that drastically changes the game\n",
        "    - Knowns as **quiescent search**\n",
        "  - **Horizon Effect**- trying to delay the inevitable because it is past the depth that is seen\n",
        "  - **Singular Extension**- extends certain moves that are clearly better\n",
        "- **Forward Pruning**- prunes moves that seem bad (Type B)\n",
        "- **Late Move Reduction**- assumes move ordering is good, moves later in the list are worse. Then reduces depth that these moves are explored.\n",
        "- **Policy**- mapping every possible state to the best move in that state\n",
        "- **Retrograde**- minimax in reverse, finds winning positions than does reverse moves to get to current position\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- **Stochastic Games**- involve random element (ex. dice)\n",
        "  - Includes **chance nodes** and Max/Min nodes\n",
        "- **Expectiminimax Value**- expected value pf the min/max move\n",
        "- **Probability** = Expected utility for nonn zero sum games\n",
        "- Able to prune channce nodes\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "- Choose actions based on desirability of the immediate outcomes \n",
        "- **Maximum Expected Utility** (MEU)- rational agent should choose the action that maximimzes the expected utility\n",
        "- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments)\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "- **Lottery**- how treat outcome of each action\n",
        "- Constraints preference rlations must obey (axioms of utility theory):\n",
        "  - Orderability- given 2 lotteries, a rational agent must prefer one or decide they are equal\n",
        "  - Transitivity- If agent prefers A to B and B to C then they must prefer A to C\n",
        "  - Continuity- If lottery B is between A and C, then there is a probability, p, that rational agent will be indifferent between knowing the result B and the lottery that yields A with probability p and C with probability 1 - p\n",
        "  - Substitutability- If agent is indifferent about A and B then A and B can be substituted in a more complex lottery\n",
        "  - Monotonicity- If two lotteries have the same two possible outcomes. If an agent preferes A to B, then the agent must prefer that has a higher probability for A\n",
        "  - Decomposability- Compound lotteries can be reduced to simpler ones using the laws of probability\n",
        "- Existence of utility function: If an agents preferences obey the axioms of utility (above), then there exists a function U such that U(A)>U(B) if and only if A is preferred and A = B if indifferent\n",
        "- Expected utility of a lottery- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n",
        "- The existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "- Utility functions map from lotteries to real numbers\n",
        "- **Preference Elicitation**- present choices to hum and observing preference to find utiloty function\n",
        "- **Normalized Utilites**- use a scale of u_lower = 0 and u_upper = 1\n",
        "- How to ascess utility\n",
        "  - Agent choose between S and **Standard Lottery** [p, u_upper; (1-p), u_lower], adjust p until it is indifferent\n",
        "- **Value of Statistical Life** = ~$10 million \n",
        "- **micromort**- one in a million chance of death\n",
        "- **QALY** (quality-adjusted life year)- accept shorter life expectancy to avoid disability\n",
        "  - ex) kidney patient on average are indifferent between living 2 years on dialysis and one year at full health\n",
        "- **Monotonic Preference**- prefer more than less\n",
        "- **Risk-Averse** vs. **Risk-Seeking**\n",
        "- EMV- expected monetary value\n",
        "- **Certainty Equivalent**- value agent will accept instead of doing a lottery\n",
        "- **Insurance Premium**- difference between the EMV of a lottery and its certainty equivalent\n",
        "- **unbiased**- ecpected value of error is zero\n",
        "- **Order statistic**- distribution of any ranked element of a sample\n",
        "- **Optomizer's curse**- Tendency for the estimated expected utility of the best choise to be too high\n",
        "- Human Judgement and Irrationality\n",
        "  - **Normative theory**- describes how a rational agent should act\n",
        "  - **Descriptive Theory**- describes how actual agents do act\n",
        "  - **Certainty Effect**- people love gains that are certain\n",
        "  - **ambiguity aversion**- people choose the known probabilities over unknown\n",
        "  - **framing effect**- wording of a problem effects decision\n",
        "  - **anchoring effect**- people make relative utility judgements\n",
        "    - ex) A $200 bottle of wine is too much but $50 is reasonable\n",
        "  - **Evolutionary Psychology**- - brain's decision making did not evolve to solve word problems\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 157,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2608
        },
        "outputId": "379a9f21-7c79-4760-98e7-019ef1471d3f"
      },
      "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": 158,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- **economy**- price increases as demand increases, don't have to predict action of an agent\n- **Evaluation Function**- estimates who is winning based off features of the game/state\n- Two Player, Zero Sum Games\n  - **Perfect Infomration** == **Fully Observable**\n  - **Zero-Sum**- something that is good for one player can not also be good for the other\n  - **move** == **action**\n  - **position** == **state**\n  - Defined using:\n    - Initial State, S_0\n    - To-Move- players whose it is\n    - Actions- legal moves\n    - Result- **transisition model** is used to solve for the resulting state from the action\n    - Is-Terminal- **terminal test** is used to see if game is over (or in **terminal state**)\n    - Utility- **utility function** solves if player has won, lost or tied\n  - **Game Tree**- search tree for every sequence of moves until the game is over\n    - Can be infinite\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- **Minimax Search**\n  - Depth-first\n  - **ply**- single player has moved, one more level deeper in the game tree\n  - **Minimax value**- value of the utility, assumes both players play perfectly\n  - **Minimax Decision**- decision made using the minimax value\n  - Time Complexity: O(b^m), m- maximum depth of tree, b- # of legal moves\n  - Space Complexity: O(bm)\n- Multiplayer Games\n  - Must replace single value of each node with a vector of values. This vector gives the utility of the state from each player’s viewpoint. (In two-player, zero-sum games, the two-element vector can be reduced to a single value because the values are always opposite.)\n  - Multiplayer games contain **alliances**\n- **Alpha-Beta Pruning**\n  - Alpha- the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. Think: “at least.”\n  - Beta- the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. Think: “at most.”\n  - Effictivenes depends on order states are examined\n- Move ordering\n  - If done perfectly, alpha-beta effective branching factor becomes sqrt(b)\n  - Dynamic move ordering- trying moves that had been the best in the past\n  - **killer moves**- best move\n  - **transposition**- repeated states due to different move order leading to the same state\n  - **transposition table**- stores huerisitc values of states\n  - Chess Computer:\n    - **Type A strategy**- consider all moves to a certain depth, uses huerisitic to estimate the quality of the states at this depth. Wide but shallw.\n    - **Type B strategy**- ignore moves that look bad and follow only good ones. Deep but narrow.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- To use time more efficiently:\n  - Apply huerisitc **evaluation function** to states, treating noterminal nodes as terminal\n  - Replace terminal test with **cutoff test**\n    - Cuts off at terminal states or at other cut off points seach certain depth\n- Huerisitc evaluation function- returns estimate of the expected utility of a state to a player\n  - For non terminal states, the eval must be between a win and a loss\n  - Calculate **features** (ex. pawns on the board)\n  - **Expected Value** = sum(chance * value)\n  - **Weighted Linear Function**- weighted sum of all features\n    - Assumes each feature is independent\n  - Function should only be applied to **Quiescent** positions- positions with no next move that drastically changes the game\n    - Knowns as **quiescent search**\n  - **Horizon Effect**- trying to delay the inevitable because it is past the depth that is seen\n  - **Singular Extension**- extends certain moves that are clearly better\n- **Forward Pruning**- prunes moves that seem bad (Type B)\n- **Late Move Reduction**- assumes move ordering is good, moves later in the list are worse. Then reduces depth that these moves are explored.\n- **Policy**- mapping every possible state to the best move in that state\n- **Retrograde**- minimax in reverse, finds winning positions than does reverse moves to get to current position\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- **Stochastic Games**- involve random element (ex. dice)\n  - Includes **chance nodes** and Max/Min nodes\n- **Expectiminimax Value**- expected value pf the min/max move\n- **Probability** = Expected utility for nonn zero sum games\n- Able to prune channce nodes\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Choose actions based on desirability of the immediate outcomes \n- **Maximum Expected Utility** (MEU)- rational agent should choose the action that maximimzes the expected utility\n- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n- **Lottery**- how treat outcome of each action\n- Constraints preference rlations must obey (axioms of utility theory):\n  - Orderability- given 2 lotteries, a rational agent must prefer one or decide they are equal\n  - Transitivity- If agent prefers A to B and B to C then they must prefer A to C\n  - Continuity- If lottery B is between A and C, then there is a probability, p, that rational agent will be indifferent between knowing the result B and the lottery that yields A with probability p and C with probability 1 - p\n  - Substitutability- If agent is indifferent about A and B then A and B can be substituted in a more complex lottery\n  - Monotonicity- If two lotteries have the same two possible outcomes. If an agent preferes A to B, then the agent must prefer that has a higher probability for A\n  - Decomposability- Compound lotteries can be reduced to simpler ones using the laws of probability\n- Existence of utility function: If an agents preferences obey the axioms of utility (above), then there exists a function U such that U(A)>U(B) if and only if A is preferred and A = B if indifferent\n- Expected utility of a lottery- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n- The existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n- Utility functions map from lotteries to real numbers\n- **Preference Elicitation**- present choices to hum and observing preference to find utiloty function\n- **Normalized Utilites**- use a scale of u_lower = 0 and u_upper = 1\n- How to ascess utility\n  - Agent choose between S and **Standard Lottery** [p, u_upper; (1-p), u_lower], adjust p until it is indifferent\n- **Value of Statistical Life** = ~$10 million \n- **micromort**- one in a million chance of death\n- **QALY** (quality-adjusted life year)- accept shorter life expectancy to avoid disability\n  - ex) kidney patient on average are indifferent between living 2 years on dialysis and one year at full health\n- **Monotonic Preference**- prefer more than less\n- **Risk-Averse** vs. **Risk-Seeking**\n- EMV- expected monetary value\n- **Certainty Equivalent**- value agent will accept instead of doing a lottery\n- **Insurance Premium**- difference between the EMV of a lottery and its certainty equivalent\n- **unbiased**- ecpected value of error is zero\n- **Order statistic**- distribution of any ranked element of a sample\n- **Optomizer's curse**- Tendency for the estimated expected utility of the best choise to be too high\n- Human Judgement and Irrationality\n  - **Normative theory**- describes how a rational agent should act\n  - **Descriptive Theory**- describes how actual agents do act\n  - **Certainty Effect**- people love gains that are certain\n  - **ambiguity aversion**- people choose the known probabilities over unknown\n  - **framing effect**- wording of a problem effects decision\n  - **anchoring effect**- people make relative utility judgements\n    - ex) A $200 bottle of wine is too much but $50 is reasonable\n  - **Evolutionary Psychology**- - brain's decision making did not evolve to solve word problems\n \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "- CSP's contain:\n",
        "  - X, a set of variables\n",
        "  - D, set of domain, 1 per variable\n",
        "  - C, set of contraints\n",
        "- Domain consisits of allowable values for variables\n",
        "- Constraints are a par: <scope, rel>\n",
        "  - scope- tuple of variables that participate\n",
        "  - rel- **relation** that defines them\n",
        "- An **assignment** that does violate a constraint is a **concistent** assignment\n",
        "- **Complete Assignment**- ever variable is assigned a value\n",
        "- Solution to CSP is a concistent, complete assignment\n",
        "- **Partial Assignment**- some variables unassigned\n",
        "- **Partial Solution**- partial assignment that is consestent\n",
        "- **Constraint Graph**- visualization of CSP\n",
        "- Why choose CSP:\n",
        "  - CSPs yield a natural representation for a wide variety of problems\n",
        "  - They have been developed for years and are fast and efficient\n",
        "  - Quickly prune large search spaces that atomic state-space searchers cannot\n",
        "- **Precedence Constraints**- Constrain on order of how things happen\n",
        "- **Disjunctive Constraint**- Two things that can't happen at the same time\n",
        "- Simplest CSPs ahave **discrete, finite domains**\n",
        "- A discrete domain can be **infinite**\n",
        "  - Must use implicit constraints\n",
        "- **linear constraints**- variable appears only in linear form\n",
        "- No algorithm exists for solving general **nonlinear constraints** on integer variables\n",
        "- **Continuous Domains** (ex. Hubble Telescope)\n",
        "- **Linear Programming** problmes- constraints must be linear equalities or inequalities\n",
        "- **Unary Constraint**- constrain a single variable\n",
        "- **Binary Constraints**- constrain two variables\n",
        "- **Binary CSP**- only has unary and binary constraints\n",
        "- **Global Constraints**- constrain arbitrary number of variables\n",
        "  - Alldi f f constraint- all variables involved must have different values\n",
        "- **Cryptarithmetic puzzles**- each letter has a different digit\n",
        "- *Constrain Hypergraph**- hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent -ary constraints—constraints involving variables\n",
        "- **Dual graph** transformation- convert n-ary CSP to binary. \n",
        "  - create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\n",
        "- **Preference constraints**- indicates preffered solutions \n",
        "- **Constrained Optimization Problems** (COP)- CSPs with preferences, solved with optimization search methods\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- **Constraint Propogation**- using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable\n",
        "- **Local Cosistency**- Treat each variable \n",
        "  - Treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph\n",
        "- **Node consistency**- single variable satisfy unary constraints\n",
        "- **Arc consistency**- every variable satisfies binary constraints\n",
        "- AC-3\n",
        "  - Maintains que of arcs to consider (initially all arcs)\n",
        "  - Then pop-off any arc\n",
        "  - Make X_i consistent with X_j\n",
        "  - If the domain is unaffected it continues to next arc, if not:\n",
        "    - Add to queue all arcs that are neighbors of X_i or X_j\n",
        "  - If domain is empty than CSP has no solution\n",
        "  - If queue is empty, search is done\n",
        "  - Time complexity O(d^2), worst case O(cd^3)\n",
        "    - d- domain size, c- arcs\n",
        "- **Path consistency**- tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "- **k- consistency**- for any k-1 variable with consisten assignments to them, a consisteny value can always be assigned to the kth variable\n",
        "- **Strongle k-consistent**-  k-consistent and is also (k-1)-consistent, (k-2)-consistent, all the way down to 1-consistent. \n",
        "- **Resource Constraint** (Atmost constraint)- constrained by total resources\n",
        "  - ex) 10 total teachers assigned for tasks, if more than 10 are assigned -> fail\n",
        "- **bounds propagation**- resource connstrain but there is a min and max of resources\n",
        "- **Bounds consistent**- bounds propagation is satisfied\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "- **Commutativity**- order of application of actions doesn't matter\n",
        "- **Minimum-Remaining-Values** hueristic (MRV)- choose variable with least amount of legal values\n",
        "- **Degree Hueristic**- select variable that is involved in most amount of constraints\n",
        "  - reduces branching factor\n",
        "- MRV is usuallly better, but degreee is helpful as a tie breaker\n",
        "- **Least-constraining-value**- prefers value that rules out fewest choices for neighboring variables\n",
        "- **Forward-checking**- when variable X is assignned, forward checking establishes arc concistency for it\n",
        "  - inference type\n",
        "- **Maintaining Arc Consistency**- checks deeper inconsistencies than forward checking\n",
        "  - Recursively propogates constraints when changes are made to variable domains (forward-checking does not)\n",
        "- **Chronological Backtracking**- - branch fails, back up to preceding variable and try a different variable\n",
        "- **Conflict set**- Set of assignments that are in conflict\n",
        "- **Backjumping**- backtracks to most recent assignment in the conflict set\n",
        "  - Tells how far to back up so we down change variables that won't fix anything\n",
        "  - Redundant to forward checking, only need one or the other \n",
        "- **Conflict-directed Backjumping**- backjumping algorithm that uses conflict sets to predict future failures\n",
        "- **Constraint learning**- finding a minimum set of variables from the conflict set that causes the problem.\n",
        "- **no-good**- Set of variables from constraint learning\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "- **min-conflicts** hueristic- elect the value that results in the minimum number of conflicts with other variables\n",
        "  - For n-queens problem this roughly independent of problem size\n",
        "- **Tabu Search**- keeping a small list of recently visited states and forbidding the algorithm to return to those states.\n",
        "- **Constraint Weighting**- All constraints initially valued at 1, then as constraints are broken the weights are changed depending on frequency amount of times constraint is broken\n",
        "  - Adds topography to avoid plateuing\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "- **Indpedent subproblems**- subcomponents of a problem that do not effect each other\n",
        "- **Connected Components**\n",
        "- **Tree**- constraint graph when any two variables are connected by one path\n",
        "  - any tree-structured CSP can be solved in time linear in the number of variables\n",
        "- **Directional Arc Consistency** (DAC)- with ordered variables X_1, X_2,..,X_n, X_i is arc concistent with each X_j for j>i\n",
        "- **Topological Sort**- ordering of the variables such that each variable appears after its parent in the tree\n",
        "- Cutset Conditioning\n",
        "  1. Cut a subset, S, of CSPs variable so that the constraint graph becomes a tree after removal. S is **cycle cutset**.\n",
        "  2. For each possible assignment to the variable on S that satisfy S:<br>\n",
        "    a. remove values from the domains of the remaining variables that are inconsistent with S.<br>\n",
        "    b. If the CSP has a solution, return with the assignment for S.\n",
        "  - Cycle cutset has size c -> Time Complexity O(d^c * (n - c)d^2)\n",
        "- **Tree Decomposition**- a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
        "  - Must satisfy 3 requirements:\n",
        "    - Every variable in the original problem must appear in at least 1 of the tree nodes\n",
        "    - If 2 variables are connect by a constrain in the original problem, they must appear together in at least of 1 of the tree nodes\n",
        "    - If a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes\n",
        "      - any variable from the original problem must have the same value wherever it appears\n",
        "  - Time complexity O(nd^2)\n",
        "  - **tree width**- One lest than size of largest node\n",
        "    - With tree width, w the problem can be solved in O(nd^(w+1)) time\n",
        "    - CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n",
        "- **Value Symmetry**- multiple ways to assign values\n",
        "- **Symmetry breaking constraint**- break symmetry in assignments.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 159,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2570
        },
        "outputId": "dfd4aec9-0adc-4d26-de6e-3b6a2153e198"
      },
      "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": 160,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- CSP's contain:\n  - X, a set of variables\n  - D, set of domain, 1 per variable\n  - C, set of contraints\n- Domain consisits of allowable values for variables\n- Constraints are a par: <scope, rel>\n  - scope- tuple of variables that participate\n  - rel- **relation** that defines them\n- An **assignment** that does violate a constraint is a **concistent** assignment\n- **Complete Assignment**- ever variable is assigned a value\n- Solution to CSP is a concistent, complete assignment\n- **Partial Assignment**- some variables unassigned\n- **Partial Solution**- partial assignment that is consestent\n- **Constraint Graph**- visualization of CSP\n- Why choose CSP:\n  - CSPs yield a natural representation for a wide variety of problems\n  - They have been developed for years and are fast and efficient\n  - Quickly prune large search spaces that atomic state-space searchers cannot\n- **Precedence Constraints**- Constrain on order of how things happen\n- **Disjunctive Constraint**- Two things that can't happen at the same time\n- Simplest CSPs ahave **discrete, finite domains**\n- A discrete domain can be **infinite**\n  - Must use implicit constraints\n- **linear constraints**- variable appears only in linear form\n- No algorithm exists for solving general **nonlinear constraints** on integer variables\n- **Continuous Domains** (ex. Hubble Telescope)\n- **Linear Programming** problmes- constraints must be linear equalities or inequalities\n- **Unary Constraint**- constrain a single variable\n- **Binary Constraints**- constrain two variables\n- **Binary CSP**- only has unary and binary constraints\n- **Global Constraints**- constrain arbitrary number of variables\n  - Alldi f f constraint- all variables involved must have different values\n- **Cryptarithmetic puzzles**- each letter has a different digit\n- *Constrain Hypergraph**- hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent -ary constraints—constraints involving variables\n- **Dual graph** transformation- convert n-ary CSP to binary. \n  - create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\n- **Preference constraints**- indicates preffered solutions \n- **Constrained Optimization Problems** (COP)- CSPs with preferences, solved with optimization search methods\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- **Constraint Propogation**- using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable\n- **Local Cosistency**- Treat each variable \n  - Treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph\n- **Node consistency**- single variable satisfy unary constraints\n- **Arc consistency**- every variable satisfies binary constraints\n- AC-3\n  - Maintains que of arcs to consider (initially all arcs)\n  - Then pop-off any arc\n  - Make X_i consistent with X_j\n  - If the domain is unaffected it continues to next arc, if not:\n    - Add to queue all arcs that are neighbors of X_i or X_j\n  - If domain is empty than CSP has no solution\n  - If queue is empty, search is done\n  - Time complexity O(d^2), worst case O(cd^3)\n    - d- domain size, c- arcs\n- **Path consistency**- tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n- **k- consistency**- for any k-1 variable with consisten assignments to them, a consisteny value can always be assigned to the kth variable\n- **Strongle k-consistent**-  k-consistent and is also (k-1)-consistent, (k-2)-consistent, all the way down to 1-consistent. \n- **Resource Constraint** (Atmost constraint)- constrained by total resources\n  - ex) 10 total teachers assigned for tasks, if more than 10 are assigned -> fail\n- **bounds propagation**- resource connstrain but there is a min and max of resources\n- **Bounds consistent**- bounds propagation is satisfied\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n- **Commutativity**- order of application of actions doesn't matter\n- **Minimum-Remaining-Values** hueristic (MRV)- choose variable with least amount of legal values\n- **Degree Hueristic**- select variable that is involved in most amount of constraints\n  - reduces branching factor\n- MRV is usuallly better, but degreee is helpful as a tie breaker\n- **Least-constraining-value**- prefers value that rules out fewest choices for neighboring variables\n- **Forward-checking**- when variable X is assignned, forward checking establishes arc concistency for it\n  - inference type\n- **Maintaining Arc Consistency**- checks deeper inconsistencies than forward checking\n  - Recursively propogates constraints when changes are made to variable domains (forward-checking does not)\n- **Chronological Backtracking**- - branch fails, back up to preceding variable and try a different variable\n- **Conflict set**- Set of assignments that are in conflict\n- **Backjumping**- backtracks to most recent assignment in the conflict set\n  - Tells how far to back up so we down change variables that won't fix anything\n  - Redundant to forward checking, only need one or the other \n- **Conflict-directed Backjumping**- backjumping algorithm that uses conflict sets to predict future failures\n- **Constraint learning**- finding a minimum set of variables from the conflict set that causes the problem.\n- **no-good**- Set of variables from constraint learning\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n- **min-conflicts** hueristic- elect the value that results in the minimum number of conflicts with other variables\n  - For n-queens problem this roughly independent of problem size\n- **Tabu Search**- keeping a small list of recently visited states and forbidding the algorithm to return to those states.\n- **Constraint Weighting**- All constraints initially valued at 1, then as constraints are broken the weights are changed depending on frequency amount of times constraint is broken\n  - Adds topography to avoid plateuing\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- **Indpedent subproblems**- subcomponents of a problem that do not effect each other\n- **Connected Components**\n- **Tree**- constraint graph when any two variables are connected by one path\n  - any tree-structured CSP can be solved in time linear in the number of variables\n- **Directional Arc Consistency** (DAC)- with ordered variables X_1, X_2,..,X_n, X_i is arc concistent with each X_j for j>i\n- **Topological Sort**- ordering of the variables such that each variable appears after its parent in the tree\n- Cutset Conditioning\n  1. Cut a subset, S, of CSPs variable so that the constraint graph becomes a tree after removal. S is **cycle cutset**.\n  2. For each possible assignment to the variable on S that satisfy S:<br>\n    a. remove values from the domains of the remaining variables that are inconsistent with S.<br>\n    b. If the CSP has a solution, return with the assignment for S.\n  - Cycle cutset has size c -> Time Complexity O(d^c * (n - c)d^2)\n- **Tree Decomposition**- a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n  - Must satisfy 3 requirements:\n    - Every variable in the original problem must appear in at least 1 of the tree nodes\n    - If 2 variables are connect by a constrain in the original problem, they must appear together in at least of 1 of the tree nodes\n    - If a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes\n      - any variable from the original problem must have the same value wherever it appears\n  - Time complexity O(nd^2)\n  - **tree width**- One lest than size of largest node\n    - With tree width, w the problem can be solved in O(nd^(w+1)) time\n    - CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n- **Value Symmetry**- multiple ways to assign values\n- **Symmetry breaking constraint**- break symmetry in assignments.\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "- **Knowledge Base** (KB)- Set of **sentences**\n",
        "- **Knowledge representation language**\n",
        "- **Axiom**- sentence that was given, not derived\n",
        "- **Inference**- Deriving new sentences from old\n",
        "- **Background Knowledge**\n",
        "- When agent is called it does:<br>\n",
        "  1. Tells knowledge base what it percieves<br>\n",
        "  2. Asks knowledge base what action it should perform<br>\n",
        "  3. Agennt tells knowledge base which action was chosen and returns the action for execution<br>\n",
        "- **Knowledge Level**- specify only what the agent knows and what its goals are, in order to determine its behavior\n",
        "- **implementation level**\n",
        "- **Declarative** Approach- Begin with empty KB, then designer tell sentence one at a time until agent knows how to operate\n",
        "- **Procedural** approach- encodes desired behaviors directly as program code\n",
        "- Succesful agent often combines both approaches\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "- **Wumpus World**- cave consisting of rooms connected by passageways\n",
        "- Definition of task enviornment is given by PEAS\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "- **Semantics**- meaning of sentence\n",
        "  - Defines the **truth** for each possible **world**\n",
        "- Every sentence must be either true or false in each possible world—there is no “in between.”\n",
        "- **model**- possible world that is not in real environment\n",
        "- I sentence, a, is true in model, m than m **satisfies** a or m **is a model of** a. M(a)\n",
        "- **Entailment**- a sentence follows logically from another sentence\n",
        "- **Logical Inference**- entailment used to derive conclusions\n",
        "- **Model checking**- algorithm that unumarets all posible models to check that a is true in all models with KB is true\n",
        "- **Sound**/**truth-preserving**- inference algorithm that only derives entialed sentences\n",
        "  - Unsound makes things up\n",
        "- **Completeness**- an inference algorithm is complete if it can derive any sentence that is entailed\n",
        "- If KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world\n",
        "- **Grounding**- connection between logical reasoning and processes and the real enviornment that the agent exists in\n",
        "  - Sensors create connection\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "- **Propositional Logic**- algorith for logical inference that uses semantic notation of entailment\n",
        "- **Syntax**- defines allowable sentences\n",
        "- **Atomic sentences**_ consist of a single **propositional symbol**\n",
        "- **Complex Sentences**- Combination of simpler sentences using parentheses and operators called **logical connectives**\n",
        "  - **Logical Connectives** (symbol on seperate paper) (in order of precedence):\n",
        "    - not- **negation**. A **literal** is either an atomic sentence (positive literal) or a negated atomic sentence (negative literal)\n",
        "    - and- **conjunction**, each part is a **conjunct**\n",
        "    - or- **disjunction**, each part is a **disjunt**\n",
        "    - implies- **implication** or **rules** or **if-then**- Its **premise** or **antecedent** and its **conclusion** or **consequent**\n",
        "    - if and only if- **biconditional**\n",
        "- **Truth value**- true or false\n",
        "- Complex sentence rules: \n",
        "  - not P is true iff is false in m. \n",
        "  - P and Q is true iff both P and Q are true in m\n",
        "  - P or Q is true iff either P or Q is true in m\n",
        "  - P implies Q is true unless P is true and Q is false in m \n",
        "  - P if and only if Q is true iff P and Q are both true or both false in m\n",
        "- every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "- **Theorem Proving**- pplying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models\n",
        "- If # of models is large and length of proof is short, then theorem proving can be more efficient than model checking\n",
        "- **Logical Equivalence**- 2 sentences a and b are logically equivalent if they are true in the same set set of models\n",
        "- **Validity**- sentence is valid if it is true in all models\n",
        "- **tautologies**- necessarily true, valid sentences\n",
        "- **Deduction theorem**\n",
        "- **Satisfiability**- sentence is satisdiable if it is true in or satisfied by some model\n",
        "- **SAT** Problem- determining the satisfiability of sentences in propositional logic\n",
        "- **Reductio ad absurdum**- reduction to an absurd thing\n",
        "  - aka **refutation** or proof by **contradiction**\n",
        "- *Inference Rules** (on seperate piece)\n",
        "- **monotonicity**- set of entailed sentences can only increase as information is added to the knowledge base\n",
        "- **Resolution**\n",
        "- **Conjunctive Normal Form** (CNF)- sentence expressed as a conjunction of clauses\n",
        "  - Setps on seperate piece\n",
        "- **Resolution closure**- the set of all clauses derivable by repeated application of the resolution rule to clauses in or their derivatives\n",
        "- **Ground resolution theorem**- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n",
        "- **Definite Clause**- a disjunction of literals of which exactly one is positive\n",
        "- **Horn Clause**- disjunction lierals of which at most one is positive\n",
        "  - All definite clauses and goal clauses are Horn clauses\n",
        "  - **Body**- premise\n",
        "  - **Head**- conclusion\n",
        "- **Goal clauses**- clauses with no positive literals\n",
        "- KB containing 1 definite clause:\n",
        "  - Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal\n",
        "  - Inference with horn clauses cann be using forward chaining and backward chaining\n",
        "  Deciding entailment with horn clauses can be done in time that is linear in size of the knowledge base\n",
        "- **Fact**- sentence consisting of single positive literal\n",
        "- **Forward Chaining**- determines if a single proposition is entailed by a KB of definite clauses\n",
        "  - **Sound**- every inference is an application of Modus Ponens\n",
        "  - **Complete**- every entailed atomic sentence will be derived\n",
        "  - **Data Driven**- focus n known data\n",
        "- **Backward Chaining**- works backward from query\n",
        "  - If query is known to be true, no work needed\n",
        "  - **Goal-directed reasoning**\n",
        "  - Cost is much less than linear in the size of KB, because only uses relevant facts\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 161,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1635
        },
        "outputId": "fa8a89db-6a55-445c-a435-541837ed17a5"
      },
      "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": 162,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- **Knowledge Base** (KB)- Set of **sentences**\n- **Knowledge representation language**\n- **Axiom**- sentence that was given, not derived\n- **Inference**- Deriving new sentences from old\n- **Background Knowledge**\n- When agent is called it does:<br>\n  1. Tells knowledge base what it percieves<br>\n  2. Asks knowledge base what action it should perform<br>\n  3. Agennt tells knowledge base which action was chosen and returns the action for execution<br>\n- **Knowledge Level**- specify only what the agent knows and what its goals are, in order to determine its behavior\n- **implementation level**\n- **Declarative** Approach- Begin with empty KB, then designer tell sentence one at a time until agent knows how to operate\n- **Procedural** approach- encodes desired behaviors directly as program code\n- Succesful agent often combines both approaches\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- **Wumpus World**- cave consisting of rooms connected by passageways\n- Definition of task enviornment is given by PEAS\n\n\n## AIMA Chapter 7.3 Logic\n\n- **Semantics**- meaning of sentence\n  - Defines the **truth** for each possible **world**\n- Every sentence must be either true or false in each possible world—there is no “in between.”\n- **model**- possible world that is not in real environment\n- I sentence, a, is true in model, m than m **satisfies** a or m **is a model of** a. M(a)\n- **Entailment**- a sentence follows logically from another sentence\n- **Logical Inference**- entailment used to derive conclusions\n- **Model checking**- algorithm that unumarets all posible models to check that a is true in all models with KB is true\n- **Sound**/**truth-preserving**- inference algorithm that only derives entialed sentences\n  - Unsound makes things up\n- **Completeness**- an inference algorithm is complete if it can derive any sentence that is entailed\n- If KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world\n- **Grounding**- connection between logical reasoning and processes and the real enviornment that the agent exists in\n  - Sensors create connection\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n- **Propositional Logic**- algorith for logical inference that uses semantic notation of entailment\n- **Syntax**- defines allowable sentences\n- **Atomic sentences**_ consist of a single **propositional symbol**\n- **Complex Sentences**- Combination of simpler sentences using parentheses and operators called **logical connectives**\n  - **Logical Connectives** (symbol on seperate paper) (in order of precedence):\n    - not- **negation**. A **literal** is either an atomic sentence (positive literal) or a negated atomic sentence (negative literal)\n    - and- **conjunction**, each part is a **conjunct**\n    - or- **disjunction**, each part is a **disjunt**\n    - implies- **implication** or **rules** or **if-then**- Its **premise** or **antecedent** and its **conclusion** or **consequent**\n    - if and only if- **biconditional**\n- **Truth value**- true or false\n- Complex sentence rules: \n  - not P is true iff is false in m. \n  - P and Q is true iff both P and Q are true in m\n  - P or Q is true iff either P or Q is true in m\n  - P implies Q is true unless P is true and Q is false in m \n  - P if and only if Q is true iff P and Q are both true or both false in m\n- every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n- **Theorem Proving**- pplying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models\n- If # of models is large and length of proof is short, then theorem proving can be more efficient than model checking\n- **Logical Equivalence**- 2 sentences a and b are logically equivalent if they are true in the same set set of models\n- **Validity**- sentence is valid if it is true in all models\n- **tautologies**- necessarily true, valid sentences\n- **Deduction theorem**\n- **Satisfiability**- sentence is satisdiable if it is true in or satisfied by some model\n- **SAT** Problem- determining the satisfiability of sentences in propositional logic\n- **Reductio ad absurdum**- reduction to an absurd thing\n  - aka **refutation** or proof by **contradiction**\n- *Inference Rules** (on seperate piece)\n- **monotonicity**- set of entailed sentences can only increase as information is added to the knowledge base\n- **Resolution**\n- **Conjunctive Normal Form** (CNF)- sentence expressed as a conjunction of clauses\n  - Setps on seperate piece\n- **Resolution closure**- the set of all clauses derivable by repeated application of the resolution rule to clauses in or their derivatives\n- **Ground resolution theorem**- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "80828ab5-3458-41f8-bc85-f5923ca92c18"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 165,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n- **Rationality**- making the right decision\n- Turing Test\n  - **Natural Language Processing**- ability to communicate with human\n  - **Knowledge representation**- remember information from before or during conversation\n  - **Automated reasoning**- Use remembered info to come to conclusions\n  - **Machine learning**- Adapt, recognize patterns and expand on them\n  - Total Turing Test\n    - **Computer vision**- in order to percieve\n    - **Robotics**- in order to move   \n- Thinking humanly\n  - **Cognitive Science** - Tries to figure out how the human mind works using tests\n- Thinking rationally\n  - Use logic to find a solution, if there is one\n- Actinng rationally: Rational Agent\n  - Acting perfectly rational is impossible in complex situations\n  - **Limited Rationality** - choosing the best option when not possible to do all calculations\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \n- **Weak AI**- act as intillegent\n- **Strong AI**- are intllegent (not simulating intellegennce)\n- **Qualification Problem**- hard to define all behaviours in a set of logical rules\n- **Embodied cognition**- study brain and body to gether, not seperately\n- **Good Old-Fashioned AI (GOFAI)**\n- **Qualification problem**- \n- **Anytime Algorithms**- Solution quality increases with time, so at any given time it has its best solution\n  - ex) iterative deepinging search\n- **Decision-theoretic metareasoning**- Computation values is dependent on the cost (time) and benefit (solution quality)\n  - Guarentees anytime property\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- Chinese room- computers have no understanding\n- **Polite Convention**- assuming everyone thinks\n- Biological naturalism\n- **Conciousness**- awareness of the outside owrld\n- **Qualia**- nature of expereince\n \n\n## AIMA 2.1 Agents and Environments\n \n- **Agent** acts on environment through **effectors**, perceieves usning **sensors**\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \n- **Rational Agent**\n  - Correct action- action that leads to success \n  - **Performance Measure**- used to tell how succesful an agent is\n  - **Omniscient** agent knows actual outcomes of its actions (impossible) \n  - Rationality is concerned with expected success given what it has percieved\n  - Rationality depends on:<br>\n    1) Performance measure<br>\n    2) **Percept sequence**- history of what the agent has percieved<br>\n    3) What an agent knows<br>\n    4) Action that agent is capable of<br>\n  - **Ideal Rational Agent**- Performs action that maximizes performance measure (given precept history and knowledge)\n- **Mapping**- list of actions from precept sequences\n  - **Ideal mapping**\n- **Autonomy**- actions based on more than just built in knowledge \n  - Behaviour determined by its own experiences\n  - Should be able to operate in multiple environments  \n\n## AIMA 2.3 The Nature of Environments\n\n- **Task Environments**- the area which rational agents can solve problems\n- Defining a task environemnt:\n  - **P**erformance (ex. safe, fuel efficient, minimize trip time, max profits)\n  - **E**nvironemnt (ex. traffic, pedestrians, highway)\n  - **A**ctuators (ex. accelerator, break, output display)\n  - **S**ensors (ex. camera, lidar, ultrasound)  \n- Environment Types:\n  - **Fully observable**- knowing the complete state of an environment\n  - **Partially observable**- Only know part of the state (innacurate sensors, missing data)\n  - **Unobservable**- no sensors\n- Agent Types:\n  - **Single agent**\n  - **Multiagent**- Another agent that is working to maximize its performance\n    - **Competitive**- Maximizing A success decreases B success (chess)\n    - **Cooperative**- work together to succeed (avoid car crash)\n- Deterministic\n  - **Deterministic**- state is completely influenced by the current state and the next action performed\n  - **Nondeterministic**- Not deterministic\n  - **Stochastic**- non-deterministic but specifically deals with percentages (ex. 25% chaince of rain)\n- Episodic\n  - **Episodic**- percieves situation, performs action with no future implication\n  - **Sequential**- decisions can effect future decisions (chess, driving)\n- Static\n  - **Static**- Environment remains same until action is taken (chess)\n  - **Dynamic**- Environment always changing (road while driving)\n  - **Semidynamic**- ex. Chess with a clock\n- Discrete\n  - **Discrete**- Limited states and actions (ex. Chess)\n  - **Continuous**- Unlimited states and actions (ex. Driving)\n- Known\n  - **Known**- Outcome of actions is known \n  - **Unknown**- Outcome of actions is unkown\n\n\n\n## AIMA 2.4 The Structure of Agents\n\n- **Agent Programs** implement an **Agent Function**\n- **Agent Architecture**- the physical sensors and actuators that make an agent\n  - Receive precepts, run the program, send actions to actuators\nagent = architecture + program\n-  **Agent Programs**\n  - Skeleton: input is precepts, return action\n  - Agent program only takes current precept, agent function depends on precept history\n  - Table driven agents are too large\n- **Simple Reflex Agents**- only take action on current precept\n  - **Condition-action rule**- condition triggers an action (ex. car infront breaking -> initiate break)\n    - A.k.a situation-action rules, productions, if-then rules\n  - infinite loops are a problem with such simplicity\n  - **Randomization**- makes a random choice if certain criteria is met\n    - This might be better than a deterministic agent\n- **Model-based reflex agents**\n  - **Internal State**- remembers past precepts\n  - Requires:\n    - **Transition Model**- how the agents world channges with time\n    - **Sensor Model**- how the agent percieves the world\n- **Goal-based agents**\n  - More flexible\n  - Agent makes an action in order to achieve a specific goal\n- **Utility based agents**\n  - **utility**- quality of the solution of the agent \n  - **utility function**- performance measure of utility\n  - **expected utility**- utility when there is uncertainty \n  - **model-free agent**- learns best action without knowing direct impact onn environemnt\n- **Learning Agent**\n  - **Learning element**- makes improvements\n    - uses feedback from **critic**\n  - **Performance element**- makes actions\n  - **Problem generator**- Suggests new action that are unfamiliar\n- **Atomic Representation**- each state is a \"black box\"\n- **Factored Representation**- states are represented as **variables**/**attributes** that are given a value.\n- **Structured Representation**- objects and relationships are defined explicitly.\n- **Localist Represenation**-  1:1 mapping of concept to a physical memory location\n- **Distributed Representation**- concepts are spread over memory locations (more robust)\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n**Problem-Solving Agents**\n- **Goal Formulation**- creating goals that then influence behaviour\n- **Problem Formulation**- the states and actions the agent considers\n- **Search**- Simulating sequences until one sequences accomplishes the goal (**solution**)\n- **Execution**- performing the action of the solution\n- **Open-loop**- agent ignores precepts on the way to solution\n- **Closed-loop**- agent possibly corrects itself on path (ex. used if environemtn is nondeterministic)\n- **Problem Definition**:\n  - States or State Space\n  - Initial State\n  - Goal States\n  - Actions\n  - Transisiton model- result of certain action\n  - Action cost function\n- **Path**- sequence of actions\n- **Optimal Solution**- lowest possible cost\n- **Model**- mathematical model\n- **Abstration**- removing detail from a problem representation\n  - valid if we can use the general solution in the more detailed world\n  - Ex. finding shortest way to Arad without worrying about roads or driver skill\n  \n\n## AIMA Chapter 3.2 Example Problems\n\n- **Standardized Problems**\n  - ex) grid world, vacuum world\n  - **States**\n  - **Initial State**\n  - **Actions**- \n  - **Transition Model**\n  - **Goal States**\n  - **Action Cost**\n- **Real-world Problems**\n  - ex) route finding problem, VLSI layout (positioning components to minimize area on a chip)\n  - **States**\n  - **Initial State**\n  - **Actions**- \n  - **Transition Model**\n  - **Goal States**\n  - **Action Cost** \n\n## AIMA Chapter 3.3 Search Algorithms\n\n- **Search Algorithm**- solves a searhch problem\n- **node**- state in a **search tree**\n- **Search Tree** is different from a **State Space** because state space has all possible states and the actions while search tree has the paths between the states.\n- **Expand** a node by taking an action, thus **generating** a new node\n- **Frontier** seperates the region that has been explore and region that has yet to be explored\n- **Best First Search**- choose node with smallest value from evaluation function f(n)\n- Data stuctures\n  - Frontier\n    - **Queue**\n      - **Priority Queue**- pops node with lowes f(n)\n      - **FIFO**- pops node that was added to queue first\n      - **LIFO** (aka **stack**)- pops node was added to queue last (most recently)\n      - Reached states should be stored as a lookup table (dict)\n- **Redundant Paths**\n  - **Graph search**- checks for redundnat paths\n  - **Tree search**- does not check for redundant paths\n  - Check for cycles\n- Measuring problem-solving\n  - **Completeness**- returns solution if there is one, returns failure if none\n    - Algorithm must be **systematic**\n  - **Optimal**- returns solution with lowest path cost\n  - **Time complexity**- how long it takes to find solution\n  - **Space complexity**- how much memory is needed to find a solution\n- **depth**- d, m- maximum depth\n- **branching factor**- b, number of successors\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- **Breadth-first Search**\n  - **early goal test**- check if node is a solution as soon as its generated\n  - **late goal test**- wait for node to be popped off queue\n  - Optimal if all actions have same cost, always complete\n  - Time and Space Complexity: O(b^d)\n- **Uniform-Cost Search**/**Djkstra's Algorithm**\n  - Check for goal when expanding\n  - Complete and optimal\n- **Depth-first Search**\n  - Not optimal, incmoplete\n  - Much smaller memory than breadth-first or best-first O(bm)\n  - **Backtracking Search**- uses less memory, one successor generated at a time\n- **Depth limited** and **Iterative Deepeninng**\n  - **Depth limited**\n    - depth limit l, if pick l badly than will fail\n    - **diameter**- known good value for depth limit l\n  - **Iterative Deepining**\n    - increases depth every iteration\n    - Optimal when all actions have same cost\n    - Complete\n- **Bidirectional Search**\n  - Searches from initial state and goal state\n\n   \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n## WARNING: Your summary of 'AIMA Chapter 3.5 Informed (Heuristic) Search Strategies' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n- **Informed searches** use **hueritic functions**, h(n)\n- **Greedy best-first search**\n  - expands lowest h(n)\n  - complete in finite spaces\n- **A*search**\n  - f(n) = g(n) + h(n)\n  - **consistency**- concisisten if every node nn and successor of n, n' from action a satisfies: h(n) <= c(n, a, n') + h(n')\n    - form of **triangle inequality** (1 side of a triangle can't be longer than the sum of the other 2)\n  - g(n) is cost from initial state to current node\n  - **Admissable Huerisitc** never overestimates\n  - Optimal with consistent hueristic \n  - Can be optimal with inadmissable hueristic \n  - **monotomic**- path cost always increases as you move forward\n  - **Sureley expanded nodes**- nodes with f(n) < C*, C* is cost of optimal solution\n  - **Optimally efficient**- all search algorithms that epand from the initial state using the same hueristic with expand all nodes that were expanded by A*\n  - **Prunes**- remove nodes not neccessary for finding optimal solution\n  - Complete, optimal, and optimally efficient\n  - **Satisficing**- solutions that are **good enough**\n    - ex) using an inadmissable hueristic that is more accurate\n  - **Detour index**- multiplier on straight line distance to account for curves in the road\n  - **Weighted A* Search**- giving the huerisitc more weight than g(n)\n- **Bounded supotimal Search**- solution must be with in a factor, W, of the optimal cost\n- **Bounded-cost search**- cost of solution is less than a constant C\n- **Unbounded-cost search**- any solution as long as it is found quickly\n- **Memory-bounded Search**\n  - **Reference counts**- number of times a state has been reached\n  - Remove from table when reference count max has been hit\n  - **Beam search**- limits frontier size by only keeping k nodes with best f(n)\n    - Incomplete, suboptimal\n  - **Iterative Deepining A* Search** (IDA*)- cutoff is the f(n) cost\n  - **Recursive Best-First Search** (RBFS)- acts a recursive depth-first search. Keeps track of f-limit and when this number is exceed it backs up and continues down the path with the better f-value.\n    - more efficient than IDA*\n    - optimal if hueristic is admissable\n  - **MA*** (memory-bound A*)- \n  - **SMA*** (simplified MA*)- continues like A* until memory is full, then drops node with worst f-value\n    - If all lead nodes have same f-value, then the oldest node is deleted and newest is expanded\n    - If there is only one leaf than the node is forgotten like it had no successors\n    - Complete if memory allows\n- **Bidirection Hueristic Search**\n  - must consider pairs of nodes (from each frontier)\n  - **Front-to-end search**- h_f is hueristic from front, h_b is huerisitc from back\n  - **Front-to-front search**- uses huerisitc to estimate distance between frontiers\n  - Bidirection expands fewer nodes with an average huerisitc, with a very good huerisitic it does not add much\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- **Manhattan Distance**/**City Block Distance**- min number of moves needed to get block to right location\n- **Effective Branching Factor** (b*)- want to be close to 1\n  - Equation: N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d\n  - N- total nodes generates, d- solution depth\n- h2 **dominates** h1 if h2 is always better than h1\n- **Relaxed problem**- problem with less rules\n- **Subproblem**- finding optimal solution for a simpler problem than the actual problem\n  - ex) For 8 tile- Getting tiles 1,2,3,4 into correct location and other tiles dont matter\n- **Pattern Databses**- store solution for all subproblems\n- **Disjoint Pattern Databases**- Combining solutions from subproblems that dont overlap\n  - ex) Getting 1,2,3,4 into correct location and getting 5,6,7,8 into location but other tiles don't exisist\n- **Precomputation**- solving problem optimally once and then using\n- **Landmark Points**- solving C* for all landmark points and using them as part of the huerisitc \n- **Shortcuts**- artificial edges that describe an optimal path\n- **Defferential Huerisitc**- huerisitc that subtracts two values rather than adds them\n- Learning to Search Better\n  - **metalevel state space**- states in a metalelvel state space are the computation state of the program\n  - **metalevel learning**- learns from mistakes\n  - Goal of learning is to minimize **total cost**\n- Learning from experience\n  - Learning from doing the problem multiple times\n  - **Features**- descriptors of a state (ex. # of misplaced tiles)\n  - Linear combination equation:\n    - h(n) = c_1 * x_1(n) + c_2 * x_2(n)\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- **economy**- price increases as demand increases, don't have to predict action of an agent\n- **Evaluation Function**- estimates who is winning based off features of the game/state\n- Two Player, Zero Sum Games\n  - **Perfect Infomration** == **Fully Observable**\n  - **Zero-Sum**- something that is good for one player can not also be good for the other\n  - **move** == **action**\n  - **position** == **state**\n  - Defined using:\n    - Initial State, S_0\n    - To-Move- players whose it is\n    - Actions- legal moves\n    - Result- **transisition model** is used to solve for the resulting state from the action\n    - Is-Terminal- **terminal test** is used to see if game is over (or in **terminal state**)\n    - Utility- **utility function** solves if player has won, lost or tied\n  - **Game Tree**- search tree for every sequence of moves until the game is over\n    - Can be infinite\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- **Minimax Search**\n  - Depth-first\n  - **ply**- single player has moved, one more level deeper in the game tree\n  - **Minimax value**- value of the utility, assumes both players play perfectly\n  - **Minimax Decision**- decision made using the minimax value\n  - Time Complexity: O(b^m), m- maximum depth of tree, b- # of legal moves\n  - Space Complexity: O(bm)\n- Multiplayer Games\n  - Must replace single value of each node with a vector of values. This vector gives the utility of the state from each player’s viewpoint. (In two-player, zero-sum games, the two-element vector can be reduced to a single value because the values are always opposite.)\n  - Multiplayer games contain **alliances**\n- **Alpha-Beta Pruning**\n  - Alpha- the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. Think: “at least.”\n  - Beta- the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. Think: “at most.”\n  - Effictivenes depends on order states are examined\n- Move ordering\n  - If done perfectly, alpha-beta effective branching factor becomes sqrt(b)\n  - Dynamic move ordering- trying moves that had been the best in the past\n  - **killer moves**- best move\n  - **transposition**- repeated states due to different move order leading to the same state\n  - **transposition table**- stores huerisitc values of states\n  - Chess Computer:\n    - **Type A strategy**- consider all moves to a certain depth, uses huerisitic to estimate the quality of the states at this depth. Wide but shallw.\n    - **Type B strategy**- ignore moves that look bad and follow only good ones. Deep but narrow.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- To use time more efficiently:\n  - Apply huerisitc **evaluation function** to states, treating noterminal nodes as terminal\n  - Replace terminal test with **cutoff test**\n    - Cuts off at terminal states or at other cut off points seach certain depth\n- Huerisitc evaluation function- returns estimate of the expected utility of a state to a player\n  - For non terminal states, the eval must be between a win and a loss\n  - Calculate **features** (ex. pawns on the board)\n  - **Expected Value** = sum(chance * value)\n  - **Weighted Linear Function**- weighted sum of all features\n    - Assumes each feature is independent\n  - Function should only be applied to **Quiescent** positions- positions with no next move that drastically changes the game\n    - Knowns as **quiescent search**\n  - **Horizon Effect**- trying to delay the inevitable because it is past the depth that is seen\n  - **Singular Extension**- extends certain moves that are clearly better\n- **Forward Pruning**- prunes moves that seem bad (Type B)\n- **Late Move Reduction**- assumes move ordering is good, moves later in the list are worse. Then reduces depth that these moves are explored.\n- **Policy**- mapping every possible state to the best move in that state\n- **Retrograde**- minimax in reverse, finds winning positions than does reverse moves to get to current position\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- **Stochastic Games**- involve random element (ex. dice)\n  - Includes **chance nodes** and Max/Min nodes\n- **Expectiminimax Value**- expected value pf the min/max move\n- **Probability** = Expected utility for nonn zero sum games\n- Able to prune channce nodes\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Choose actions based on desirability of the immediate outcomes \n- **Maximum Expected Utility** (MEU)- rational agent should choose the action that maximimzes the expected utility\n- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n- **Lottery**- how treat outcome of each action\n- Constraints preference rlations must obey (axioms of utility theory):\n  - Orderability- given 2 lotteries, a rational agent must prefer one or decide they are equal\n  - Transitivity- If agent prefers A to B and B to C then they must prefer A to C\n  - Continuity- If lottery B is between A and C, then there is a probability, p, that rational agent will be indifferent between knowing the result B and the lottery that yields A with probability p and C with probability 1 - p\n  - Substitutability- If agent is indifferent about A and B then A and B can be substituted in a more complex lottery\n  - Monotonicity- If two lotteries have the same two possible outcomes. If an agent preferes A to B, then the agent must prefer that has a higher probability for A\n  - Decomposability- Compound lotteries can be reduced to simpler ones using the laws of probability\n- Existence of utility function: If an agents preferences obey the axioms of utility (above), then there exists a function U such that U(A)>U(B) if and only if A is preferred and A = B if indifferent\n- Expected utility of a lottery- The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n- The existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n- Utility functions map from lotteries to real numbers\n- **Preference Elicitation**- present choices to hum and observing preference to find utiloty function\n- **Normalized Utilites**- use a scale of u_lower = 0 and u_upper = 1\n- How to ascess utility\n  - Agent choose between S and **Standard Lottery** [p, u_upper; (1-p), u_lower], adjust p until it is indifferent\n- **Value of Statistical Life** = ~$10 million \n- **micromort**- one in a million chance of death\n- **QALY** (quality-adjusted life year)- accept shorter life expectancy to avoid disability\n  - ex) kidney patient on average are indifferent between living 2 years on dialysis and one year at full health\n- **Monotonic Preference**- prefer more than less\n- **Risk-Averse** vs. **Risk-Seeking**\n- EMV- expected monetary value\n- **Certainty Equivalent**- value agent will accept instead of doing a lottery\n- **Insurance Premium**- difference between the EMV of a lottery and its certainty equivalent\n- **unbiased**- ecpected value of error is zero\n- **Order statistic**- distribution of any ranked element of a sample\n- **Optomizer's curse**- Tendency for the estimated expected utility of the best choise to be too high\n- Human Judgement and Irrationality\n  - **Normative theory**- describes how a rational agent should act\n  - **Descriptive Theory**- describes how actual agents do act\n  - **Certainty Effect**- people love gains that are certain\n  - **ambiguity aversion**- people choose the known probabilities over unknown\n  - **framing effect**- wording of a problem effects decision\n  - **anchoring effect**- people make relative utility judgements\n    - ex) A $200 bottle of wine is too much but $50 is reasonable\n  - **Evolutionary Psychology**- - brain's decision making did not evolve to solve word problems\n \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- CSP's contain:\n  - X, a set of variables\n  - D, set of domain, 1 per variable\n  - C, set of contraints\n- Domain consisits of allowable values for variables\n- Constraints are a par: <scope, rel>\n  - scope- tuple of variables that participate\n  - rel- **relation** that defines them\n- An **assignment** that does violate a constraint is a **concistent** assignment\n- **Complete Assignment**- ever variable is assigned a value\n- Solution to CSP is a concistent, complete assignment\n- **Partial Assignment**- some variables unassigned\n- **Partial Solution**- partial assignment that is consestent\n- **Constraint Graph**- visualization of CSP\n- Why choose CSP:\n  - CSPs yield a natural representation for a wide variety of problems\n  - They have been developed for years and are fast and efficient\n  - Quickly prune large search spaces that atomic state-space searchers cannot\n- **Precedence Constraints**- Constrain on order of how things happen\n- **Disjunctive Constraint**- Two things that can't happen at the same time\n- Simplest CSPs ahave **discrete, finite domains**\n- A discrete domain can be **infinite**\n  - Must use implicit constraints\n- **linear constraints**- variable appears only in linear form\n- No algorithm exists for solving general **nonlinear constraints** on integer variables\n- **Continuous Domains** (ex. Hubble Telescope)\n- **Linear Programming** problmes- constraints must be linear equalities or inequalities\n- **Unary Constraint**- constrain a single variable\n- **Binary Constraints**- constrain two variables\n- **Binary CSP**- only has unary and binary constraints\n- **Global Constraints**- constrain arbitrary number of variables\n  - Alldi f f constraint- all variables involved must have different values\n- **Cryptarithmetic puzzles**- each letter has a different digit\n- *Constrain Hypergraph**- hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares), which represent -ary constraints—constraints involving variables\n- **Dual graph** transformation- convert n-ary CSP to binary. \n  - create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\n- **Preference constraints**- indicates preffered solutions \n- **Constrained Optimization Problems** (COP)- CSPs with preferences, solved with optimization search methods\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- **Constraint Propogation**- using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable\n- **Local Cosistency**- Treat each variable \n  - Treat each variable as a node in a graph and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph\n- **Node consistency**- single variable satisfy unary constraints\n- **Arc consistency**- every variable satisfies binary constraints\n- AC-3\n  - Maintains que of arcs to consider (initially all arcs)\n  - Then pop-off any arc\n  - Make X_i consistent with X_j\n  - If the domain is unaffected it continues to next arc, if not:\n    - Add to queue all arcs that are neighbors of X_i or X_j\n  - If domain is empty than CSP has no solution\n  - If queue is empty, search is done\n  - Time complexity O(d^2), worst case O(cd^3)\n    - d- domain size, c- arcs\n- **Path consistency**- tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n- **k- consistency**- for any k-1 variable with consisten assignments to them, a consisteny value can always be assigned to the kth variable\n- **Strongle k-consistent**-  k-consistent and is also (k-1)-consistent, (k-2)-consistent, all the way down to 1-consistent. \n- **Resource Constraint** (Atmost constraint)- constrained by total resources\n  - ex) 10 total teachers assigned for tasks, if more than 10 are assigned -> fail\n- **bounds propagation**- resource connstrain but there is a min and max of resources\n- **Bounds consistent**- bounds propagation is satisfied\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n- **Commutativity**- order of application of actions doesn't matter\n- **Minimum-Remaining-Values** hueristic (MRV)- choose variable with least amount of legal values\n- **Degree Hueristic**- select variable that is involved in most amount of constraints\n  - reduces branching factor\n- MRV is usuallly better, but degreee is helpful as a tie breaker\n- **Least-constraining-value**- prefers value that rules out fewest choices for neighboring variables\n- **Forward-checking**- when variable X is assignned, forward checking establishes arc concistency for it\n  - inference type\n- **Maintaining Arc Consistency**- checks deeper inconsistencies than forward checking\n  - Recursively propogates constraints when changes are made to variable domains (forward-checking does not)\n- **Chronological Backtracking**- - branch fails, back up to preceding variable and try a different variable\n- **Conflict set**- Set of assignments that are in conflict\n- **Backjumping**- backtracks to most recent assignment in the conflict set\n  - Tells how far to back up so we down change variables that won't fix anything\n  - Redundant to forward checking, only need one or the other \n- **Conflict-directed Backjumping**- backjumping algorithm that uses conflict sets to predict future failures\n- **Constraint learning**- finding a minimum set of variables from the conflict set that causes the problem.\n- **no-good**- Set of variables from constraint learning\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n- **min-conflicts** hueristic- elect the value that results in the minimum number of conflicts with other variables\n  - For n-queens problem this roughly independent of problem size\n- **Tabu Search**- keeping a small list of recently visited states and forbidding the algorithm to return to those states.\n- **Constraint Weighting**- All constraints initially valued at 1, then as constraints are broken the weights are changed depending on frequency amount of times constraint is broken\n  - Adds topography to avoid plateuing\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- **Indpedent subproblems**- subcomponents of a problem that do not effect each other\n- **Connected Components**\n- **Tree**- constraint graph when any two variables are connected by one path\n  - any tree-structured CSP can be solved in time linear in the number of variables\n- **Directional Arc Consistency** (DAC)- with ordered variables X_1, X_2,..,X_n, X_i is arc concistent with each X_j for j>i\n- **Topological Sort**- ordering of the variables such that each variable appears after its parent in the tree\n- Cutset Conditioning\n  1. Cut a subset, S, of CSPs variable so that the constraint graph becomes a tree after removal. S is **cycle cutset**.\n  2. For each possible assignment to the variable on S that satisfy S:<br>\n    a. remove values from the domains of the remaining variables that are inconsistent with S.<br>\n    b. If the CSP has a solution, return with the assignment for S.\n  - Cycle cutset has size c -> Time Complexity O(d^c * (n - c)d^2)\n- **Tree Decomposition**- a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n  - Must satisfy 3 requirements:\n    - Every variable in the original problem must appear in at least 1 of the tree nodes\n    - If 2 variables are connect by a constrain in the original problem, they must appear together in at least of 1 of the tree nodes\n    - If a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes\n      - any variable from the original problem must have the same value wherever it appears\n  - Time complexity O(nd^2)\n  - **tree width**- One lest than size of largest node\n    - With tree width, w the problem can be solved in O(nd^(w+1)) time\n    - CSPs with constraint graphs of bounded tree width are solvable in polynomial time\n- **Value Symmetry**- multiple ways to assign values\n- **Symmetry breaking constraint**- break symmetry in assignments.\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- **Knowledge Base** (KB)- Set of **sentences**\n- **Knowledge representation language**\n- **Axiom**- sentence that was given, not derived\n- **Inference**- Deriving new sentences from old\n- **Background Knowledge**\n- When agent is called it does:<br>\n  1. Tells knowledge base what it percieves<br>\n  2. Asks knowledge base what action it should perform<br>\n  3. Agennt tells knowledge base which action was chosen and returns the action for execution<br>\n- **Knowledge Level**- specify only what the agent knows and what its goals are, in order to determine its behavior\n- **implementation level**\n- **Declarative** Approach- Begin with empty KB, then designer tell sentence one at a time until agent knows how to operate\n- **Procedural** approach- encodes desired behaviors directly as program code\n- Succesful agent often combines both approaches\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- **Wumpus World**- cave consisting of rooms connected by passageways\n- Definition of task enviornment is given by PEAS\n\n\n## AIMA Chapter 7.3 Logic\n\n- **Semantics**- meaning of sentence\n  - Defines the **truth** for each possible **world**\n- Every sentence must be either true or false in each possible world—there is no “in between.”\n- **model**- possible world that is not in real environment\n- I sentence, a, is true in model, m than m **satisfies** a or m **is a model of** a. M(a)\n- **Entailment**- a sentence follows logically from another sentence\n- **Logical Inference**- entailment used to derive conclusions\n- **Model checking**- algorithm that unumarets all posible models to check that a is true in all models with KB is true\n- **Sound**/**truth-preserving**- inference algorithm that only derives entialed sentences\n  - Unsound makes things up\n- **Completeness**- an inference algorithm is complete if it can derive any sentence that is entailed\n- If KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world\n- **Grounding**- connection between logical reasoning and processes and the real enviornment that the agent exists in\n  - Sensors create connection\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n- **Propositional Logic**- algorith for logical inference that uses semantic notation of entailment\n- **Syntax**- defines allowable sentences\n- **Atomic sentences**_ consist of a single **propositional symbol**\n- **Complex Sentences**- Combination of simpler sentences using parentheses and operators called **logical connectives**\n  - **Logical Connectives** (symbol on seperate paper) (in order of precedence):\n    - not- **negation**. A **literal** is either an atomic sentence (positive literal) or a negated atomic sentence (negative literal)\n    - and- **conjunction**, each part is a **conjunct**\n    - or- **disjunction**, each part is a **disjunt**\n    - implies- **implication** or **rules** or **if-then**- Its **premise** or **antecedent** and its **conclusion** or **consequent**\n    - if and only if- **biconditional**\n- **Truth value**- true or false\n- Complex sentence rules: \n  - not P is true iff is false in m. \n  - P and Q is true iff both P and Q are true in m\n  - P or Q is true iff either P or Q is true in m\n  - P implies Q is true unless P is true and Q is false in m \n  - P if and only if Q is true iff P and Q are both true or both false in m\n- every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n- **Theorem Proving**- pplying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models\n- If # of models is large and length of proof is short, then theorem proving can be more efficient than model checking\n- **Logical Equivalence**- 2 sentences a and b are logically equivalent if they are true in the same set set of models\n- **Validity**- sentence is valid if it is true in all models\n- **tautologies**- necessarily true, valid sentences\n- **Deduction theorem**\n- **Satisfiability**- sentence is satisdiable if it is true in or satisfied by some model\n- **SAT** Problem- determining the satisfiability of sentences in propositional logic\n- **Reductio ad absurdum**- reduction to an absurd thing\n  - aka **refutation** or proof by **contradiction**\n- *Inference Rules** (on seperate piece)\n- **monotonicity**- set of entailed sentences can only increase as information is added to the knowledge base\n- **Resolution**\n- **Conjunctive Normal Form** (CNF)- sentence expressed as a conjunction of clauses\n  - Setps on seperate piece\n- **Resolution closure**- the set of all clauses derivable by repeated application of the resolution rule to clauses in or their derivatives\n- **Ground resolution theorem**- If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}