{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS 421 Notes Midterm 1",
      "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": "c6b219ed-576b-4d39-db31-7d04f022cfaa"
      },
      "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": 3,
      "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": "b6f03e41-ce0e-4953-e33f-e820c7de2619"
      },
      "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": 4,
      "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 = \"\"\" 3 things that a computer needs\\\\\n",
        "\n",
        "-natural language processing to communicate successfully in human language\\\\\n",
        "\n",
        "-knowledge representation to store information\\\\\n",
        "\n",
        "-autmated reasoning to answer questions and draw new conclusions\\\\\n",
        "\n",
        "A total Turing test requires interactions with people in the real world in order to pass this test\\\\\n",
        "\n",
        "A rational agent is one that acts so as to achieve the best outcome or the best expected outcome.\\\\\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 = \"\"\" Weak AI - machines could act as if they were intelligent\\\\\n",
        "\n",
        "Strong AI - machines that act as if they were intelligent actually are\\\\\n",
        "\n",
        "Qualification problem - the difficulty to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\\\\\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" The chinese room argument is a though experiment where someone, who understands only English,\\\\\n",
        "\n",
        "is inside a room that contains a rule book with which he uses to translate chinese to english.\\\\\n",
        "\n",
        "Computers do this and it seems like they're actually intelligent.\\\\\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Four things that make rationality a thing:\\\\\n",
        "\n",
        "- The performance measure that defines the criterion of success\\\\\n",
        "\n",
        "- The Agent's pior knowledge of the environment\\\\\n",
        "\n",
        "- The actions that the agent can perform\\\\\n",
        "\n",
        "-The agent's percept sequence to date\\\\\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Agents are anything that is able to perceive it's environment through sensors and then act on it through actuators. \\\n",
        "These agents act within task environments. In order to define a task environment you need to define a performance measure, environment, actuators, \\\n",
        "and sensors. There are many things that a task environment can be (see definitions) the hardest type of environment would be a continuous, partially \\\n",
        "observable, stochastic, and multiagent environment. \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"Rational Behavior\" : \"doing the right thing\",\n",
        "\"Rational Agent\": \"an agent that perceives the environment and behaves rationally\",\n",
        "\"Performance Measure\":\"an objective criterion for success of an agent's behavior\",\n",
        "\"Fully Observable\": \"a task agent's sensors see all aspects of the environment that are relevant to agent's choice of action\",\n",
        "\"Deterministic\": \"we know the state after an action is made\",\n",
        "\"Nondeterministic\": \"outcome after action is unknown. Rolling dice\",\n",
        "\"Stochastic\": \"Probablistic. If we can quantify the likelihood of each possible outcome\",\n",
        "\"Episodic\": \"an environment in whcih the agent needs to process self contained episodes\",\n",
        "\"Sequential\": \"current decision makes impact on future ones\",\n",
        "\"Static\": \"take time to make move with no chance of change\",\n",
        "\"Dynamic\": \"while agent thinks, environment can change\",\n",
        "\"Discrete\": \"environment can be represented using a discrete number of distinct states and a number of actions that can be taken\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5da73ed6-cadd-4322-e485-610118f93667"
      },
      "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": 6,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n 3 things that a computer needs-natural language processing to communicate successfully in human language\\\n\n-knowledge representation to store information\\\n\n-autmated reasoning to answer questions and draw new conclusions\\\n\nA total Turing test requires interactions with people in the real world in order to pass this test\\\n\nA rational agent is one that acts so as to achieve the best outcome or the best expected outcome.\\\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI - machines could act as if they were intelligentStrong AI - machines that act as if they were intelligent actually are\\\n\nQualification problem - the difficulty to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\\\n\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n The chinese room argument is a though experiment where someone, who understands only English,is inside a room that contains a rule book with which he uses to translate chinese to english.\\\n\nComputers do this and it seems like they're actually intelligent.\\\n \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Four things that make rationality a thing:- The performance measure that defines the criterion of success\\\n\n- The Agent's pior knowledge of the environment\\\n\n- The actions that the agent can perform\\\n\n-The agent's percept sequence to date\\\n \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Agents are anything that is able to perceive it's environment through sensors and then act on it through actuators. These agents act within task environments. In order to define a task environment you need to define a performance measure, environment, actuators, and sensors. There are many things that a task environment can be (see definitions) the hardest type of environment would be a continuous, partially observable, stochastic, and multiagent environment. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Rational behavior** - doing the right thing\n* **Rational agent** - an agent that perceives the environment and behaves rationally\n* **Performance measure** - an objective criterion for success of an agent's behavior\n* **Fully observable** - a task agent's sensors see all aspects of the environment that are relevant to agent's choice of action\n* **Deterministic** - we know the state after an action is made\n* **Nondeterministic** - outcome after action is unknown. Rolling dice\n* **Stochastic** - Probablistic. If we can quantify the likelihood of each possible outcome\n* **Episodic** - an environment in whcih the agent needs to process self contained episodes\n* **Sequential** - current decision makes impact on future ones\n* **Static** - take time to make move with no chance of change\n* **Dynamic** - while agent thinks, environment can change\n* **Discrete** - environment can be represented using a discrete number of distinct states and a number of actions that can be taken\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",
        "-Programs run on major platforms without change\n",
        "Various built-in types:\n",
        "-lists, dictionaries, sets: useful for AI\n",
        "Large collection of support libraries:\n",
        "-NumPy for Matlab like programming\n",
        "-Pandas for data analysis\n",
        "-Sklearn for machine learning\n",
        "-Pytorch and TensorFlow for deep learning\n",
        " \n",
        "Objects and Types\n",
        "All data treated as objects:\n",
        "An object is deleted (by garbage collection) once unreachable.\n",
        " \n",
        "Strong Typing:\n",
        "Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
        "that type (eg. “foo” + 2)\n",
        "type(object)\n",
        "isinstance(object, type)\n",
        " \n",
        "Examples of Types:\n",
        "int, float\n",
        "str, tuple, dict, list\n",
        "bool: True, False\n",
        "None, generator, function\n",
        " \n",
        "Python has dynamic typing: Variables come into existence when first assigned.\n",
        "Strings are immutable, lists are mutable\n",
        " \n",
        "Sequence Types\n",
        "Tuple:\n",
        "-A simple immutable ordered sequence of items\n",
        "-Immutable: a tuple cannot be modified once created\n",
        "-Items can be of mixed types, including collection types\n",
        " \n",
        "Strings:\n",
        "-Immutable\n",
        "-Regular strings are Unicode and use 2-byte characters (Regular strings in\n",
        "Python 2 use 8-bit characters)\n",
        "List:\n",
        "-Mutable ordered sequence of items of mixed types\n",
        " \n",
        " \n",
        "Python allows multiple return values.\n",
        "Not all arguments need to be called for the function to be called.\n",
        " \n",
        "Functions are first class\n",
        "First class object:\n",
        "-An entity that can be dynamically created, destroyed, passed to a function,\n",
        "returned as a value, and have all the rights as other variables in the\n",
        "programming language have\n",
        "Functions are “first-class citizens”:\n",
        "-Pass functions as arguments to other functions\n",
        "-Return functions as the values from other functions\n",
        "-Assign functions to variables or store them in data structures\n",
        "Higher order functions: take functions as input\n",
        " \n",
        "Subclasses:\n",
        "-no extend keyword\n",
        "-multiple inheritance is allowed\n",
        " \n",
        "Methods that behave like built ins:\n",
        "__init__: The constructor for the class.\n",
        "__len__ : Define how len( obj ) works.\n",
        "__copy__: Define how to copy a class.\n",
        "__cmp__ : Define how == works for class.\n",
        "__add__ : Define how + works for class\n",
        "__neg__ : Define how unary negation works for class\n",
        " \n",
        "Iterator Objects:\n",
        "Iterable objects can be used in a for loop because they have an __iter__ magic\n",
        "method, which converts them to iterator objects\n",
        "- no hasNext in python\n",
        " \n",
        "Generators:\n",
        "-Generators are iterators (with __next()__ method)\n",
        "-Creating Generators: yield\n",
        " \n",
        "YIELD: Each time we call the __next__ method of the generator, the method runs until it\n",
        "encounters a yield statement, and then it stops and returns the value that was yielded.\n",
        "Next time, it resumes where it left off\n",
        " \n",
        "Benefits of generators:\n",
        "-Less code than writing a standard iterator\n",
        "-Maintains local state automatically\n",
        "-Values are computed one at a time, as they’re needed\n",
        "-Avoids storing the entire sequence in memory\n",
        "-Good for aggregating (summing, counting) items. One pass.\n",
        "-Crucial for infinite sequences\n",
        "-Bad if you need to inspect the individual values\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 707
        },
        "outputId": "53d4366d-3644-4923-9e20-6ac9135c939d"
      },
      "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": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n-Programs run on major platforms without change\nVarious built-in types:\n-lists, dictionaries, sets: useful for AI\nLarge collection of support libraries:\n-NumPy for Matlab like programming\n-Pandas for data analysis\n-Sklearn for machine learning\n-Pytorch and TensorFlow for deep learning\n \nObjects and Types\nAll data treated as objects:\nAn object is deleted (by garbage collection) once unreachable.\n \nStrong Typing:\nEvery object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2)\ntype(object)\nisinstance(object, type)\n \nExamples of Types:\nint, float\nstr, tuple, dict, list\nbool: True, False\nNone, generator, function\n \nPython has dynamic typing: Variables come into existence when first assigned.\nStrings are immutable, lists are mutable\n \nSequence Types\nTuple:\n-A simple immutable ordered sequence of items\n-Immutable: a tuple cannot be modified once created\n-Items can be of mixed types, including collection types\n \nStrings:\n-Immutable\n-Regular strings are Unicode and use 2-byte characters (Regular strings in\nPython 2 use 8-bit characters)\nList:\n-Mutable ordered sequence of items of mixed types\n \n \nPython allows multiple return values.\nNot all arguments need to be called for the function to be called.\n \nFunctions are first class\nFirst class object:\n-An entity that can be dynamically created, destroyed, passed to a function,\nreturned as a value, and have all the rights as other variables in the\nprogramming language have\nFunctions are “first-class citizens”:\n-Pass functions as arguments to other functions\n-Return functions as the values from other functions\n-Assign functions to variables or store them in data structures\nHigher order functions: take functions as input\n \nSubclasses:\n-no extend keyword\n-multiple inheritance is allowed\n \nMethods that behave like built ins:\n__init__: The constructor for the class.\n__len__ : Define how len( obj ) works.\n__copy__: Define how to copy a class.\n__cmp__ : Define how == works for class.\n__add__ : Define how + works for class\n__neg__ : Define how unary negation works for class\n \nIterator Objects:\nIterable objects can be used in a for loop because they have an __iter__ magic\nmethod, which converts them to iterator objects\n- no hasNext in python\n \nGenerators:\n-Generators are iterators (with __next()__ method)\n-Creating Generators: yield\n \nYIELD: Each time we call the __next__ method of the generator, the method runs until it\nencounters a yield statement, and then it stops and returns the value that was yielded.\nNext time, it resumes where it left off\n \nBenefits of generators:\n-Less code than writing a standard iterator\n-Maintains local state automatically\n-Values are computed one at a time, as they’re needed\n-Avoids storing the entire sequence in memory\n-Good for aggregating (summing, counting) items. One pass.\n-Crucial for infinite sequences\n-Bad if you need to inspect the individual values\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Criterion for search problems:\\\\\n",
        "\n",
        "-A state space\\\\\n",
        "\n",
        "-Initial State\\\\\n",
        "\n",
        "-Goal States\\\\\n",
        "\n",
        "-Set of actions \\\\\n",
        "\n",
        "-Transition Model\\\\\n",
        "\n",
        "-Action Cost function\\\\\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Best First Search - greedy solution that utilizes a priority queue lowest h(n)\\\\\n",
        "\n",
        "Graph search checks to see if path is redundant\\\\\n",
        "\n",
        "Tree search does not check to see if the path is redundant\\\\\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" Bidirectional Search Searches - searches from initial state and backwards from goal state\\\\\n",
        "has frontier that is a priority queue and reached states for forward and backward search\\\\\n",
        "O(b^(d/2)) complete and optimal \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" BFS - Complete and Optimal\\\\\n",
        "\n",
        "Uniform Cost Search - Complete and Optimal\\\\\n",
        "\n",
        "DFS - Not complete and Not Optimal\\\\\n",
        "\n",
        "Depth Limited Search - Not complete and Not Optimal\\\\\n",
        "\n",
        "Iterative Deepening Search - Complete and Optimal\\\\\n",
        "\n",
        "Bidirectional Search - Complete and Optimal\\\\\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",
        "\"Reflex Agent\": \"selects an action based on only current percept. Ignores percept history\",\n",
        "\"Search\": \"a computational process which will uncover a sequence of actions that form a path to a goal state(solution)\",\n",
        "\"Optimal Solution\": \"a solution that has the lowest path cost\",\n",
        "\"State Space\": \"the set of all states reachable from the initial state by any sequence of moves\",\n",
        "\"Path\": \"sequence of actions leading from one state s_j to another s_k\",\n",
        "\"Frontier\":\"those states that are available for expanding\",\n",
        "\"Solution\": \"path from initial state s_i to s_j that satisfies the goal test\",\n",
        "\"Uninformed Search\": \"all non-goal nodes in frontier look equally good\",\n",
        "\"Informed Search\": \"some non-goal nodes look better than others\",\n",
        "\"Completeness\": \"guaranteed to find a solution\",\n",
        "\"Optimality\": \"finds a least cost solution first\",\n",
        "\"Depth limited search\": \"a search algorithm that is DFS but with a depth limit l. you get rid of infinite depth problem\",\n",
        "\"Iterative Deepening Search\": \"a search algorithm that uses DLS as a subroutine and increments l\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 942
        },
        "outputId": "fce0b45f-3c62-42c8-a683-6cdd59cbb849"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Criterion for search problems:-A state space\\\n\n-Initial State\\\n\n-Goal States\\\n\n-Set of actions \\\n\n-Transition Model\\\n\n-Action Cost function\\\n \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Best First Search - greedy solution that utilizes a priority queue lowest h(n)Graph search checks to see if path is redundant\\\n\nTree search does not check to see if the path is redundant\\\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Bidirectional Search Searches - searches from initial state and backwards from goal state\\has frontier that is a priority queue and reached states for forward and backward search\\O(b^(d/2)) complete and optimal \n\n## Module 3 Lecture Notes\n BFS - Complete and OptimalUniform Cost Search - Complete and Optimal\\\n\nDFS - Not complete and Not Optimal\\\n\nDepth Limited Search - Not complete and Not Optimal\\\n\nIterative Deepening Search - Complete and Optimal\\\n\nBidirectional Search - Complete and Optimal\\\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** - selects an action based on only current percept. Ignores percept history\n* **Search** - a computational process which will uncover a sequence of actions that form a path to a goal state(solution)\n* **Optimal solution** - a solution that has the lowest path cost\n* **State space** - the set of all states reachable from the initial state by any sequence of moves\n* **Path** - sequence of actions leading from one state s_j to another s_k\n* **Frontier** - those states that are available for expanding\n* **Solution** - path from initial state s_i to s_j that satisfies the goal test\n* **Uninformed search** - all non-goal nodes in frontier look equally good\n* **Informed search** - some non-goal nodes look better than others\n* **Completeness** - guaranteed to find a solution\n* **Optimality** - finds a least cost solution first\n* **Depth limited search** - a search algorithm that is DFS but with a depth limit l. you get rid of infinite depth problem\n* **Iterative deepening search** - a search algorithm that uses DLS as a subroutine and increments l\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 = \"\"\" A* only returns cost-optimal paths proof:\n",
        "$$f(n)> C*,$$ else we would have expanded n\n",
        "$$f(n) = g(n) + h(n),$$ by def\n",
        "$$f(n) =g*(n)+h(n),$$ since n is on an optimal path\n",
        "$$f(n) \\leq  g*(n) +h*(n),$$ due to admissibility\n",
        "$$f(n) \\leq C*,$$ by def $C* = g*(n) +h*(n)$ \\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform Cost Search is a search algorithm that is similar to BFS in that it goes layer by layer, however \\\n",
        "it utilizes a different type of frontier. While BFS uses a FIFO frontier, this uses a priority queue orderd by g(N) which is the path cost function.\\\n",
        "Basically, each layer is determined by the nodes with the same cost. However, because this is uninformed we can end up searching the wrong direction.\\\n",
        "Heuristic functions serve as an estimate for the distance from a state to the goal. It allows us to reduce space for possible solutions and not have to\\ \n",
        "solve everything to completion. It should always be less than or equal to actual distance.\\\n",
        "We consider Greedy Best First Search alg which is an algorithm that is the exact same as Uniform Cost search except it uses a priority queue that is \\\n",
        "ordered by lowest f(n) which is equal to some function that includes the h(n) value. This algorithm is not optimal\\\n",
        "Finally we have A* algorithm which does the same thing as GBFS except this time it calculates f(n) = g(n) + h(n). In this case we always need h(n) to be\\\n",
        "admissible in order for A* to be optimal. We can get an admissible heuristic function through use of a relaxed problem (a problem with fewer restrictions).\\\n",
        "Cost of optimal solution to relaxed problem is admissible heuristic for OG problem. \n",
        "```\n",
        "GREEDY BEST-FIRST SEARCH PSEUDOCODE:\n",
        " \n",
        "frontier = PriorityQueue()\n",
        "frontier.put(start, 0)\n",
        "came_from = {}\n",
        "came_from[start] = None\n",
        "while not frontier.empty():\n",
        " current = frontier.get()\n",
        " if current == goal:\n",
        "   break\n",
        " for next in graph.neighbors(current):\n",
        "   if next not in came_from:\n",
        "     priority = heuristic(goal, next)\n",
        "     frontier.put(next, priority)\n",
        "     came_from[next] = current\n",
        " \n",
        "A* PSEUDOCODE:\n",
        " \n",
        "frontier = Queue()\n",
        "frontier.put(start)\n",
        "visited = {}\n",
        "visited[start] = True\n",
        "while not frontier.empty():\n",
        " current = frontier.get()\n",
        " for next in graph.neighbors(current):\n",
        "   if next not in visited:\n",
        "   frontier.put(next)\n",
        "   visited[next] = True\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Uniform Cost Search\" : \"algorithm that is similar to BFS since it goes in layers uses a priority queue ordered by lowest g(N) optimal\",\n",
        "\"Heuristic Function\":\"a function that returns an estimate of the distance from a state to a goal state\", \n",
        "\"Greedy Best First Search\":\"algorithm that is exactly the same as UCS but uses priority queue on f(n). not optimal\",\n",
        "\"Path Cost Function\": \"The cost from the intitial state to some node n as denoted by g(N)\",\n",
        "\"Relaxed Problem\": \"a problem with fewer restrictions on the actions than the original problem\",\n",
        "\"Admissible Heuristic\": \"a heuristic function that never overestimates the cost from a node n to the goal\",\n",
        "\"Dominance of Heuristics\": \"when for every node n $h_2(n) \\geq h_1(n)$\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1029f962-d522-4566-8277-a470d3a1194b"
      },
      "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": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n A* only returns cost-optimal paths proof:\n$$f(n)> C*,$$ else we would have expanded n\n$$f(n) = g(n) + h(n),$$ by def\n$$f(n) =g*(n)+h(n),$$ since n is on an optimal path\n$$f(n) \\leq  g*(n) +h*(n),$$ due to admissibility\n$$f(n) \\leq C*,$$ by def $C* = g*(n) +h*(n)$ \\\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Uniform Cost Search is a search algorithm that is similar to BFS in that it goes layer by layer, however it utilizes a different type of frontier. While BFS uses a FIFO frontier, this uses a priority queue orderd by g(N) which is the path cost function.Basically, each layer is determined by the nodes with the same cost. However, because this is uninformed we can end up searching the wrong direction.Heuristic functions serve as an estimate for the distance from a state to the goal. It allows us to reduce space for possible solutions and not have to\\ \nsolve everything to completion. It should always be less than or equal to actual distance.We consider Greedy Best First Search alg which is an algorithm that is the exact same as Uniform Cost search except it uses a priority queue that is ordered by lowest f(n) which is equal to some function that includes the h(n) value. This algorithm is not optimalFinally we have A* algorithm which does the same thing as GBFS except this time it calculates f(n) = g(n) + h(n). In this case we always need h(n) to beadmissible in order for A* to be optimal. We can get an admissible heuristic function through use of a relaxed problem (a problem with fewer restrictions).Cost of optimal solution to relaxed problem is admissible heuristic for OG problem. \n```\nGREEDY BEST-FIRST SEARCH PSEUDOCODE:\n \nfrontier = PriorityQueue()\nfrontier.put(start, 0)\ncame_from = {}\ncame_from[start] = None\nwhile not frontier.empty():\n current = frontier.get()\n if current == goal:\n   break\n for next in graph.neighbors(current):\n   if next not in came_from:\n     priority = heuristic(goal, next)\n     frontier.put(next, priority)\n     came_from[next] = current\n \nA* PSEUDOCODE:\n \nfrontier = Queue()\nfrontier.put(start)\nvisited = {}\nvisited[start] = True\nwhile not frontier.empty():\n current = frontier.get()\n for next in graph.neighbors(current):\n   if next not in visited:\n   frontier.put(next)\n   visited[next] = True\n```\n\n\n## Module 4 Definitions\n* **Uniform cost search** - algorithm that is similar to BFS since it goes in layers uses a priority queue ordered by lowest g(N) optimal\n* **Heuristic function** - a function that returns an estimate of the distance from a state to a goal state\n* **Greedy best first search** - algorithm that is exactly the same as UCS but uses priority queue on f(n). not optimal\n* **Path cost function** - The cost from the intitial state to some node n as denoted by g(N)\n* **Relaxed problem** - a problem with fewer restrictions on the actions than the original problem\n* **Admissible heuristic** - a heuristic function that never overestimates the cost from a node n to the goal\n* **Dominance of heuristics** - when for every node n $h_2(n) \\geq h_1(n)$\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" With minmax search, given a game tree we can determine the optimal strategy by by working out minmax value of each state\\\n",
        "Minmax value is the utility for Max player of being in that particular state assuming that both players play optimally from there to the\\\n",
        "end of the game. We know that the minmax value of each terminal state is just the utility (which is given by utility function).\\\n",
        "Max will move to the next highest valued node and then min moves to next lowest value node and so on.\\\\\n",
        "For multiplayer games we use vector of values instead $<V_1, V_2, V_3>$\\.\n",
        "Alpha Beta pruning the idea: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the same\\\n",
        "level or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\\\n",
        "$\\Alpha$ is the value of the best (highest val) chioce we have found so far at any choice point along the path for Max.\\\\\n",
        "$\\Beta$ is the value of the best (lowest val) choice we have found so far at any choice point along the path for Min.\\\\\n",
        "Move ordering is a way to ensure even faster pruning as well. Which if done perfectly brings runtime down from $O(b^m)$ to $O(b^{m/2})$\\\\\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" A heuristic evaluation function, EVAL(s,p) returns an estimate of the expected utility of the state s to player p.\\\\\n",
        "We want to be able to use this to our advantage and cut it off the search as early as possible.\n",
        "For some terminal state $S_x$ EVAL($S_x$,p) is equal to Utility($S_x$, p)\\\\\n",
        "We can create an evaluation function by picking criteria that are easy to calculate and are highly correlated with winning.\\\\\n",
        "For example we can use a material advantage method which assigns value to parts of a state. In chess, the pieces.\\\\\n",
        "We add up the values of each of the factors and that is the value of the eval function.\\\\\n",
        "Output should be normalized so that $$0 \\leq eval \\leq 1$$ where 1 is winning and 0 is losing.\\\\\n",
        "Things that can get in the way of EVAL effectiveness:\\\\\n",
        "Eval function should only be applied to positions that are quiescent. Checking if a state is quiescent is called a quiescent search.\\\\\n",
        "The horizon effect can be stopped by allowing singular extensions.\\\\\n",
        "Forward pruning prunes moves that seem bad but might be good. This decreases comp time at the expense of possible error.\\\\\n",
        "One example of it is beam search which only considers a \"beam\" of n best moves according to eval function. (might get rid of good moves).\\\\\n",
        "Another exmple is Late move reduction which assumes good move ordering and so it doesn't do a full search of children nodes to save time.\\\\\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" in stochastic game trees you must include chance nodes in addition to max and min nodes. Branches leading from chance nodes go to\\\\\n",
        "each different possibility/outcome. Ex: dice roll labeled with outcome and probability.\\\\\n",
        "Positions in this treedo not have definitive minmax values but instead we calculate the expected value of a position.\\\\\n",
        "Average over all possible outcomes of the chance nodes.\\\\\n",
        "We use expectimax value for games with chance nodes. Terminal nodes and min/max nodes work the same.\\\\\n",
        "For chance nodes we use expected value: sum of the value over all outcomes weighted by probability of each chance action.\\\\\n",
        "Just like with minmax game trees we can use eval functions. With these games though we must return values that are a positive linear transformation of \\\\\n",
        "the probability of winning.\\\\\n",
        "Runtime is $O(b^mn^m)$ where n is the number of rolls of dice/times probability is introduced.\\\\\n",
        "We can do something similar to Alpha Beta pruning as well by placing bounds on the utility function we can actually arrive at bounds for the average\\\\\n",
        "of a chance node without looking at the all the children.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\\\\\n",
        "Environment is assumed to be episodic.\\\\\n",
        "The utility function assings a numerical value to a state to express it's desirability.\\\\\\\n",
        "Expected Utility = average utility of all outcomes times probability that outcome happens\\\\\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" We can consider each set of outcomes from an action as a lottery where each outcome is\\\n",
        "assigned a probability. L= [prob1, action1; prob2, action2...]\\\\\n",
        "There are multiple axioms of utility theory:\\\\\n",
        "\n",
        "-ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\\\\\n",
        "\n",
        "-TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\\\\\n",
        "\n",
        "-CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be\\\n",
        "indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p.\\\\\n",
        "\n",
        "-SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B , then the agent is indifferent between two more complex \\\n",
        "lotteries that are the same except that B is substituted for A in one of them.\\\\\n",
        "\n",
        "-MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B\\\n",
        ". If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A(and vice versa)\\\\\n",
        "\n",
        "-DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\\\n",
        "We can derive the following from these:\\\\\n",
        "\n",
        "EXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U\\\\\n",
        "\n",
        "EXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome\\\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Although according to Decision theory people should be maximizing expected utility, in reality people are actually\\\\\n",
        "\n",
        "picking things with the highest estimated expected utility. Estimates can be WAYYYY off. Optimistic expectations are valued higher as a result.\\\\\n",
        "\n",
        "Decision theory is a normative theory - how agents SHOULD act.\\\\\n",
        "Descriptive Theory is how agents do act.\\\\\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" A game tree represents a game problem space. Nodes are board positions and the edges are legal moves from that state.\\\\\n",
        "\n",
        "Each even level represents that it's Max's turn to move. Each odd level represents that it's Min's turn to move.\\\\\n",
        "\n",
        "Minmax algorithm, recurse to the leaves and return the utility for those nodes using utility function. Then, depending on if the node above (parent)\\\\\n",
        "\n",
        "min or max, select the min/max value returned respectively.\\\\\n",
        "\n",
        "continue this process recursively until you reach top.\\\\\n",
        "\n",
        "We assume that min and max will play optimally.\\\\\n",
        "\n",
        "For alpha beta search the idea is that: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the same\\\n",
        "level or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\\\n",
        "\n",
        "For an evaluation function, we are basically given a numeric value for how good a board is.\\\\\n",
        "\n",
        "If it is greater than 0 max is winning. If it is 0 Max is tied at that state. If it is less than zero max is losing.\\\\\n",
        "\n",
        "We can use the eval function to stop a minmax tree from going too long. We can essentially cut a tree off after a certain ply (see definitions)\\\\\n",
        "\n",
        "and then for the leaves we assign them a value based on the eval function and run minmax that way.\\\\\n",
        "\n",
        "There are games also that involve chance. In order to deal with unknown moves, we add chance nodes. The value of these nodes are the outcome (say rolling a 6\\\\\n",
        "\n",
        "the value would be a 6) and then the edge weight would be the probability that that outcome occurs.\\\\\n",
        "\n",
        "the value of the chance node then is the sum of the individual outcomes multiplied by their respective probabilities.\\\\\n",
        "\n",
        "There is a form of pruning that can be done on this. See above lesson 5.5\\\\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"minmax value\" : \"the utility for max of being in that particular game state assuming that both players play optimally\",\n",
        "\"Runtime of MinMax\": \"$O(b^m)$\",\n",
        "\"Alpha Beta Pruning\": \"a method of simplifying calculations by eliminating subtrees with suboptimal moves\",\n",
        "\"alpha\":\"the value of the best (highest value) choice we have found at any choice point along the path max\",\n",
        "\"beta\":\"the value of the best (lowest value) choice we have found at any choice point along the path min\",\n",
        "\"transpositions\": \"different permutations of the move sequence that end up in the same position (leads to redundancy)\",\n",
        "\"Transposition table\": \"caches heuristic values of states. stops transpositions\",\n",
        "\"Type A Strategy\": \"wide but shallow. Considers all possible moves to a certain ply, then uses heuristic eval funciton to estimate utility\",\n",
        "\"Type B Strategy\": \"ignore moves that look bad and follow good looking paths.\",\n",
        "\"Horizon Effect\": \"when a bad move is inevitable but computer prolongs it by using delaying tactics\",\n",
        "\"Beam Search\": \"a forward pruning method that only looks at the n best moves according to eval funciton\",\n",
        "\"late move reduction\": \"doesn't check all values but assumes good move ordering so doesn't check all the way to save time\",\n",
        "\"Stochastic Game Trees\": \"game trees that involve chance nodes\",\n",
        "\"Preference Elicitation\": \"the process of working out a human's utility function\",\n",
        "\"Optimizers curse\": \"the tendency of the estimated expected utility of the best choice to be too high\",\n",
        "\"Normative Theory\": \"how agents SHOULD act\",\n",
        "\"Descriptive Theory\": \"how agents actually act\",\n",
        "\"Ply\": \"one move by one player. Identifiable as a signle layer of a game tree\",\n",
        "\"Evaluation funciton\": \"eval(s,p) evaluates how good a board position is\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6725baf2-647d-41b0-e67d-b4b8a36ad3f9"
      },
      "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": 14,
      "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 With minmax search, given a game tree we can determine the optimal strategy by by working out minmax value of each stateMinmax value is the utility for Max player of being in that particular state assuming that both players play optimally from there to theend of the game. We know that the minmax value of each terminal state is just the utility (which is given by utility function).Max will move to the next highest valued node and then min moves to next lowest value node and so on.\\For multiplayer games we use vector of values instead $<V_1, V_2, V_3>$\\.\nAlpha Beta pruning the idea: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the samelevel or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\n$\\Alpha$ is the value of the best (highest val) chioce we have found so far at any choice point along the path for Max.\\\n$\\Beta$ is the value of the best (lowest val) choice we have found so far at any choice point along the path for Min.\\\nMove ordering is a way to ensure even faster pruning as well. Which if done perfectly brings runtime down from $O(b^m)$ to $O(b^{m/2})$\\\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function, EVAL(s,p) returns an estimate of the expected utility of the state s to player p.\\We want to be able to use this to our advantage and cut it off the search as early as possible.\nFor some terminal state $S_x$ EVAL($S_x$,p) is equal to Utility($S_x$, p)\\\nWe can create an evaluation function by picking criteria that are easy to calculate and are highly correlated with winning.\\\nFor example we can use a material advantage method which assigns value to parts of a state. In chess, the pieces.\\\nWe add up the values of each of the factors and that is the value of the eval function.\\\nOutput should be normalized so that $$0 \\leq eval \\leq 1$$ where 1 is winning and 0 is losing.\\\nThings that can get in the way of EVAL effectiveness:\\\nEval function should only be applied to positions that are quiescent. Checking if a state is quiescent is called a quiescent search.\\\nThe horizon effect can be stopped by allowing singular extensions.\\\nForward pruning prunes moves that seem bad but might be good. This decreases comp time at the expense of possible error.\\\nOne example of it is beam search which only considers a \"beam\" of n best moves according to eval function. (might get rid of good moves).\\\nAnother exmple is Late move reduction which assumes good move ordering and so it doesn't do a full search of children nodes to save time.\\\n\n\n## AIMA Chapter 5.5 Stochastic Games\n in stochastic game trees you must include chance nodes in addition to max and min nodes. Branches leading from chance nodes go to\\each different possibility/outcome. Ex: dice roll labeled with outcome and probability.\\Positions in this treedo not have definitive minmax values but instead we calculate the expected value of a position.\\Average over all possible outcomes of the chance nodes.\\We use expectimax value for games with chance nodes. Terminal nodes and min/max nodes work the same.\\For chance nodes we use expected value: sum of the value over all outcomes weighted by probability of each chance action.\\Just like with minmax game trees we can use eval functions. With these games though we must return values that are a positive linear transformation of \the probability of winning.\\Runtime is $O(b^mn^m)$ where n is the number of rolls of dice/times probability is introduced.\\We can do something similar to Alpha Beta pruning as well by placing bounds on the utility function we can actually arrive at bounds for the average\\of a chance node without looking at the all the children.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\\Environment is assumed to be episodic.\\The utility function assings a numerical value to a state to express it's desirability.\\Expected Utility = average utility of all outcomes times probability that outcome happens\\ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We can consider each set of outcomes from an action as a lottery where each outcome isassigned a probability. L= [prob1, action1; prob2, action2...]\\There are multiple axioms of utility theory:-ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\\\n\n-TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\\\n\n-CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will beindifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p.\\\n\n-SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B , then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them.\\\n\n-MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A(and vice versa)\\\n\n-DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.We can derive the following from these:\\\n\nEXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility, then there exists a function U\\\n\nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome\n\n## AIMA Chapter 16.3 Utility Functions\n Although according to Decision theory people should be maximizing expected utility, in reality people are actuallypicking things with the highest estimated expected utility. Estimates can be WAYYYY off. Optimistic expectations are valued higher as a result.\\\n\nDecision theory is a normative theory - how agents SHOULD act.\\\nDescriptive Theory is how agents do act.\\\n \n\n## Module 5 Lecture Notes\n A game tree represents a game problem space. Nodes are board positions and the edges are legal moves from that state.Each even level represents that it's Max's turn to move. Each odd level represents that it's Min's turn to move.\\\n\nMinmax algorithm, recurse to the leaves and return the utility for those nodes using utility function. Then, depending on if the node above (parent)\\\n\nmin or max, select the min/max value returned respectively.\\\n\ncontinue this process recursively until you reach top.\\\n\nWe assume that min and max will play optimally.\\\n\nFor alpha beta search the idea is that: consider a node n such that Player has a choice of moving to n. If player has a better choice either at the samelevel or anywhere higher in the tree then Player won't move to n and it's safe to prune (get rid of).\\\n\nFor an evaluation function, we are basically given a numeric value for how good a board is.\\\n\nIf it is greater than 0 max is winning. If it is 0 Max is tied at that state. If it is less than zero max is losing.\\\n\nWe can use the eval function to stop a minmax tree from going too long. We can essentially cut a tree off after a certain ply (see definitions)\\\n\nand then for the leaves we assign them a value based on the eval function and run minmax that way.\\\n\nThere are games also that involve chance. In order to deal with unknown moves, we add chance nodes. The value of these nodes are the outcome (say rolling a 6\\\n\nthe value would be a 6) and then the edge weight would be the probability that that outcome occurs.\\\n\nthe value of the chance node then is the sum of the individual outcomes multiplied by their respective probabilities.\\\n\nThere is a form of pruning that can be done on this. See above lesson 5.5\\\n\n \n\n## Module 5 Definitions\n* **Minmax value** - the utility for max of being in that particular game state assuming that both players play optimally\n* **Runtime of minmax** - $O(b^m)$\n* **Alpha beta pruning** - a method of simplifying calculations by eliminating subtrees with suboptimal moves\n* **Alpha** - the value of the best (highest value) choice we have found at any choice point along the path max\n* **Beta** - the value of the best (lowest value) choice we have found at any choice point along the path min\n* **Transpositions** - different permutations of the move sequence that end up in the same position (leads to redundancy)\n* **Transposition table** - caches heuristic values of states. stops transpositions\n* **Type a strategy** - wide but shallow. Considers all possible moves to a certain ply, then uses heuristic eval funciton to estimate utility\n* **Type b strategy** - ignore moves that look bad and follow good looking paths.\n* **Horizon effect** - when a bad move is inevitable but computer prolongs it by using delaying tactics\n* **Beam search** - a forward pruning method that only looks at the n best moves according to eval funciton\n* **Late move reduction** - doesn't check all values but assumes good move ordering so doesn't check all the way to save time\n* **Stochastic game trees** - game trees that involve chance nodes\n* **Preference elicitation** - the process of working out a human's utility function\n* **Optimizers curse** - the tendency of the estimated expected utility of the best choice to be too high\n* **Normative theory** - how agents SHOULD act\n* **Descriptive theory** - how agents actually act\n* **Ply** - one move by one player. Identifiable as a signle layer of a game tree\n* **Evaluation funciton** - eval(s,p) evaluates how good a board position is\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 = \"\"\" There are three main components to a CSP:\\\\\n",
        "\n",
        "- X the set of variables\\\\\n",
        "\n",
        "-D the set of domains \\\\\n",
        "\n",
        "-C constraints that allow combinations\\\\\n",
        "\n",
        "Solving a CSP is an NP complete task\\\\\n",
        "\n",
        "We can represent a CSP as a constraint graph where the nodes are the variables\\\\\n",
        "and the edges are scopes\\\\\n",
        "\n",
        "The main 3 reasons for CSP:\\\\\n",
        "\n",
        "- Easy to make a problem into a CSP\\\\\n",
        "-Mush research into CSP to make it fast and efficient\\\\\n",
        "- Prune state space faster than atomic state space searcher.\\\\\n",
        "State space searcher can only check if a goal has been reached, but a CSP cuts out bad states.\\\\\n",
        "The simplest csps are the ones with finite domains\\\\\n",
        "The most common global constraint is allDif\"\"\"\n",
        "chapter6_2 = \"\"\" Node consistency - for a single node, there is a constraint or preference\\\\\n",
        "\n",
        "Arc Consistency - when you compare two variables and remove inconsitencies from the first variable\\\\\n",
        "An example of this is AC3\\\\\n",
        "\n",
        "Path consistency - when you have two variables that are consistent with each other\\\\\n",
        "and you have a third that you make consistent to the two\\\\\n",
        "\n",
        "\"\"\"\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 = \"\"\" Big idea of CSP's: represent the constraints that solutions must satisfy in a uniform declarative language\\\\\n",
        "\n",
        "find solutions by general purpose search algorithm awith no changes from probelm to problem\\\\\n",
        "\n",
        "CSPs consist of: \n",
        "-Finite set of variables (X)\\\\\n",
        "\n",
        "-Nonempty domain of possible values D\\\\\n",
        "\n",
        "-finite set of constraints\\\\\n",
        "\n",
        "A solution to CSP is complete and consistent\\\\\n",
        "\n",
        "Different Representations of CSP's:\\\\\n",
        "\n",
        "- Constraint Graph - where nodes are variables and edges are binary constraints\\\\\n",
        "\n",
        "- Standard representations pattern - variables with values\\\\\n",
        "\n",
        "- Constraint graph simplifies the search\\\\\n",
        "\n",
        "Flavors of variables for CSP:\\\\\n",
        "\n",
        "-Discrete variables: \n",
        "  -Finite Domain - n variables, domain sized d O(d^n) complete assignments\\\\\n",
        "  \n",
        "  -infinite Domain\\\\\n",
        "\n",
        "-Continuous Variables:\n",
        "  -linear constraints solvable in polynomial time by linear programming\\\\\n",
        "\n",
        "CSP's can be seen as search problems\\\\\n",
        "\n",
        "- Initial state = empty assignment $\\{\\}$\\\\\n",
        "\n",
        "-Successor function = assign value to any unassigned variable provided no constraint conflict\\\\\n",
        "\n",
        "- Goal Test = current assignment is complete \\\\\n",
        "\n",
        "-Path cost: constant cost for every step\\\\\n",
        "\n",
        "The solution is always at depth n for n variables\\\\\n",
        "\n",
        "CSP's are commutative\\\\\n",
        "\n",
        "Only need to consider assignments to a single variable at each node b = d; $d^n$ leaves\\\\\n",
        "\n",
        "We can use depth first search since tree is bounded and use backtracking to make the basic uninformed alg for CSP\\\\\n",
        "\n",
        "We can make heuristics to make it better.\\\\\n",
        "\n",
        "- Start of with most constrained variable (fewest legal values) and if tied do the most constraining variable\\\\\n",
        "\n",
        "-least constraining variable next\\\\\n",
        "\n",
        "-forward checking\n",
        "\n",
        "The idea of forward checking:\\\\\n",
        "\n",
        "-Keep track of remaining legal values for unassigned variables\\\\\n",
        "\n",
        "-Terminate search when any unassigned variable has no remaining legal values\\\\\n",
        "\n",
        "An ar(i,j) is arc consistent iff every v in $X_i$ is consistent with some label on$Y_j$\\\\\n",
        "\n",
        "To make consistent:\\\\\n",
        "\n",
        "for each value v on $X_i$\\\\\n",
        "if there is no label on $Y_j$ consistent with v remove v from $X_i$\\\\\n",
        "\n",
        "\n",
        "AC3:\\\\\n",
        "queue of arcs\\\\\n",
        "pop\\\\\n",
        "remove values from tail inconsistant values between tail and head\\\\\n",
        "for each $X_k$ in neighbors[$X_i$] - $X_j$ do:\\\\\n",
        "queue.add$(X_k,X_i)$\\\\\n",
        "worst case $O(n^2)$\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fb7d4b4b-adfc-4d02-ad24-780f082af2ad"
      },
      "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": 16,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n There are three main components to a CSP:- X the set of variables\\\n\n-D the set of domains \\\n\n-C constraints that allow combinations\\\n\nSolving a CSP is an NP complete task\\\n\nWe can represent a CSP as a constraint graph where the nodes are the variables\\\nand the edges are scopes\\\n\nThe main 3 reasons for CSP:\\\n\n- Easy to make a problem into a CSP\\\n-Mush research into CSP to make it fast and efficient\\\n- Prune state space faster than atomic state space searcher.\\\nState space searcher can only check if a goal has been reached, but a CSP cuts out bad states.\\\nThe simplest csps are the ones with finite domains\\\nThe most common global constraint is allDif\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Node consistency - for a single node, there is a constraint or preferenceArc Consistency - when you compare two variables and remove inconsitencies from the first variable\\\nAn example of this is AC3\\\n\nPath consistency - when you have two variables that are consistent with each other\\\nand you have a third that you make consistent to the two\\\n\n\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 Big idea of CSP's: represent the constraints that solutions must satisfy in a uniform declarative languagefind solutions by general purpose search algorithm awith no changes from probelm to problem\\\n\nCSPs consist of: \n-Finite set of variables (X)\\\n\n-Nonempty domain of possible values D\\\n\n-finite set of constraints\\\n\nA solution to CSP is complete and consistent\\\n\nDifferent Representations of CSP's:\\\n\n- Constraint Graph - where nodes are variables and edges are binary constraints\\\n\n- Standard representations pattern - variables with values\\\n\n- Constraint graph simplifies the search\\\n\nFlavors of variables for CSP:\\\n\n-Discrete variables: \n  -Finite Domain - n variables, domain sized d O(d^n) complete assignments\\\n  \n  -infinite Domain\\\n\n-Continuous Variables:\n  -linear constraints solvable in polynomial time by linear programming\\\n\nCSP's can be seen as search problems\\\n\n- Initial state = empty assignment $\\{\\}$\\\n\n-Successor function = assign value to any unassigned variable provided no constraint conflict\\\n\n- Goal Test = current assignment is complete \\\n\n-Path cost: constant cost for every step\\\n\nThe solution is always at depth n for n variables\\\n\nCSP's are commutative\\\n\nOnly need to consider assignments to a single variable at each node b = d; $d^n$ leaves\\\n\nWe can use depth first search since tree is bounded and use backtracking to make the basic uninformed alg for CSP\\\n\nWe can make heuristics to make it better.\\\n\n- Start of with most constrained variable (fewest legal values) and if tied do the most constraining variable\\\n\n-least constraining variable next\\\n\n-forward checking\n\nThe idea of forward checking:\\\n\n-Keep track of remaining legal values for unassigned variables\\\n\n-Terminate search when any unassigned variable has no remaining legal values\\\n\nAn ar(i,j) is arc consistent iff every v in $X_i$ is consistent with some label on$Y_j$\\\n\nTo make consistent:\\\n\nfor each value v on $X_i$\\\nif there is no label on $Y_j$ consistent with v remove v from $X_i$\\\n\n\nAC3:\\\nqueue of arcs\\\npop\\\nremove values from tail inconsistant values between tail and head\\\nfor each $X_k$ in neighbors[$X_i$] - $X_j$ do:\\\nqueue.add$(X_k,X_i)$\\\nworst case $O(n^2)$\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 = \"\"\" Knowledge based Agents use a process of reasoning over an internal representation of knowledge to decide what action to take\\\\\n",
        "\n",
        "A central component of a knowledge based agent is a knowledge base which contains a set of sentences that are written in a knowledge representation language. The sentence contains some assertion about the world\\\\\n",
        "\n",
        "Logic can serve as a general class of representations for knolwedge based agents. \\\\\n",
        "\n",
        "A logic defines the semantics of the sentences which is their meaning.\\\\\n",
        "\n",
        "The semantics defines the truth of each sentence with respect to a possible world, which we will often call a model.\\\\\n",
        "\n",
        "if a sentence alpha is true in model m then we say that m satisfies alpha or that m is a model of a\\\\\n",
        "\n",
        "M(alpha) then is the set of all models of a\\\\\n",
        "\n",
        "Logical reasoning involves the entailment relation between sentences.\\\\\n",
        "\n",
        "alpha entails beta iff M(alpha) is a subset of M(beta)\n",
        "\n",
        "This means that alpha is ore specific or stronger than beta\\\\\n",
        "\n",
        "model checking is the process of enumerating all possible models that are compatible with KB\n",
        "\n",
        "entailment can be applied to derive conclusions in a process called logical inference.\\\\\n",
        "\n",
        "When an inference alg i allows us to conclude that alpha is true then we write a is derived from KB by i.\\\\\n",
        "\n",
        "$$((\\Alpha \\Wedge \\Beta)\\Wedge \\Omega) = (\\Alpha \\Wedge(\\Beta \\Wedge \\Omega))$$\\\\\n",
        "\n",
        "$$((\\Alpha \\Vee \\Beta)\\Vee \\Omega) = (\\Alpha \\Vee(\\Beta \\Vee \\Omeg$))$$\\\\\n",
        "\n",
        "$$(\\alpha \\Rightarrow \\beta) = (\\neg \\alpha \\Rightarrow \\neg \\beta)$$\\\\\n",
        "\n",
        "$$((\\alpha \\wedge \\beta) \\vee \\omega) = ((\\alpha \\wedge \\beta) \\vee (\\alpha \\wedge \\omega))$$\\\\\n",
        "\n",
        "$$((\\alpha \\vee \\beta) \\wedge \\omega) = ((\\alpha \\vee \\beta) \\wedge (\\alpha \\vee \\omega))$$\\\\\n",
        "\n",
        "For conjunctive normal form make it into just normal phrases but only ands and ors \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Axioms\" : \"A sentence that is given\",\n",
        "\"Derived Sentences\": \"A new sentences that is derived from other sentences\",\n",
        "\"Inference\":\"the process of deriving new sentences from old sentences\",\n",
        "\"sound\":\"the inference algorithm should only derive entailed sentences\",\n",
        "\"complete\": \"an inference algorithm is complete if ti can derive all sentences that are entailed\",\n",
        "\"Definite clause\": \"disjunction of literals where exactly one is positive\" ,\n",
        "\"Horn Clause\": \"disjunciton of literals where at least one is positive including definite clauses and clauses with no positive literals\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "21b48042-9aa0-4d14-d44b-6241ef2e5ca5"
      },
      "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": 47,
      "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 Knowledge based Agents use a process of reasoning over an internal representation of knowledge to decide what action to takeA central component of a knowledge based agent is a knowledge base which contains a set of sentences that are written in a knowledge representation language. The sentence contains some assertion about the world\\\n\nLogic can serve as a general class of representations for knolwedge based agents. \\\n\nA logic defines the semantics of the sentences which is their meaning.\\\n\nThe semantics defines the truth of each sentence with respect to a possible world, which we will often call a model.\\\n\nif a sentence alpha is true in model m then we say that m satisfies alpha or that m is a model of a\\\n\nM(alpha) then is the set of all models of a\\\n\nLogical reasoning involves the entailment relation between sentences.\\\n\nalpha entails beta iff M(alpha) is a subset of M(beta)\n\nThis means that alpha is ore specific or stronger than beta\\\n\nmodel checking is the process of enumerating all possible models that are compatible with KB\n\nentailment can be applied to derive conclusions in a process called logical inference.\\\n\nWhen an inference alg i allows us to conclude that alpha is true then we write a is derived from KB by i.\\\n\n$$((\\Alpha \\Wedge \\Beta)\\Wedge \\Omega) = (\\Alpha \\Wedge(\\Beta \\Wedge \\Omega))$$\\\n\n$$((\\Alpha \\Vee \\Beta)\\Vee \\Omega) = (\\Alpha \\Vee(\\Beta \\Vee \\Omeg$))$$\\\n\n$$(\u0007lpha \\Rightarrow \beta) = (\neg \u0007lpha \\Rightarrow \neg \beta)$$\\\n\n$$((\u0007lpha \\wedge \beta) \u000bee \\omega) = ((\u0007lpha \\wedge \beta) \u000bee (\u0007lpha \\wedge \\omega))$$\\\n\n$$((\u0007lpha \u000bee \beta) \\wedge \\omega) = ((\u0007lpha \u000bee \beta) \\wedge (\u0007lpha \u000bee \\omega))$$\\\n\nFor conjunctive normal form make it into just normal phrases but only ands and ors \n\n## Module 7 Definitions\n* **Axioms** - A sentence that is given\n* **Derived sentences** - A new sentences that is derived from other sentences\n* **Inference** - the process of deriving new sentences from old sentences\n* **Sound** - the inference algorithm should only derive entailed sentences\n* **Complete** - an inference algorithm is complete if ti can derive all sentences that are entailed\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunciton of literals where at least one is positive including definite clauses and clauses with no positive literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 232
        },
        "id": "T3cm1WV542_a",
        "outputId": "f8aaae91-9400-4c1b-8161-e002784ecd01"
      },
      "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": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-9-197fd754e469>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# This will generate the full set of notes that you can use for your exam.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m full_markdown = \"\\n\\n\".join([module1_markdown, \n\u001b[0m\u001b[1;32m      3\u001b[0m                              \u001b[0mmodule2_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m                              \u001b[0mmodule3_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m                              \u001b[0mmodule4_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mNameError\u001b[0m: name 'module1_markdown' is not defined"
          ]
        }
      ]
    }
  ]
}