{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "5yG3-YncJfTB"
      ],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9c935a08-e79b-4339-d91a-09e5f971aa0e"
      },
      "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": 56,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "683cd6c7-468f-4201-eb49-7127b08a5704"
      },
      "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": 57,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\"Limits of AI\"\"\"\n",
        "chapter27_2 = \"\"\"Can Machines Really Think\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"Intelligent Agents: Agents and Environments\"\"\"\n",
        "chapter2_2 = \"\"\"Good Behavior: Rationality\"\"\"\n",
        "chapter2_3 = \"\"\"The Nature of Environments\"\"\"\n",
        "chapter2_4 = \"\"\"Structure of Agents\\n\n",
        "1) simple reflex agents\\n\n",
        "2) model based reflex agents\\n\n",
        "3) goal-based agents: search \\n\n",
        "4) utility-based agents\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "\"Ch1\" : \"Ch1\",\n",
        "\"rationality\" : \"doing the right thing\",\n",
        "\"Turing test\" : \"can a machine think?\",\n",
        "\"rational agent\" : \"agent that acts to get the best (expected) outcome\",\n",
        "\"standard model\" : \"AI model with agents that do the right thing\",\n",
        "\"limited rationality\" : \"when computational demands are too high, acting appropriately\",\n",
        "\"value of alignment problem\" : \"the objectives/values that a machine has must be aligned with those of a human\",\n",
        "\"provably beneficial\" : \"how to define fgood in AI, build in uncertrainty about human preferences\",\n",
        "\"ch 27_1\" : \"ch 27_1\",\n",
        "\"weak AI\" : \"machines could act as if they were intelligent, but arent actually intelligent\",\n",
        "\"strong AI\" : \"machines that act intelligent actually are consciously thinking\",\n",
        "\"Good Old Fashions AI (GOFAI)\" : \"formal set of rules that try to define human behaviors (criticized by Turing)\",\n",
        "\"qualification problem\" : \"the difficulty of capturing every possible behavior with a set of necessary and suffieicinet logical rules\",\n",
        "\"embodied cognition\" : \"you shouldn't consider the brain separately in AI, should encompass the entire body & its environment too(sensors)\",\n",
        "\"ch 27_2\" : \"ch 27_2\",\n",
        "\"Chinese room\" : \"experiment where Chinese appeared to be translated, but was not understood\",\n",
        "\"biological naturalism\" : \"mental states are high level features caused by low level physical processes in the neurons\",\n",
        "\"consciousness\" : \"awareness of outside world, self, subjective expereinces of living\",\n",
        "\"qualia\" : \"the intrinstic nature of experiences\",\n",
        "\"ch2\" : \"ch2\",\n",
        "\"sensor\" : \"how an agent perceives environemnt\",\n",
        "\"actuator\" : \"how an agent acts on environemnt\",\n",
        "\"percept\" : \"content that an agent's sensor perceive\",  \n",
        "\"percept sequence\" : \"historyof everything an agent has pereived\",\n",
        "\"agent function\" : \"maps percept sequence to an action for the agent\",\n",
        "\"agent program\" : \"implementation of agent function in real life\",\n",
        "\"rational agent\" : \"agent that does the right thing\",\n",
        "\"consequentialism\" : \"evaluating agent's behavior by its consequences\",\n",
        "\"omniscience\" : \"an agent that knows the actual outcome of its actions, this is impossible\",\n",
        "\"information gathering\" : \"performing actions to modify future percepts, exploration\",  \n",
        "\"learn\" : \"moodify its knowledge from what it perceives from environment\",\n",
        "\"autonomy\" : \"an agent that acts on its own percepts and learning\",\n",
        "\"task environments\" : \"a situation that an agent must solve\",\n",
        "\"PEAS\" : \"parts of a task environment, Performance, Environment, Actuators, Sensors\",\n",
        "\"fully observable\" : \"agent knows the complete state of the environment at each point in time\",\n",
        "\"partially observable\" : \"an agent onlt sees part of the envirnoment at a point in time\",\n",
        "\"single vs multi agent\" : \"one agent or multiple agents\",\n",
        "\"competititve vs cooperative\" : \"ceompeting against one another vs working together\",\n",
        "\"deterministic vs nondeterministic\" : \"next state is 100% determined by agent's current state and actionvs not\",\n",
        "\"stochastic\" : \"environment that deals with probabilities\",\n",
        "\"episodic\" : \"agent's experience split up into atomic episodes, next eipsode doesn't depend on previous ones\",\n",
        "\"sequential\" : \"the current decisions have an effect on future ones\",\n",
        "\"static vs dynamic\" : \"environment doesnt change while agent things vs it does\",\n",
        "\"discrete vs continuous\" : \"envinroments and actions can be discrete or continuous\",\n",
        "\"known vs unknown\" : \"agent's konws the outcome of all its actions vs agent has to learn how the environment works\",\n",
        "\"simple reflex agent\" : \"select actions based ONLY ON the current percept\",\n",
        "\"condition-aciton rule\" : \"an agent taking an action based on a certain condition happening\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 59,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "34a29b2d-c4db-4f75-a69a-9e19c38e3042"
      },
      "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": 60,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\nLimits of AI\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nCan Machines Really Think\n\n## AIMA 2.1 Agents and Environments\nIntelligent Agents: Agents and Environments\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nGood Behavior: Rationality\n\n## AIMA 2.3 The Nature of Environments\nThe Nature of Environments\n\n## AIMA 2.4 The Structure of Agents\nStructure of Agents\n\n1) simple reflex agents\n\n2) model based reflex agents\n\n3) goal-based agents: search \n\n4) utility-based agents\n\n\n\n\n## Module 1 Lecture Notes\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content that an agent's sensor perceive\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Ch1** - Ch1\n* **Rationality** - doing the right thing\n* **Turing test** - can a machine think?\n* **Rational agent** - agent that does the right thing\n* **Standard model** - AI model with agents that do the right thing\n* **Limited rationality** - when computational demands are too high, acting appropriately\n* **Value of alignment problem** - the objectives/values that a machine has must be aligned with those of a human\n* **Provably beneficial** - how to define fgood in AI, build in uncertrainty about human preferences\n* **Ch 27_1** - ch 27_1\n* **Weak ai** - machines could act as if they were intelligent, but arent actually intelligent\n* **Strong ai** - machines that act intelligent actually are consciously thinking\n* **Good old fashions ai (gofai)** - formal set of rules that try to define human behaviors (criticized by Turing)\n* **Qualification problem** - the difficulty of capturing every possible behavior with a set of necessary and suffieicinet logical rules\n* **Embodied cognition** - you shouldn't consider the brain separately in AI, should encompass the entire body & its environment too(sensors)\n* **Ch 27_2** - ch 27_2\n* **Chinese room** - experiment where Chinese appeared to be translated, but was not understood\n* **Biological naturalism** - mental states are high level features caused by low level physical processes in the neurons\n* **Consciousness** - awareness of outside world, self, subjective expereinces of living\n* **Qualia** - the intrinstic nature of experiences\n* **Ch2** - ch2\n* **Sensor** - how an agent perceives environemnt\n* **Actuator** - how an agent acts on environemnt\n* **Percept sequence** - historyof everything an agent has pereived\n* **Agent function** - maps percept sequence to an action for the agent\n* **Agent program** - implementation of agent function in real life\n* **Consequentialism** - evaluating agent's behavior by its consequences\n* **Omniscience** - an agent that knows the actual outcome of its actions, this is impossible\n* **Information gathering** - performing actions to modify future percepts, exploration\n* **Learn** - moodify its knowledge from what it perceives from environment\n* **Autonomy** - an agent that acts on its own percepts and learning\n* **Task environments** - a situation that an agent must solve\n* **Peas** - parts of a task environment, Performance, Environment, Actuators, Sensors\n* **Fully observable** - agent knows the complete state of the environment at each point in time\n* **Partially observable** - an agent onlt sees part of the envirnoment at a point in time\n* **Single vs multi agent** - one agent or multiple agents\n* **Competititve vs cooperative** - ceompeting against one another vs working together\n* **Deterministic vs nondeterministic** - next state is 100% determined by agent's current state and actionvs not\n* **Stochastic** - environment that deals with probabilities\n* **Episodic** - agent's experience split up into atomic episodes, next eipsode doesn't depend on previous ones\n* **Sequential** - the current decisions have an effect on future ones\n* **Static vs dynamic** - environment doesnt change while agent things vs it does\n* **Discrete vs continuous** - envinroments and actions can be discrete or continuous\n* **Known vs unknown** - agent's konws the outcome of all its actions vs agent has to learn how the environment works\n* **Simple reflex agent** - select actions based ONLY ON the current percept\n* **Condition-aciton rule** - an agent taking an action based on a certain condition happening\n* **** - \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 = \"\"\"\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",  \n",
        "}"
      ],
      "execution_count": 61,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 202
        },
        "outputId": "e9771993-40a3-4fa3-b997-8c0961694e98"
      },
      "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": 62,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"Problem-Solving Agents\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"Search Problems\\n\n",
        "Best First Search: choose to expand node with minimum evaluation function value (f(n)) using a \\\n",
        "queue as the frontier\\n\n",
        "-There are 3 kinds of queues in serach problems: priority queue, FIFO queue, LIFO queue\\n\n",
        "1) priority queue: pops node w mimumm cost according to f(n), used in best-first search\\n\n",
        "2) FIFO queue: first in first out, used in breadth first serach\\n\n",
        "3) LIFO queue (stack): last in first out, used in depth first serach\\n\n",
        "x\\n\n",
        "x\\n\n",
        "Uninformed Search\\n\n",
        "1) Breadth First Search: f(n) is the depth of the node, FIFO queue\\n\n",
        "2) Dijkstra's algoirthm (Uniform cost serach)\\n\n",
        "3) Depth first serach: \\n\n",
        "4) Depth limited & iterative deepening search: prevent DFS from going down infinite path incorrectly\\n\n",
        "5) Bidirectional serach: searches forward form intial stae and backwards from goal state\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "-Terminology: \\n\n",
        "\t1) State: set S\\n\n",
        "\t2) initial state: si in S\\n\n",
        "\t3) Action: set of actions applicable in s\\n\n",
        "\t4) Transition Function: state + action  successor\\n\n",
        "\t5) Path Cost: performance measure, additive\\n\n",
        "\t6) Goal State: Goal(s)\\n\n",
        "x\\n\n",
        "-Useful Concepts:\\n\n",
        "\t-State Space: set of states\\n\n",
        "\t-Path: sequence of actions\\n\n",
        "\t-Frontier: states available for expanding\\n\n",
        "\t-Solution: path fron initial to goal state with actions\\n\n",
        "x\\n\n",
        "-Basic Search Algorithms:\\n\n",
        "(Abstract Search Algos)\\n\n",
        "-Tree Search \\n\n",
        "\t\t-nodes serached through transition model\\n\n",
        "\t-state vs node (has more info.)\\n\n",
        "\t-ex) 8-Puzzle Search Tree\\n\n",
        "\t\t-careful of repeated states, keep track of them\\n\n",
        "-Graph Search: keep track of all possible states, bad for memory b/c extra data structure\\n\n",
        "x\\n\n",
        "-(Instances of Search Algos)\\n\n",
        "-Uninformed Search: all non-goal nodes in frontier look equally good\\n\n",
        "-Informed Search: Some non-goal nodes can be ranked above others\\n\n",
        "\n",
        "-Search Strategy:\\n\n",
        "\t-Strategy: order for tree expansion\\n\n",
        "\t\t-implemented by queue data structure (LIFO DFS, FIFO BFS, priority)\\n\n",
        "\t-Dimensions: \\n\n",
        "\t\t-Completeness: always find solution?\\n\n",
        "\t\t-Optimality: least cost solution\\n\n",
        "-Time Complexity: # nodes generated\\n\n",
        "-Space Complexity: # nodes in memory simultaneously\\n\n",
        "\t-b, max. branching factor: max # of actions I can take from state\\n\n",
        "-d, depth: goal with minimum depth\\n\n",
        "-m: max possible length of any path in graph\\n\n",
        "x\\n\n",
        "x\\n\n",
        "(Uninformed Search)\\n\n",
        "1) Breadth-first Search: \\n\n",
        "-expand shallowest node\\n\n",
        "-frontier is FIFO queue: put successors at end of frontier\\n\n",
        "-**when to test during algo** whether node is solution as soon as you expand node\\n\n",
        "x\\n\n",
        "2) Depth-first Search:\\n\n",
        "\t-expand deepest first\\n\n",
        "\t-frontier is LIFO queue: put successors at front of frontier\\n\n",
        "x\\n\n",
        "  3) Depth-Limited Search: limit the depth of DFS with l\\n\n",
        "\t-no inifinite paths\\n\n",
        "\t-pick l by luck: if l<d incomplete, l>d suboptimal\\n\n",
        "\t-so….\\n\n",
        "x\\n\n",
        "4) Iterative Deepening Search (ID Search): find best depth limit l\\n\n",
        "\t-use depth-limited search as subroutine, increasing l iteratively\\n\n",
        "x\\n\n",
        "(TABLE)\\n\n",
        "-Asymptotic Analysis\\n\n",
        "x\\n\n",
        "5*) “Uniform Cost” Search (Dijkstra’s): for weighted graphs (step cost is not all one like for 1-4 )\\n\n",
        "\t-name: all costs <100 first, then all costs 100 <= cost < 200, etc.\\n\n",
        "\t-g(N): path cost function\\n\n",
        "\t-frontier: priority queue data structure ordered by g(n)\\n\n",
        "\t-expand lowest path cost first\\n\n",
        "-**when to test during algo**: test node when picked for expansion (BFS: when added to frontier)\\n\n",
        "x\\n\n",
        "x\\n\n",
        "x\\n\n",
        "x\\n\n",
        "SEARCH SUMMARY:\\n\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\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",
        "\"optimal solution\" : \"lowerst path cost among all possible solution\",\n",
        "\"graph serach\" : \"check redundant path\",\n",
        "\"tree search\" : \"does not check redudnant path\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 63,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "126edcb5-8064-49ba-a4f3-50eaeab568c3"
      },
      "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": 64,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem-Solving Agents\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nSearch Problems\n\nBest First Search: choose to expand node with minimum evaluation function value (f(n)) using a queue as the frontier\n\n-There are 3 kinds of queues in serach problems: priority queue, FIFO queue, LIFO queue\n\n1) priority queue: pops node w mimumm cost according to f(n), used in best-first search\n\n2) FIFO queue: first in first out, used in breadth first serach\n\n3) LIFO queue (stack): last in first out, used in depth first serach\n\nx\n\nx\n\nUninformed Search\n\n1) Breadth First Search: f(n) is the depth of the node, FIFO queue\n\n2) Dijkstra's algoirthm (Uniform cost serach)\n\n3) Depth first serach: \n\n4) Depth limited & iterative deepening search: prevent DFS from going down infinite path incorrectly\n\n5) Bidirectional serach: searches forward form intial stae and backwards from goal state\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n-Terminology: \n\n\t1) State: set S\n\n\t2) initial state: si in S\n\n\t3) Action: set of actions applicable in s\n\n\t4) Transition Function: state + action  successor\n\n\t5) Path Cost: performance measure, additive\n\n\t6) Goal State: Goal(s)\n\nx\n\n-Useful Concepts:\n\n\t-State Space: set of states\n\n\t-Path: sequence of actions\n\n\t-Frontier: states available for expanding\n\n\t-Solution: path fron initial to goal state with actions\n\nx\n\n-Basic Search Algorithms:\n\n(Abstract Search Algos)\n\n-Tree Search \n\n\t\t-nodes serached through transition model\n\n\t-state vs node (has more info.)\n\n\t-ex) 8-Puzzle Search Tree\n\n\t\t-careful of repeated states, keep track of them\n\n-Graph Search: keep track of all possible states, bad for memory b/c extra data structure\n\nx\n\n-(Instances of Search Algos)\n\n-Uninformed Search: all non-goal nodes in frontier look equally good\n\n-Informed Search: Some non-goal nodes can be ranked above others\n\n\n-Search Strategy:\n\n\t-Strategy: order for tree expansion\n\n\t\t-implemented by queue data structure (LIFO DFS, FIFO BFS, priority)\n\n\t-Dimensions: \n\n\t\t-Completeness: always find solution?\n\n\t\t-Optimality: least cost solution\n\n-Time Complexity: # nodes generated\n\n-Space Complexity: # nodes in memory simultaneously\n\n\t-b, max. branching factor: max # of actions I can take from state\n\n-d, depth: goal with minimum depth\n\n-m: max possible length of any path in graph\n\nx\n\nx\n\n(Uninformed Search)\n\n1) Breadth-first Search: \n\n-expand shallowest node\n\n-frontier is FIFO queue: put successors at end of frontier\n\n-**when to test during algo** whether node is solution as soon as you expand node\n\nx\n\n2) Depth-first Search:\n\n\t-expand deepest first\n\n\t-frontier is LIFO queue: put successors at front of frontier\n\nx\n\n  3) Depth-Limited Search: limit the depth of DFS with l\n\n\t-no inifinite paths\n\n\t-pick l by luck: if l<d incomplete, l>d suboptimal\n\n\t-so….\n\nx\n\n4) Iterative Deepening Search (ID Search): find best depth limit l\n\n\t-use depth-limited search as subroutine, increasing l iteratively\n\nx\n\n(TABLE)\n\n-Asymptotic Analysis\n\nx\n\n5*) “Uniform Cost” Search (Dijkstra’s): for weighted graphs (step cost is not all one like for 1-4 )\n\n\t-name: all costs <100 first, then all costs 100 <= cost < 200, etc.\n\n\t-g(N): path cost function\n\n\t-frontier: priority queue data structure ordered by g(n)\n\n\t-expand lowest path cost first\n\n-**when to test during algo**: test node when picked for expansion (BFS: when added to frontier)\n\nx\n\nx\n\nx\n\nx\n\nSEARCH SUMMARY:\n\n\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Optimal solution** - lowerst path cost among all possible solution\n* **Graph serach** - check redundant path\n* **Tree search** - does not check redudnant path\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Informed (heuristic) Search\\n\n",
        "1) Greedy Best First Search: like best first serch but expands node with lowest h(n)\\n\n",
        "2) A* search: evaluation function is f(n) = h(n) + g(n), prunes away branches without checking them for efficiency, complete, cost optimal, efficient\\n\n",
        "others\\n\n",
        "3)weighted A* search:\\n\n",
        "4)memory-bounded search: uses memoryspace better than A+ serach, beam search: limits size of frontier\\n\n",
        "5)iterative deepending A* serach (IDA*): uses A* serach and also limits depth (just like for IDDFS)\\n\n",
        "6)\txrecursive best first serach (RBFS): similar to best first search but in linear space, like recursive depth first ssearch with limit\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"Heuristic Problems \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Informed Search\\n\n",
        "-Best First Search: uses heuristics to estimate, which uninformed search doesn’t do\\n\n",
        "1) Greedy Best-First Serach: select node to expand with minimum heuristic f(n) = h(n)\\n\n",
        "\t-priority queue  same as UCS with f(n) instead of g(n)\\n\n",
        "\t-this is bad: incomplete, suboptimal\\n\n",
        "\\n\n",
        "2**) A* Search: best best-first serach, expand most promising paths, avoid expanding already expensive ones\\n\n",
        "\t-f(n) = g(n) + h(n)\t\\n\n",
        "\t-Frontier: priority queue by increasing f(n)\\n\n",
        "\t-Admissability: never overestimates cost (pessimistic) to reach goal  optimistic\\n\n",
        "\t\t-0 <= h(n) <= h*(n)\\n\n",
        "\t\t-Define h(n), can make Relaxed Problems\\n\n",
        "\t\t-Dominance: if both admissable, bigger heuristic dominates because estimates better\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 65,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 823
        },
        "cellView": "form",
        "outputId": "c2993c46-b902-4e83-b341-8ab18a9753d5"
      },
      "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": 66,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed (heuristic) Search\n\n1) Greedy Best First Search: like best first serch but expands node with lowest h(n)\n\n2) A* search: evaluation function is f(n) = h(n) + g(n), prunes away branches without checking them for efficiency, complete, cost optimal, efficient\n\nothers\n\n3)weighted A* search:\n\n4)memory-bounded search: uses memoryspace better than A+ serach, beam search: limits size of frontier\n\n5)iterative deepending A* serach (IDA*): uses A* serach and also limits depth (just like for IDDFS)\n\n6)\txrecursive best first serach (RBFS): similar to best first search but in linear space, like recursive depth first ssearch with limit\n\n\n\n\n\n\n\n\n\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\nHeuristic Problems \n\n## Module 4 Lecture Notes\n\nInformed Search\n\n-Best First Search: uses heuristics to estimate, which uninformed search doesn’t do\n\n1) Greedy Best-First Serach: select node to expand with minimum heuristic f(n) = h(n)\n\n\t-priority queue  same as UCS with f(n) instead of g(n)\n\n\t-this is bad: incomplete, suboptimal\n\n\n\n2**) A* Search: best best-first serach, expand most promising paths, avoid expanding already expensive ones\n\n\t-f(n) = g(n) + h(n)\t\n\n\t-Frontier: priority queue by increasing f(n)\n\n\t-Admissability: never overestimates cost (pessimistic) to reach goal  optimistic\n\n\t\t-0 <= h(n) <= h*(n)\n\n\t\t-Define h(n), can make Relaxed Problems\n\n\t\t-Dominance: if both admissable, bigger heuristic dominates because estimates better\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 4 Definitions\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Game Theory\"\"\"\n",
        "chapter5_2 = \"\"\"Optimal Decisions in Games: Minimax Search\\n\n",
        "(TABLE)\\n\n",
        "Alpha Beta Pruning (see table)\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic Alphe Beta Tree Search \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic GAmes: involve random elemnts in the game, use expected minimax \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\"Basic Utility Theory:\\n\n",
        "-6 constraints\\n\n",
        "1)orderability: rational agent must prefer one or the other, else it must equally prefer each one\\n\n",
        "2)transitivity: given 3 lotteries, if the agent prefers A to B and B to C,it prefers A to C\\n\n",
        "3)continuity: if some lottery B is between A and C in terms of preference, then there \\\n",
        "is some probability p that agent will be indifferent between getting B \\\n",
        "for sure, and yield A with prob p and C with prob 1-p\n",
        "4)substitutability: if an agent indifferent between two lotteries A and B, then its also \\\n",
        "indiffferent between two more complex lotteries that are the same except that B\\\n",
        "is substituted for A in one of them\\n\n",
        "5)monotinicity: two lotteries have 2 possible otcomes, A and B, then if agent prefers A\\\n",
        "to B, it will chooose lottery w/ higher probabilty of A\\n\n",
        "6)decomposiblity: compound lotteries can be reduced to simpler ones using laws of probability\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Utility Functions \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "-Outline:\\n\n",
        "\t1) Games as Search\\n\n",
        "\t2) Adversarial Search\\n\n",
        "x\\n\n",
        "-Simple Games:\\n\n",
        "\t1) Multiagent: playing against opponent, basing our decisions on opponents decision\\n\n",
        "\t2) Static: no change in environment while agent is thinking\\n\n",
        "\t3) Discrete: finite set of actions (vs continuous like aiming a gun, angle is continuous)\\n\n",
        "\t4) Fully Obeservable: agent’s sensor gives complete state of environment\\n\n",
        "\t5) Strategic: next state determined by current state & action executed by agent & action of one other agent\\n\n",
        "x\\n\n",
        "-Key Properties of our games:\\n\n",
        "\t1) two player alternate moves\\n\n",
        "\t2) zero-sum: one wins, other loses\\n\n",
        "\t3) clear set of legal moves\\n\n",
        "\t4) well defined outcomes (win, lose, draw)\\n\n",
        "x\\n\n",
        "-Formalize Game Setup:\\n\n",
        "\t-Two players: MAX and MIN, MAX moves first\\n\n",
        "\t-take turns until game over\\n\n",
        "\t-winner gets award, loser gets penalty\\n\n",
        "\n",
        "\t-Games as search:\\n\n",
        "\t1) Initial state: board configuration\\n\n",
        "\t2) Successor function: list of (move, state) pairs specifying legal moves\\n\n",
        "\t* Evaluation functionL: given current state of the board, how good is it for us and our oppponents?\\n\n",
        "\t3) Terminal test: is game finished?\\n\n",
        "\t4) Utility function: gives numerical values of terminal states, ex) win (+inf), lose (-inf), draw (0)\\n\n",
        "\t5) MAX uses serach tree to determine next move\\n\n",
        "x\\n\n",
        "-How to Play Game by Searching\\n\n",
        "\tGeneral Scheme:\\n\n",
        "\t1) Consider all legal successors to current state (“board position)\\n\n",
        "\t2) Evaluate each successor board position\\n\n",
        "\t3) Pick move that leads to best board position\\n\n",
        "  4) After opponent moves, REPEAT\\n\n",
        "x\\n\n",
        "Design issues:\\n\t\n",
        "1) representing the ‘board’\\n\n",
        "2) representing legal next boards\\n\n",
        "3) evaluating positions\\n\n",
        "4) looking ahead\\n\n",
        "x\\n\n",
        "-2 players: MAX and MIN (MAX’s opponent)\\n\n",
        "-play computed from MAX’s vantage point\\n\n",
        "-MAX attemps to MAXimize MAX’s outcome, MIN attempts to MINmimize MAX’s outcome\\n\n",
        "\t-MAX moves first\\n\n",
        "\n",
        "\t-root (level 0) MAX\\n\n",
        "\t-alternate MAX/MIN labels for each successful tree level (ply)\\n\n",
        "\t-Even level is MAX’s turn, Odd level is MIN’s turn\\n\n",
        "x\\n\n",
        "-Game Trees:\\n\n",
        "\t-represents game problem by tree:\\n\n",
        "\t\t-node = ‘board position’, edge = legal moves\\n\n",
        "\t\t-root node is first position\\n\n",
        "\t-Evaluation function f assigns score to ‘board’ without reference to path\\n\n",
        "\t-terminal nodes represent way game could end with desirability label of that ending (win/lose/draw, \tnumerical score)\\n\n",
        "\n",
        "-Evaluation function: f(n)\\n\n",
        "\t-built using expert knowledge\\n\n",
        "\t-evaluate how good board position is based on static features of that board alone\\n\n",
        "\t-zero-sum assumption:\\n\n",
        "\t\t-f(n) > 0: if MAX is winning in position n\\n\n",
        "\t\t-f(n) = 0: if position n is tied\\n\n",
        "\t\t-f(n) < 0: if MIN is winning in position n\\n\n",
        "x\\n\n",
        "x\\n\n",
        "Nxt Section: Minimax and Alpha Beta Pruning\\n\n",
        "-Make the best move for MAX assuming that MIN always replies with the best move for MIN\\n\n",
        "-computed by recursion:\\n\n",
        "\t-backed-up value of a node is determined by value of its children:\\n\n",
        "\t\t-for MAX node: backed-up value is maximum of the values of its children\\n\n",
        "-for MIN node: backed-up value is minimum of the values of its children\\n\n",
        "x\\n\n",
        "(TABLE)\\n\n",
        "-Minimax Procedure:\\n\n",
        "\t-Until game is over:\\n\n",
        "\t\t1) start with current positoin as MAX node\\n\n",
        "2) expand game tree by fixed number of ply\\n\n",
        "3) apply evalution function to the leaf positions\\n\n",
        "4) calculate back-up values bottom-up\\n\n",
        "5) pick move assigned to MAX at root\\n\n",
        "6) wait for MIN to respond\\n\n",
        "x\\n\n",
        "(TABLE)\\n\n",
        "-Alpha-Beta Pruning: cut out parts of tree that make no difference in final decision  reduce number of branches\\n\n",
        "\t-during Minimax:\\n\n",
        "\t\t-alpha: MAX’s current lower bound on MAX’s outcome\\n\n",
        "\t\t-beta: MIN’s current upper bound on MIN’s outcome\\n\n",
        "\t-(laymen’s terms)\\n\n",
        "\t\t-MAX will never allow move that is worse than alpha (for MIN)\\n\n",
        "\t\t-MIN will never allow move that is better than beta (for MAX)\\n\n",
        " \t-(when evaluating)\\n\n",
        "\t\t-when evaluating MIN: value v <= alpha is backed up, MAX will never select that MIN node\\n\n",
        "\t\t-when evaluating MAX: value v >= beta is backed up, MIN will never select that MAX node\\n\n",
        "x\\n\n",
        "(TABLE)\\n\n",
        "-Expectimax and Utilities: games with uncertain outcomes\\n\n",
        "\t -why? Randomness, unpredictable opponents (suboptimal decisions), actions fail (wheels slip)\\n\n",
        "\t-values reflect average case outcome (expectimax) vs worst case outcome (minimax) \\n\n",
        "-Expectimax Search: compute average score under optimal play\\n\n",
        "\t\t1) max nodes like in minimax search\\n\n",
        "\t\t2) chance nodes are similar to min nodes, with uncertain outcomes\\n\n",
        "\t\t3) calculate expected utility ¬ take weighted average of children\\n\n",
        "\t\t*Markov Decision Processes (formalization of uncertain result problems)\\n\n",
        "\t\t-Pruning for Expectimax: MUCH HARDER\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Alpha-Beta Pruning\" : \"cuts out parts of tree that make no difference in final decision, reduce number of branches\",\n",
        "\"alpha\" : \"MAX’s current lower bound on MAX’s outcome\",\n",
        "\"beta\" : \"MIN’s current upper bound on MIN’s outcome\",\n",
        "\"minimax value\" : \"value of each state in the tree for games\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 67,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ea3b4bab-4fa6-4775-86d8-71c811981cb4"
      },
      "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": 68,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nGame Theory\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nOptimal Decisions in Games: Minimax Search\n\n(TABLE)\n\nAlpha Beta Pruning (see table)\n\n\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alphe Beta Tree Search \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic GAmes: involve random elemnts in the game, use expected minimax \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nBasic Utility Theory:\n\n-6 constraints\n\n1)orderability: rational agent must prefer one or the other, else it must equally prefer each one\n\n2)transitivity: given 3 lotteries, if the agent prefers A to B and B to C,it prefers A to C\n\n3)continuity: if some lottery B is between A and C in terms of preference, then there is some probability p that agent will be indifferent between getting B for sure, and yield A with prob p and C with prob 1-p\n4)substitutability: if an agent indifferent between two lotteries A and B, then its also indiffferent between two more complex lotteries that are the same except that Bis substituted for A in one of them\n\n5)monotinicity: two lotteries have 2 possible otcomes, A and B, then if agent prefers Ato B, it will chooose lottery w/ higher probabilty of A\n\n6)decomposiblity: compound lotteries can be reduced to simpler ones using laws of probability\n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility Functions \n\n## Module 5 Lecture Notes\n\n-Outline:\n\n\t1) Games as Search\n\n\t2) Adversarial Search\n\nx\n\n-Simple Games:\n\n\t1) Multiagent: playing against opponent, basing our decisions on opponents decision\n\n\t2) Static: no change in environment while agent is thinking\n\n\t3) Discrete: finite set of actions (vs continuous like aiming a gun, angle is continuous)\n\n\t4) Fully Obeservable: agent’s sensor gives complete state of environment\n\n\t5) Strategic: next state determined by current state & action executed by agent & action of one other agent\n\nx\n\n-Key Properties of our games:\n\n\t1) two player alternate moves\n\n\t2) zero-sum: one wins, other loses\n\n\t3) clear set of legal moves\n\n\t4) well defined outcomes (win, lose, draw)\n\nx\n\n-Formalize Game Setup:\n\n\t-Two players: MAX and MIN, MAX moves first\n\n\t-take turns until game over\n\n\t-winner gets award, loser gets penalty\n\n\n\t-Games as search:\n\n\t1) Initial state: board configuration\n\n\t2) Successor function: list of (move, state) pairs specifying legal moves\n\n\t* Evaluation functionL: given current state of the board, how good is it for us and our oppponents?\n\n\t3) Terminal test: is game finished?\n\n\t4) Utility function: gives numerical values of terminal states, ex) win (+inf), lose (-inf), draw (0)\n\n\t5) MAX uses serach tree to determine next move\n\nx\n\n-How to Play Game by Searching\n\n\tGeneral Scheme:\n\n\t1) Consider all legal successors to current state (“board position)\n\n\t2) Evaluate each successor board position\n\n\t3) Pick move that leads to best board position\n\n  4) After opponent moves, REPEAT\n\nx\n\nDesign issues:\n\t\n1) representing the ‘board’\n\n2) representing legal next boards\n\n3) evaluating positions\n\n4) looking ahead\n\nx\n\n-2 players: MAX and MIN (MAX’s opponent)\n\n-play computed from MAX’s vantage point\n\n-MAX attemps to MAXimize MAX’s outcome, MIN attempts to MINmimize MAX’s outcome\n\n\t-MAX moves first\n\n\n\t-root (level 0) MAX\n\n\t-alternate MAX/MIN labels for each successful tree level (ply)\n\n\t-Even level is MAX’s turn, Odd level is MIN’s turn\n\nx\n\n-Game Trees:\n\n\t-represents game problem by tree:\n\n\t\t-node = ‘board position’, edge = legal moves\n\n\t\t-root node is first position\n\n\t-Evaluation function f assigns score to ‘board’ without reference to path\n\n\t-terminal nodes represent way game could end with desirability label of that ending (win/lose/draw, \tnumerical score)\n\n\n-Evaluation function: f(n)\n\n\t-built using expert knowledge\n\n\t-evaluate how good board position is based on static features of that board alone\n\n\t-zero-sum assumption:\n\n\t\t-f(n) > 0: if MAX is winning in position n\n\n\t\t-f(n) = 0: if position n is tied\n\n\t\t-f(n) < 0: if MIN is winning in position n\n\nx\n\nx\n\nNxt Section: Minimax and Alpha Beta Pruning\n\n-Make the best move for MAX assuming that MIN always replies with the best move for MIN\n\n-computed by recursion:\n\n\t-backed-up value of a node is determined by value of its children:\n\n\t\t-for MAX node: backed-up value is maximum of the values of its children\n\n-for MIN node: backed-up value is minimum of the values of its children\n\nx\n\n(TABLE)\n\n-Minimax Procedure:\n\n\t-Until game is over:\n\n\t\t1) start with current positoin as MAX node\n\n2) expand game tree by fixed number of ply\n\n3) apply evalution function to the leaf positions\n\n4) calculate back-up values bottom-up\n\n5) pick move assigned to MAX at root\n\n6) wait for MIN to respond\n\nx\n\n(TABLE)\n\n-Alpha-Beta Pruning: cut out parts of tree that make no difference in final decision  reduce number of branches\n\n\t-during Minimax:\n\n\t\t-alpha: MAX’s current lower bound on MAX’s outcome\n\n\t\t-beta: MIN’s current upper bound on MIN’s outcome\n\n\t-(laymen’s terms)\n\n\t\t-MAX will never allow move that is worse than alpha (for MIN)\n\n\t\t-MIN will never allow move that is better than beta (for MAX)\n\n \t-(when evaluating)\n\n\t\t-when evaluating MIN: value v <= alpha is backed up, MAX will never select that MIN node\n\n\t\t-when evaluating MAX: value v >= beta is backed up, MIN will never select that MAX node\n\nx\n\n(TABLE)\n\n-Expectimax and Utilities: games with uncertain outcomes\n\n\t -why? Randomness, unpredictable opponents (suboptimal decisions), actions fail (wheels slip)\n\n\t-values reflect average case outcome (expectimax) vs worst case outcome (minimax) \n\n-Expectimax Search: compute average score under optimal play\n\n\t\t1) max nodes like in minimax search\n\n\t\t2) chance nodes are similar to min nodes, with uncertain outcomes\n\n\t\t3) calculate expected utility ¬ take weighted average of children\n\n\t\t*Markov Decision Processes (formalization of uncertain result problems)\n\n\t\t-Pruning for Expectimax: MUCH HARDER\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 5 Definitions\n* **Alpha-beta pruning** - cuts out parts of tree that make no difference in final decision, reduce number of branches\n* **Alpha** - MAX’s current lower bound on MAX’s outcome\n* **Beta** - MIN’s current upper bound on MIN’s outcome\n* **Minimax value** - value of each state in the tree for games\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" k consistency\\n\n",
        "node consistency k = 1\\n\n",
        "arc consistency k = 2\\n\n",
        "path consistency k = 3 \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Constraint Satisfaction Problems (identification problems)\\n\n",
        "-Goal: come up with a set of variable assignments that are consistent with set of constraints using declarative language\\n\n",
        "-represent constraints that solution must satisfy in uniform declarative language\\n\n",
        "-find solutions by general purpose search algorithms that can be used for any problem\\n\n",
        "-“what are constraints of a problem, develop general set of algorithms that apply \\\n",
        "those constraints and find correct assignment of values to variables”\\n\n",
        "CSP contains:\\n\n",
        "1)Finite set of variables: X1, X2,…, Xn\\n\n",
        "2) Nonempty domain of possible values for each variable: D1, D2, …, Dn\\n\n",
        "3) Finite set of constraints: C1, C2,…., Cm\\n\n",
        "-each constraint limits values that variable can take (i.e. X1 != X2)\\n\n",
        "2 Cond for Sol.\\n\n",
        "1) consistent assignment does not violate constraints\\n\n",
        "2) complete: every variable has a value\\n\n",
        "Benefits of CSP: clean specification of many problems, generic goal, successor functions, heurstics\\n\n",
        "-CSP ‘knows’ which varibles violate constraints\\n\n",
        "-CSP automatically prunes off all branches that violate constraints\\n\n",
        "x\\n\n",
        "Idea1: CSP as a search problem, backtracking search\\n\n",
        "-initial state: empty assignment {}\\n\n",
        "-successfor function: assign value to any unassigned variable with no constraint conflict\\n\n",
        "-goal test: current assignment complete\\n\n",
        "-path cost: constant cost for every step\\n\n",
        "*solution always at depth n for n variables  can use DFS\\n\n",
        "Search and branching factor:\\n\n",
        "-n variables, domain size d\\n\n",
        "-branching factor: n*d\\n\n",
        "-total leaves: n! * d^n\\n\n",
        "x\\n\n",
        "idea 2: improve backtrack efficiency, heuristics with backtracking search: forward checking\\n\n",
        "\t-general purpose methods and heuristics increase speed on avg.\\n\n",
        "\t\t-which variable should be assigned next?  most constrained variable\\n\n",
        "\t\t-what order should variables values be tried?  least constaining value\\n\n",
        "\t\t-detect failure early?  forward checking\\n\n",
        "\t\t-Heuristic 1: Most constrained variable (minimum remaining values (MRV) heuristic): fewest legal valu\\n\n",
        "\t\t-Heuristic 2: Most constraining variable: tiebreaker between most constrained variables\\n\n",
        "\t\t-Heuristic 3: Least constrainint value: given variable, choose least constraining VALUES (not VARIABLES)\\n\n",
        "\t\t-Heuristic 4: Forward Checking: keep track of legal values for unassigned variables, terminate serach when no remaining legal values for unassigned variables\\n\n",
        "x\\n\n",
        "***idea 3 (BIG IDEA)***: inference in CSPs: Arc Consistency, Constraint Propagation & AC-3\\n\n",
        "\t-CSP combines Search & Inference\\n\n",
        "\t1) search: assign value to variable\\n\n",
        "\t2) constraint propagation (inference): given current partial solution, is it going to lead to correct solution?\\n\n",
        "\t-can do inference or search first, intertwine\\n\n",
        "\\n\n",
        "-Local Consistency\\n\n",
        "\t1) Node consistency: satisfies unary constraints\\n\n",
        "\t2) Arc consistency: satisfies binary constraint\\n\n",
        "\t\t-undirected edge to directed arcs (x --> y: x tail, y head; remove value from tail)\\n\n",
        "\t\t\t-X --> Y is consisitent iff: for every value of X, there is some allowed Y\\n\n",
        "\t\t\t-if X loses a value, recheck neighbors of X\\n\n",
        "-Waltz/Mackworth Constraint Propagation Algorithm  inefficient  towards AC-3\\n\n",
        "\t1) Assign every node in the constraint graph a set of all possible values\\n\n",
        "\t2) Repeat until there is no change in the set of values for any node\\n\n",
        "\t\t3. for each node i:\\n\n",
        "\t\t\t4. for each neighbording node j in the picture\\n\n",
        "\t\t\t\t5. remove any value i which is not arc consistent with j\\n\n",
        "\t-inefficient: only need to check tail, NOT head  AC-3 algorithm\\n\n",
        "x\\n\n",
        "x\\n\n",
        "Recap\\n\n",
        "\t-Constraint graph: nodes are variables, edges are constraints\\n\n",
        "\t-Edges to Arcs: Constraint graph  Directed Graphs\\n\n",
        "\t\t-Arc Consistency check: use propagation to check concistency  if X loses value, recheck neighbors \\n\n",
        "\n",
        "\t2 Steps:\\n\n",
        "\t\t1) Search Steps: assign value to variable, one step further in DFS\\n\n",
        "\t\t2) Inference Steps: based on value assignments & elimanted items, are there other nodes with no possible value assignments?  remove that node and backtrack\\n\n",
        "\t\t-recheck neighbors of X\\n\n",
        "\n",
        "\t-Replacing Search: Constraint Propagation Invented:\\n\n",
        "\t\t-Search: use constraints to add labels to find one solution\\n\n",
        "\t\t-Constraint Propagation: use constraints to eliminae labels to simultaneously find all solutions\\n\n",
        "\n",
        "\t-Waltz/Lackworth Constraint Propagation Algorithm\\n\n",
        "\t\t1) Assign every node in constraint graph a set of all possible values\\n\n",
        "\t\t2) Repeat until there is no change in the set of values for any node\\n\n",
        "\t\t\t3. for each node i:\\n\n",
        "\t\t\t\t4. for each neighbording node j in the picture\\n\n",
        "\t\t\t\t\t5. remove any value i which is not arc consistent with j\\n\n",
        "\t\t*INEFFICIENT  AC-3\\n\n",
        "\n",
        "\t-***AC-3***: keep track of things we need to recheck, ONLY recheck neighbors of tail\\n\n",
        "\t\t1) Each iteration: only examin Xi where at least one neighbor of Xi has lost a value in prev. iteration\\n\n",
        "\t\t2)  if Xi loses a value b/c of arc inconsistency with Yj, don’t need to check Yj on next iteartion\\n\n",
        "\t\t3) Removing value on Xi can only make Yj arc inconsisntent wrt Xi itself, only check that (j,i) still arc consistent\t\\n\n",
        "\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"identification problem\",\n",
        "\"state\" : \"is an assignment of values to some or all variables\",\n",
        "\"Backtracking Search\" : \"DFS serach for CSP with with single variable assignemnts\",\n",
        "\"MAC\" : \"maintaining arc consistency by interleaving search and inference\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",    \n",
        "}\n"
      ],
      "execution_count": 69,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ea0c3838-e4ac-41a2-c1e1-dec21d7f8ab7"
      },
      "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": 70,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n k consistency\n\nnode consistency k = 1\n\narc consistency k = 2\n\npath consistency k = 3 \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\nConstraint Satisfaction Problems (identification problems)\n\n-Goal: come up with a set of variable assignments that are consistent with set of constraints using declarative language\n\n-represent constraints that solution must satisfy in uniform declarative language\n\n-find solutions by general purpose search algorithms that can be used for any problem\n\n-“what are constraints of a problem, develop general set of algorithms that apply those constraints and find correct assignment of values to variables”\n\nCSP contains:\n\n1)Finite set of variables: X1, X2,…, Xn\n\n2) Nonempty domain of possible values for each variable: D1, D2, …, Dn\n\n3) Finite set of constraints: C1, C2,…., Cm\n\n-each constraint limits values that variable can take (i.e. X1 != X2)\n\n2 Cond for Sol.\n\n1) consistent assignment does not violate constraints\n\n2) complete: every variable has a value\n\nBenefits of CSP: clean specification of many problems, generic goal, successor functions, heurstics\n\n-CSP ‘knows’ which varibles violate constraints\n\n-CSP automatically prunes off all branches that violate constraints\n\nx\n\nIdea1: CSP as a search problem, backtracking search\n\n-initial state: empty assignment {}\n\n-successfor function: assign value to any unassigned variable with no constraint conflict\n\n-goal test: current assignment complete\n\n-path cost: constant cost for every step\n\n*solution always at depth n for n variables  can use DFS\n\nSearch and branching factor:\n\n-n variables, domain size d\n\n-branching factor: n*d\n\n-total leaves: n! * d^n\n\nx\n\nidea 2: improve backtrack efficiency, heuristics with backtracking search: forward checking\n\n\t-general purpose methods and heuristics increase speed on avg.\n\n\t\t-which variable should be assigned next?  most constrained variable\n\n\t\t-what order should variables values be tried?  least constaining value\n\n\t\t-detect failure early?  forward checking\n\n\t\t-Heuristic 1: Most constrained variable (minimum remaining values (MRV) heuristic): fewest legal valu\n\n\t\t-Heuristic 2: Most constraining variable: tiebreaker between most constrained variables\n\n\t\t-Heuristic 3: Least constrainint value: given variable, choose least constraining VALUES (not VARIABLES)\n\n\t\t-Heuristic 4: Forward Checking: keep track of legal values for unassigned variables, terminate serach when no remaining legal values for unassigned variables\n\nx\n\n***idea 3 (BIG IDEA)***: inference in CSPs: Arc Consistency, Constraint Propagation & AC-3\n\n\t-CSP combines Search & Inference\n\n\t1) search: assign value to variable\n\n\t2) constraint propagation (inference): given current partial solution, is it going to lead to correct solution?\n\n\t-can do inference or search first, intertwine\n\n\n\n-Local Consistency\n\n\t1) Node consistency: satisfies unary constraints\n\n\t2) Arc consistency: satisfies binary constraint\n\n\t\t-undirected edge to directed arcs (x --> y: x tail, y head; remove value from tail)\n\n\t\t\t-X --> Y is consisitent iff: for every value of X, there is some allowed Y\n\n\t\t\t-if X loses a value, recheck neighbors of X\n\n-Waltz/Mackworth Constraint Propagation Algorithm  inefficient  towards AC-3\n\n\t1) Assign every node in the constraint graph a set of all possible values\n\n\t2) Repeat until there is no change in the set of values for any node\n\n\t\t3. for each node i:\n\n\t\t\t4. for each neighbording node j in the picture\n\n\t\t\t\t5. remove any value i which is not arc consistent with j\n\n\t-inefficient: only need to check tail, NOT head  AC-3 algorithm\n\nx\n\nx\n\nRecap\n\n\t-Constraint graph: nodes are variables, edges are constraints\n\n\t-Edges to Arcs: Constraint graph  Directed Graphs\n\n\t\t-Arc Consistency check: use propagation to check concistency  if X loses value, recheck neighbors \n\n\n\t2 Steps:\n\n\t\t1) Search Steps: assign value to variable, one step further in DFS\n\n\t\t2) Inference Steps: based on value assignments & elimanted items, are there other nodes with no possible value assignments?  remove that node and backtrack\n\n\t\t-recheck neighbors of X\n\n\n\t-Replacing Search: Constraint Propagation Invented:\n\n\t\t-Search: use constraints to add labels to find one solution\n\n\t\t-Constraint Propagation: use constraints to eliminae labels to simultaneously find all solutions\n\n\n\t-Waltz/Lackworth Constraint Propagation Algorithm\n\n\t\t1) Assign every node in constraint graph a set of all possible values\n\n\t\t2) Repeat until there is no change in the set of values for any node\n\n\t\t\t3. for each node i:\n\n\t\t\t\t4. for each neighbording node j in the picture\n\n\t\t\t\t\t5. remove any value i which is not arc consistent with j\n\n\t\t*INEFFICIENT  AC-3\n\n\n\t-***AC-3***: keep track of things we need to recheck, ONLY recheck neighbors of tail\n\n\t\t1) Each iteration: only examin Xi where at least one neighbor of Xi has lost a value in prev. iteration\n\n\t\t2)  if Xi loses a value b/c of arc inconsistency with Yj, don’t need to check Yj on next iteartion\n\n\t\t3) Removing value on Xi can only make Yj arc inconsisntent wrt Xi itself, only check that (j,i) still arc consistent\t\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n* **Csp** - identification problem\n* **State** - is an assignment of values to some or all variables\n* **Backtracking search** - DFS serach for CSP with with single variable assignemnts\n* **Mac** - maintaining arc consistency by interleaving search and inference\n* **** - \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 = \"\"\"dsfe \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "KB Agents\\n\n",
        "x\\n\n",
        "Propositional Logic:\\n\n",
        "-KB consists of sentences in the representation language (RL)\\n\n",
        "-RL has syntax that specifies sentences that are well-formed\\n\n",
        "-a logic defines the semantics of the sentences  meaning\\n\n",
        "-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\\n\n",
        "x\\n\n",
        "Possible worlds and models (m=model, alpha = sentence, {true, false}):\\n\n",
        "  -m satisfies alpha\\n\n",
        "  -m is a model of alpha\\n\n",
        "  -M(alpha): set of all models of alpha\\n\n",
        "  -alpha entails sentence β: alpha⊨β\\n\n",
        "  -alpha⊨β if and only if M(alpha) ⊆ M(β)\\n\n",
        "x\\n\n",
        "x\\n\n",
        "Knowledge Base\\n\n",
        "Logical Equivalence (Table)\\n\n",
        "Inference Rules (Table)\\n\n",
        "Search for a Proof:\\n\n",
        "1) Initial state\\n\n",
        "2) Actions: all inferences rules applied to all setnences that match top 1/2 of inference rules \\n\n",
        "3) Result: add the sentence to KB \\n\n",
        "4) Goal: state that contains sentence we are trying to probe \\n\n",
        "-Sound and Complete\\n\n",
        "x\\n\n",
        "Conjunctive Normal Form (CNF): transform sentence to this form to use resolution algo (TABLE)\\n\n",
        "Resolution Algo: complete, not necessarily efficient (TABLE)\\n\n",
        "For efficiency in Resolution Algo\\n\n",
        "1) Definite Clause\\n\n",
        "2) Horn Clause: includes definite claus+clause with no positiuve \\n\n",
        "x\\n\n",
        "forward chaining(data driven reasoninig): set of data we know is true, move \\\n",
        "through environment and get percepts, enumerate new conclusions\\n\n",
        "backward chaining (goal directed reasoning):work backwards from query, if query \\\n",
        "known to be true, then nothing. Otherwise, find rules where gamma is conclusion \\\n",
        "and if query true, then alpha and beta is true\\n\n",
        "x\\n\n",
        "x\\n\n",
        "x\\n\n",
        "x\\n\n",
        "-Knowledge-based Agents: use process of reasoning over an internal representation of knowledge to decide on actions  MORE COMPLEX\\n\n",
        "\t-so far: problem-solving agents have performed serach over states to find plan  atomic: we don’t really \tknow anything about them (too brittle)\\n\n",
        "\n",
        "\t-knowledge base (KB): contains set of sentences that are written in knowledge representation language that \thas some assertion about the world\\n\n",
        "\t\t\n",
        "\t\t-2 kinds of sentences:\\n\n",
        "\t\t1) axiom: given setneces\\n\n",
        "\t\t2) derived sentences: new sentences derived from other setences (by a process called inference)\\n\n",
        "\n",
        "\t\t-KB contains background info abt world\\n\n",
        "1) KB Agent can add info by observation\\n\n",
        "2) KB Agent queries KB and derive new knowledge\\n\n",
        "x\\n\n",
        "\t-WAMPA WORLD EXAMPLE\\n\n",
        "x\\n\n",
        "-Logic: general calss of representation for knowledge-based agents \\n\n",
        "-Propositional Logic:\\n\n",
        "\t-KB consists of sentences in the representation language (RL)\\n\n",
        "\t-RL has syntax that specifies sentences that are well-formed\\n\n",
        "\t-a logic defines the semantics of the sentences  meaning\\n\n",
        "\t-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\\n\n",
        "x\\n\n",
        "-Possible worlds and models (m=model, alpha = sentence, {true, false}):\\n\n",
        "-m satisfies alpha \\n\n",
        "-m is a model of alpha\\n\n",
        "-M(alpha): set of all models of alpha\\n\n",
        "x\\n\n",
        "-Logical Entailment:\\n\n",
        "\t-logical reasoning: involves entailment relation between setnences\\n\n",
        "\t-entailment: a setnences follows logicallt from another setnences\\n\n",
        "x\\n\n",
        "-Knowledge Base\\n\n",
        "\t-KB is false in any models that contrafict what agent knows\\n\n",
        "\t-M(KB) inside M(alpha)\\n\n",
        "x\\n\n",
        "-Logical Inference: entailment (additional setneces from KB))    derive additional conclusions\\n\n",
        "\t-derive inference algorithm to enumerate setnences\\n\n",
        "\t\t-inference algorithm I allows us to use knowledge base to derive sentence alpha\\n\n",
        "x\\n\n",
        "-Propositional Logic: \\n\n",
        "\t-atomic sentences represented with single propositional symbols: statements that are true or false\\n\n",
        "\t-complex setences made from simpler ones with logical connectives \\n\n",
        "(Logical Symbols TABLE)\\n\n",
        "(Truth TABLE)\\n\n",
        "x\\n\n",
        "-A Simple knowledge base\\n\n",
        "-Entailment and Inference\\n\n",
        "x\\n\n",
        "-Inference Algorithm: FIND which sentences are entailed by KB based on search\\n\n",
        "\t-Sound: should only derive entailed sentences\\n\n",
        "\t-Complete: can derive all sentences that are entailed\\n\n",
        "x\\n\n",
        "-Theorem Proving: inference algorithm does automated theorem proving\\n\n",
        "-Logical Equivalence: two sentneces logically equivalent if they are true and in same set of models\\n\n",
        "(Logical Equivalence Table)\\n\n",
        "(Inference Rules TAble)\\n\n",
        "x\\n\n",
        "-Search for a Proof:\\n\n",
        "\t1) Initial State:\\n\n",
        "\t2) Actions: all inference rules applied to all sentences that match the top half of the inference rule\\n\n",
        "\t3) Result: add the sentence to KB \\n\n",
        "\t4) Goal: state that contains the sentence that we are trying to prove\\n\n",
        "\n",
        "\t-Monotinicity:set of entailed setneces can only increase as information is added to KB --> Soundness\\n\n",
        "\t-Proof by Resolution: single inference rule that yields a complete inference algoirthm when coupled with any \tcomplete search algorithm --> Complete\\n\n",
        "\n",
        "  -Resolution: eliminate l1 and m by unit resolution (JUST FOR disjunctions (OR) of literals/clauses)\\n\n",
        "\t\t-how do we get everything to a disjunction? …….\\n\n",
        "\t\n",
        "  -Conjunctive Normal Form (CNF): every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals\\n\n",
        "(CDN info TABLE)\\n\n",
        "x\\n\n",
        "-Resolution Algorithm (COMPLETE, but not necessarily efficient):\\n\n",
        "\t\t-empty clause is the contradiction (step 2 in last step)xxxxx\\n\n",
        "(Resolution Algo CodeTABLE)\\n\n",
        "\t-Resolution Algorithm Efficiency:\\n\n",
        "    -disjunction = or \\n\n",
        "\t\t1) Definite Clause: disjunction where exactly one is positive\\n\n",
        "\t\t2) Horn Clause: disjunction where at most one is positive\\n\n",
        "\t\t\t-includes definite clauses\\n\n",
        "\t\t\t-includes clauses with no positive\\n\n",
        "      (Definite Clause info TABLE)\\n\n",
        "      -Forward Chaining (data driven reasoning): set of data we know is true, move through environment and get percepts, enumerate new conclusions\\n\n",
        "      -Backward Chaining (goal-directed reasoning): work backwards from query, if query known to be true, then nothing. Otherwise, find rules where gamma is conclusion and if query true, then alpha and beta is true.\\n\n",
        "\t-\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agent\" : \"complex problem solving agent use reasoning over an internal \\\n",
        "representation of knowledge tochoose action\",    \n",
        "\"knowledge base (KB)\" : \"set of sentences that are written in \\\n",
        "knowledge representation language that \thave some assertion about the world\",\n",
        "\"logical reasoning\" : \"involves entailment relation between setnences\",\n",
        "\"entailment\" : \"sentences that follows logically from another setnences\",\n",
        "\"Inference Algorithm\" : \"helps to find which sentences are entailed by KB based on search\",\n",
        "\"Sound\" : \"an algo should only derive entailed sentences\",\n",
        "\"Complete\" : \"an algo can derive all sentences that are entailed\",\n",
        "\"logical equivalence\" : \"two sentneces logically equivalent if they are true and in same set of models\",\n",
        "\"Monotinicity\" : \"a set of entailed sentences can only increase as information is\\\n",
        " added to KB, implies SOUNDNESS\",\n",
        "\"Proof by Resolution\" : \"single inference rule that yields a complete inference\\\n",
        " algorithm when coupled with any complete search algorithm implies Completebess\",\n",
        "\"Conjunctive Normal Form (CNF)\" : \"every sentence of propositional logic is logically equivalent to a conjunction of clauses\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 71,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ded0f311-51be-47d0-9b13-c1ed49310fb9"
      },
      "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": 72,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\ndsfe \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\nKB Agents\n\nx\n\nPropositional Logic:\n\n-KB consists of sentences in the representation language (RL)\n\n-RL has syntax that specifies sentences that are well-formed\n\n-a logic defines the semantics of the sentences  meaning\n\n-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\n\nx\n\nPossible worlds and models (m=model, alpha = sentence, {true, false}):\n\n  -m satisfies alpha\n\n  -m is a model of alpha\n\n  -M(alpha): set of all models of alpha\n\n  -alpha entails sentence β: alpha⊨β\n\n  -alpha⊨β if and only if M(alpha) ⊆ M(β)\n\nx\n\nx\n\nKnowledge Base\n\nLogical Equivalence (Table)\n\nInference Rules (Table)\n\nSearch for a Proof:\n\n1) Initial state\n\n2) Actions: all inferences rules applied to all setnences that match top 1/2 of inference rules \n\n3) Result: add the sentence to KB \n\n4) Goal: state that contains sentence we are trying to probe \n\n-Sound and Complete\n\nx\n\nConjunctive Normal Form (CNF): transform sentence to this form to use resolution algo (TABLE)\n\nResolution Algo: complete, not necessarily efficient (TABLE)\n\nFor efficiency in Resolution Algo\n\n1) Definite Clause\n\n2) Horn Clause: includes definite claus+clause with no positiuve \n\nx\n\nforward chaining(data driven reasoninig): set of data we know is true, move through environment and get percepts, enumerate new conclusions\n\nbackward chaining (goal directed reasoning):work backwards from query, if query known to be true, then nothing. Otherwise, find rules where gamma is conclusion and if query true, then alpha and beta is true\n\nx\n\nx\n\nx\n\nx\n\n-Knowledge-based Agents: use process of reasoning over an internal representation of knowledge to decide on actions  MORE COMPLEX\n\n\t-so far: problem-solving agents have performed serach over states to find plan  atomic: we don’t really \tknow anything about them (too brittle)\n\n\n\t-knowledge base (KB): contains set of sentences that are written in knowledge representation language that \thas some assertion about the world\n\n\t\t\n\t\t-2 kinds of sentences:\n\n\t\t1) axiom: given setneces\n\n\t\t2) derived sentences: new sentences derived from other setences (by a process called inference)\n\n\n\t\t-KB contains background info abt world\n\n1) KB Agent can add info by observation\n\n2) KB Agent queries KB and derive new knowledge\n\nx\n\n\t-WAMPA WORLD EXAMPLE\n\nx\n\n-Logic: general calss of representation for knowledge-based agents \n\n-Propositional Logic:\n\n\t-KB consists of sentences in the representation language (RL)\n\n\t-RL has syntax that specifies sentences that are well-formed\n\n\t-a logic defines the semantics of the sentences  meaning\n\n\t-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\n\nx\n\n-Possible worlds and models (m=model, alpha = sentence, {true, false}):\n\n-m satisfies alpha \n\n-m is a model of alpha\n\n-M(alpha): set of all models of alpha\n\nx\n\n-Logical Entailment:\n\n\t-logical reasoning: involves entailment relation between setnences\n\n\t-entailment: a setnences follows logicallt from another setnences\n\nx\n\n-Knowledge Base\n\n\t-KB is false in any models that contrafict what agent knows\n\n\t-M(KB) inside M(alpha)\n\nx\n\n-Logical Inference: entailment (additional setneces from KB))    derive additional conclusions\n\n\t-derive inference algorithm to enumerate setnences\n\n\t\t-inference algorithm I allows us to use knowledge base to derive sentence alpha\n\nx\n\n-Propositional Logic: \n\n\t-atomic sentences represented with single propositional symbols: statements that are true or false\n\n\t-complex setences made from simpler ones with logical connectives \n\n(Logical Symbols TABLE)\n\n(Truth TABLE)\n\nx\n\n-A Simple knowledge base\n\n-Entailment and Inference\n\nx\n\n-Inference Algorithm: FIND which sentences are entailed by KB based on search\n\n\t-Sound: should only derive entailed sentences\n\n\t-Complete: can derive all sentences that are entailed\n\nx\n\n-Theorem Proving: inference algorithm does automated theorem proving\n\n-Logical Equivalence: two sentneces logically equivalent if they are true and in same set of models\n\n(Logical Equivalence Table)\n\n(Inference Rules TAble)\n\nx\n\n-Search for a Proof:\n\n\t1) Initial State:\n\n\t2) Actions: all inference rules applied to all sentences that match the top half of the inference rule\n\n\t3) Result: add the sentence to KB \n\n\t4) Goal: state that contains the sentence that we are trying to prove\n\n\n\t-Monotinicity:set of entailed setneces can only increase as information is added to KB --> Soundness\n\n\t-Proof by Resolution: single inference rule that yields a complete inference algoirthm when coupled with any \tcomplete search algorithm --> Complete\n\n\n  -Resolution: eliminate l1 and m by unit resolution (JUST FOR disjunctions (OR) of literals/clauses)\n\n\t\t-how do we get everything to a disjunction? …….\n\n\t\n  -Conjunctive Normal Form (CNF): every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals\n\n(CDN info TABLE)\n\nx\n\n-Resolution Algorithm (COMPLETE, but not necessarily efficient):\n\n\t\t-empty clause is the contradiction (step 2 in last step)xxxxx\n\n(Resolution Algo CodeTABLE)\n\n\t-Resolution Algorithm Efficiency:\n\n    -disjunction = or \n\n\t\t1) Definite Clause: disjunction where exactly one is positive\n\n\t\t2) Horn Clause: disjunction where at most one is positive\n\n\t\t\t-includes definite clauses\n\n\t\t\t-includes clauses with no positive\n\n      (Definite Clause info TABLE)\n\n      -Forward Chaining (data driven reasoning): set of data we know is true, move through environment and get percepts, enumerate new conclusions\n\n      -Backward Chaining (goal-directed reasoning): work backwards from query, if query known to be true, then nothing. Otherwise, find rules where gamma is conclusion and if query true, then alpha and beta is true.\n\n\t-\n\n\n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - complex problem solving agent use reasoning over an internal representation of knowledge tochoose action\n* **Knowledge base (kb)** - set of sentences that are written in knowledge representation language that \thave some assertion about the world\n* **Logical reasoning** - involves entailment relation between setnences\n* **Entailment** - sentences that follows logically from another setnences\n* **Inference algorithm** - helps to find which sentences are entailed by KB based on search\n* **Sound** - an algo should only derive entailed sentences\n* **Complete** - an algo can derive all sentences that are entailed\n* **Logical equivalence** - two sentneces logically equivalent if they are true and in same set of models\n* **Monotinicity** - a set of entailed sentences can only increase as information is added to KB, implies SOUNDNESS\n* **Proof by resolution** - single inference rule that yields a complete inference algorithm when coupled with any complete search algorithm implies Completebess\n* **Conjunctive normal form (cnf)** - every sentence of propositional logic is logically equivalent to a conjunction of clauses\n* **** - \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": "183e576f-ce7d-40ee-b324-b69c441b8e6e"
      },
      "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": 73,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\nLimits of AI\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nCan Machines Really Think\n\n## AIMA 2.1 Agents and Environments\nIntelligent Agents: Agents and Environments\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nGood Behavior: Rationality\n\n## AIMA 2.3 The Nature of Environments\nThe Nature of Environments\n\n## AIMA 2.4 The Structure of Agents\nStructure of Agents\n\n1) simple reflex agents\n\n2) model based reflex agents\n\n3) goal-based agents: search \n\n4) utility-based agents\n\n\n\n\n## Module 1 Lecture Notes\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content that an agent's sensor perceive\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Ch1** - Ch1\n* **Rationality** - doing the right thing\n* **Turing test** - can a machine think?\n* **Rational agent** - agent that does the right thing\n* **Standard model** - AI model with agents that do the right thing\n* **Limited rationality** - when computational demands are too high, acting appropriately\n* **Value of alignment problem** - the objectives/values that a machine has must be aligned with those of a human\n* **Provably beneficial** - how to define fgood in AI, build in uncertrainty about human preferences\n* **Ch 27_1** - ch 27_1\n* **Weak ai** - machines could act as if they were intelligent, but arent actually intelligent\n* **Strong ai** - machines that act intelligent actually are consciously thinking\n* **Good old fashions ai (gofai)** - formal set of rules that try to define human behaviors (criticized by Turing)\n* **Qualification problem** - the difficulty of capturing every possible behavior with a set of necessary and suffieicinet logical rules\n* **Embodied cognition** - you shouldn't consider the brain separately in AI, should encompass the entire body & its environment too(sensors)\n* **Ch 27_2** - ch 27_2\n* **Chinese room** - experiment where Chinese appeared to be translated, but was not understood\n* **Biological naturalism** - mental states are high level features caused by low level physical processes in the neurons\n* **Consciousness** - awareness of outside world, self, subjective expereinces of living\n* **Qualia** - the intrinstic nature of experiences\n* **Ch2** - ch2\n* **Sensor** - how an agent perceives environemnt\n* **Actuator** - how an agent acts on environemnt\n* **Percept sequence** - historyof everything an agent has pereived\n* **Agent function** - maps percept sequence to an action for the agent\n* **Agent program** - implementation of agent function in real life\n* **Consequentialism** - evaluating agent's behavior by its consequences\n* **Omniscience** - an agent that knows the actual outcome of its actions, this is impossible\n* **Information gathering** - performing actions to modify future percepts, exploration\n* **Learn** - moodify its knowledge from what it perceives from environment\n* **Autonomy** - an agent that acts on its own percepts and learning\n* **Task environments** - a situation that an agent must solve\n* **Peas** - parts of a task environment, Performance, Environment, Actuators, Sensors\n* **Fully observable** - agent knows the complete state of the environment at each point in time\n* **Partially observable** - an agent onlt sees part of the envirnoment at a point in time\n* **Single vs multi agent** - one agent or multiple agents\n* **Competititve vs cooperative** - ceompeting against one another vs working together\n* **Deterministic vs nondeterministic** - next state is 100% determined by agent's current state and actionvs not\n* **Stochastic** - environment that deals with probabilities\n* **Episodic** - agent's experience split up into atomic episodes, next eipsode doesn't depend on previous ones\n* **Sequential** - the current decisions have an effect on future ones\n* **Static vs dynamic** - environment doesnt change while agent things vs it does\n* **Discrete vs continuous** - envinroments and actions can be discrete or continuous\n* **Known vs unknown** - agent's konws the outcome of all its actions vs agent has to learn how the environment works\n* **Simple reflex agent** - select actions based ONLY ON the current percept\n* **Condition-aciton rule** - an agent taking an action based on a certain condition happening\n* **** - \n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **** - \n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem-Solving Agents\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nSearch Problems\n\nBest First Search: choose to expand node with minimum evaluation function value (f(n)) using a queue as the frontier\n\n-There are 3 kinds of queues in serach problems: priority queue, FIFO queue, LIFO queue\n\n1) priority queue: pops node w mimumm cost according to f(n), used in best-first search\n\n2) FIFO queue: first in first out, used in breadth first serach\n\n3) LIFO queue (stack): last in first out, used in depth first serach\n\nx\n\nx\n\nUninformed Search\n\n1) Breadth First Search: f(n) is the depth of the node, FIFO queue\n\n2) Dijkstra's algoirthm (Uniform cost serach)\n\n3) Depth first serach: \n\n4) Depth limited & iterative deepening search: prevent DFS from going down infinite path incorrectly\n\n5) Bidirectional serach: searches forward form intial stae and backwards from goal state\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n-Terminology: \n\n\t1) State: set S\n\n\t2) initial state: si in S\n\n\t3) Action: set of actions applicable in s\n\n\t4) Transition Function: state + action  successor\n\n\t5) Path Cost: performance measure, additive\n\n\t6) Goal State: Goal(s)\n\nx\n\n-Useful Concepts:\n\n\t-State Space: set of states\n\n\t-Path: sequence of actions\n\n\t-Frontier: states available for expanding\n\n\t-Solution: path fron initial to goal state with actions\n\nx\n\n-Basic Search Algorithms:\n\n(Abstract Search Algos)\n\n-Tree Search \n\n\t\t-nodes serached through transition model\n\n\t-state vs node (has more info.)\n\n\t-ex) 8-Puzzle Search Tree\n\n\t\t-careful of repeated states, keep track of them\n\n-Graph Search: keep track of all possible states, bad for memory b/c extra data structure\n\nx\n\n-(Instances of Search Algos)\n\n-Uninformed Search: all non-goal nodes in frontier look equally good\n\n-Informed Search: Some non-goal nodes can be ranked above others\n\n\n-Search Strategy:\n\n\t-Strategy: order for tree expansion\n\n\t\t-implemented by queue data structure (LIFO DFS, FIFO BFS, priority)\n\n\t-Dimensions: \n\n\t\t-Completeness: always find solution?\n\n\t\t-Optimality: least cost solution\n\n-Time Complexity: # nodes generated\n\n-Space Complexity: # nodes in memory simultaneously\n\n\t-b, max. branching factor: max # of actions I can take from state\n\n-d, depth: goal with minimum depth\n\n-m: max possible length of any path in graph\n\nx\n\nx\n\n(Uninformed Search)\n\n1) Breadth-first Search: \n\n-expand shallowest node\n\n-frontier is FIFO queue: put successors at end of frontier\n\n-**when to test during algo** whether node is solution as soon as you expand node\n\nx\n\n2) Depth-first Search:\n\n\t-expand deepest first\n\n\t-frontier is LIFO queue: put successors at front of frontier\n\nx\n\n  3) Depth-Limited Search: limit the depth of DFS with l\n\n\t-no inifinite paths\n\n\t-pick l by luck: if l<d incomplete, l>d suboptimal\n\n\t-so….\n\nx\n\n4) Iterative Deepening Search (ID Search): find best depth limit l\n\n\t-use depth-limited search as subroutine, increasing l iteratively\n\nx\n\n(TABLE)\n\n-Asymptotic Analysis\n\nx\n\n5*) “Uniform Cost” Search (Dijkstra’s): for weighted graphs (step cost is not all one like for 1-4 )\n\n\t-name: all costs <100 first, then all costs 100 <= cost < 200, etc.\n\n\t-g(N): path cost function\n\n\t-frontier: priority queue data structure ordered by g(n)\n\n\t-expand lowest path cost first\n\n-**when to test during algo**: test node when picked for expansion (BFS: when added to frontier)\n\nx\n\nx\n\nx\n\nx\n\nSEARCH SUMMARY:\n\n\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Optimal solution** - lowerst path cost among all possible solution\n* **Graph serach** - check redundant path\n* **Tree search** - does not check redudnant path\n* **** - \n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed (heuristic) Search\n\n1) Greedy Best First Search: like best first serch but expands node with lowest h(n)\n\n2) A* search: evaluation function is f(n) = h(n) + g(n), prunes away branches without checking them for efficiency, complete, cost optimal, efficient\n\nothers\n\n3)weighted A* search:\n\n4)memory-bounded search: uses memoryspace better than A+ serach, beam search: limits size of frontier\n\n5)iterative deepending A* serach (IDA*): uses A* serach and also limits depth (just like for IDDFS)\n\n6)\txrecursive best first serach (RBFS): similar to best first search but in linear space, like recursive depth first ssearch with limit\n\n\n\n\n\n\n\n\n\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\nHeuristic Problems \n\n## Module 4 Lecture Notes\n\nInformed Search\n\n-Best First Search: uses heuristics to estimate, which uninformed search doesn’t do\n\n1) Greedy Best-First Serach: select node to expand with minimum heuristic f(n) = h(n)\n\n\t-priority queue  same as UCS with f(n) instead of g(n)\n\n\t-this is bad: incomplete, suboptimal\n\n\n\n2**) A* Search: best best-first serach, expand most promising paths, avoid expanding already expensive ones\n\n\t-f(n) = g(n) + h(n)\t\n\n\t-Frontier: priority queue by increasing f(n)\n\n\t-Admissability: never overestimates cost (pessimistic) to reach goal  optimistic\n\n\t\t-0 <= h(n) <= h*(n)\n\n\t\t-Define h(n), can make Relaxed Problems\n\n\t\t-Dominance: if both admissable, bigger heuristic dominates because estimates better\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 4 Definitions\n* **** - \n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nGame Theory\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nOptimal Decisions in Games: Minimax Search\n\n(TABLE)\n\nAlpha Beta Pruning (see table)\n\n\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alphe Beta Tree Search \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic GAmes: involve random elemnts in the game, use expected minimax \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nBasic Utility Theory:\n\n-6 constraints\n\n1)orderability: rational agent must prefer one or the other, else it must equally prefer each one\n\n2)transitivity: given 3 lotteries, if the agent prefers A to B and B to C,it prefers A to C\n\n3)continuity: if some lottery B is between A and C in terms of preference, then there is some probability p that agent will be indifferent between getting B for sure, and yield A with prob p and C with prob 1-p\n4)substitutability: if an agent indifferent between two lotteries A and B, then its also indiffferent between two more complex lotteries that are the same except that Bis substituted for A in one of them\n\n5)monotinicity: two lotteries have 2 possible otcomes, A and B, then if agent prefers Ato B, it will chooose lottery w/ higher probabilty of A\n\n6)decomposiblity: compound lotteries can be reduced to simpler ones using laws of probability\n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Utility Functions \n\n## Module 5 Lecture Notes\n\n-Outline:\n\n\t1) Games as Search\n\n\t2) Adversarial Search\n\nx\n\n-Simple Games:\n\n\t1) Multiagent: playing against opponent, basing our decisions on opponents decision\n\n\t2) Static: no change in environment while agent is thinking\n\n\t3) Discrete: finite set of actions (vs continuous like aiming a gun, angle is continuous)\n\n\t4) Fully Obeservable: agent’s sensor gives complete state of environment\n\n\t5) Strategic: next state determined by current state & action executed by agent & action of one other agent\n\nx\n\n-Key Properties of our games:\n\n\t1) two player alternate moves\n\n\t2) zero-sum: one wins, other loses\n\n\t3) clear set of legal moves\n\n\t4) well defined outcomes (win, lose, draw)\n\nx\n\n-Formalize Game Setup:\n\n\t-Two players: MAX and MIN, MAX moves first\n\n\t-take turns until game over\n\n\t-winner gets award, loser gets penalty\n\n\n\t-Games as search:\n\n\t1) Initial state: board configuration\n\n\t2) Successor function: list of (move, state) pairs specifying legal moves\n\n\t* Evaluation functionL: given current state of the board, how good is it for us and our oppponents?\n\n\t3) Terminal test: is game finished?\n\n\t4) Utility function: gives numerical values of terminal states, ex) win (+inf), lose (-inf), draw (0)\n\n\t5) MAX uses serach tree to determine next move\n\nx\n\n-How to Play Game by Searching\n\n\tGeneral Scheme:\n\n\t1) Consider all legal successors to current state (“board position)\n\n\t2) Evaluate each successor board position\n\n\t3) Pick move that leads to best board position\n\n  4) After opponent moves, REPEAT\n\nx\n\nDesign issues:\n\t\n1) representing the ‘board’\n\n2) representing legal next boards\n\n3) evaluating positions\n\n4) looking ahead\n\nx\n\n-2 players: MAX and MIN (MAX’s opponent)\n\n-play computed from MAX’s vantage point\n\n-MAX attemps to MAXimize MAX’s outcome, MIN attempts to MINmimize MAX’s outcome\n\n\t-MAX moves first\n\n\n\t-root (level 0) MAX\n\n\t-alternate MAX/MIN labels for each successful tree level (ply)\n\n\t-Even level is MAX’s turn, Odd level is MIN’s turn\n\nx\n\n-Game Trees:\n\n\t-represents game problem by tree:\n\n\t\t-node = ‘board position’, edge = legal moves\n\n\t\t-root node is first position\n\n\t-Evaluation function f assigns score to ‘board’ without reference to path\n\n\t-terminal nodes represent way game could end with desirability label of that ending (win/lose/draw, \tnumerical score)\n\n\n-Evaluation function: f(n)\n\n\t-built using expert knowledge\n\n\t-evaluate how good board position is based on static features of that board alone\n\n\t-zero-sum assumption:\n\n\t\t-f(n) > 0: if MAX is winning in position n\n\n\t\t-f(n) = 0: if position n is tied\n\n\t\t-f(n) < 0: if MIN is winning in position n\n\nx\n\nx\n\nNxt Section: Minimax and Alpha Beta Pruning\n\n-Make the best move for MAX assuming that MIN always replies with the best move for MIN\n\n-computed by recursion:\n\n\t-backed-up value of a node is determined by value of its children:\n\n\t\t-for MAX node: backed-up value is maximum of the values of its children\n\n-for MIN node: backed-up value is minimum of the values of its children\n\nx\n\n(TABLE)\n\n-Minimax Procedure:\n\n\t-Until game is over:\n\n\t\t1) start with current positoin as MAX node\n\n2) expand game tree by fixed number of ply\n\n3) apply evalution function to the leaf positions\n\n4) calculate back-up values bottom-up\n\n5) pick move assigned to MAX at root\n\n6) wait for MIN to respond\n\nx\n\n(TABLE)\n\n-Alpha-Beta Pruning: cut out parts of tree that make no difference in final decision  reduce number of branches\n\n\t-during Minimax:\n\n\t\t-alpha: MAX’s current lower bound on MAX’s outcome\n\n\t\t-beta: MIN’s current upper bound on MIN’s outcome\n\n\t-(laymen’s terms)\n\n\t\t-MAX will never allow move that is worse than alpha (for MIN)\n\n\t\t-MIN will never allow move that is better than beta (for MAX)\n\n \t-(when evaluating)\n\n\t\t-when evaluating MIN: value v <= alpha is backed up, MAX will never select that MIN node\n\n\t\t-when evaluating MAX: value v >= beta is backed up, MIN will never select that MAX node\n\nx\n\n(TABLE)\n\n-Expectimax and Utilities: games with uncertain outcomes\n\n\t -why? Randomness, unpredictable opponents (suboptimal decisions), actions fail (wheels slip)\n\n\t-values reflect average case outcome (expectimax) vs worst case outcome (minimax) \n\n-Expectimax Search: compute average score under optimal play\n\n\t\t1) max nodes like in minimax search\n\n\t\t2) chance nodes are similar to min nodes, with uncertain outcomes\n\n\t\t3) calculate expected utility ¬ take weighted average of children\n\n\t\t*Markov Decision Processes (formalization of uncertain result problems)\n\n\t\t-Pruning for Expectimax: MUCH HARDER\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 5 Definitions\n* **Alpha-beta pruning** - cuts out parts of tree that make no difference in final decision, reduce number of branches\n* **Alpha** - MAX’s current lower bound on MAX’s outcome\n* **Beta** - MIN’s current upper bound on MIN’s outcome\n* **Minimax value** - value of each state in the tree for games\n* **** - \n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n k consistency\n\nnode consistency k = 1\n\narc consistency k = 2\n\npath consistency k = 3 \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\nConstraint Satisfaction Problems (identification problems)\n\n-Goal: come up with a set of variable assignments that are consistent with set of constraints using declarative language\n\n-represent constraints that solution must satisfy in uniform declarative language\n\n-find solutions by general purpose search algorithms that can be used for any problem\n\n-“what are constraints of a problem, develop general set of algorithms that apply those constraints and find correct assignment of values to variables”\n\nCSP contains:\n\n1)Finite set of variables: X1, X2,…, Xn\n\n2) Nonempty domain of possible values for each variable: D1, D2, …, Dn\n\n3) Finite set of constraints: C1, C2,…., Cm\n\n-each constraint limits values that variable can take (i.e. X1 != X2)\n\n2 Cond for Sol.\n\n1) consistent assignment does not violate constraints\n\n2) complete: every variable has a value\n\nBenefits of CSP: clean specification of many problems, generic goal, successor functions, heurstics\n\n-CSP ‘knows’ which varibles violate constraints\n\n-CSP automatically prunes off all branches that violate constraints\n\nx\n\nIdea1: CSP as a search problem, backtracking search\n\n-initial state: empty assignment {}\n\n-successfor function: assign value to any unassigned variable with no constraint conflict\n\n-goal test: current assignment complete\n\n-path cost: constant cost for every step\n\n*solution always at depth n for n variables  can use DFS\n\nSearch and branching factor:\n\n-n variables, domain size d\n\n-branching factor: n*d\n\n-total leaves: n! * d^n\n\nx\n\nidea 2: improve backtrack efficiency, heuristics with backtracking search: forward checking\n\n\t-general purpose methods and heuristics increase speed on avg.\n\n\t\t-which variable should be assigned next?  most constrained variable\n\n\t\t-what order should variables values be tried?  least constaining value\n\n\t\t-detect failure early?  forward checking\n\n\t\t-Heuristic 1: Most constrained variable (minimum remaining values (MRV) heuristic): fewest legal valu\n\n\t\t-Heuristic 2: Most constraining variable: tiebreaker between most constrained variables\n\n\t\t-Heuristic 3: Least constrainint value: given variable, choose least constraining VALUES (not VARIABLES)\n\n\t\t-Heuristic 4: Forward Checking: keep track of legal values for unassigned variables, terminate serach when no remaining legal values for unassigned variables\n\nx\n\n***idea 3 (BIG IDEA)***: inference in CSPs: Arc Consistency, Constraint Propagation & AC-3\n\n\t-CSP combines Search & Inference\n\n\t1) search: assign value to variable\n\n\t2) constraint propagation (inference): given current partial solution, is it going to lead to correct solution?\n\n\t-can do inference or search first, intertwine\n\n\n\n-Local Consistency\n\n\t1) Node consistency: satisfies unary constraints\n\n\t2) Arc consistency: satisfies binary constraint\n\n\t\t-undirected edge to directed arcs (x --> y: x tail, y head; remove value from tail)\n\n\t\t\t-X --> Y is consisitent iff: for every value of X, there is some allowed Y\n\n\t\t\t-if X loses a value, recheck neighbors of X\n\n-Waltz/Mackworth Constraint Propagation Algorithm  inefficient  towards AC-3\n\n\t1) Assign every node in the constraint graph a set of all possible values\n\n\t2) Repeat until there is no change in the set of values for any node\n\n\t\t3. for each node i:\n\n\t\t\t4. for each neighbording node j in the picture\n\n\t\t\t\t5. remove any value i which is not arc consistent with j\n\n\t-inefficient: only need to check tail, NOT head  AC-3 algorithm\n\nx\n\nx\n\nRecap\n\n\t-Constraint graph: nodes are variables, edges are constraints\n\n\t-Edges to Arcs: Constraint graph  Directed Graphs\n\n\t\t-Arc Consistency check: use propagation to check concistency  if X loses value, recheck neighbors \n\n\n\t2 Steps:\n\n\t\t1) Search Steps: assign value to variable, one step further in DFS\n\n\t\t2) Inference Steps: based on value assignments & elimanted items, are there other nodes with no possible value assignments?  remove that node and backtrack\n\n\t\t-recheck neighbors of X\n\n\n\t-Replacing Search: Constraint Propagation Invented:\n\n\t\t-Search: use constraints to add labels to find one solution\n\n\t\t-Constraint Propagation: use constraints to eliminae labels to simultaneously find all solutions\n\n\n\t-Waltz/Lackworth Constraint Propagation Algorithm\n\n\t\t1) Assign every node in constraint graph a set of all possible values\n\n\t\t2) Repeat until there is no change in the set of values for any node\n\n\t\t\t3. for each node i:\n\n\t\t\t\t4. for each neighbording node j in the picture\n\n\t\t\t\t\t5. remove any value i which is not arc consistent with j\n\n\t\t*INEFFICIENT  AC-3\n\n\n\t-***AC-3***: keep track of things we need to recheck, ONLY recheck neighbors of tail\n\n\t\t1) Each iteration: only examin Xi where at least one neighbor of Xi has lost a value in prev. iteration\n\n\t\t2)  if Xi loses a value b/c of arc inconsistency with Yj, don’t need to check Yj on next iteartion\n\n\t\t3) Removing value on Xi can only make Yj arc inconsisntent wrt Xi itself, only check that (j,i) still arc consistent\t\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n* **Csp** - identification problem\n* **State** - is an assignment of values to some or all variables\n* **Backtracking search** - DFS serach for CSP with with single variable assignemnts\n* **Mac** - maintaining arc consistency by interleaving search and inference\n* **** - \n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\ndsfe \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\nKB Agents\n\nx\n\nPropositional Logic:\n\n-KB consists of sentences in the representation language (RL)\n\n-RL has syntax that specifies sentences that are well-formed\n\n-a logic defines the semantics of the sentences  meaning\n\n-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\n\nx\n\nPossible worlds and models (m=model, alpha = sentence, {true, false}):\n\n  -m satisfies alpha\n\n  -m is a model of alpha\n\n  -M(alpha): set of all models of alpha\n\n  -alpha entails sentence β: alpha⊨β\n\n  -alpha⊨β if and only if M(alpha) ⊆ M(β)\n\nx\n\nx\n\nKnowledge Base\n\nLogical Equivalence (Table)\n\nInference Rules (Table)\n\nSearch for a Proof:\n\n1) Initial state\n\n2) Actions: all inferences rules applied to all setnences that match top 1/2 of inference rules \n\n3) Result: add the sentence to KB \n\n4) Goal: state that contains sentence we are trying to probe \n\n-Sound and Complete\n\nx\n\nConjunctive Normal Form (CNF): transform sentence to this form to use resolution algo (TABLE)\n\nResolution Algo: complete, not necessarily efficient (TABLE)\n\nFor efficiency in Resolution Algo\n\n1) Definite Clause\n\n2) Horn Clause: includes definite claus+clause with no positiuve \n\nx\n\nforward chaining(data driven reasoninig): set of data we know is true, move through environment and get percepts, enumerate new conclusions\n\nbackward chaining (goal directed reasoning):work backwards from query, if query known to be true, then nothing. Otherwise, find rules where gamma is conclusion and if query true, then alpha and beta is true\n\nx\n\nx\n\nx\n\nx\n\n-Knowledge-based Agents: use process of reasoning over an internal representation of knowledge to decide on actions  MORE COMPLEX\n\n\t-so far: problem-solving agents have performed serach over states to find plan  atomic: we don’t really \tknow anything about them (too brittle)\n\n\n\t-knowledge base (KB): contains set of sentences that are written in knowledge representation language that \thas some assertion about the world\n\n\t\t\n\t\t-2 kinds of sentences:\n\n\t\t1) axiom: given setneces\n\n\t\t2) derived sentences: new sentences derived from other setences (by a process called inference)\n\n\n\t\t-KB contains background info abt world\n\n1) KB Agent can add info by observation\n\n2) KB Agent queries KB and derive new knowledge\n\nx\n\n\t-WAMPA WORLD EXAMPLE\n\nx\n\n-Logic: general calss of representation for knowledge-based agents \n\n-Propositional Logic:\n\n\t-KB consists of sentences in the representation language (RL)\n\n\t-RL has syntax that specifies sentences that are well-formed\n\n\t-a logic defines the semantics of the sentences  meaning\n\n\t-the semantics defines the truth of each sentences w.r.t. a possible world (a model)\n\nx\n\n-Possible worlds and models (m=model, alpha = sentence, {true, false}):\n\n-m satisfies alpha \n\n-m is a model of alpha\n\n-M(alpha): set of all models of alpha\n\nx\n\n-Logical Entailment:\n\n\t-logical reasoning: involves entailment relation between setnences\n\n\t-entailment: a setnences follows logicallt from another setnences\n\nx\n\n-Knowledge Base\n\n\t-KB is false in any models that contrafict what agent knows\n\n\t-M(KB) inside M(alpha)\n\nx\n\n-Logical Inference: entailment (additional setneces from KB))    derive additional conclusions\n\n\t-derive inference algorithm to enumerate setnences\n\n\t\t-inference algorithm I allows us to use knowledge base to derive sentence alpha\n\nx\n\n-Propositional Logic: \n\n\t-atomic sentences represented with single propositional symbols: statements that are true or false\n\n\t-complex setences made from simpler ones with logical connectives \n\n(Logical Symbols TABLE)\n\n(Truth TABLE)\n\nx\n\n-A Simple knowledge base\n\n-Entailment and Inference\n\nx\n\n-Inference Algorithm: FIND which sentences are entailed by KB based on search\n\n\t-Sound: should only derive entailed sentences\n\n\t-Complete: can derive all sentences that are entailed\n\nx\n\n-Theorem Proving: inference algorithm does automated theorem proving\n\n-Logical Equivalence: two sentneces logically equivalent if they are true and in same set of models\n\n(Logical Equivalence Table)\n\n(Inference Rules TAble)\n\nx\n\n-Search for a Proof:\n\n\t1) Initial State:\n\n\t2) Actions: all inference rules applied to all sentences that match the top half of the inference rule\n\n\t3) Result: add the sentence to KB \n\n\t4) Goal: state that contains the sentence that we are trying to prove\n\n\n\t-Monotinicity:set of entailed setneces can only increase as information is added to KB --> Soundness\n\n\t-Proof by Resolution: single inference rule that yields a complete inference algoirthm when coupled with any \tcomplete search algorithm --> Complete\n\n\n  -Resolution: eliminate l1 and m by unit resolution (JUST FOR disjunctions (OR) of literals/clauses)\n\n\t\t-how do we get everything to a disjunction? …….\n\n\t\n  -Conjunctive Normal Form (CNF): every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals\n\n(CDN info TABLE)\n\nx\n\n-Resolution Algorithm (COMPLETE, but not necessarily efficient):\n\n\t\t-empty clause is the contradiction (step 2 in last step)xxxxx\n\n(Resolution Algo CodeTABLE)\n\n\t-Resolution Algorithm Efficiency:\n\n    -disjunction = or \n\n\t\t1) Definite Clause: disjunction where exactly one is positive\n\n\t\t2) Horn Clause: disjunction where at most one is positive\n\n\t\t\t-includes definite clauses\n\n\t\t\t-includes clauses with no positive\n\n      (Definite Clause info TABLE)\n\n      -Forward Chaining (data driven reasoning): set of data we know is true, move through environment and get percepts, enumerate new conclusions\n\n      -Backward Chaining (goal-directed reasoning): work backwards from query, if query known to be true, then nothing. Otherwise, find rules where gamma is conclusion and if query true, then alpha and beta is true.\n\n\t-\n\n\n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - complex problem solving agent use reasoning over an internal representation of knowledge tochoose action\n* **Knowledge base (kb)** - set of sentences that are written in knowledge representation language that \thave some assertion about the world\n* **Logical reasoning** - involves entailment relation between setnences\n* **Entailment** - sentences that follows logically from another setnences\n* **Inference algorithm** - helps to find which sentences are entailed by KB based on search\n* **Sound** - an algo should only derive entailed sentences\n* **Complete** - an algo can derive all sentences that are entailed\n* **Logical equivalence** - two sentneces logically equivalent if they are true and in same set of models\n* **Monotinicity** - a set of entailed sentences can only increase as information is added to KB, implies SOUNDNESS\n* **Proof by resolution** - single inference rule that yields a complete inference algorithm when coupled with any complete search algorithm implies Completebess\n* **Conjunctive normal form (cnf)** - every sentence of propositional logic is logically equivalent to a conjunction of clauses\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}