{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e2fc0e08-f9c6-444c-a201-2dfa412bd3f8"
      },
      "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": null,
      "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": "240ff161-40f2-4ff5-dbcf-228abd67112c"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "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 = \"\"\" Some ppl define AI in terms of human performance, others have formal defition of rationality, doing the right thing. Human vs. rational, thought vs. behavior.\n",
        "Diff types of ppl want machines to either be optimal or think exactly like humans\n",
        "Turing test-can a machine think like a human?\n",
        "total turing test involves interaction with humans in the real world\n",
        "need to know how humans think for cognitive modeling approach -- introspection, psychology, cognitive science\n",
        "Thinking rationally\n",
        "an agent is something that acts\n",
        "rational agent acts to achieve the best outcome\n",
        "limited rationality when not enough time\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \n",
        "weak AI, machines act like they are thinking\n",
        "strong AI machines are actually consciously thinking\n",
        "There are limits to what AI and machines can do overall\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Chinese room argument is that even if you can find patterns and reproduce chinese symbols based on english, you don't actually understand chinese\n",
        "biological naturalism says that understanding and high level features come from neurons. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" simple reflex agents select actions based on current percepts and ignore other history. \n",
        "problem-solving agent must plan ahead. computational process that it takes is called a search\n",
        "Goal based agents act to try to get to a goal, and utility based agents act to try to maximize happiness\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "  Agents include humans, robots, softbots, thermostats,\n",
        "  design performance meaures in terms of what you want to be achieved, not how you think agent should behave\n",
        "  rational agents try to maximize their performance measures\n",
        "  maximize the EXPECTED VALUE of their performance since they dont know what it will be\n",
        "  PEAS for task environment\n",
        "  P = performance measure\n",
        "  E = environment\n",
        "  A = actuators\n",
        "  S = sensors\n",
        "  Goal of a rational agent designer is to construct agent function that maximizes expected value of performance measure (abstract)\n",
        "  Then we want to design an agent program that implements this agent function (concrete implementation)\n",
        "\n",
        "  fully observable v. partially observable\n",
        "  deterministic v. nondeterministic v. stochastic\n",
        "  episodic v. sequential\n",
        "  static v. dynamic\n",
        "\n",
        "  hardest are partially observable, stochastic, continuous, multi agent\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",
        "\"rational agent\" : \"agent that acts to achieve the best outcome\",\n",
        "\"performance measure\" : \"evaluating success of agents behavior based on what it could have done\",\n",
        "\"task environment\": \"environment/challenge where agent is supposed to solve something\",\n",
        "\"limited rationality\": \"acting rationally when there isnt enough time to do all the computations\",\n",
        "\"agent function\": \"function which maps a set of percept vectors p to action a from the set A\",\n",
        "\"natural language processing\": \"ability for computer to communicate in a human language\",\n",
        "\"knowledge representation\": \"ability for computer to store what it knows or hears\",\n",
        "\"automated reasoning\": \"ability for computer to answer questions and draw new conclusions\",\n",
        "\"machine learning\": \"ability for computer to adapt to new circumstances and detect patterns\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "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": "acc6ba0c-7f02-430c-b2fc-a928fdd286c3"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Some ppl define AI in terms of human performance, others have formal defition of rationality, doing the right thing. Human vs. rational, thought vs. behavior.\nDiff types of ppl want machines to either be optimal or think exactly like humans\nTuring test-can a machine think like a human?\ntotal turing test involves interaction with humans in the real world\nneed to know how humans think for cognitive modeling approach -- introspection, psychology, cognitive science\nThinking rationally\nan agent is something that acts\nrational agent acts to achieve the best outcome\nlimited rationality when not enough time\n \n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak AI, machines act like they are thinking\nstrong AI machines are actually consciously thinking\nThere are limits to what AI and machines can do overall\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room argument is that even if you can find patterns and reproduce chinese symbols based on english, you don't actually understand chinese\nbiological naturalism says that understanding and high level features come from neurons. \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n simple reflex agents select actions based on current percepts and ignore other history. \nproblem-solving agent must plan ahead. computational process that it takes is called a search\nGoal based agents act to try to get to a goal, and utility based agents act to try to maximize happiness\n \n\n## Module 1 Lecture Notes\n \n  Agents include humans, robots, softbots, thermostats,\n  design performance meaures in terms of what you want to be achieved, not how you think agent should behave\n  rational agents try to maximize their performance measures\n  maximize the EXPECTED VALUE of their performance since they dont know what it will be\n  PEAS for task environment\n  P = performance measure\n  E = environment\n  A = actuators\n  S = sensors\n  Goal of a rational agent designer is to construct agent function that maximizes expected value of performance measure (abstract)\n  Then we want to design an agent program that implements this agent function (concrete implementation)\n\n  fully observable v. partially observable\n  deterministic v. nondeterministic v. stochastic\n  episodic v. sequential\n  static v. dynamic\n\n  hardest are partially observable, stochastic, continuous, multi agent\n\n  \n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts to achieve the best outcome\n* **Performance measure** - evaluating success of agents behavior based on what it could have done\n* **Task environment** - environment/challenge where agent is supposed to solve something\n* **Limited rationality** - acting rationally when there isnt enough time to do all the computations\n* **Agent function** - function which maps a set of percept vectors p to action a from the set A\n* **Natural language processing** - ability for computer to communicate in a human language\n* **Knowledge representation** - ability for computer to store what it knows or hears\n* **Automated reasoning** - ability for computer to answer questions and draw new conclusions\n* **Machine learning** - ability for computer to adapt to new circumstances and detect patterns\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "all data treated as objects\n",
        "strong typing\n",
        "dynamic typing\n",
        "prefixing strings with r means raw, no escape characters\n",
        "strings are immutable, lists are mutable\n",
        "use y = x[:] to get a shallow copy of mutable stuff\n",
        "sequence types - tuples, strings, lists\n",
        "can mix and match types within a sequence\n",
        "tuples are immutable and hashable\n",
        "strings are immutable and hashable\n",
        "lists are mutable and not hashable\n",
        ".index() gets first occurrence in a list\n",
        ".sort() and .reverse()\n",
        ".upper() is all upper for a string, .capitalize() is just first letter\n",
        "\n",
        "dictionaries are mapping -- create, add, update\n",
        "\n",
        "functions -- no function overloading like in java (cant have same name)\n",
        "but operator overloading is possible with specific function names\n",
        "you have *args and *kwargs, you can put them together too\n",
        "\n",
        "functions are first class objects -- dynamically created, destroyed, passed to a function, returned as a value\n",
        "\n",
        "to define a subclass put the name of the superclass in parentheses after subclasses name -- class AI_student(Student):\n",
        "\n",
        "magic methods are init, len, copy, cmp, add, neg, etc\n",
        "\n",
        "list comprehension replaces for loops -- [expression for name in list]\n",
        "can add an if statement for filtered list comprehension\n",
        "dictionary, set comprehension occurs in a similar way\n",
        "\n",
        "iterator objects have next()\n",
        "iterators use memory efficiently\n",
        "\n",
        "generators use yield\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"can be modified after creation\",\n",
        "\"defaultdict\": \"automatically initializes nonexistent dictionary values\",\n",
        "\"*args\": \"accept a variable number of non keyword args\",\n",
        "\"*kwargs\": \"accept a variable number of keyword args\",\n",
        "\"magic method\": \"user defined classes can have regular type operations like + - < > etc\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 546
        },
        "outputId": "887fb5c8-4f8c-4091-caa4-ac279826bbe4"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nall data treated as objects\nstrong typing\ndynamic typing\nprefixing strings with r means raw, no escape characters\nstrings are immutable, lists are mutable\nuse y = x[:] to get a shallow copy of mutable stuff\nsequence types - tuples, strings, lists\ncan mix and match types within a sequence\ntuples are immutable and hashable\nstrings are immutable and hashable\nlists are mutable and not hashable\n.index() gets first occurrence in a list\n.sort() and .reverse()\n.upper() is all upper for a string, .capitalize() is just first letter\n\ndictionaries are mapping -- create, add, update\n\nfunctions -- no function overloading like in java (cant have same name)\nbut operator overloading is possible with specific function names\nyou have *args and *kwargs, you can put them together too\n\nfunctions are first class objects -- dynamically created, destroyed, passed to a function, returned as a value\n\nto define a subclass put the name of the superclass in parentheses after subclasses name -- class AI_student(Student):\n\nmagic methods are init, len, copy, cmp, add, neg, etc\n\nlist comprehension replaces for loops -- [expression for name in list]\ncan add an if statement for filtered list comprehension\ndictionary, set comprehension occurs in a similar way\n\niterator objects have next()\niterators use memory efficiently\n\ngenerators use yield\n\n\n\n## Module 2 Definitions\n* **Mutability** - can be modified after creation\n* **Defaultdict** - automatically initializes nonexistent dictionary values\n* ***args** - accept a variable number of non keyword args\n* ***kwargs** - accept a variable number of keyword args\n* **Magic method** - user defined classes can have regular type operations like + - < > etc\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "  reflex agents only focus on current precept \\n\n",
        "  problem solving agents need to consider a sequence of actions from start to goal state \\n\n",
        "  this sequence is called a solution \\n\n",
        "\n",
        "  If environment is fully observable, deterministic, known, then the solution is just a sequence of actions \\n\n",
        "  But if its nondeterministic or partially observable, it depends, and could involve branching \\n\n",
        "\n",
        "  Need to formulate a goal, formulate a search problem, and then find a solution \\n\n",
        "\n",
        "  FORMAL DEFINITION OF SEARCH PROBLEMS \\n\n",
        "  1. states\\n\n",
        "  2. initial state\\n\n",
        "  3. A set of possible actions\\n\n",
        "  4. A transition model and successors\\n\n",
        "  5. path cost (performance measure) must be additive\\n\n",
        "  6. goal test (can be implicit)\\n\n",
        "\n",
        "  Formulating a search problem is an art:\n",
        "  For the initial state, goal state, and intermediate states, need to decide which properties matter and how to represent them\\n\n",
        "  For the operator set, need to decide which actions are possible and how to represent them\\n\n",
        "  Decide which action is next\\n\n",
        "\n",
        "  !) Formulation affects combinatorics of search space and thus how much time search problem will take\\n\n",
        "\n",
        "  Selecting a state space is hard bc real world is complex, need to use abstractions for states and actions\\n\n",
        "\n",
        "  BASIC SEARCH ALGORITHMS\\n\n",
        "\n",
        "  Tree search\\n\n",
        "  In tree search, you get all paths from the initial state and search through explicit tree generation\\n\n",
        "  initialize frontier to the initial state, and just extract from frontier and keep expanding and adding resulting nodes to frontier until you get to a solution\\n\n",
        "  !) But the issue here is that with repeated states you can get an exponential time problem from a linear one\n",
        "  The solution is... \\n\\n\n",
        "\n",
        "  Graph Search\\n\n",
        "  One difference with this and tree search is you just check which nodes you've seen before and you expand them only if you haven't seen them\\n\n",
        "\n",
        "  Uninformed search strategies\\n\n",
        "  in uninformed search, all nodes that are not the goal look equally good\\n \n",
        "  uses only info in problem definition\\n\n",
        "\n",
        "  GRAPH SEARCH ALGOS\\n\n",
        "\n",
        "  BFS\\n\n",
        "  expand the shallowest node in the frontier first\\n\n",
        "  frontier is FIFO\\n\n",
        "  Complete if branching factor is finite\\n\n",
        "  Optimal if every step has the same cost (not optimal in general)\\n\n",
        "  Time complexity is $O(b^d)$\\n\n",
        "  Space complexity is $O(b^d)$ because it keeps all nodes in memory\\n\n",
        "  exponential time is not good\\n\n",
        "\n",
        "  DFS\\n\n",
        "  expand the DEEPEST unexpanded node\\n\n",
        "  frontier is LIFO (stack)\\n\n",
        "  NOT complete (if you have infinite length paths it will keep going)\\n\n",
        "  NOT optimal\\n \n",
        "  Time is $O(b^m)$\\n\n",
        "  Space is $O(bm)$\\n\n",
        "\n",
        "  BFS vs DFS\\n\n",
        "  Use DFS if *space is restricted*\\n\n",
        "  Use DFS if there are many possible solutions with long paths and wrong solutions end quickly\\n\n",
        "  Use DFS if the search can be fine tuned quickly\\n \n",
        "  Use BFS if there are *possible infinite paths*\\n\n",
        "  Use BFS if some solutions have short paths\\n\n",
        "  Use BFS if you can quickly discard unlikely paths\\n\n",
        "\n",
        "  BFS is complete, optimal, BUT uses O($b^d$) space\\n\n",
        "  DFS is not complete unless m is bounded, not optimal, uses O($b^m$) time, BUT only uses O($bm$) space.\\n\n",
        "\n",
        "  How do you get the best of both?\\n\n",
        "\n",
        "  Depth-limited search: a building block\\n\n",
        "  You put a depth limit $l$ so that you have no infinite path problem\\n\n",
        "  If $l = d$, then its optimal\\n\n",
        "  But if $l > d$ then not optimal, but if $l < d$ then incomplete\\n\n",
        "  Time complexity is $O(b^l)$ and space complexity is $O(bl)$\\n\n",
        "\n",
        "  Iterative deepening search\\n\n",
        "  Use depth-limited search as a subroutine and keep increasing $l$ by 1 until you get it\\n\n",
        "  This is complete and optimal\\n\n",
        "  Time: $O(b^d)$\\n\n",
        "  Space: $O(bd)$\\n\n",
        "  No infinite paths so its complete\\n\n",
        "  Optimal if the step cost is 1\\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",
        "\"solution\": \"path that a problem solving agent takes from start to goal state\",\n",
        "\"state space\": \"set of all states that you can get to from the source via ANY sequence of actions\",\n",
        "\"path\": \"to get from state a to state b, what actions you took to get there\",\n",
        "\"solution\": \"a path to the a state that satisfies the goal test\", \n",
        "\"search tree\": \"a way to represent possible paths explored\",\n",
        "\"frontier\": \"states that are available for expansion/to continue searching on\",\n",
        "\"optimal solution\": \"if no other solution can be achieved with lower path cost, the solution is optimal\",\n",
        "\"strategy\": \"the strategy in a search problem is the order in which we expand the tree\",\n",
        "\"completeness\": \"a complete search algorithm always finds the solution\",\n",
        "\"optimal\": \"an optimal search algorithm finds the lowest cost solution first\",\n",
        "\"time complexity\": \"worst case number of nodes generated in the search\", \n",
        "\"space complexity\": \"the worst case number of nodes that are being stored in memory at any given time\",\n",
        "\"b (branching factor)\": \"maximum branching factor of a tree is the max number of children that a node can have\",\n",
        "\"d\": \"lowest possible depth of a goal node (lowest meaning smallest magnitude)\",\n",
        "\"m\": \"maximum length of paths that exist\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "68b4d57e-901e-4bde-b8d1-85b4eb791a20"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n  reflex agents only focus on current precept \n\n  problem solving agents need to consider a sequence of actions from start to goal state \n\n  this sequence is called a solution \n\n\n  If environment is fully observable, deterministic, known, then the solution is just a sequence of actions \n\n  But if its nondeterministic or partially observable, it depends, and could involve branching \n\n\n  Need to formulate a goal, formulate a search problem, and then find a solution \n\n\n  FORMAL DEFINITION OF SEARCH PROBLEMS \n\n  1. states\n\n  2. initial state\n\n  3. A set of possible actions\n\n  4. A transition model and successors\n\n  5. path cost (performance measure) must be additive\n\n  6. goal test (can be implicit)\n\n\n  Formulating a search problem is an art:\n  For the initial state, goal state, and intermediate states, need to decide which properties matter and how to represent them\n\n  For the operator set, need to decide which actions are possible and how to represent them\n\n  Decide which action is next\n\n\n  !) Formulation affects combinatorics of search space and thus how much time search problem will take\n\n\n  Selecting a state space is hard bc real world is complex, need to use abstractions for states and actions\n\n\n  BASIC SEARCH ALGORITHMS\n\n\n  Tree search\n\n  In tree search, you get all paths from the initial state and search through explicit tree generation\n\n  initialize frontier to the initial state, and just extract from frontier and keep expanding and adding resulting nodes to frontier until you get to a solution\n\n  !) But the issue here is that with repeated states you can get an exponential time problem from a linear one\n  The solution is... \n\n\n\n  Graph Search\n\n  One difference with this and tree search is you just check which nodes you've seen before and you expand them only if you haven't seen them\n\n\n  Uninformed search strategies\n\n  in uninformed search, all nodes that are not the goal look equally good\n \n  uses only info in problem definition\n\n\n  GRAPH SEARCH ALGOS\n\n\n  BFS\n\n  expand the shallowest node in the frontier first\n\n  frontier is FIFO\n\n  Complete if branching factor is finite\n\n  Optimal if every step has the same cost (not optimal in general)\n\n  Time complexity is $O(b^d)$\n\n  Space complexity is $O(b^d)$ because it keeps all nodes in memory\n\n  exponential time is not good\n\n\n  DFS\n\n  expand the DEEPEST unexpanded node\n\n  frontier is LIFO (stack)\n\n  NOT complete (if you have infinite length paths it will keep going)\n\n  NOT optimal\n \n  Time is $O(b^m)$\n\n  Space is $O(bm)$\n\n\n  BFS vs DFS\n\n  Use DFS if *space is restricted*\n\n  Use DFS if there are many possible solutions with long paths and wrong solutions end quickly\n\n  Use DFS if the search can be fine tuned quickly\n \n  Use BFS if there are *possible infinite paths*\n\n  Use BFS if some solutions have short paths\n\n  Use BFS if you can quickly discard unlikely paths\n\n\n  BFS is complete, optimal, BUT uses O($b^d$) space\n\n  DFS is not complete unless m is bounded, not optimal, uses O($b^m$) time, BUT only uses O($bm$) space.\n\n\n  How do you get the best of both?\n\n\n  Depth-limited search: a building block\n\n  You put a depth limit $l$ so that you have no infinite path problem\n\n  If $l = d$, then its optimal\n\n  But if $l > d$ then not optimal, but if $l < d$ then incomplete\n\n  Time complexity is $O(b^l)$ and space complexity is $O(bl)$\n\n\n  Iterative deepening search\n\n  Use depth-limited search as a subroutine and keep increasing $l$ by 1 until you get it\n\n  This is complete and optimal\n\n  Time: $O(b^d)$\n\n  Space: $O(bd)$\n\n  No infinite paths so its complete\n\n  Optimal if the step cost is 1\n\n\n \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Solution** - a path to the a state that satisfies the goal test\n* **State space** - set of all states that you can get to from the source via ANY sequence of actions\n* **Path** - to get from state a to state b, what actions you took to get there\n* **Search tree** - a way to represent possible paths explored\n* **Frontier** - states that are available for expansion/to continue searching on\n* **Optimal solution** - if no other solution can be achieved with lower path cost, the solution is optimal\n* **Strategy** - the strategy in a search problem is the order in which we expand the tree\n* **Completeness** - a complete search algorithm always finds the solution\n* **Optimal** - an optimal search algorithm finds the lowest cost solution first\n* **Time complexity** - worst case number of nodes generated in the search\n* **Space complexity** - the worst case number of nodes that are being stored in memory at any given time\n* **B (branching factor)** - maximum branching factor of a tree is the max number of children that a node can have\n* **D** - lowest possible depth of a goal node (lowest meaning smallest magnitude)\n* **M** - maximum length of paths that exist\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Informed search is quicker than uninformed\\n\n",
        "\n",
        "UNIFORM COST SEARCH\\n\n",
        "this is a confusing name, it's not uniform edge weights. You DO take into account edge weights\\n\n",
        "g(n) is the path cost function -- cost to reach a node from the source\\n\n",
        "path cost function is the sum of all of the weigts of the edges taken to get to it\\n\n",
        "It is an expansion of BFS -- expand the node with LOWEST path cost\\n\n",
        "Frontier is a priority queue ordered by g(n)\\n\n",
        "Test if a node is in goal state when its selected for expansion, not when its added to frontier like in BFS\\n\n",
        "Update the node on frontier if a better path to the same state is found\\n\n",
        "Enqueues a node BEFORE checking whether it is a goal node\\n\n",
        "UCS lets us prioritize which paths to explore. Favors lower cost path resulting in cost contours.\n",
        "\n",
        "\\n\n",
        "\n",
        "A BETTER IDEA...\\n\n",
        "Node expansion based on an estimate or heuristic\\n\n",
        "Want an evaluation function and sort the frontier queue by the evaluation function\\n\n",
        "Straight line distance is a good heuristic\\n\n",
        "\n",
        "GREEDY BEST FIRST SEARCH\\n\n",
        "priority queue with heuristic as the priority\\n\n",
        "h(n) = f(n)\\n\n",
        "Same thing as UCS but with h(n) instead of g(n)\\n\n",
        "if there are obstacles, this will NOT give you an optimal path\\n\n",
        "It can also get stuck in loops\\n\n",
        "\n",
        "A* search\\n\n",
        "this prunes out expensive paths and expands promising ones\\n\n",
        "Best known form of best-first search\\n\n",
        "f(n) = g(n) + h(n)\\n\n",
        "Key concept is admissible heuristics, admissible means they never overestimate the cost to reach goal\\n\n",
        "Theorem is that if h(n) is admissible, then A* using tree search is optimal\\n\n",
        "admissibility is the idea that when something looks promising, give it a reward\\n\n",
        "\n",
        "A good heuristic function can reduce the search process\\n\n",
        "A good way of coming up with a heuristic is to have the same problem but with a couple restrictions removed/relaxed\\n\n",
        "!) the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\\n\n",
        "Dominant admissible metrics are better beacuse they are still optimistic but also more accurate\\n\n",
        "h*(n) is the best heuristic and 0 is the worst heuristic\\n\n",
        "\n",
        "Admissible heuristics slow down bad plans but don't outweight true costs -- the true best plan will always be expanded\\n\n",
        "Inadmissible heuristics could make the true best path not look good and push it back on the frontier and they won't get expanded\\n\n",
        "\n",
        "A* expands mainly towards the goal, but does hedge its bets to ensure optimality\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"uniform-cost search\" : \"search algorithm to go over a WEIGHTED tree or graph\",\n",
        "\"heuristic function\": \"given a state, it returns an estimate of the cost to the goal from that state\",\n",
        "\"admissible\": \"never overstimate the cost to goal, optimistic\",\n",
        "\"dominance\": \"when one heuristic is always larger than another for all n, the first one dominates the second\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4289eb9d-7b93-4cfe-92d7-e54e25147c61"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n\nInformed search is quicker than uninformed\n\n\nUNIFORM COST SEARCH\n\nthis is a confusing name, it's not uniform edge weights. You DO take into account edge weights\n\ng(n) is the path cost function -- cost to reach a node from the source\n\npath cost function is the sum of all of the weigts of the edges taken to get to it\n\nIt is an expansion of BFS -- expand the node with LOWEST path cost\n\nFrontier is a priority queue ordered by g(n)\n\nTest if a node is in goal state when its selected for expansion, not when its added to frontier like in BFS\n\nUpdate the node on frontier if a better path to the same state is found\n\nEnqueues a node BEFORE checking whether it is a goal node\n\nUCS lets us prioritize which paths to explore. Favors lower cost path resulting in cost contours.\n\n\n\n\nA BETTER IDEA...\n\nNode expansion based on an estimate or heuristic\n\nWant an evaluation function and sort the frontier queue by the evaluation function\n\nStraight line distance is a good heuristic\n\n\nGREEDY BEST FIRST SEARCH\n\npriority queue with heuristic as the priority\n\nh(n) = f(n)\n\nSame thing as UCS but with h(n) instead of g(n)\n\nif there are obstacles, this will NOT give you an optimal path\n\nIt can also get stuck in loops\n\n\nA* search\n\nthis prunes out expensive paths and expands promising ones\n\nBest known form of best-first search\n\nf(n) = g(n) + h(n)\n\nKey concept is admissible heuristics, admissible means they never overestimate the cost to reach goal\n\nTheorem is that if h(n) is admissible, then A* using tree search is optimal\n\nadmissibility is the idea that when something looks promising, give it a reward\n\n\nA good heuristic function can reduce the search process\n\nA good way of coming up with a heuristic is to have the same problem but with a couple restrictions removed/relaxed\n\n!) the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\nDominant admissible metrics are better beacuse they are still optimistic but also more accurate\n\nh*(n) is the best heuristic and 0 is the worst heuristic\n\n\nAdmissible heuristics slow down bad plans but don't outweight true costs -- the true best plan will always be expanded\n\nInadmissible heuristics could make the true best path not look good and push it back on the frontier and they won't get expanded\n\n\nA* expands mainly towards the goal, but does hedge its bets to ensure optimality\n\n\n\n \n\n## Module 4 Definitions\n* **Uniform-cost search** - search algorithm to go over a WEIGHTED tree or graph\n* **Heuristic function** - given a state, it returns an estimate of the cost to the goal from that state\n* **Admissible** - never overstimate the cost to goal, optimistic\n* **Dominance** - when one heuristic is always larger than another for all n, the first one dominates the second\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Now we need to reason about opponent movements\\n\n",
        "Games are a search problem of a certain kind\\n\n",
        "The simplest GAME environment for rational agents are multiagent, static (no change while agent deliberates), discrete/finite, fully observable, and strategic (the next state is determined by current state and action executed by agent and actions of one other agent)\\n\n",
        "Properties of game -- players alternate, zero-sum, set of legal moves, well-defined outcomes\\n\n",
        "More complicated games are stochastic, not fully observable, real time, etc\\n\n",
        "\n",
        "Formalizing game setup\\n\n",
        "1. 2 players MAX and MIN\\n\n",
        "2. MAX and MIN take turns until game over\\n\n",
        "3. Winner gets an award, loser gets a penalty\\n\n",
        "\n",
        "Games as search\\n\n",
        "initial state, successor function, terminal test (is game finished?), utility function (gives numerical value of terminal states)\\n\n",
        "MAX uses search tree to determine next move\\n\n",
        "General scheme of search\\n\n",
        "1. consider all legal successors to the current state\\n\n",
        "2. evaluate each successor board position\\n\n",
        "3. pick move which leads to best board position\\n\n",
        "4. after opponent moves, repeat\\n\n",
        "\n",
        "Issues with this such as representing board, representing next legal boards, evaluating positions, and looking ahead\\n\n",
        "Game trees -- represent the game problem space by a tree where nodes are board positions and edges are legal moves\\n\n",
        "We need to make our own evaluation function that evaluates how good a board position is.\\n\n",
        "If f(n) > 0 MAX is winning at that particular position\\n\n",
        "\n",
        "\n",
        "MINIMAX\\n\n",
        "Main idea is don't play hope chess, make the best move for MAX assuming that MIN will make best move for MIN\\n\n",
        "Until game is over, do the following:\\n\n",
        "Start with the current position as a MAX node.\\n\n",
        "Expand the game tree a fixed number of ply.\\n\n",
        "Apply the evaluation function to the leaf positions.\\n\n",
        "Calculate back-up values bottom-up.\\n\n",
        "Pick the move assigned to MAX at the root\\n\n",
        "Wait for MIN to respond\\n\n",
        "\n",
        "\n",
        "ALPHA BETA PRUNING\\n\n",
        "During minimax keep track of 2 values:\\n\n",
        "alpha--MAX's current lower bound on MAX's outcome. MAX will never allow a move that could lead to a worse score than alpha\\n\n",
        "beta--MIN's current upper bound on MIN's outcome. MIN will never allow a move that could lead to a better score for MAX than beta\\n\n",
        "Thus, the pruning happens when, for a max node, if a value >= beta is backed up, because min will never select that max node. It also happens for a MIN node if a value <= alpha is backed up, because MAX will never pick that min node.\\n\n",
        "\n",
        "Expectimax search: compute the average score under optimal play\\n\n",
        "Chance nodes are like min nodes but their outcome is uncertain, so we need to calculate expected utilities\\n\n",
        "EXP agent returns expected values\\n\n",
        "Some people think that you can \"learn\" probabilities, through Bayesian stuff, called informed probabilities\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"random variable\" : \"represents an event whose outcome is unknown\",    \n",
        "\"probability distribution\": \"assignment of weights to outcomes\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "841ed450-4aee-4f87-ae40-70a02f461515"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nNow we need to reason about opponent movements\n\nGames are a search problem of a certain kind\n\nThe simplest GAME environment for rational agents are multiagent, static (no change while agent deliberates), discrete/finite, fully observable, and strategic (the next state is determined by current state and action executed by agent and actions of one other agent)\n\nProperties of game -- players alternate, zero-sum, set of legal moves, well-defined outcomes\n\nMore complicated games are stochastic, not fully observable, real time, etc\n\n\nFormalizing game setup\n\n1. 2 players MAX and MIN\n\n2. MAX and MIN take turns until game over\n\n3. Winner gets an award, loser gets a penalty\n\n\nGames as search\n\ninitial state, successor function, terminal test (is game finished?), utility function (gives numerical value of terminal states)\n\nMAX uses search tree to determine next move\n\nGeneral scheme of search\n\n1. consider all legal successors to the current state\n\n2. evaluate each successor board position\n\n3. pick move which leads to best board position\n\n4. after opponent moves, repeat\n\n\nIssues with this such as representing board, representing next legal boards, evaluating positions, and looking ahead\n\nGame trees -- represent the game problem space by a tree where nodes are board positions and edges are legal moves\n\nWe need to make our own evaluation function that evaluates how good a board position is.\n\nIf f(n) > 0 MAX is winning at that particular position\n\n\n\nMINIMAX\n\nMain idea is don't play hope chess, make the best move for MAX assuming that MIN will make best move for MIN\n\nUntil game is over, do the following:\n\nStart with the current position as a MAX node.\n\nExpand the game tree a fixed number of ply.\n\nApply the evaluation function to the leaf positions.\n\nCalculate back-up values bottom-up.\n\nPick the move assigned to MAX at the root\n\nWait for MIN to respond\n\n\n\nALPHA BETA PRUNING\n\nDuring minimax keep track of 2 values:\n\nalpha--MAX's current lower bound on MAX's outcome. MAX will never allow a move that could lead to a worse score than alpha\n\nbeta--MIN's current upper bound on MIN's outcome. MIN will never allow a move that could lead to a better score for MAX than beta\n\nThus, the pruning happens when, for a max node, if a value >= beta is backed up, because min will never select that max node. It also happens for a MIN node if a value <= alpha is backed up, because MAX will never pick that min node.\n\n\nExpectimax search: compute the average score under optimal play\n\nChance nodes are like min nodes but their outcome is uncertain, so we need to calculate expected utilities\n\nEXP agent returns expected values\n\nSome people think that you can \"learn\" probabilities, through Bayesian stuff, called informed probabilities\n\n\n\n\n\n\n \n\n## Module 5 Definitions\n* **Random variable** - represents an event whose outcome is unknown\n* **Probability distribution** - assignment of weights to outcomes\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "There are different types of searches. Before, we focused on planning searches where the path to goal was most important thing.\\n\n",
        "For CSPs, its an identification problem where you assign things to variables. CSPs are specialized for identification problems.\\n\n",
        "!) represent the constraints that solutions must satisfy in a declarative language.\\n\n",
        "You then use generalm purpose search algorithms, without transition functions or heuristics.\\n\n",
        "Just need to specify the problem in formal declarative language, and then general-purpose algorithm does everything else.\\n\n",
        "\n",
        "A CSP consists of: variables to be assigned to, domain of possible values, set of constraints\\n\n",
        "A consistent assignment does not violate constraints\\n\n",
        "\n",
        "A complete assignment is where every variable is assigned a value.\\n\n",
        "!) A solution to a CSP is a complete, consistent assignment.\\n\n",
        "As long as you have the formal specification of the CSP, you can solve it with a general purpose algorithm\\n\n",
        "\n",
        "Benefits of CSP:\\n\n",
        "generic goal and clean specification\\n\n",
        "CSPs know which variables violate constraints\\n\n",
        "CSPs will prune off branches which violate constraints\\n\n",
        "\n",
        "Constraint graph:\\n\n",
        "nodes are variables\\n\n",
        "arcs are binary constraints\\n\n",
        "\n",
        "Varieties of CSPs:\\n\n",
        "Discrete variables: n variables and domain size d -> O($d^n$) assignments\\n\n",
        "continous variables\\n\n",
        "\n",
        "Unary constraints involve one variable, binary constraints involve 2 variables\\n\n",
        "\n",
        "CSPs have initial state, successor function, goal test, path cost\\n\n",
        "Solution is always found at depth n for n variables --> use DFS\\n\n",
        "!) backtracking search is the basic uninformed algorithm for CSPs\\n\n",
        "To improve backtracking efficiency, we can apply heuristics and stuff:\\n\n",
        "1. One example of a heuristic is you want to assign the variable with the most constraints/the one with the least amount of legal values\\n\n",
        "2. If there are ties, then you can assign the least constrained variables\\n\n",
        "3. Or another heuristic is the least constraining value\\n\n",
        "4. forward checking -- keep track of remaining legal values for unassigned variables, end search when any unassigned variable has no values left\\n\n",
        "\n",
        "Towards constraint propogation\\n\n",
        "Forward checking propagates information assigned to unassigned variables but doesn't provide early detection for failures\\n\n",
        "Constraint propagation goes beyond forward checking and repeatedly enforces constraints locally\\n\n",
        "\n",
        "Arc consistency, constraint propagation, and AC3\\n\n",
        "\n",
        "INFERENCE in CSPs:\\n\n",
        "Constraint propagation (inference)\\n\n",
        "Eliminates possible values for a variable if the value would violate local consistency\\n\n",
        "Can do inference first, or intertwine it with search\\n\n",
        "Node consistency satisfies unary constraints\\n\n",
        "Arc consistency satisfies binary constraints\\n\n",
        "\n",
        "Simplest form of consistency propagation makes each arc CONSISTENT\\n\n",
        "X->Y is consistent iff for every value of x there is some allowed y\\n\n",
        "If X loses a value, recheck neighbors of x\\n\n",
        "This can detect failures earlier than forward checking\\n\n",
        "!) To make an arc (i,j) consistent, for each value $v$ on $X_i$, if there is no label on $Y_j$ consistent with v then remove $v$ from $X_i$\\n\n",
        "If there are $d$ values in the domain, it takes $O(d^2)$ time\\n\n",
        "!) AC3 puts arcs into a queue and continuously removes inconsistent values until every arc has been satisfied\\n\n",
        "remove inconsistent values for Xi and Xj, and then add all arcs that are neighbors of Xi that arent Xj back into the queue and continue\n",
        "Worst case is $O(n^2d^3)$\\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "92689dcb-9c2c-4524-e9d3-517205bb4990"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nThere are different types of searches. Before, we focused on planning searches where the path to goal was most important thing.\n\nFor CSPs, its an identification problem where you assign things to variables. CSPs are specialized for identification problems.\n\n!) represent the constraints that solutions must satisfy in a declarative language.\n\nYou then use generalm purpose search algorithms, without transition functions or heuristics.\n\nJust need to specify the problem in formal declarative language, and then general-purpose algorithm does everything else.\n\n\nA CSP consists of: variables to be assigned to, domain of possible values, set of constraints\n\nA consistent assignment does not violate constraints\n\n\nA complete assignment is where every variable is assigned a value.\n\n!) A solution to a CSP is a complete, consistent assignment.\n\nAs long as you have the formal specification of the CSP, you can solve it with a general purpose algorithm\n\n\nBenefits of CSP:\n\ngeneric goal and clean specification\n\nCSPs know which variables violate constraints\n\nCSPs will prune off branches which violate constraints\n\n\nConstraint graph:\n\nnodes are variables\n\narcs are binary constraints\n\n\nVarieties of CSPs:\n\nDiscrete variables: n variables and domain size d -> O($d^n$) assignments\n\ncontinous variables\n\n\nUnary constraints involve one variable, binary constraints involve 2 variables\n\n\nCSPs have initial state, successor function, goal test, path cost\n\nSolution is always found at depth n for n variables --> use DFS\n\n!) backtracking search is the basic uninformed algorithm for CSPs\n\nTo improve backtracking efficiency, we can apply heuristics and stuff:\n\n1. One example of a heuristic is you want to assign the variable with the most constraints/the one with the least amount of legal values\n\n2. If there are ties, then you can assign the least constrained variables\n\n3. Or another heuristic is the least constraining value\n\n4. forward checking -- keep track of remaining legal values for unassigned variables, end search when any unassigned variable has no values left\n\n\nTowards constraint propogation\n\nForward checking propagates information assigned to unassigned variables but doesn't provide early detection for failures\n\nConstraint propagation goes beyond forward checking and repeatedly enforces constraints locally\n\n\nArc consistency, constraint propagation, and AC3\n\n\nINFERENCE in CSPs:\n\nConstraint propagation (inference)\n\nEliminates possible values for a variable if the value would violate local consistency\n\nCan do inference first, or intertwine it with search\n\nNode consistency satisfies unary constraints\n\nArc consistency satisfies binary constraints\n\n\nSimplest form of consistency propagation makes each arc CONSISTENT\n\nX->Y is consistent iff for every value of x there is some allowed y\n\nIf X loses a value, recheck neighbors of x\n\nThis can detect failures earlier than forward checking\n\n!) To make an arc (i,j) consistent, for each value $v$ on $X_i$, if there is no label on $Y_j$ consistent with v then remove $v$ from $X_i$\n\nIf there are $d$ values in the domain, it takes $O(d^2)$ time\n\n!) AC3 puts arcs into a queue and continuously removes inconsistent values until every arc has been satisfied\n\nremove inconsistent values for Xi and Xj, and then add all arcs that are neighbors of Xi that arent Xj back into the queue and continue\nWorst case is $O(n^2d^3)$\n\n\n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "KNowledge based agents use the knowledge of their surroundings. \n",
        "Knowledge based agent is an instance of logic based agent -- use process of reasoning over internal representation of knowledge to decide what action to take\n",
        "This process is called reasoning. Before, we just perform searches over states and the states are atomic. They don't contain info that an agent would need to reason\n",
        "Storing knowledge of the world and representing it. \n",
        "Knowledge base (KB): contains set of things called sentences written in a knowledge representation language, containing facts about the world.\n",
        "formal language vs natural language\n",
        "planet(hoth) vs Hoth is a planet\n",
        "far_from(hoth, sol) vs Hoth is far from the sun\n",
        "2 kinds of sentences. Axioms are a sentence that is given, Derived sentences is a new senence derived from other sentences\n",
        "Deriving new sentences from old ones is called inference\n",
        "KB contains background info about world, and knowledge based agent can add to information in the KB through observations of the world. \n",
        "KB agent can also query the KB. \n",
        "\n",
        "\n",
        "Wampa world problem is deterministic, discrete, static, single-agent. Sequential because reward doesnt come for many steps. Paritally pbservable because some parts of state are not directly perceivable. \n",
        "\n",
        "Logic\n",
        "use pieces of information in knowledge base to reason about what we do\n",
        "Logic is a feneral class of representations for knowledge-based agents. We examine propositional logic here:\n",
        "KB consists of sentences in the represetnation langauae.\n",
        "Representation language ahs a syntax that specifies sentences that are well-formed.\n",
        "A logic defines the semantics of the sentences which is their meaning\n",
        "Models are mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence.\n",
        "If a sentence alpha is true in model m, then we say m satisties alpha or \n",
        "Logical entailment. Sentence follows logically from another sentence. \n",
        "A entails B if and only if M(A) is a subset of M(B)\n",
        "\n",
        "KB can be thought of as a set of sentences. If a1 is there is no pit in [1,2] but some particular model m has a pit in [1,2] then the KB is false for that model\n",
        "Model checking is the process of enumerating all possible models compatible with KB\n",
        "\n",
        "logical inference: entailment can be applied to derive conclusions. What we want to do is add to knowledge based by inference\n",
        "alpha is derived from KB by i <- when an inference algorithm i allows us to conclude that a is true \n",
        "\n",
        "A knowledge base is what you know about the game in general, and then a model is the specifics of a particular instance of that game.\n",
        "\n",
        "Propositional Logic\n",
        "Atomic sentences are represented witha. single propositional symbol\n",
        "Symbol stands for a statement that can be true or false/\n",
        "W_{1,3} is a propositional symbol we can use to say there is a wampa at [1,3]\n",
        "Complex sentences are constructed from simpler ones using parentheses and logical connectives. \n",
        "~ not, ^ and, V or, => implies, <=> iff\n",
        "\n",
        "distributivity of and over or:\n",
        "((a and b) or c) = ((a and b) or (a and c))\n",
        "distributivity of or over and:\n",
        "((a or b) and c) = ((a or b) and (a or c))\n",
        "\n",
        "Inference rules\n",
        "If A => B, and I'm given A, i can infer B\n",
        "If A <=> b, I can infer A => B and B => A\n",
        "same way other way around\n",
        "If I am given A and B, I can infer A. i can also infer B\n",
        "\n",
        "Search for a proof\n",
        "use search algs to find sequence of steps to consitute a proof\n",
        "initial state: initial knowledge base\n",
        "actions: inference rules that you make to sentences\n",
        "result: add sentence to bottom half of KB\n",
        "goal state: the statement we are trying to prove\n",
        "\n",
        "Resolution is an inference rule which yields a complete inference algorithm when coupled with any complete search alg\n",
        "If l_i and m are complimentary literals, which means that one is the negation of another, then we can eliminate them via unit resolution\n",
        "resolution rule only applies to clauses (== disjunctions of literals)\n",
        "KB has full set of logical sentences\n",
        "every sentence is equivalent to a conjunction of clauses\n",
        "\n",
        "CNF conjunctive normal form\n",
        "Conjunction of clauses which are disjunction of literals, (a big and or a bunch of ors)\n",
        "CNF is NOT just 2 literals in each clause\n",
        "\n",
        "Resolution algorithm:\n",
        "To show KB entails a, we can show that KB and not a is unsatisfiable\n",
        "Convert KB and not a to CNF\n",
        "then apply resolution rule to resulting clauses\n",
        "resolve pairs that contain complimentary literals \n",
        "if new clause isnt present already, add it to set\n",
        "continue process until: 1. no new clauses to be added, in which case KB does not entail a, OR 2. empty clause added, in which case KB entails a\n",
        "\n",
        "Some KBs have stricter limitations so that you can use more efficient algs\n",
        "inference with horn clauses can be done through forward and backward chaining algs\n",
        "can be done in linear time\n",
        "\n",
        "forward chaining is data driven reasoning. agent starts with known data and adds premises as new percepts come in. Then incrementally apply alg to derive new conclusions\n",
        "Backward chaining works backwards from a query. if query known to be true, no work needed. Otherwise algo finds implications in KB whos conclusions is the query. If all premises of one of those can be true, then query is true\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"model\" : \"representation of the world where each sentence has a truth value\",\n",
        "\"sound\" : \"inference algorithm should only derive entailed sentences\",\n",
        "\"complete\" : \"an ingerence algorithm is complete if it can derive all sentences that are entailed\",\n",
        "\"monotonicity\" : \"You can build upon a knowledge base without invalidating what came before, implies soundness\",\n",
        "\"definite clause\": \"disjunction of literals where exactly one is positive\",\n",
        "\"horn clause\": \"disjunction of literals where at least one is positive, closed under resolution\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "081f6a37-64a5-41ae-8826-120029f9c12b"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n \nKNowledge based agents use the knowledge of their surroundings. \nKnowledge based agent is an instance of logic based agent -- use process of reasoning over internal representation of knowledge to decide what action to take\nThis process is called reasoning. Before, we just perform searches over states and the states are atomic. They don't contain info that an agent would need to reason\nStoring knowledge of the world and representing it. \nKnowledge base (KB): contains set of things called sentences written in a knowledge representation language, containing facts about the world.\nformal language vs natural language\nplanet(hoth) vs Hoth is a planet\nfar_from(hoth, sol) vs Hoth is far from the sun\n2 kinds of sentences. Axioms are a sentence that is given, Derived sentences is a new senence derived from other sentences\nDeriving new sentences from old ones is called inference\nKB contains background info about world, and knowledge based agent can add to information in the KB through observations of the world. \nKB agent can also query the KB. \n\n\nWampa world problem is deterministic, discrete, static, single-agent. Sequential because reward doesnt come for many steps. Paritally pbservable because some parts of state are not directly perceivable. \n\nLogic\nuse pieces of information in knowledge base to reason about what we do\nLogic is a feneral class of representations for knowledge-based agents. We examine propositional logic here:\nKB consists of sentences in the represetnation langauae.\nRepresentation language ahs a syntax that specifies sentences that are well-formed.\nA logic defines the semantics of the sentences which is their meaning\nModels are mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence.\nIf a sentence alpha is true in model m, then we say m satisties alpha or \nLogical entailment. Sentence follows logically from another sentence. \nA entails B if and only if M(A) is a subset of M(B)\n\nKB can be thought of as a set of sentences. If a1 is there is no pit in [1,2] but some particular model m has a pit in [1,2] then the KB is false for that model\nModel checking is the process of enumerating all possible models compatible with KB\n\nlogical inference: entailment can be applied to derive conclusions. What we want to do is add to knowledge based by inference\nalpha is derived from KB by i <- when an inference algorithm i allows us to conclude that a is true \n\nA knowledge base is what you know about the game in general, and then a model is the specifics of a particular instance of that game.\n\nPropositional Logic\nAtomic sentences are represented witha. single propositional symbol\nSymbol stands for a statement that can be true or false/\nW_{1,3} is a propositional symbol we can use to say there is a wampa at [1,3]\nComplex sentences are constructed from simpler ones using parentheses and logical connectives. \n~ not, ^ and, V or, => implies, <=> iff\n\ndistributivity of and over or:\n((a and b) or c) = ((a and b) or (a and c))\ndistributivity of or over and:\n((a or b) and c) = ((a or b) and (a or c))\n\nInference rules\nIf A => B, and I'm given A, i can infer B\nIf A <=> b, I can infer A => B and B => A\nsame way other way around\nIf I am given A and B, I can infer A. i can also infer B\n\nSearch for a proof\nuse search algs to find sequence of steps to consitute a proof\ninitial state: initial knowledge base\nactions: inference rules that you make to sentences\nresult: add sentence to bottom half of KB\ngoal state: the statement we are trying to prove\n\nResolution is an inference rule which yields a complete inference algorithm when coupled with any complete search alg\nIf l_i and m are complimentary literals, which means that one is the negation of another, then we can eliminate them via unit resolution\nresolution rule only applies to clauses (== disjunctions of literals)\nKB has full set of logical sentences\nevery sentence is equivalent to a conjunction of clauses\n\nCNF conjunctive normal form\nConjunction of clauses which are disjunction of literals, (a big and or a bunch of ors)\nCNF is NOT just 2 literals in each clause\n\nResolution algorithm:\nTo show KB entails a, we can show that KB and not a is unsatisfiable\nConvert KB and not a to CNF\nthen apply resolution rule to resulting clauses\nresolve pairs that contain complimentary literals \nif new clause isnt present already, add it to set\ncontinue process until: 1. no new clauses to be added, in which case KB does not entail a, OR 2. empty clause added, in which case KB entails a\n\nSome KBs have stricter limitations so that you can use more efficient algs\ninference with horn clauses can be done through forward and backward chaining algs\ncan be done in linear time\n\nforward chaining is data driven reasoning. agent starts with known data and adds premises as new percepts come in. Then incrementally apply alg to derive new conclusions\nBackward chaining works backwards from a query. if query known to be true, no work needed. Otherwise algo finds implications in KB whos conclusions is the query. If all premises of one of those can be true, then query is true\n\n \n\n## Module 7 Definitions\n* **Model** - representation of the world where each sentence has a truth value\n* **Sound** - inference algorithm should only derive entailed sentences\n* **Complete** - an ingerence algorithm is complete if it can derive all sentences that are entailed\n* **Monotonicity** - You can build upon a knowledge base without invalidating what came before, implies soundness\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at least one is positive, closed under resolution\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": "11c3d181-993d-46ca-b525-3312825db0a3"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Some ppl define AI in terms of human performance, others have formal defition of rationality, doing the right thing. Human vs. rational, thought vs. behavior.\nDiff types of ppl want machines to either be optimal or think exactly like humans\nTuring test-can a machine think like a human?\ntotal turing test involves interaction with humans in the real world\nneed to know how humans think for cognitive modeling approach -- introspection, psychology, cognitive science\nThinking rationally\nan agent is something that acts\nrational agent acts to achieve the best outcome\nlimited rationality when not enough time\n \n\n## AIMA Chapter 27.1 The Limits of AI\n \nweak AI, machines act like they are thinking\nstrong AI machines are actually consciously thinking\nThere are limits to what AI and machines can do overall\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room argument is that even if you can find patterns and reproduce chinese symbols based on english, you don't actually understand chinese\nbiological naturalism says that understanding and high level features come from neurons. \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n simple reflex agents select actions based on current percepts and ignore other history. \nproblem-solving agent must plan ahead. computational process that it takes is called a search\nGoal based agents act to try to get to a goal, and utility based agents act to try to maximize happiness\n \n\n## Module 1 Lecture Notes\n \n  Agents include humans, robots, softbots, thermostats,\n  design performance meaures in terms of what you want to be achieved, not how you think agent should behave\n  rational agents try to maximize their performance measures\n  maximize the EXPECTED VALUE of their performance since they dont know what it will be\n  PEAS for task environment\n  P = performance measure\n  E = environment\n  A = actuators\n  S = sensors\n  Goal of a rational agent designer is to construct agent function that maximizes expected value of performance measure (abstract)\n  Then we want to design an agent program that implements this agent function (concrete implementation)\n\n  fully observable v. partially observable\n  deterministic v. nondeterministic v. stochastic\n  episodic v. sequential\n  static v. dynamic\n\n  hardest are partially observable, stochastic, continuous, multi agent\n\n  \n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts to achieve the best outcome\n* **Performance measure** - evaluating success of agents behavior based on what it could have done\n* **Task environment** - environment/challenge where agent is supposed to solve something\n* **Limited rationality** - acting rationally when there isnt enough time to do all the computations\n* **Agent function** - function which maps a set of percept vectors p to action a from the set A\n* **Natural language processing** - ability for computer to communicate in a human language\n* **Knowledge representation** - ability for computer to store what it knows or hears\n* **Automated reasoning** - ability for computer to answer questions and draw new conclusions\n* **Machine learning** - ability for computer to adapt to new circumstances and detect patterns\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nall data treated as objects\nstrong typing\ndynamic typing\nprefixing strings with r means raw, no escape characters\nstrings are immutable, lists are mutable\nuse y = x[:] to get a shallow copy of mutable stuff\nsequence types - tuples, strings, lists\ncan mix and match types within a sequence\ntuples are immutable and hashable\nstrings are immutable and hashable\nlists are mutable and not hashable\n.index() gets first occurrence in a list\n.sort() and .reverse()\n.upper() is all upper for a string, .capitalize() is just first letter\n\ndictionaries are mapping -- create, add, update\n\nfunctions -- no function overloading like in java (cant have same name)\nbut operator overloading is possible with specific function names\nyou have *args and *kwargs, you can put them together too\n\nfunctions are first class objects -- dynamically created, destroyed, passed to a function, returned as a value\n\nto define a subclass put the name of the superclass in parentheses after subclasses name -- class AI_student(Student):\n\nmagic methods are init, len, copy, cmp, add, neg, etc\n\nlist comprehension replaces for loops -- [expression for name in list]\ncan add an if statement for filtered list comprehension\ndictionary, set comprehension occurs in a similar way\n\niterator objects have next()\niterators use memory efficiently\n\ngenerators use yield\n\n\n\n## Module 2 Definitions\n* **Mutability** - can be modified after creation\n* **Defaultdict** - automatically initializes nonexistent dictionary values\n* ***args** - accept a variable number of non keyword args\n* ***kwargs** - accept a variable number of keyword args\n* **Magic method** - user defined classes can have regular type operations like + - < > etc\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n  reflex agents only focus on current precept \n\n  problem solving agents need to consider a sequence of actions from start to goal state \n\n  this sequence is called a solution \n\n\n  If environment is fully observable, deterministic, known, then the solution is just a sequence of actions \n\n  But if its nondeterministic or partially observable, it depends, and could involve branching \n\n\n  Need to formulate a goal, formulate a search problem, and then find a solution \n\n\n  FORMAL DEFINITION OF SEARCH PROBLEMS \n\n  1. states\n\n  2. initial state\n\n  3. A set of possible actions\n\n  4. A transition model and successors\n\n  5. path cost (performance measure) must be additive\n\n  6. goal test (can be implicit)\n\n\n  Formulating a search problem is an art:\n  For the initial state, goal state, and intermediate states, need to decide which properties matter and how to represent them\n\n  For the operator set, need to decide which actions are possible and how to represent them\n\n  Decide which action is next\n\n\n  !) Formulation affects combinatorics of search space and thus how much time search problem will take\n\n\n  Selecting a state space is hard bc real world is complex, need to use abstractions for states and actions\n\n\n  BASIC SEARCH ALGORITHMS\n\n\n  Tree search\n\n  In tree search, you get all paths from the initial state and search through explicit tree generation\n\n  initialize frontier to the initial state, and just extract from frontier and keep expanding and adding resulting nodes to frontier until you get to a solution\n\n  !) But the issue here is that with repeated states you can get an exponential time problem from a linear one\n  The solution is... \n\n\n\n  Graph Search\n\n  One difference with this and tree search is you just check which nodes you've seen before and you expand them only if you haven't seen them\n\n\n  Uninformed search strategies\n\n  in uninformed search, all nodes that are not the goal look equally good\n \n  uses only info in problem definition\n\n\n  GRAPH SEARCH ALGOS\n\n\n  BFS\n\n  expand the shallowest node in the frontier first\n\n  frontier is FIFO\n\n  Complete if branching factor is finite\n\n  Optimal if every step has the same cost (not optimal in general)\n\n  Time complexity is $O(b^d)$\n\n  Space complexity is $O(b^d)$ because it keeps all nodes in memory\n\n  exponential time is not good\n\n\n  DFS\n\n  expand the DEEPEST unexpanded node\n\n  frontier is LIFO (stack)\n\n  NOT complete (if you have infinite length paths it will keep going)\n\n  NOT optimal\n \n  Time is $O(b^m)$\n\n  Space is $O(bm)$\n\n\n  BFS vs DFS\n\n  Use DFS if *space is restricted*\n\n  Use DFS if there are many possible solutions with long paths and wrong solutions end quickly\n\n  Use DFS if the search can be fine tuned quickly\n \n  Use BFS if there are *possible infinite paths*\n\n  Use BFS if some solutions have short paths\n\n  Use BFS if you can quickly discard unlikely paths\n\n\n  BFS is complete, optimal, BUT uses O($b^d$) space\n\n  DFS is not complete unless m is bounded, not optimal, uses O($b^m$) time, BUT only uses O($bm$) space.\n\n\n  How do you get the best of both?\n\n\n  Depth-limited search: a building block\n\n  You put a depth limit $l$ so that you have no infinite path problem\n\n  If $l = d$, then its optimal\n\n  But if $l > d$ then not optimal, but if $l < d$ then incomplete\n\n  Time complexity is $O(b^l)$ and space complexity is $O(bl)$\n\n\n  Iterative deepening search\n\n  Use depth-limited search as a subroutine and keep increasing $l$ by 1 until you get it\n\n  This is complete and optimal\n\n  Time: $O(b^d)$\n\n  Space: $O(bd)$\n\n  No infinite paths so its complete\n\n  Optimal if the step cost is 1\n\n\n \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Solution** - a path to the a state that satisfies the goal test\n* **State space** - set of all states that you can get to from the source via ANY sequence of actions\n* **Path** - to get from state a to state b, what actions you took to get there\n* **Search tree** - a way to represent possible paths explored\n* **Frontier** - states that are available for expansion/to continue searching on\n* **Optimal solution** - if no other solution can be achieved with lower path cost, the solution is optimal\n* **Strategy** - the strategy in a search problem is the order in which we expand the tree\n* **Completeness** - a complete search algorithm always finds the solution\n* **Optimal** - an optimal search algorithm finds the lowest cost solution first\n* **Time complexity** - worst case number of nodes generated in the search\n* **Space complexity** - the worst case number of nodes that are being stored in memory at any given time\n* **B (branching factor)** - maximum branching factor of a tree is the max number of children that a node can have\n* **D** - lowest possible depth of a goal node (lowest meaning smallest magnitude)\n* **M** - maximum length of paths that exist\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n\nInformed search is quicker than uninformed\n\n\nUNIFORM COST SEARCH\n\nthis is a confusing name, it's not uniform edge weights. You DO take into account edge weights\n\ng(n) is the path cost function -- cost to reach a node from the source\n\npath cost function is the sum of all of the weigts of the edges taken to get to it\n\nIt is an expansion of BFS -- expand the node with LOWEST path cost\n\nFrontier is a priority queue ordered by g(n)\n\nTest if a node is in goal state when its selected for expansion, not when its added to frontier like in BFS\n\nUpdate the node on frontier if a better path to the same state is found\n\nEnqueues a node BEFORE checking whether it is a goal node\n\nUCS lets us prioritize which paths to explore. Favors lower cost path resulting in cost contours.\n\n\n\n\nA BETTER IDEA...\n\nNode expansion based on an estimate or heuristic\n\nWant an evaluation function and sort the frontier queue by the evaluation function\n\nStraight line distance is a good heuristic\n\n\nGREEDY BEST FIRST SEARCH\n\npriority queue with heuristic as the priority\n\nh(n) = f(n)\n\nSame thing as UCS but with h(n) instead of g(n)\n\nif there are obstacles, this will NOT give you an optimal path\n\nIt can also get stuck in loops\n\n\nA* search\n\nthis prunes out expensive paths and expands promising ones\n\nBest known form of best-first search\n\nf(n) = g(n) + h(n)\n\nKey concept is admissible heuristics, admissible means they never overestimate the cost to reach goal\n\nTheorem is that if h(n) is admissible, then A* using tree search is optimal\n\nadmissibility is the idea that when something looks promising, give it a reward\n\n\nA good heuristic function can reduce the search process\n\nA good way of coming up with a heuristic is to have the same problem but with a couple restrictions removed/relaxed\n\n!) the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\nDominant admissible metrics are better beacuse they are still optimistic but also more accurate\n\nh*(n) is the best heuristic and 0 is the worst heuristic\n\n\nAdmissible heuristics slow down bad plans but don't outweight true costs -- the true best plan will always be expanded\n\nInadmissible heuristics could make the true best path not look good and push it back on the frontier and they won't get expanded\n\n\nA* expands mainly towards the goal, but does hedge its bets to ensure optimality\n\n\n\n \n\n## Module 4 Definitions\n* **Uniform-cost search** - search algorithm to go over a WEIGHTED tree or graph\n* **Heuristic function** - given a state, it returns an estimate of the cost to the goal from that state\n* **Admissible** - never overstimate the cost to goal, optimistic\n* **Dominance** - when one heuristic is always larger than another for all n, the first one dominates the second\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nNow we need to reason about opponent movements\n\nGames are a search problem of a certain kind\n\nThe simplest GAME environment for rational agents are multiagent, static (no change while agent deliberates), discrete/finite, fully observable, and strategic (the next state is determined by current state and action executed by agent and actions of one other agent)\n\nProperties of game -- players alternate, zero-sum, set of legal moves, well-defined outcomes\n\nMore complicated games are stochastic, not fully observable, real time, etc\n\n\nFormalizing game setup\n\n1. 2 players MAX and MIN\n\n2. MAX and MIN take turns until game over\n\n3. Winner gets an award, loser gets a penalty\n\n\nGames as search\n\ninitial state, successor function, terminal test (is game finished?), utility function (gives numerical value of terminal states)\n\nMAX uses search tree to determine next move\n\nGeneral scheme of search\n\n1. consider all legal successors to the current state\n\n2. evaluate each successor board position\n\n3. pick move which leads to best board position\n\n4. after opponent moves, repeat\n\n\nIssues with this such as representing board, representing next legal boards, evaluating positions, and looking ahead\n\nGame trees -- represent the game problem space by a tree where nodes are board positions and edges are legal moves\n\nWe need to make our own evaluation function that evaluates how good a board position is.\n\nIf f(n) > 0 MAX is winning at that particular position\n\n\n\nMINIMAX\n\nMain idea is don't play hope chess, make the best move for MAX assuming that MIN will make best move for MIN\n\nUntil game is over, do the following:\n\nStart with the current position as a MAX node.\n\nExpand the game tree a fixed number of ply.\n\nApply the evaluation function to the leaf positions.\n\nCalculate back-up values bottom-up.\n\nPick the move assigned to MAX at the root\n\nWait for MIN to respond\n\n\n\nALPHA BETA PRUNING\n\nDuring minimax keep track of 2 values:\n\nalpha--MAX's current lower bound on MAX's outcome. MAX will never allow a move that could lead to a worse score than alpha\n\nbeta--MIN's current upper bound on MIN's outcome. MIN will never allow a move that could lead to a better score for MAX than beta\n\nThus, the pruning happens when, for a max node, if a value >= beta is backed up, because min will never select that max node. It also happens for a MIN node if a value <= alpha is backed up, because MAX will never pick that min node.\n\n\nExpectimax search: compute the average score under optimal play\n\nChance nodes are like min nodes but their outcome is uncertain, so we need to calculate expected utilities\n\nEXP agent returns expected values\n\nSome people think that you can \"learn\" probabilities, through Bayesian stuff, called informed probabilities\n\n\n\n\n\n\n \n\n## Module 5 Definitions\n* **Random variable** - represents an event whose outcome is unknown\n* **Probability distribution** - assignment of weights to outcomes\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nThere are different types of searches. Before, we focused on planning searches where the path to goal was most important thing.\n\nFor CSPs, its an identification problem where you assign things to variables. CSPs are specialized for identification problems.\n\n!) represent the constraints that solutions must satisfy in a declarative language.\n\nYou then use generalm purpose search algorithms, without transition functions or heuristics.\n\nJust need to specify the problem in formal declarative language, and then general-purpose algorithm does everything else.\n\n\nA CSP consists of: variables to be assigned to, domain of possible values, set of constraints\n\nA consistent assignment does not violate constraints\n\n\nA complete assignment is where every variable is assigned a value.\n\n!) A solution to a CSP is a complete, consistent assignment.\n\nAs long as you have the formal specification of the CSP, you can solve it with a general purpose algorithm\n\n\nBenefits of CSP:\n\ngeneric goal and clean specification\n\nCSPs know which variables violate constraints\n\nCSPs will prune off branches which violate constraints\n\n\nConstraint graph:\n\nnodes are variables\n\narcs are binary constraints\n\n\nVarieties of CSPs:\n\nDiscrete variables: n variables and domain size d -> O($d^n$) assignments\n\ncontinous variables\n\n\nUnary constraints involve one variable, binary constraints involve 2 variables\n\n\nCSPs have initial state, successor function, goal test, path cost\n\nSolution is always found at depth n for n variables --> use DFS\n\n!) backtracking search is the basic uninformed algorithm for CSPs\n\nTo improve backtracking efficiency, we can apply heuristics and stuff:\n\n1. One example of a heuristic is you want to assign the variable with the most constraints/the one with the least amount of legal values\n\n2. If there are ties, then you can assign the least constrained variables\n\n3. Or another heuristic is the least constraining value\n\n4. forward checking -- keep track of remaining legal values for unassigned variables, end search when any unassigned variable has no values left\n\n\nTowards constraint propogation\n\nForward checking propagates information assigned to unassigned variables but doesn't provide early detection for failures\n\nConstraint propagation goes beyond forward checking and repeatedly enforces constraints locally\n\n\nArc consistency, constraint propagation, and AC3\n\n\nINFERENCE in CSPs:\n\nConstraint propagation (inference)\n\nEliminates possible values for a variable if the value would violate local consistency\n\nCan do inference first, or intertwine it with search\n\nNode consistency satisfies unary constraints\n\nArc consistency satisfies binary constraints\n\n\nSimplest form of consistency propagation makes each arc CONSISTENT\n\nX->Y is consistent iff for every value of x there is some allowed y\n\nIf X loses a value, recheck neighbors of x\n\nThis can detect failures earlier than forward checking\n\n!) To make an arc (i,j) consistent, for each value $v$ on $X_i$, if there is no label on $Y_j$ consistent with v then remove $v$ from $X_i$\n\nIf there are $d$ values in the domain, it takes $O(d^2)$ time\n\n!) AC3 puts arcs into a queue and continuously removes inconsistent values until every arc has been satisfied\n\nremove inconsistent values for Xi and Xj, and then add all arcs that are neighbors of Xi that arent Xj back into the queue and continue\nWorst case is $O(n^2d^3)$\n\n\n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n \nKNowledge based agents use the knowledge of their surroundings. \nKnowledge based agent is an instance of logic based agent -- use process of reasoning over internal representation of knowledge to decide what action to take\nThis process is called reasoning. Before, we just perform searches over states and the states are atomic. They don't contain info that an agent would need to reason\nStoring knowledge of the world and representing it. \nKnowledge base (KB): contains set of things called sentences written in a knowledge representation language, containing facts about the world.\nformal language vs natural language\nplanet(hoth) vs Hoth is a planet\nfar_from(hoth, sol) vs Hoth is far from the sun\n2 kinds of sentences. Axioms are a sentence that is given, Derived sentences is a new senence derived from other sentences\nDeriving new sentences from old ones is called inference\nKB contains background info about world, and knowledge based agent can add to information in the KB through observations of the world. \nKB agent can also query the KB. \n\n\nWampa world problem is deterministic, discrete, static, single-agent. Sequential because reward doesnt come for many steps. Paritally pbservable because some parts of state are not directly perceivable. \n\nLogic\nuse pieces of information in knowledge base to reason about what we do\nLogic is a feneral class of representations for knowledge-based agents. We examine propositional logic here:\nKB consists of sentences in the represetnation langauae.\nRepresentation language ahs a syntax that specifies sentences that are well-formed.\nA logic defines the semantics of the sentences which is their meaning\nModels are mathematical abstractions that have a fixed set of truth values which are {true,false} for each sentence.\nIf a sentence alpha is true in model m, then we say m satisties alpha or \nLogical entailment. Sentence follows logically from another sentence. \nA entails B if and only if M(A) is a subset of M(B)\n\nKB can be thought of as a set of sentences. If a1 is there is no pit in [1,2] but some particular model m has a pit in [1,2] then the KB is false for that model\nModel checking is the process of enumerating all possible models compatible with KB\n\nlogical inference: entailment can be applied to derive conclusions. What we want to do is add to knowledge based by inference\nalpha is derived from KB by i <- when an inference algorithm i allows us to conclude that a is true \n\nA knowledge base is what you know about the game in general, and then a model is the specifics of a particular instance of that game.\n\nPropositional Logic\nAtomic sentences are represented witha. single propositional symbol\nSymbol stands for a statement that can be true or false/\nW_{1,3} is a propositional symbol we can use to say there is a wampa at [1,3]\nComplex sentences are constructed from simpler ones using parentheses and logical connectives. \n~ not, ^ and, V or, => implies, <=> iff\n\ndistributivity of and over or:\n((a and b) or c) = ((a and b) or (a and c))\ndistributivity of or over and:\n((a or b) and c) = ((a or b) and (a or c))\n\nInference rules\nIf A => B, and I'm given A, i can infer B\nIf A <=> b, I can infer A => B and B => A\nsame way other way around\nIf I am given A and B, I can infer A. i can also infer B\n\nSearch for a proof\nuse search algs to find sequence of steps to consitute a proof\ninitial state: initial knowledge base\nactions: inference rules that you make to sentences\nresult: add sentence to bottom half of KB\ngoal state: the statement we are trying to prove\n\nResolution is an inference rule which yields a complete inference algorithm when coupled with any complete search alg\nIf l_i and m are complimentary literals, which means that one is the negation of another, then we can eliminate them via unit resolution\nresolution rule only applies to clauses (== disjunctions of literals)\nKB has full set of logical sentences\nevery sentence is equivalent to a conjunction of clauses\n\nCNF conjunctive normal form\nConjunction of clauses which are disjunction of literals, (a big and or a bunch of ors)\nCNF is NOT just 2 literals in each clause\n\nResolution algorithm:\nTo show KB entails a, we can show that KB and not a is unsatisfiable\nConvert KB and not a to CNF\nthen apply resolution rule to resulting clauses\nresolve pairs that contain complimentary literals \nif new clause isnt present already, add it to set\ncontinue process until: 1. no new clauses to be added, in which case KB does not entail a, OR 2. empty clause added, in which case KB entails a\n\nSome KBs have stricter limitations so that you can use more efficient algs\ninference with horn clauses can be done through forward and backward chaining algs\ncan be done in linear time\n\nforward chaining is data driven reasoning. agent starts with known data and adds premises as new percepts come in. Then incrementally apply alg to derive new conclusions\nBackward chaining works backwards from a query. if query known to be true, no work needed. Otherwise algo finds implications in KB whos conclusions is the query. If all premises of one of those can be true, then query is true\n\n \n\n## Module 7 Definitions\n* **Model** - representation of the world where each sentence has a truth value\n* **Sound** - inference algorithm should only derive entailed sentences\n* **Complete** - an ingerence algorithm is complete if it can derive all sentences that are entailed\n* **Monotonicity** - You can build upon a knowledge base without invalidating what came before, implies soundness\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at least one is positive, closed under resolution\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}