{
  "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",
      "execution_count": 53,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "5b2d0e95-0ece-4db7-a44c-fccf7382e04b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 54,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "72f59c35-f6a2-43b1-bc42-9164525e4e2b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 55,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 56,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Intelligence defined relative to psychology focuses on \\\n",
        "observing human behavior and thought processes, while intelligence using \\\n",
        "a rationalist approach involves a combination of math and engineering.\n",
        "\n",
        "The first approach is acting humanly (turing test approach). The turing test \\\n",
        "is successful if a human asks a computer and a human questions and is unable \\\n",
        "to differentiate between the two answers. Most AI researchers don't like the \\\n",
        "Turing test. \n",
        "\n",
        "The second approach is thinking humanly, which focuses on \\\n",
        "understanding how humans think. Once we understand the mind, we can formulate \\\n",
        "this into a computer program (cog sci approach).\n",
        "\n",
        "Third approach is thinking \\\n",
        "rationally, which is using logic and probability to generate intelligent \\\n",
        "behavior.\n",
        "\n",
        "The 4th approach is acting rationally. A rational agent is one that \\\n",
        "acts so as to achieve 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 = \"\"\" Turing argued that human behvaior is too complex to be \\\n",
        "captured by any formal set of rules. Humans use informal guidelines that can't \\\n",
        "be captured by a set of rules and codified in a computer program. Computers \\\n",
        "are limited by the fact that they are not exposed to the same type of \\\n",
        "environment as humans (ex: a person understands a dog bc they have interacted \\\n",
        "with one in person).\"\"\"\n",
        "chapter27_2 = \"\"\" Humans have a clear advantage over machiens in the matter of \\\n",
        "modeling experiences. There's a debate over consciousness of machines. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent's choice of action depends on its percept sequence. \\\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" With humans, they choose actions that are desirable from \\\n",
        "their point of view. Machines do not have desires and prefs on their own. \\\n",
        "It's good to design perf measure based on what one actually wants to be \\\n",
        "achieved.\n",
        "\n",
        "Rationality depends on performance measure, agent's prior knowledge \\\n",
        "of the environment, actions, and the percent sequence so far. Rational agents\\\n",
        " can learn from their environment. An agent that relies of prior knowledge \\\n",
        "rather than percepts and learning lacks autonomy. Rational agents should be \\\n",
        "autonomous.\"\"\"\n",
        "chapter2_3 = \"\"\" An environment is fully observable if the sensors give the \\\n",
        "agent a complete view of the environment at any given time. The agent wouldn't \\\n",
        "need to internally keep track of the world. Partially unobservable means that \\\n",
        "parts of the state are missing from sensor data.\n",
        "\n",
        "Competitive environments (two \\\n",
        "agents want the same parking spot) vs cooperative (two cars don't want to \\\n",
        "crash). Stochastic if it deals with explicit probabilities and nondeterminstic \\\n",
        "if the possibilities are listed without being quantified.\n",
        "\n",
        "Episodic task \\\n",
        "environments have that future decisions are independent of past actions, which \\\n",
        "is the opposite of sequential environments.\"\"\"\n",
        "chapter2_4 = \"\"\" The simple reflex agent selects actions using only the \\\n",
        "current percept. Infinite loops can be avoided if we introduce randomness. \\\n",
        "In single-agent environments, randomization is typically not rational.\n",
        "\n",
        "Transition model can describe how the world works. A sensor model would tell \\\n",
        "us that when a car initiates breaking. The transition and sensor model allow \\\n",
        "an agent to keep track of the state of the world (model-based agent). Goal \\\n",
        "based agents has states that are desirable (use search or planning). \\\n",
        "The learning element uses feedback on how agent is doing to modify the \\\n",
        "performance element. A critic lets the learning element know how the agent is \\\n",
        "doing so far.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" The agent program runs on physical architecture to \\\n",
        "get f (agent function). We want to avoid having a table that maps every seq\\\n",
        " to every action bc this is computationally expensive. \"\"\"\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",
        "\"weak ai\": \"machines acting as if they are intelligent\",\n",
        "\"strong ai\": \"machines consciously thinking\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content the agent's sensors perceive\",\n",
        "\"actuators\": \"how agents act upon their environment\",\n",
        "\"percept sequence\": \"history of agent's perceptions\",\n",
        "\"agent function\": \"maps percept sequence to an action\",\n",
        "\"agent program\": \"implements an agent function\",\n",
        "\"rational agent\": \"for each PS, RA selects an action expected to max PM.\",\n",
        "\"consequentialism\": \"what are the consequences of an action\",\n",
        "\"performance measure\": \"evaluates the desirability of a sequence of states\",\n",
        "\"omniscient agent\": \"knows the actual outcome of its actions\",\n",
        "\"information gathering\": \"choosing actions in order to change future percepts\",\n",
        "\"task environment\": \"PEAS (performance, environment, actuators, sensors)\",\n",
        "\"unobservable environment\": \"agent has no sensors\",\n",
        "\"deterministic\": \"next state is completely determined by the current state + action\",\n",
        "\"undeterministic\": \"there is uncertainty in the environment\",\n",
        "\"dynamic vs static\": \"does environment change while agent deliberates\",\n",
        "\"semidynamic\": \"environment is static but agent's PM changes over time\",\n",
        "\"known vs unknown\": \"whether outcomes for all actions are given\",\n",
        "\"environment class\": \"many environments can be drawn from one\",\n",
        "\"agent architecture\": \"allows agent to run program and get an action\",\n",
        "\"utility funciton\": \"internalization of the agent's PM\",\n",
        "\"model-free agent\": \"learns best actions without learning how it affects environment\",\n",
        "\"problem generator\": \"suggests actions that allows the agent to learn from new exp.\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "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",
      "execution_count": 57,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "a5cb018d-8cde-4a0b-e309-aa5bdace01e3"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Intelligence defined relative to psychology focuses on observing human behavior and thought processes, while intelligence using a rationalist approach involves a combination of math and engineering.\n",
              "\n",
              "The first approach is acting humanly (turing test approach). The turing test is successful if a human asks a computer and a human questions and is unable to differentiate between the two answers. Most AI researchers don't like the Turing test. \n",
              "\n",
              "The second approach is thinking humanly, which focuses on understanding how humans think. Once we understand the mind, we can formulate this into a computer program (cog sci approach).\n",
              "\n",
              "Third approach is thinking rationally, which is using logic and probability to generate intelligent behavior.\n",
              "\n",
              "The 4th approach is acting rationally. A rational agent is one that acts so as to achieve the best expected outcome.\n",
              " \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Turing argued that human behvaior is too complex to be captured by any formal set of rules. Humans use informal guidelines that can't be captured by a set of rules and codified in a computer program. Computers are limited by the fact that they are not exposed to the same type of environment as humans (ex: a person understands a dog bc they have interacted with one in person).\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Humans have a clear advantage over machiens in the matter of modeling experiences. There's a debate over consciousness of machines. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent's choice of action depends on its percept sequence.  \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " With humans, they choose actions that are desirable from their point of view. Machines do not have desires and prefs on their own. It's good to design perf measure based on what one actually wants to be achieved.\n",
              "\n",
              "Rationality depends on performance measure, agent's prior knowledge of the environment, actions, and the percent sequence so far. Rational agents can learn from their environment. An agent that relies of prior knowledge rather than percepts and learning lacks autonomy. Rational agents should be autonomous.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " An environment is fully observable if the sensors give the agent a complete view of the environment at any given time. The agent wouldn't need to internally keep track of the world. Partially unobservable means that parts of the state are missing from sensor data.\n",
              "\n",
              "Competitive environments (two agents want the same parking spot) vs cooperative (two cars don't want to crash). Stochastic if it deals with explicit probabilities and nondeterminstic if the possibilities are listed without being quantified.\n",
              "\n",
              "Episodic task environments have that future decisions are independent of past actions, which is the opposite of sequential environments.\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " The simple reflex agent selects actions using only the current percept. Infinite loops can be avoided if we introduce randomness. In single-agent environments, randomization is typically not rational.\n",
              "\n",
              "Transition model can describe how the world works. A sensor model would tell us that when a car initiates breaking. The transition and sensor model allow an agent to keep track of the state of the world (model-based agent). Goal based agents has states that are desirable (use search or planning). The learning element uses feedback on how agent is doing to modify the performance element. A critic lets the learning element know how the agent is doing so far.\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " The agent program runs on physical architecture to get f (agent function). We want to avoid having a table that maps every seq to every action bc this is computationally expensive. \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Weak ai** - machines acting as if they are intelligent\n",
              "* **Strong ai** - machines consciously thinking\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - content the agent's sensors perceive\n",
              "* **Actuators** - how agents act upon their environment\n",
              "* **Percept sequence** - history of agent's perceptions\n",
              "* **Agent function** - maps percept sequence to an action\n",
              "* **Agent program** - implements an agent function\n",
              "* **Rational agent** - for each PS, RA selects an action expected to max PM.\n",
              "* **Consequentialism** - what are the consequences of an action\n",
              "* **Performance measure** - evaluates the desirability of a sequence of states\n",
              "* **Omniscient agent** - knows the actual outcome of its actions\n",
              "* **Information gathering** - choosing actions in order to change future percepts\n",
              "* **Task environment** - PEAS (performance, environment, actuators, sensors)\n",
              "* **Unobservable environment** - agent has no sensors\n",
              "* **Deterministic** - next state is completely determined by the current state + action\n",
              "* **Undeterministic** - there is uncertainty in the environment\n",
              "* **Dynamic vs static** - does environment change while agent deliberates\n",
              "* **Semidynamic** - environment is static but agent's PM changes over time\n",
              "* **Known vs unknown** - whether outcomes for all actions are given\n",
              "* **Environment class** - many environments can be drawn from one\n",
              "* **Agent architecture** - allows agent to run program and get an action\n",
              "* **Utility funciton** - internalization of the agent's PM\n",
              "* **Model-free agent** - learns best actions without learning how it affects environment\n",
              "* **Problem generator** - suggests actions that allows the agent to learn from new exp.\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 58,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DpBvu7EMx7sy",
        "outputId": "6c7dec9b-4c95-4569-c7d4-6c430a0db307"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 695\n",
            "The length in characters is 4669\n"
          ]
        }
      ],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Python was developed by Guido van Rossum in 1989. \\\n",
        "Python has fast development, portability, built-in types and support libraries.\\\n",
        " REPL allows you to run python from command line. \n",
        " \n",
        "Use \\ to go to a new line \\\n",
        "prematurely. All data is treated as objects. The object will be garbage \\\n",
        "collected once the object is unreachable in the program. \n",
        "\n",
        "Strong typing means \\\n",
        "that every object has a fixed type, and we can't perform operations like \\\n",
        "(\"hello\" + 2) that aren't compatible. We can do type(object) or isInstance(\\\n",
        "object, type). \n",
        "\n",
        "Types: int, float, str, tuple, dict, list, bool, None, function.\\\n",
        " Python uses dynamic typing which means types are decided at runtime when vars \\\n",
        "first come into existence. If reassigned, type(var) is updated.\n",
        "\n",
        "Use (and, or, \\\n",
        "not) instead of symbols.\n",
        "\n",
        "Modulo (%), power (**), boolean (True).\n",
        "\n",
        "String use \\\n",
        "single or double quotes. String concat(+). No need to escape special characters \\\n",
        "by using r which means raw (r'\\n')\n",
        "```\n",
        "print(\"%s can speak %d languages\" % (\"C3PO\", 6000))\n",
        "```\n",
        "String are immutable, lists are mutable and ordered, == checks whether \\\n",
        "variables point to \\\n",
        "obj of same value, is checks whether they point to the same value. y = x[:] \\\n",
        "gets a shallow copy of any sequence (new obj of same value).\n",
        "```\n",
        "tup = (23, 'abc')\n",
        "li = ['abc', 12]\n",
        "tup[1] = 'abc'\n",
        "tup[-1] = 'abc' # negative lookup starting from right at -1\n",
        "```\n",
        "Slicing:\n",
        "```\n",
        "t = (1, 'a', 4, (2, 2), 'def')\n",
        "t[1:4] = ('a', 4, (2, 2))\n",
        "t[1:-1] = ('a', 4, (2, 2))\n",
        "t[1:-1:2] = ('a', (2, 2))\n",
        "t[:2] = (1, 'a')\n",
        "t[2:] = (4, (2, 2), 'def')\n",
        "```\n",
        "Operations on List:\n",
        "```\n",
        "list.insert(2, 'i'): add an i at index 2\n",
        "list.index('b'): get the index of 1st occurrence\n",
        "list.count('b'): count number of b's in the list\n",
        "list.remove('b'): remove first occurrence\n",
        "list.reverse(): reverse in place\n",
        "list.sort(): sort in place # don't need list = list.sort()\n",
        "sorted(list): returns a copy yhat is sorted\n",
        "[1, 2] + [3, 4] = [4, 6]\n",
        "```\n",
        "Operations on Strings:\n",
        "```\n",
        "words = s.split(\" \")\n",
        "sentence = \" \".join(words)\n",
        "s.upper()\n",
        "s.lower()\n",
        "s.capitalize()\n",
        "```\n",
        "Dictionaries are unordered and use hashing, therefore keys must be immutable.\n",
        "```\n",
        "dict = {'bob': 5, 'joe': 7}\n",
        "dict['bob'] = 5\n",
        "dict['bob'] = 11\n",
        "# following all return lists\n",
        "dict.keys()\n",
        "dict.values()\n",
        "dict.items()\n",
        "```\n",
        "defaultdict automatically initializes nonexistent dict values.\n",
        "\n",
        "You can provide default values for a function's arguments, which are then \\\n",
        "optional (for ex: funOne(b, c = 5)). You can call arguments out of order by \\\n",
        "doing funOne(4, c = 1, b = 7), where b = 7 is a keyword argument. To accept a \\\n",
        "variable number of non-keyword args \\\n",
        "you can do print(*args). For a variable number of keyword arguments, it's **args\\\n",
        ".\n",
        "\n",
        "For memoization, default parameter values are evaluted only when \\\n",
        "the def statement they belong to is first executed.\n",
        "\n",
        "Functions are first-class objects, that can pass functions as arguments to \\\n",
        "other functions, return function, or assign functions to variables or store \\\n",
        "them in data structures.\n",
        "\n",
        "Creating a class:\n",
        "```\n",
        "class Student:\n",
        "  univ = \"penn\"\n",
        "  def __init__(self, name, credit_units):\n",
        "    self.student_name = name\n",
        "    self.student_units = credit_units\n",
        "  def increase_cu(self):\n",
        "    self.student_units += 1\n",
        "student1 = Student(\"Skylar\", 5)\n",
        "student1.increase_cu()\n",
        "Student.increase_cu(student1)\n",
        "```\n",
        "Define a subclass where the superclass is Student\n",
        "```\n",
        "class AI_Student(Student):\n",
        "  def __init__(self, name, credit_units)\n",
        "    Student.__init__(self, name, credit_units)\n",
        "  def increase_cu(self):\n",
        "    self.increase_cu += 2\n",
        "```\n",
        "Multiple inheritance is supported in python. The only time you should \\\n",
        "explicitly pass self as an arg is when calling a method of an ancestor.\n",
        "\n",
        "When printing ints using concatenation, use str(56) for example.\n",
        "```\n",
        "def __str__(self):\n",
        "  \"I am \" + self.age + \" years old!\"\n",
        "print(s) # gives \"I am 20 years old!\"\n",
        "```\n",
        "Python's main method is __main__\n",
        "```\n",
        "if __name__ == '__main__':\n",
        "```\n",
        "For loops:\n",
        "```\n",
        "list(range(5)) = [0, 1, 2, 3, 4]\n",
        "# list comprehension\n",
        "squares = [x * x for x in nums]\n",
        "new_list = [el * 2 for el in li if el > 5]\n",
        "d = {k: v for k, v in lst}\n",
        "```\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",
        "Python iterators do not have a hasnext() method. You can catch the \\\n",
        "stopIteration exception.\n",
        "Generators:\n",
        "```\n",
        "def f(n):\n",
        "  yield n\n",
        "  yield n + 1\n",
        "type(f(10)) == <class 'generator'>\n",
        "[i for i in f(6)] = [6, 7]\n",
        "gen = f(5)\n",
        "next(gen)\n",
        "next(gen)\n",
        "```\n",
        "Benefits of generators: less code, maintains local state, calcs values as needed\\\n",
        ", avoids storing entire sequence, good for aggregation, good for inf sequences, \\\n",
        "bad for inspecting individual values.\n",
        "```\n",
        "while True:\n",
        "  try:\n",
        "    print(g.__next__())\n",
        "  except StopIteration:\n",
        "    print('Done')\n",
        "    break\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"ability of objects to change their value\",\n",
        "\"tuple\": \"immutable ordered sequence of items (can be of mixed types)\",\n",
        "\"higher order functions\": \"functions that take functions as input\",\n",
        "\"subclass\": \"class extends the definition of another class\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module2_lecture_notes))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 59,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "2001f295-2d79-4773-8dc9-f96bb2253d5c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " Python was developed by Guido van Rossum in 1989. Python has fast development, portability, built-in types and support libraries. REPL allows you to run python from command line. \n",
              " \n",
              "Use \\ to go to a new line prematurely. All data is treated as objects. The object will be garbage collected once the object is unreachable in the program. \n",
              "\n",
              "Strong typing means that every object has a fixed type, and we can't perform operations like (\"hello\" + 2) that aren't compatible. We can do type(object) or isInstance(object, type). \n",
              "\n",
              "Types: int, float, str, tuple, dict, list, bool, None, function. Python uses dynamic typing which means types are decided at runtime when vars first come into existence. If reassigned, type(var) is updated.\n",
              "\n",
              "Use (and, or, not) instead of symbols.\n",
              "\n",
              "Modulo (%), power (**), boolean (True).\n",
              "\n",
              "String use single or double quotes. String concat(+). No need to escape special characters by using r which means raw (r'\n",
              "')\n",
              "```\n",
              "print(\"%s can speak %d languages\" % (\"C3PO\", 6000))\n",
              "```\n",
              "String are immutable, lists are mutable and ordered, == checks whether variables point to obj of same value, is checks whether they point to the same value. y = x[:] gets a shallow copy of any sequence (new obj of same value).\n",
              "```\n",
              "tup = (23, 'abc')\n",
              "li = ['abc', 12]\n",
              "tup[1] = 'abc'\n",
              "tup[-1] = 'abc' # negative lookup starting from right at -1\n",
              "```\n",
              "Slicing:\n",
              "```\n",
              "t = (1, 'a', 4, (2, 2), 'def')\n",
              "t[1:4] = ('a', 4, (2, 2))\n",
              "t[1:-1] = ('a', 4, (2, 2))\n",
              "t[1:-1:2] = ('a', (2, 2))\n",
              "t[:2] = (1, 'a')\n",
              "t[2:] = (4, (2, 2), 'def')\n",
              "```\n",
              "Operations on List:\n",
              "```\n",
              "list.insert(2, 'i'): add an i at index 2\n",
              "list.index('b'): get the index of 1st occurrence\n",
              "list.count('b'): count number of b's in the list\n",
              "list.remove('b'): remove first occurrence\n",
              "list.reverse(): reverse in place\n",
              "list.sort(): sort in place # don't need list = list.sort()\n",
              "sorted(list): returns a copy yhat is sorted\n",
              "[1, 2] + [3, 4] = [4, 6]\n",
              "```\n",
              "Operations on Strings:\n",
              "```\n",
              "words = s.split(\" \")\n",
              "sentence = \" \".join(words)\n",
              "s.upper()\n",
              "s.lower()\n",
              "s.capitalize()\n",
              "```\n",
              "Dictionaries are unordered and use hashing, therefore keys must be immutable.\n",
              "```\n",
              "dict = {'bob': 5, 'joe': 7}\n",
              "dict['bob'] = 5\n",
              "dict['bob'] = 11\n",
              "# following all return lists\n",
              "dict.keys()\n",
              "dict.values()\n",
              "dict.items()\n",
              "```\n",
              "defaultdict automatically initializes nonexistent dict values.\n",
              "\n",
              "You can provide default values for a function's arguments, which are then optional (for ex: funOne(b, c = 5)). You can call arguments out of order by doing funOne(4, c = 1, b = 7), where b = 7 is a keyword argument. To accept a variable number of non-keyword args you can do print(*args). For a variable number of keyword arguments, it's **args.\n",
              "\n",
              "For memoization, default parameter values are evaluted only when the def statement they belong to is first executed.\n",
              "\n",
              "Functions are first-class objects, that can pass functions as arguments to other functions, return function, or assign functions to variables or store them in data structures.\n",
              "\n",
              "Creating a class:\n",
              "```\n",
              "class Student:\n",
              "  univ = \"penn\"\n",
              "  def __init__(self, name, credit_units):\n",
              "    self.student_name = name\n",
              "    self.student_units = credit_units\n",
              "  def increase_cu(self):\n",
              "    self.student_units += 1\n",
              "student1 = Student(\"Skylar\", 5)\n",
              "student1.increase_cu()\n",
              "Student.increase_cu(student1)\n",
              "```\n",
              "Define a subclass where the superclass is Student\n",
              "```\n",
              "class AI_Student(Student):\n",
              "  def __init__(self, name, credit_units)\n",
              "    Student.__init__(self, name, credit_units)\n",
              "  def increase_cu(self):\n",
              "    self.increase_cu += 2\n",
              "```\n",
              "Multiple inheritance is supported in python. The only time you should explicitly pass self as an arg is when calling a method of an ancestor.\n",
              "\n",
              "When printing ints using concatenation, use str(56) for example.\n",
              "```\n",
              "def __str__(self):\n",
              "  \"I am \" + self.age + \" years old!\"\n",
              "print(s) # gives \"I am 20 years old!\"\n",
              "```\n",
              "Python's main method is __main__\n",
              "```\n",
              "if __name__ == '__main__':\n",
              "```\n",
              "For loops:\n",
              "```\n",
              "list(range(5)) = [0, 1, 2, 3, 4]\n",
              "# list comprehension\n",
              "squares = [x * x for x in nums]\n",
              "new_list = [el * 2 for el in li if el > 5]\n",
              "d = {k: v for k, v in lst}\n",
              "```\n",
              "Iterable objects can be used in a for loop because they have an __iter__ magic method, which converts them to iterator objects.\n",
              "Python iterators do not have a hasnext() method. You can catch the stopIteration exception.\n",
              "Generators:\n",
              "```\n",
              "def f(n):\n",
              "  yield n\n",
              "  yield n + 1\n",
              "type(f(10)) == <class 'generator'>\n",
              "[i for i in f(6)] = [6, 7]\n",
              "gen = f(5)\n",
              "next(gen)\n",
              "next(gen)\n",
              "```\n",
              "Benefits of generators: less code, maintains local state, calcs values as needed, avoids storing entire sequence, good for aggregation, good for inf sequences, bad for inspecting individual values.\n",
              "```\n",
              "while True:\n",
              "  try:\n",
              "    print(g.__next__())\n",
              "  except StopIteration:\n",
              "    print('Done')\n",
              "    break\n",
              "```\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - ability of objects to change their value\n",
              "* **Tuple** - immutable ordered sequence of items (can be of mixed types)\n",
              "* **Higher order functions** - functions that take functions as input\n",
              "* **Subclass** - class extends the definition of another class\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 60,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" In an unknown environment, an agent can do no better but to \\\n",
        "choose an action at random. We want to use abstraction when possible.\"\"\"\n",
        "chapter3_2 = \"\"\" TSP is a touring problem (describes set of locations that must \\\n",
        "be visited). \"\"\"\n",
        "chapter3_3 = \"\"\" For best-first search, we expand a node n that has min value \\\n",
        "of some evaluation function, f(n). We check when we pop the node from the \\\n",
        "priority queue if it's the goal node. For BFS and DFS, check if each child node \\\n",
        "is the goal. \"\"\"\n",
        "chapter3_4 = \"\"\" Uniform-cost search/Dijkstra's is using best first search where \\\n",
        "our evaluation function is the cost of the path from the root to the current node.\\\n",
        " The time complexity of UCS is O(b^(1 + floor(C / e))) where X is the cost of \\\n",
        "the optimal solution and e is a lower bound on the cost of each action (must \\\n",
        "be positive). UCS is complete and optimal.\n",
        "\n",
        "DFS can be implemented as a call to \\\n",
        "best first search where eval func f is the negative of the depth. This is not how \\\n",
        "it usually gets implemented though. In cyclic state spaces, DFS can end up \\\n",
        "in an infinite loop.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" A problem-solving agent must plan ahead and the \\\n",
        "process it undergoes is referred to as search. It considers a sequence of \\\n",
        "actions that are a path to the goal state (solution).\n",
        "\n",
        "An example search problem\\\n",
        " is the 8-puzzle (fully observable and deterministic). There are 9! states. \\\n",
        "There are 4 actions at any given time. Our performance measure would be to \\\n",
        "minimize total moves.\n",
        "\n",
        "To define a search problem, we need the following: \\\n",
        "states, initial state, actions, transition model: if we apply an action to a state \\\n",
        "we get back another state, path cost/action cost function (performance measure), and goal states.\n",
        "\n",
        "Tree search treats different paths to the same node as distinct. By failing \\\n",
        "to recognize repeated states, a learning problem can become exponential. \\\n",
        "We can fix this by creating an explored set. Graph search checks for redundant \\\n",
        "states and doesn't add them to the frontier (but this requires more space).\n",
        "\n",
        "We evaluate a search algo in terms of completeness, optimality, and time and space \\\n",
        "complexity. Depth-limited search is DFS but we only explore up to l depth. \\\n",
        "If l = d, then optimal, if l < d, then incomplete, if l > d then not optimal. \\\n",
        "The time complexity is for b = branching factor, O(b^l) and the space complexity\\\n",
        " will be O(bl).\n",
        " \n",
        "Iterative deepening search does depth limited search until it \\\n",
        "returns a solution by increasing l on every iteration. This is complete and \\\n",
        "optimal (if cost = 1). Time: O(b^d) and space O(bd).\n",
        "\n",
        "Implement BFS using a FIFO\\\n",
        " queue. DFS frontier is LIFO. M is the maximum length of any path in the state \\\n",
        "space. D is the depth of the shallowest goal node. Root node = depth 0. For \\\n",
        "bidirectional search, we need two frontiers and two reaches states tables.\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",
        "\"state space\": \"set of all states reachable from the initial state\",\n",
        "\"search tree\": \"way of representing the paths that a search algo has explored\",\n",
        "\"frontier\": \"those states that are available for expanding\",\n",
        "\"complete\": \"finds a solution if one exists and none if not\",\n",
        "\"optimal\": \"always finds the lowest cost solution\",\n",
        "\"uninformed search\": \"all non-goal nodes look equally good\",\n",
        "\"open-loop system\": \"if the agent knows the solution to a problem, it can ignore its percepts\",\n",
        "\"standardized problem\": \"used by researchers as a performance benchmark\",\n",
        "\"early goal test\": \"check if a node is a sol as soon as it's generated (BFS, DFS)\",\n",
        "\"late goal test\": \"don't check if a node is a sol until it's popped (best first search)\",\n",
        "\"backtracking search\": \"only one successor is generated at a time\",\n",
        "\"bidirectional search\": \"searches forward from initial state/ backtracks from goal\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 61,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "ff52b8e3-ecbc-4152-844c-2f38f4403f02"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " In an unknown environment, an agent can do no better but to choose an action at random. We want to use abstraction when possible.\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " TSP is a touring problem (describes set of locations that must be visited). \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " For best-first search, we expand a node n that has min value of some evaluation function, f(n). We check when we pop the node from the priority queue if it's the goal node. For BFS and DFS, check if each child node is the goal. \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Uniform-cost search/Dijkstra's is using best first search where our evaluation function is the cost of the path from the root to the current node. The time complexity of UCS is O(b^(1 + floor(C / e))) where X is the cost of the optimal solution and e is a lower bound on the cost of each action (must be positive). UCS is complete and optimal.\n",
              "\n",
              "DFS can be implemented as a call to best first search where eval func f is the negative of the depth. This is not how it usually gets implemented though. In cyclic state spaces, DFS can end up in an infinite loop.\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " A problem-solving agent must plan ahead and the process it undergoes is referred to as search. It considers a sequence of actions that are a path to the goal state (solution).\n",
              "\n",
              "An example search problem is the 8-puzzle (fully observable and deterministic). There are 9! states. There are 4 actions at any given time. Our performance measure would be to minimize total moves.\n",
              "\n",
              "To define a search problem, we need the following: states, initial state, actions, transition model: if we apply an action to a state we get back another state, path cost/action cost function (performance measure), and goal states.\n",
              "\n",
              "Tree search treats different paths to the same node as distinct. By failing to recognize repeated states, a learning problem can become exponential. We can fix this by creating an explored set. Graph search checks for redundant states and doesn't add them to the frontier (but this requires more space).\n",
              "\n",
              "We evaluate a search algo in terms of completeness, optimality, and time and space complexity. Depth-limited search is DFS but we only explore up to l depth. If l = d, then optimal, if l < d, then incomplete, if l > d then not optimal. The time complexity is for b = branching factor, O(b^l) and the space complexity will be O(bl).\n",
              " \n",
              "Iterative deepening search does depth limited search until it returns a solution by increasing l on every iteration. This is complete and optimal (if cost = 1). Time: O(b^d) and space O(bd).\n",
              "\n",
              "Implement BFS using a FIFO queue. DFS frontier is LIFO. M is the maximum length of any path in the state space. D is the depth of the shallowest goal node. Root node = depth 0. For bidirectional search, we need two frontiers and two reaches states tables.\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State space** - set of all states reachable from the initial state\n",
              "* **Search tree** - way of representing the paths that a search algo has explored\n",
              "* **Frontier** - those states that are available for expanding\n",
              "* **Complete** - finds a solution if one exists and none if not\n",
              "* **Optimal** - always finds the lowest cost solution\n",
              "* **Uninformed search** - all non-goal nodes look equally good\n",
              "* **Open-loop system** - if the agent knows the solution to a problem, it can ignore its percepts\n",
              "* **Standardized problem** - used by researchers as a performance benchmark\n",
              "* **Early goal test** - check if a node is a sol as soon as it's generated (BFS, DFS)\n",
              "* **Late goal test** - don't check if a node is a sol until it's popped (best first search)\n",
              "* **Backtracking search** - only one successor is generated at a time\n",
              "* **Bidirectional search** - searches forward from initial state/ backtracks from goal\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 62,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" A heuristic is consistent if for any node n and any successor n'\\\n",
        "generated by action a, h(n) <= c(n, a, n') + h(n'). Every consistent heuristic \\\n",
        "is admissible.\n",
        "\n",
        "A* expands nodes where f(n) < C (surely expanded), sometimes expands \\\n",
        "nodes where f(n) = C, and never expands the rest of the nodes. A* with a \\\n",
        " consistent heuristic is optimally efficient in that it always expands all nodes \\\n",
        "that are surely expanded by A*.\"\"\"\n",
        "chapter3_6 = \"\"\" A dominant heuristic will always expand at most the same number\\\n",
        " of nodes as a worse heuristic. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform cost search uses a pr queue ordered by g(n) \\\n",
        "(path cost function). In this case, G(n) gives the cost of going from starting \\\n",
        "node to node n. A new concept is a heuristic function h(n), which estimates the \\\n",
        "distance/cost from node n to the goal node.\n",
        "\n",
        "Greedy best first search is \\\n",
        "not optimal or complete (can get stuck in loops).\n",
        "\n",
        "A* search is optimal and \\\n",
        "complete. Time complexity is O(b^d) where b is the solution to \\\n",
        "N + 1 = 1 + b + b^2 + ... + b^d where N = num of expanded nodes. Remember that \\\n",
        "we don't check in A* if the node is the goal until we pop it.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"greedy best first search\" : \"expand node with lowest h(n)\",\n",
        "\"A* search\": \"best form of best first search w/ f(n) = h(n) + g(n)\",\n",
        "\"admissible heuristic\": \"never overestimates cost to reach the goal\",\n",
        "\"relaxed problems\": \"create h(n) by relaxing constraints\",\n",
        "\"monotonic\": \"paths costs strictly increase as you go along a path\",\n",
        "\"pruning\": \"eliminating non-optimal possibilities from consideration without examining\",\n",
        "\"bounded suboptimal search\": \"look for sol that is within factor W of optimal cost\",\n",
        "\"bounded-cost search\": \"find a solution with cost less than some C\",\n",
        "\"unbounded-cost search\": \"accept a solution of any cost\",\n",
        "\"speedy search\": \"solves unbounded cost with h(n) = num actions to reach goal\",\n",
        "\"memory-bounded search\": \"remove states from reached when they are no longer needed\",\n",
        "\"reference counts\": \"keep track of num of times a node has been reached\",\n",
        "\"beam search\": \"limits size of frontier by keeping best options\",\n",
        "\"recursive best-first search\": \"uses f_limit to keep track of f-value of best alt. path\",\n",
        "\"backed-up value\": \"best f-value of a node's children\",\n",
        "\"SMA*\": \"does A* until memory is full, when it deletes worst leaf node\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 63,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 784
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "56995975-4b8e-47ee-d3b3-bec165d8586a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " A heuristic is consistent if for any node n and any successor n'generated by action a, h(n) <= c(n, a, n') + h(n'). Every consistent heuristic is admissible.\n",
              "\n",
              "A* expands nodes where f(n) < C (surely expanded), sometimes expands nodes where f(n) = C, and never expands the rest of the nodes. A* with a  consistent heuristic is optimally efficient in that it always expands all nodes that are surely expanded by A*.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " A dominant heuristic will always expand at most the same number of nodes as a worse heuristic. \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform cost search uses a pr queue ordered by g(n) (path cost function). In this case, G(n) gives the cost of going from starting node to node n. A new concept is a heuristic function h(n), which estimates the distance/cost from node n to the goal node.\n",
              "\n",
              "Greedy best first search is not optimal or complete (can get stuck in loops).\n",
              "\n",
              "A* search is optimal and complete. Time complexity is O(b^d) where b is the solution to N + 1 = 1 + b + b^2 + ... + b^d where N = num of expanded nodes. Remember that we don't check in A* if the node is the goal until we pop it.\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Greedy best first search** - expand node with lowest h(n)\n",
              "* **A* search** - best form of best first search w/ f(n) = h(n) + g(n)\n",
              "* **Admissible heuristic** - never overestimates cost to reach the goal\n",
              "* **Relaxed problems** - create h(n) by relaxing constraints\n",
              "* **Monotonic** - paths costs strictly increase as you go along a path\n",
              "* **Pruning** - eliminating non-optimal possibilities from consideration without examining\n",
              "* **Bounded suboptimal search** - look for sol that is within factor W of optimal cost\n",
              "* **Bounded-cost search** - find a solution with cost less than some C\n",
              "* **Unbounded-cost search** - accept a solution of any cost\n",
              "* **Speedy search** - solves unbounded cost with h(n) = num actions to reach goal\n",
              "* **Memory-bounded search** - remove states from reached when they are no longer needed\n",
              "* **Reference counts** - keep track of num of times a node has been reached\n",
              "* **Beam search** - limits size of frontier by keeping best options\n",
              "* **Recursive best-first search** - uses f_limit to keep track of f-value of best alt. path\n",
              "* **Backed-up value** - best f-value of a node's children\n",
              "* **Sma*** - does A* until memory is full, when it deletes worst leaf node\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 64,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iEIOpL7vyWcc",
        "outputId": "d42900ed-3aa5-4dfb-b7f3-824b0136cd99"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 871\n",
            "The length in characters is 4416\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"  \"\"\"\n",
        "chapter5_2 = \"\"\" Alpha-beta with perfect move ordering can solve a tree \\\n",
        "roughly twice as deep as minimax in the same time. With random move ordering, \\\n",
        "the total number of nodes examined is about O(b^(3m/4)) \"\"\"\n",
        "chapter5_3 = \"\"\"  \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games introduce randomness. A game tree in backgammon \\\n",
        "must have MAX, MIN, and chance nodes. \"\"\"\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 \\\n",
        "how desirable the immediate outcome is. A utility function U(S) assigns a number \\\n",
        "for the desirability of a certain state. \"\"\"\n",
        "chapter16_2 = \"\"\" A rational agent either prefers every option equally, or has a \\\n",
        "clear ordering of preference. \"\"\"\n",
        "chapter16_3 = \"\"\" Humans have their own unique prefs. Certainty effect means that \\\n",
        "people tend to like gains that are certain over riskiness. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" 1997: IBM designs AI called Deep Blue that beats \\\n",
        "world Chess champion. Over time, AI has gotten better at beating humans in Chess\\\n",
        ". Google DeepMind's AlphaGo is impressive because Go has so many more possible \\\n",
        "moves than Chess does.\n",
        "\n",
        "The simplest game environment is multiagent, static, \\\n",
        "discrete, fully observable, and strategic.\n",
        "\n",
        "Properties of this game are 2 players \\\n",
        "who alternative moves, zero-sum, clear set of legal moves, and well defined \\\n",
        "outcomes (win, lose, tie). Let's call our first player MAX and our 2nd MIN. A \\\n",
        "utility function gives numerical values to terminal states (inf, -inf, 0).\n",
        "\n",
        "We can play a game by searching by\n",
        "- considering all legal successors to current state\n",
        "- evaluate each successor board position\n",
        "- pick move that leads to the best position for us\n",
        "MAX and MIN nodes:\n",
        "- When MAX moves, MAX attempts to maximize MAX's outcome\n",
        "- When MIN moves, MIN attempts to minimize MAX's outcome\n",
        "- Root level 0 is MAX\n",
        "- Assume MAX goes first (even levels MAX)\n",
        "- Evaluation function f(n) gives real number scores to board positions irrelevant \\\n",
        "of path\n",
        "- If f(n) > 0, then max is currently winning\n",
        "- Ex: for tic tac toe, f(n) = number of 3 lengths open for max - open for min\n",
        "Minimax Rule: Assume that min will respond with the best strategy for itself\n",
        "Computed Using a Recursive Process\n",
        "- Backed-up valie of each node is determined by values of its children\n",
        "- For MAX(MIN) node, the backed-up value is the max(min) of the values of its children\n",
        "Procedure\n",
        "- Until game is over:\n",
        "- Start with current pos as MAX node\n",
        "- Expand the game tree a fixed number of ply\n",
        "- Apply eval func to the leaf positions\n",
        "- Calc back-up values bottom-up\n",
        "- Pick move assigned to MAX at the root\n",
        "- Wait for min's response\n",
        "\n",
        "```\n",
        "def max_value(state):\n",
        "  if state = terminal\n",
        "    return state's utility\n",
        "  v = -inf\n",
        "  for successor of state:\n",
        "    v = max(v, min-value(successor))\n",
        "  return v\n",
        "def min_value(state):\n",
        "  if state = terminal\n",
        "    return state's utility\n",
        "  v = inf\n",
        "  for successor of state:\n",
        "    v = min(v, max-value(successor))\n",
        "  return v\n",
        "```\n",
        "Alpha-Beta Pruning:\n",
        "- During minimax, keep track of alpha (MAX's current lower bound on its outcome), \\\n",
        "and beta (MIN's current upper bound on MIN's outcome)\n",
        "- MAX will never allow a move that could lead to a worse score than a\n",
        "- MIN will never allow a move that could lead to a better score (for MAX) than B\n",
        "Stop evaluating a branch when:\n",
        "- When evaluating a MAX node, a value v >= b is backed-up\n",
        "- When evaluating a MIN node, a value v <= a is backed-up\n",
        "Alpha: best already explored option along path to the root for maximizer\n",
        "Beta: best already explored option along path to the root for minimizer\n",
        "For max_value: alpha = max(alpha, best_value)\n",
        "For min_value: beta = min(beta, best_value)\n",
        "Expectimax Search\n",
        "- Used when we don't know what the result of an action will be (dice roll, /\n",
        "unpredictable opponents, action fails)\n",
        "- Values should now reflect average-case (expectimax) outcomes\n",
        "Expectimax search: compute the average score under optimal play\n",
        "- MAX nodes are the same as minimax search\n",
        "- Chance nodes are like MIN nodes but the outcome is uncertain\n",
        "- Calculate their expected utilities\n",
        "- Take weighted average (expectation) of children\n",
        "```\n",
        "def value(state):\n",
        "  if state is terminal: return state's utility\n",
        "  if the next agent is MAX: return max-value(state)\n",
        "  if the next agent is EXP: return exp-value(state)\n",
        "def max-value(state):\n",
        "  v = -inf\n",
        "  for successor of state:\n",
        "    v = max(v, value(successor))\n",
        "  return v\n",
        "def exp-value(state):\n",
        "  v = 0\n",
        "  for successor or state:\n",
        "    p = prob(successor)\n",
        "    v += p * value(successor)\n",
        "  return v\n",
        "```\n",
        "\n",
        "AB Code:\n",
        "```\n",
        "        if self.game_over(move_is_vertical) or limit == 0:\n",
        "            return None, self.board_value(max_is_vertical), 1\n",
        "        # initialize return variables\n",
        "        best_move = 0\n",
        "        best_value = float(\"-inf\")\n",
        "        num_leaves = 0\n",
        "        # Find max of self's successors\n",
        "        for move, result in self.successors(move_is_vertical):\n",
        "            new_move, new_value, new_leaves = result.min_value(\n",
        "                max_is_vertical, not move_is_vertical, limit - 1, alpha, beta)\n",
        "            num_leaves += new_leaves\n",
        "            # update variables for new max\n",
        "            if new_value > best_value:\n",
        "                best_value = new_value\n",
        "                best_move = move\n",
        "            if best_value >= beta:\n",
        "                break\n",
        "            alpha = max(alpha, best_value)\n",
        "        return best_move, best_value, num_leaves\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"static\": \"no change while the agent is deliberating\",\n",
        "\"discrete\": \"finite set of actions\",\n",
        "\"strategic\": \"next state is determined by curr state and both agents' actions\",\n",
        "\"ply\": \"one move by one player, bringing us one level deeper in the tree\",\n",
        "\"type a\": \"explore a wide but shallow portion of the tree\",\n",
        "\"type b\": \"explore a deep but narrow portion of the tree\",\n",
        "\"transpositions\": \"permutations of move sequence that end in same place\",\n",
        "\"transposition table\": \"caches heuristic value of states\",\n",
        "\"forward pruning\": \"prunes moves that appear to be mad, but could be good\",\n",
        "\"late move reduction\": \"moves that appear later in list are searched in reduced depth\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(module5_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module5_lecture_notes))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 65,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "4922c3dd-7652-4df6-b450-36d2dd860c36"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Alpha-beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same time. With random move ordering, the total number of nodes examined is about O(b^(3m/4)) \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Stochastic games introduce randomness. A game tree in backgammon must have MAX, MIN, and chance nodes. \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory deals with choosing among actions based on how desirable the immediate outcome is. A utility function U(S) assigns a number for the desirability of a certain state. \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " A rational agent either prefers every option equally, or has a clear ordering of preference. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Humans have their own unique prefs. Certainty effect means that people tend to like gains that are certain over riskiness. \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " 1997: IBM designs AI called Deep Blue that beats world Chess champion. Over time, AI has gotten better at beating humans in Chess. Google DeepMind's AlphaGo is impressive because Go has so many more possible moves than Chess does.\n",
              "\n",
              "The simplest game environment is multiagent, static, discrete, fully observable, and strategic.\n",
              "\n",
              "Properties of this game are 2 players who alternative moves, zero-sum, clear set of legal moves, and well defined outcomes (win, lose, tie). Let's call our first player MAX and our 2nd MIN. A utility function gives numerical values to terminal states (inf, -inf, 0).\n",
              "\n",
              "We can play a game by searching by\n",
              "- considering all legal successors to current state\n",
              "- evaluate each successor board position\n",
              "- pick move that leads to the best position for us\n",
              "MAX and MIN nodes:\n",
              "- When MAX moves, MAX attempts to maximize MAX's outcome\n",
              "- When MIN moves, MIN attempts to minimize MAX's outcome\n",
              "- Root level 0 is MAX\n",
              "- Assume MAX goes first (even levels MAX)\n",
              "- Evaluation function f(n) gives real number scores to board positions irrelevant of path\n",
              "- If f(n) > 0, then max is currently winning\n",
              "- Ex: for tic tac toe, f(n) = number of 3 lengths open for max - open for min\n",
              "Minimax Rule: Assume that min will respond with the best strategy for itself\n",
              "Computed Using a Recursive Process\n",
              "- Backed-up valie of each node is determined by values of its children\n",
              "- For MAX(MIN) node, the backed-up value is the max(min) of the values of its children\n",
              "Procedure\n",
              "- Until game is over:\n",
              "- Start with current pos as MAX node\n",
              "- Expand the game tree a fixed number of ply\n",
              "- Apply eval func to the leaf positions\n",
              "- Calc back-up values bottom-up\n",
              "- Pick move assigned to MAX at the root\n",
              "- Wait for min's response\n",
              "\n",
              "```\n",
              "def max_value(state):\n",
              "  if state = terminal\n",
              "    return state's utility\n",
              "  v = -inf\n",
              "  for successor of state:\n",
              "    v = max(v, min-value(successor))\n",
              "  return v\n",
              "def min_value(state):\n",
              "  if state = terminal\n",
              "    return state's utility\n",
              "  v = inf\n",
              "  for successor of state:\n",
              "    v = min(v, max-value(successor))\n",
              "  return v\n",
              "```\n",
              "Alpha-Beta Pruning:\n",
              "- During minimax, keep track of alpha (MAX's current lower bound on its outcome), and beta (MIN's current upper bound on MIN's outcome)\n",
              "- MAX will never allow a move that could lead to a worse score than a\n",
              "- MIN will never allow a move that could lead to a better score (for MAX) than B\n",
              "Stop evaluating a branch when:\n",
              "- When evaluating a MAX node, a value v >= b is backed-up\n",
              "- When evaluating a MIN node, a value v <= a is backed-up\n",
              "Alpha: best already explored option along path to the root for maximizer\n",
              "Beta: best already explored option along path to the root for minimizer\n",
              "For max_value: alpha = max(alpha, best_value)\n",
              "For min_value: beta = min(beta, best_value)\n",
              "Expectimax Search\n",
              "- Used when we don't know what the result of an action will be (dice roll, /\n",
              "unpredictable opponents, action fails)\n",
              "- Values should now reflect average-case (expectimax) outcomes\n",
              "Expectimax search: compute the average score under optimal play\n",
              "- MAX nodes are the same as minimax search\n",
              "- Chance nodes are like MIN nodes but the outcome is uncertain\n",
              "- Calculate their expected utilities\n",
              "- Take weighted average (expectation) of children\n",
              "```\n",
              "def value(state):\n",
              "  if state is terminal: return state's utility\n",
              "  if the next agent is MAX: return max-value(state)\n",
              "  if the next agent is EXP: return exp-value(state)\n",
              "def max-value(state):\n",
              "  v = -inf\n",
              "  for successor of state:\n",
              "    v = max(v, value(successor))\n",
              "  return v\n",
              "def exp-value(state):\n",
              "  v = 0\n",
              "  for successor or state:\n",
              "    p = prob(successor)\n",
              "    v += p * value(successor)\n",
              "  return v\n",
              "```\n",
              "\n",
              "AB Code:\n",
              "```\n",
              "        if self.game_over(move_is_vertical) or limit == 0:\n",
              "            return None, self.board_value(max_is_vertical), 1\n",
              "        # initialize return variables\n",
              "        best_move = 0\n",
              "        best_value = float(\"-inf\")\n",
              "        num_leaves = 0\n",
              "        # Find max of self's successors\n",
              "        for move, result in self.successors(move_is_vertical):\n",
              "            new_move, new_value, new_leaves = result.min_value(\n",
              "                max_is_vertical, not move_is_vertical, limit - 1, alpha, beta)\n",
              "            num_leaves += new_leaves\n",
              "            # update variables for new max\n",
              "            if new_value > best_value:\n",
              "                best_value = new_value\n",
              "                best_move = move\n",
              "            if best_value >= beta:\n",
              "                break\n",
              "            alpha = max(alpha, best_value)\n",
              "        return best_move, best_value, num_leaves\n",
              "```\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Static** - no change while the agent is deliberating\n",
              "* **Discrete** - finite set of actions\n",
              "* **Strategic** - next state is determined by curr state and both agents' actions\n",
              "* **Ply** - one move by one player, bringing us one level deeper in the tree\n",
              "* **Type a** - explore a wide but shallow portion of the tree\n",
              "* **Type b** - explore a deep but narrow portion of the tree\n",
              "* **Transpositions** - permutations of move sequence that end in same place\n",
              "* **Transposition table** - caches heuristic value of states\n",
              "* **Forward pruning** - prunes moves that appear to be mad, but could be good\n",
              "* **Late move reduction** - moves that appear later in list are searched in reduced depth\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 66,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP (Constraint satisfaction problems) represent the \\\n",
        "constraints that solutions must satisfy.\n",
        "\n",
        "CSP consists of:\n",
        "- Finite set of variables\n",
        "- Nonempty domain of possible values for each variable\n",
        "- Finite set of constraints\n",
        "\n",
        "A consistent assignment does not violate the constraints. A complete assignment\\\n",
        " assigns every variable to a value.\n",
        "\n",
        "\n",
        "Applications: map coloring, scheduling, floor planning, Sudoku\n",
        "Constraint graph: nodes are variable, arcs are binary constraints\n",
        "Varieties of CSPs: discrete variables (what we will focus on) vs continuous \\\n",
        "variables\n",
        "\n",
        "CSP as a search problem:\n",
        "Initial state: empty assignment\n",
        "Successor function: assign value to any unaassigned variable if there's no conflict\n",
        "Goal test: current assignment is complete\n",
        "Path cost: a constant cost for every step\n",
        "\n",
        "Solution is always found at depth n for n variables, so DFS can be used\n",
        "Variable assignments are commutative (order doesn't matter)\n",
        "Therefore it's a tree search, not a graph search\n",
        "\n",
        "We only need to consider assignments to a single variable at each node, so b = d \\\n",
        "and there are d^n leaves\n",
        "\n",
        "Heuristic 1: Most constrained variable\n",
        "Choose a variable with the fewest legal values (Minimum remaining values)\n",
        "\n",
        "Heuristic 2: Pick most constraining variable\n",
        "Tie-breaker among most constrained variables\n",
        "Choose the varaible with the most constraints on remaining variables\n",
        "\n",
        "Heuristic 3: Least constraining value\n",
        "Given a variable, choose the least constraining value: the one that rules out \\\n",
        "the fewest values in the remaining variables\n",
        "\n",
        "Heuristic 4: Forward Checking\n",
        "Keep track of remaining legal values for unassigned variables\n",
        "Terminate search when any unassigned variable has no remaining legal values\n",
        "\n",
        "Inference in CSPs\n",
        "- CSP solvers combine search and inference\n",
        "- Search: assigning a value to a variable\n",
        "- Constraint propagation (inference): eliminates possible values\n",
        "\n",
        "Local consistency\n",
        "- Node consistency: satisfies unary constraints\n",
        "- Arc consistency: satisfies binary constraints\n",
        "\n",
        "X -> Y is consistent iff for every value x of X there is some allowed Y\n",
        "If X loses a value, recheck values of neighbors\n",
        "\n",
        "Waltz Algo:\n",
        "Only inefficient part is that we check too many nodes\n",
        "\n",
        "AC3-Algo\n",
        "```\n",
        "    def infer_ac3(self):\n",
        "        queue = collections.deque(Sudoku.ARCS)\n",
        "        while queue:\n",
        "            (cell1, cell2) = queue.pop()\n",
        "            if self.remove_inconsistent_values(cell1, cell2):\n",
        "                cell_1_set = self.board[cell1]\n",
        "                if len(cell_1_set) == 0:\n",
        "                    return False\n",
        "                for neighbor in get_neighbors(cell1):\n",
        "                    if neighbor != cell2:\n",
        "                        queue.append((neighbor, cell1))\n",
        "        return True\n",
        "```\n",
        "AC-3: Worst case O(n^2d^3)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"identification problem\" : \"choosing assignments to variables\",\n",
        "\"backtracking search\": \"DFS for CSPs with single-variable assignments\"\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 67,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "6ea909ae-146d-4b43-86fa-1fc401fe8089"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " CSP (Constraint satisfaction problems) represent the constraints that solutions must satisfy.\n",
              "\n",
              "CSP consists of:\n",
              "- Finite set of variables\n",
              "- Nonempty domain of possible values for each variable\n",
              "- Finite set of constraints\n",
              "\n",
              "A consistent assignment does not violate the constraints. A complete assignment assigns every variable to a value.\n",
              "\n",
              "\n",
              "Applications: map coloring, scheduling, floor planning, Sudoku\n",
              "Constraint graph: nodes are variable, arcs are binary constraints\n",
              "Varieties of CSPs: discrete variables (what we will focus on) vs continuous variables\n",
              "\n",
              "CSP as a search problem:\n",
              "Initial state: empty assignment\n",
              "Successor function: assign value to any unaassigned variable if there's no conflict\n",
              "Goal test: current assignment is complete\n",
              "Path cost: a constant cost for every step\n",
              "\n",
              "Solution is always found at depth n for n variables, so DFS can be used\n",
              "Variable assignments are commutative (order doesn't matter)\n",
              "Therefore it's a tree search, not a graph search\n",
              "\n",
              "We only need to consider assignments to a single variable at each node, so b = d and there are d^n leaves\n",
              "\n",
              "Heuristic 1: Most constrained variable\n",
              "Choose a variable with the fewest legal values (Minimum remaining values)\n",
              "\n",
              "Heuristic 2: Pick most constraining variable\n",
              "Tie-breaker among most constrained variables\n",
              "Choose the varaible with the most constraints on remaining variables\n",
              "\n",
              "Heuristic 3: Least constraining value\n",
              "Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables\n",
              "\n",
              "Heuristic 4: Forward Checking\n",
              "Keep track of remaining legal values for unassigned variables\n",
              "Terminate search when any unassigned variable has no remaining legal values\n",
              "\n",
              "Inference in CSPs\n",
              "- CSP solvers combine search and inference\n",
              "- Search: assigning a value to a variable\n",
              "- Constraint propagation (inference): eliminates possible values\n",
              "\n",
              "Local consistency\n",
              "- Node consistency: satisfies unary constraints\n",
              "- Arc consistency: satisfies binary constraints\n",
              "\n",
              "X -> Y is consistent iff for every value x of X there is some allowed Y\n",
              "If X loses a value, recheck values of neighbors\n",
              "\n",
              "Waltz Algo:\n",
              "Only inefficient part is that we check too many nodes\n",
              "\n",
              "AC3-Algo\n",
              "```\n",
              "    def infer_ac3(self):\n",
              "        queue = collections.deque(Sudoku.ARCS)\n",
              "        while queue:\n",
              "            (cell1, cell2) = queue.pop()\n",
              "            if self.remove_inconsistent_values(cell1, cell2):\n",
              "                cell_1_set = self.board[cell1]\n",
              "                if len(cell_1_set) == 0:\n",
              "                    return False\n",
              "                for neighbor in get_neighbors(cell1):\n",
              "                    if neighbor != cell2:\n",
              "                        queue.append((neighbor, cell1))\n",
              "        return True\n",
              "```\n",
              "AC-3: Worst case O(n^2d^3)\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Identification problem** - choosing assignments to variables\n",
              "* **Backtracking search** - DFS for CSPs with single-variable assignments\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 68,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "Knowledge Base\n",
        "- Contains sentences that are written in a knowledge representation language\n",
        "- Hoth is a planet -> planet(hoth)\n",
        "\n",
        "Two kinds of sentences:\n",
        "axioms - a sentence that is given\n",
        "derived - new sentence derived from other sentences\n",
        "\n",
        "Process of deriving sentences is called inference. KB starts with some knowledge \\\n",
        "about the world and can add through observation. Knowledge based agents can also \\\n",
        "query the KB for answers.\n",
        "\n",
        "Logic: serves as general class of representations for KBA\n",
        "- KB consists of sentences in the representation language\n",
        "- Representation lang has a syntax that specifies well-formed sentences\n",
        "- Logic defines semantics of the sentences (meaning)\n",
        "- Semantics determines the truth of sentences with regards to the world\n",
        "\n",
        "Models are math abstractions that have a fixed set of truth values (true, false) \\\n",
        "for each sentence\n",
        "- If sentence a is true in model m, then m satisfies a and m is a model of a\n",
        "- M(a): set of all models of a\n",
        "- Ex: a = there's no pit in [2, 2], M(a) = all configs where [2, 2] has no pit\n",
        "\n",
        "Logical Entailment\n",
        "- One sentence follows logically from another\n",
        "- a entails b iff M(a) is a subset of M(b)\n",
        "- My pet is a cat entails that my pet is an animal\n",
        "KB = set of sentences\n",
        "\n",
        "Propositional Logic\n",
        "- Atomic sentences are represented with single prop. symbols\n",
        "- Prob symbols represent a statement that can be true or false\n",
        "- Ex: facingwest - stands for \"the agent is facing west\"\n",
        "\n",
        "Entailment and Inference\n",
        "- Entailment can be applied to derive conclusions\n",
        "- We want to design inference algos to enumerate these sentences\n",
        "\n",
        "Soundness and Completeness\n",
        "- Sound: the inference algo should only derive entailed sentences\n",
        "- Complete: should derive all entailed sentences\n",
        "\n",
        "Logical Equivalence: see table on handwritten notes\n",
        "\n",
        "Inference rules can be used to derive proofs\n",
        "\n",
        "Search for a Proof\n",
        "- Initial state: the initial KB\n",
        "- Actions: all inference rules applied to all sentences\n",
        "- Result: add sentence to KB\n",
        "- Goal: state that contains the sentence we're trying to prove\n",
        "\n",
        "Conjunctive Normal Form (CNF)\n",
        "- Resolution algorithm: proof by contradition\n",
        "- To show KB |= a, then we can show that KB (conj) not a is unsatisfiable\n",
        "\n",
        "Steps\n",
        "- Convert (KB ^ not a) into CNF\n",
        "- Apply res rule to resulting clauses\n",
        "- Resolve every pair with comp. literals to produce new clause\n",
        "- If new clause isn't present, add to the set\n",
        "- Continue until: no new clauses can be added (KB doesn't entail a) \\\n",
        "or two clauses yield the empty clause (KB does entail a)\n",
        "\n",
        "Horn Clauses and Definite Clauses\n",
        "- Res algo is complete\n",
        "- Definite clause: disj w exactly 1 positive\n",
        "- Horn clause: disj w at least 1 positive (closed under resolution)\n",
        "If you apply resolution to a horn clause, you'll get a horn clause\n",
        "\n",
        "Forward Chaining Algorithm: KB has to be a set of prop clauses with def clauses\n",
        "Entailment with Horn Clauses can be done in linear time (size of KB)\n",
        "\n",
        "Backwards Chaining: works backwards from a query and asks KB to arrive at that\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use process of reasoning over an internal representation \\\n",
        "of knowledge\",\n",
        "\"model checking\": \"enumerating all possible models that are compatible with the KB\",\n",
        "\"logical inference\": \"derive conclusions from existing sentences\",\n",
        "\"complex sentences\": \"combine simpler ones with parentheses and logical connectives\",\n",
        "\"logical equivalence\": \"a and b are true in same models\",\n",
        "\"monotonicity\": \"we can safely add to the KB without invalidating anything\",\n",
        "\"complete\": \"method derives all entailed sentences\",\n",
        "\"resolution\": \"given compl. literals, we can eliminate them until we reach resolution\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 69,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "e95b66aa-caad-4466-eb9c-4c3b5c3041ee"
      },
      "outputs": [
        {
          "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",
              " \n",
              "Knowledge Base\n",
              "- Contains sentences that are written in a knowledge representation language\n",
              "- Hoth is a planet -> planet(hoth)\n",
              "\n",
              "Two kinds of sentences:\n",
              "axioms - a sentence that is given\n",
              "derived - new sentence derived from other sentences\n",
              "\n",
              "Process of deriving sentences is called inference. KB starts with some knowledge about the world and can add through observation. Knowledge based agents can also query the KB for answers.\n",
              "\n",
              "Logic: serves as general class of representations for KBA\n",
              "- KB consists of sentences in the representation language\n",
              "- Representation lang has a syntax that specifies well-formed sentences\n",
              "- Logic defines semantics of the sentences (meaning)\n",
              "- Semantics determines the truth of sentences with regards to the world\n",
              "\n",
              "Models are math abstractions that have a fixed set of truth values (true, false) for each sentence\n",
              "- If sentence a is true in model m, then m satisfies a and m is a model of a\n",
              "- M(a): set of all models of a\n",
              "- Ex: a = there's no pit in [2, 2], M(a) = all configs where [2, 2] has no pit\n",
              "\n",
              "Logical Entailment\n",
              "- One sentence follows logically from another\n",
              "- a entails b iff M(a) is a subset of M(b)\n",
              "- My pet is a cat entails that my pet is an animal\n",
              "KB = set of sentences\n",
              "\n",
              "Propositional Logic\n",
              "- Atomic sentences are represented with single prop. symbols\n",
              "- Prob symbols represent a statement that can be true or false\n",
              "- Ex: facingwest - stands for \"the agent is facing west\"\n",
              "\n",
              "Entailment and Inference\n",
              "- Entailment can be applied to derive conclusions\n",
              "- We want to design inference algos to enumerate these sentences\n",
              "\n",
              "Soundness and Completeness\n",
              "- Sound: the inference algo should only derive entailed sentences\n",
              "- Complete: should derive all entailed sentences\n",
              "\n",
              "Logical Equivalence: see table on handwritten notes\n",
              "\n",
              "Inference rules can be used to derive proofs\n",
              "\n",
              "Search for a Proof\n",
              "- Initial state: the initial KB\n",
              "- Actions: all inference rules applied to all sentences\n",
              "- Result: add sentence to KB\n",
              "- Goal: state that contains the sentence we're trying to prove\n",
              "\n",
              "Conjunctive Normal Form (CNF)\n",
              "- Resolution algorithm: proof by contradition\n",
              "- To show KB |= a, then we can show that KB (conj) not a is unsatisfiable\n",
              "\n",
              "Steps\n",
              "- Convert (KB ^ not a) into CNF\n",
              "- Apply res rule to resulting clauses\n",
              "- Resolve every pair with comp. literals to produce new clause\n",
              "- If new clause isn't present, add to the set\n",
              "- Continue until: no new clauses can be added (KB doesn't entail a) or two clauses yield the empty clause (KB does entail a)\n",
              "\n",
              "Horn Clauses and Definite Clauses\n",
              "- Res algo is complete\n",
              "- Definite clause: disj w exactly 1 positive\n",
              "- Horn clause: disj w at least 1 positive (closed under resolution)\n",
              "If you apply resolution to a horn clause, you'll get a horn clause\n",
              "\n",
              "Forward Chaining Algorithm: KB has to be a set of prop clauses with def clauses\n",
              "Entailment with Horn Clauses can be done in linear time (size of KB)\n",
              "\n",
              "Backwards Chaining: works backwards from a query and asks KB to arrive at that\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge-based agents** - use process of reasoning over an internal representation of knowledge\n",
              "* **Model checking** - enumerating all possible models that are compatible with the KB\n",
              "* **Logical inference** - derive conclusions from existing sentences\n",
              "* **Complex sentences** - combine simpler ones with parentheses and logical connectives\n",
              "* **Logical equivalence** - a and b are true in same models\n",
              "* **Monotonicity** - we can safely add to the KB without invalidating anything\n",
              "* **Complete** - method derives all entailed sentences\n",
              "* **Resolution** - given compl. literals, we can eliminate them until we reach resolution\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 70,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "793b09e3-ec80-4a8f-ce7b-5c6730203837"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Intelligence defined relative to psychology focuses on observing human behavior and thought processes, while intelligence using a rationalist approach involves a combination of math and engineering.\n",
              "\n",
              "The first approach is acting humanly (turing test approach). The turing test is successful if a human asks a computer and a human questions and is unable to differentiate between the two answers. Most AI researchers don't like the Turing test. \n",
              "\n",
              "The second approach is thinking humanly, which focuses on understanding how humans think. Once we understand the mind, we can formulate this into a computer program (cog sci approach).\n",
              "\n",
              "Third approach is thinking rationally, which is using logic and probability to generate intelligent behavior.\n",
              "\n",
              "The 4th approach is acting rationally. A rational agent is one that acts so as to achieve the best expected outcome.\n",
              " \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Turing argued that human behvaior is too complex to be captured by any formal set of rules. Humans use informal guidelines that can't be captured by a set of rules and codified in a computer program. Computers are limited by the fact that they are not exposed to the same type of environment as humans (ex: a person understands a dog bc they have interacted with one in person).\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Humans have a clear advantage over machiens in the matter of modeling experiences. There's a debate over consciousness of machines. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent's choice of action depends on its percept sequence.  \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " With humans, they choose actions that are desirable from their point of view. Machines do not have desires and prefs on their own. It's good to design perf measure based on what one actually wants to be achieved.\n",
              "\n",
              "Rationality depends on performance measure, agent's prior knowledge of the environment, actions, and the percent sequence so far. Rational agents can learn from their environment. An agent that relies of prior knowledge rather than percepts and learning lacks autonomy. Rational agents should be autonomous.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " An environment is fully observable if the sensors give the agent a complete view of the environment at any given time. The agent wouldn't need to internally keep track of the world. Partially unobservable means that parts of the state are missing from sensor data.\n",
              "\n",
              "Competitive environments (two agents want the same parking spot) vs cooperative (two cars don't want to crash). Stochastic if it deals with explicit probabilities and nondeterminstic if the possibilities are listed without being quantified.\n",
              "\n",
              "Episodic task environments have that future decisions are independent of past actions, which is the opposite of sequential environments.\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " The simple reflex agent selects actions using only the current percept. Infinite loops can be avoided if we introduce randomness. In single-agent environments, randomization is typically not rational.\n",
              "\n",
              "Transition model can describe how the world works. A sensor model would tell us that when a car initiates breaking. The transition and sensor model allow an agent to keep track of the state of the world (model-based agent). Goal based agents has states that are desirable (use search or planning). The learning element uses feedback on how agent is doing to modify the performance element. A critic lets the learning element know how the agent is doing so far.\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " The agent program runs on physical architecture to get f (agent function). We want to avoid having a table that maps every seq to every action bc this is computationally expensive. \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Weak ai** - machines acting as if they are intelligent\n",
              "* **Strong ai** - machines consciously thinking\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - content the agent's sensors perceive\n",
              "* **Actuators** - how agents act upon their environment\n",
              "* **Percept sequence** - history of agent's perceptions\n",
              "* **Agent function** - maps percept sequence to an action\n",
              "* **Agent program** - implements an agent function\n",
              "* **Rational agent** - for each PS, RA selects an action expected to max PM.\n",
              "* **Consequentialism** - what are the consequences of an action\n",
              "* **Performance measure** - evaluates the desirability of a sequence of states\n",
              "* **Omniscient agent** - knows the actual outcome of its actions\n",
              "* **Information gathering** - choosing actions in order to change future percepts\n",
              "* **Task environment** - PEAS (performance, environment, actuators, sensors)\n",
              "* **Unobservable environment** - agent has no sensors\n",
              "* **Deterministic** - next state is completely determined by the current state + action\n",
              "* **Undeterministic** - there is uncertainty in the environment\n",
              "* **Dynamic vs static** - does environment change while agent deliberates\n",
              "* **Semidynamic** - environment is static but agent's PM changes over time\n",
              "* **Known vs unknown** - whether outcomes for all actions are given\n",
              "* **Environment class** - many environments can be drawn from one\n",
              "* **Agent architecture** - allows agent to run program and get an action\n",
              "* **Utility funciton** - internalization of the agent's PM\n",
              "* **Model-free agent** - learns best actions without learning how it affects environment\n",
              "* **Problem generator** - suggests actions that allows the agent to learn from new exp.\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " Python was developed by Guido van Rossum in 1989. Python has fast development, portability, built-in types and support libraries. REPL allows you to run python from command line. \n",
              " \n",
              "Use \\ to go to a new line prematurely. All data is treated as objects. The object will be garbage collected once the object is unreachable in the program. \n",
              "\n",
              "Strong typing means that every object has a fixed type, and we can't perform operations like (\"hello\" + 2) that aren't compatible. We can do type(object) or isInstance(object, type). \n",
              "\n",
              "Types: int, float, str, tuple, dict, list, bool, None, function. Python uses dynamic typing which means types are decided at runtime when vars first come into existence. If reassigned, type(var) is updated.\n",
              "\n",
              "Use (and, or, not) instead of symbols.\n",
              "\n",
              "Modulo (%), power (**), boolean (True).\n",
              "\n",
              "String use single or double quotes. String concat(+). No need to escape special characters by using r which means raw (r'\n",
              "')\n",
              "```\n",
              "print(\"%s can speak %d languages\" % (\"C3PO\", 6000))\n",
              "```\n",
              "String are immutable, lists are mutable and ordered, == checks whether variables point to obj of same value, is checks whether they point to the same value. y = x[:] gets a shallow copy of any sequence (new obj of same value).\n",
              "```\n",
              "tup = (23, 'abc')\n",
              "li = ['abc', 12]\n",
              "tup[1] = 'abc'\n",
              "tup[-1] = 'abc' # negative lookup starting from right at -1\n",
              "```\n",
              "Slicing:\n",
              "```\n",
              "t = (1, 'a', 4, (2, 2), 'def')\n",
              "t[1:4] = ('a', 4, (2, 2))\n",
              "t[1:-1] = ('a', 4, (2, 2))\n",
              "t[1:-1:2] = ('a', (2, 2))\n",
              "t[:2] = (1, 'a')\n",
              "t[2:] = (4, (2, 2), 'def')\n",
              "```\n",
              "Operations on List:\n",
              "```\n",
              "list.insert(2, 'i'): add an i at index 2\n",
              "list.index('b'): get the index of 1st occurrence\n",
              "list.count('b'): count number of b's in the list\n",
              "list.remove('b'): remove first occurrence\n",
              "list.reverse(): reverse in place\n",
              "list.sort(): sort in place # don't need list = list.sort()\n",
              "sorted(list): returns a copy yhat is sorted\n",
              "[1, 2] + [3, 4] = [4, 6]\n",
              "```\n",
              "Operations on Strings:\n",
              "```\n",
              "words = s.split(\" \")\n",
              "sentence = \" \".join(words)\n",
              "s.upper()\n",
              "s.lower()\n",
              "s.capitalize()\n",
              "```\n",
              "Dictionaries are unordered and use hashing, therefore keys must be immutable.\n",
              "```\n",
              "dict = {'bob': 5, 'joe': 7}\n",
              "dict['bob'] = 5\n",
              "dict['bob'] = 11\n",
              "# following all return lists\n",
              "dict.keys()\n",
              "dict.values()\n",
              "dict.items()\n",
              "```\n",
              "defaultdict automatically initializes nonexistent dict values.\n",
              "\n",
              "You can provide default values for a function's arguments, which are then optional (for ex: funOne(b, c = 5)). You can call arguments out of order by doing funOne(4, c = 1, b = 7), where b = 7 is a keyword argument. To accept a variable number of non-keyword args you can do print(*args). For a variable number of keyword arguments, it's **args.\n",
              "\n",
              "For memoization, default parameter values are evaluted only when the def statement they belong to is first executed.\n",
              "\n",
              "Functions are first-class objects, that can pass functions as arguments to other functions, return function, or assign functions to variables or store them in data structures.\n",
              "\n",
              "Creating a class:\n",
              "```\n",
              "class Student:\n",
              "  univ = \"penn\"\n",
              "  def __init__(self, name, credit_units):\n",
              "    self.student_name = name\n",
              "    self.student_units = credit_units\n",
              "  def increase_cu(self):\n",
              "    self.student_units += 1\n",
              "student1 = Student(\"Skylar\", 5)\n",
              "student1.increase_cu()\n",
              "Student.increase_cu(student1)\n",
              "```\n",
              "Define a subclass where the superclass is Student\n",
              "```\n",
              "class AI_Student(Student):\n",
              "  def __init__(self, name, credit_units)\n",
              "    Student.__init__(self, name, credit_units)\n",
              "  def increase_cu(self):\n",
              "    self.increase_cu += 2\n",
              "```\n",
              "Multiple inheritance is supported in python. The only time you should explicitly pass self as an arg is when calling a method of an ancestor.\n",
              "\n",
              "When printing ints using concatenation, use str(56) for example.\n",
              "```\n",
              "def __str__(self):\n",
              "  \"I am \" + self.age + \" years old!\"\n",
              "print(s) # gives \"I am 20 years old!\"\n",
              "```\n",
              "Python's main method is __main__\n",
              "```\n",
              "if __name__ == '__main__':\n",
              "```\n",
              "For loops:\n",
              "```\n",
              "list(range(5)) = [0, 1, 2, 3, 4]\n",
              "# list comprehension\n",
              "squares = [x * x for x in nums]\n",
              "new_list = [el * 2 for el in li if el > 5]\n",
              "d = {k: v for k, v in lst}\n",
              "```\n",
              "Iterable objects can be used in a for loop because they have an __iter__ magic method, which converts them to iterator objects.\n",
              "Python iterators do not have a hasnext() method. You can catch the stopIteration exception.\n",
              "Generators:\n",
              "```\n",
              "def f(n):\n",
              "  yield n\n",
              "  yield n + 1\n",
              "type(f(10)) == <class 'generator'>\n",
              "[i for i in f(6)] = [6, 7]\n",
              "gen = f(5)\n",
              "next(gen)\n",
              "next(gen)\n",
              "```\n",
              "Benefits of generators: less code, maintains local state, calcs values as needed, avoids storing entire sequence, good for aggregation, good for inf sequences, bad for inspecting individual values.\n",
              "```\n",
              "while True:\n",
              "  try:\n",
              "    print(g.__next__())\n",
              "  except StopIteration:\n",
              "    print('Done')\n",
              "    break\n",
              "```\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - ability of objects to change their value\n",
              "* **Tuple** - immutable ordered sequence of items (can be of mixed types)\n",
              "* **Higher order functions** - functions that take functions as input\n",
              "* **Subclass** - class extends the definition of another class\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " In an unknown environment, an agent can do no better but to choose an action at random. We want to use abstraction when possible.\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " TSP is a touring problem (describes set of locations that must be visited). \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " For best-first search, we expand a node n that has min value of some evaluation function, f(n). We check when we pop the node from the priority queue if it's the goal node. For BFS and DFS, check if each child node is the goal. \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Uniform-cost search/Dijkstra's is using best first search where our evaluation function is the cost of the path from the root to the current node. The time complexity of UCS is O(b^(1 + floor(C / e))) where X is the cost of the optimal solution and e is a lower bound on the cost of each action (must be positive). UCS is complete and optimal.\n",
              "\n",
              "DFS can be implemented as a call to best first search where eval func f is the negative of the depth. This is not how it usually gets implemented though. In cyclic state spaces, DFS can end up in an infinite loop.\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " A problem-solving agent must plan ahead and the process it undergoes is referred to as search. It considers a sequence of actions that are a path to the goal state (solution).\n",
              "\n",
              "An example search problem is the 8-puzzle (fully observable and deterministic). There are 9! states. There are 4 actions at any given time. Our performance measure would be to minimize total moves.\n",
              "\n",
              "To define a search problem, we need the following: states, initial state, actions, transition model: if we apply an action to a state we get back another state, path cost/action cost function (performance measure), and goal states.\n",
              "\n",
              "Tree search treats different paths to the same node as distinct. By failing to recognize repeated states, a learning problem can become exponential. We can fix this by creating an explored set. Graph search checks for redundant states and doesn't add them to the frontier (but this requires more space).\n",
              "\n",
              "We evaluate a search algo in terms of completeness, optimality, and time and space complexity. Depth-limited search is DFS but we only explore up to l depth. If l = d, then optimal, if l < d, then incomplete, if l > d then not optimal. The time complexity is for b = branching factor, O(b^l) and the space complexity will be O(bl).\n",
              " \n",
              "Iterative deepening search does depth limited search until it returns a solution by increasing l on every iteration. This is complete and optimal (if cost = 1). Time: O(b^d) and space O(bd).\n",
              "\n",
              "Implement BFS using a FIFO queue. DFS frontier is LIFO. M is the maximum length of any path in the state space. D is the depth of the shallowest goal node. Root node = depth 0. For bidirectional search, we need two frontiers and two reaches states tables.\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State space** - set of all states reachable from the initial state\n",
              "* **Search tree** - way of representing the paths that a search algo has explored\n",
              "* **Frontier** - those states that are available for expanding\n",
              "* **Complete** - finds a solution if one exists and none if not\n",
              "* **Optimal** - always finds the lowest cost solution\n",
              "* **Uninformed search** - all non-goal nodes look equally good\n",
              "* **Open-loop system** - if the agent knows the solution to a problem, it can ignore its percepts\n",
              "* **Standardized problem** - used by researchers as a performance benchmark\n",
              "* **Early goal test** - check if a node is a sol as soon as it's generated (BFS, DFS)\n",
              "* **Late goal test** - don't check if a node is a sol until it's popped (best first search)\n",
              "* **Backtracking search** - only one successor is generated at a time\n",
              "* **Bidirectional search** - searches forward from initial state/ backtracks from goal\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " A heuristic is consistent if for any node n and any successor n'generated by action a, h(n) <= c(n, a, n') + h(n'). Every consistent heuristic is admissible.\n",
              "\n",
              "A* expands nodes where f(n) < C (surely expanded), sometimes expands nodes where f(n) = C, and never expands the rest of the nodes. A* with a  consistent heuristic is optimally efficient in that it always expands all nodes that are surely expanded by A*.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " A dominant heuristic will always expand at most the same number of nodes as a worse heuristic. \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform cost search uses a pr queue ordered by g(n) (path cost function). In this case, G(n) gives the cost of going from starting node to node n. A new concept is a heuristic function h(n), which estimates the distance/cost from node n to the goal node.\n",
              "\n",
              "Greedy best first search is not optimal or complete (can get stuck in loops).\n",
              "\n",
              "A* search is optimal and complete. Time complexity is O(b^d) where b is the solution to N + 1 = 1 + b + b^2 + ... + b^d where N = num of expanded nodes. Remember that we don't check in A* if the node is the goal until we pop it.\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Greedy best first search** - expand node with lowest h(n)\n",
              "* **A* search** - best form of best first search w/ f(n) = h(n) + g(n)\n",
              "* **Admissible heuristic** - never overestimates cost to reach the goal\n",
              "* **Relaxed problems** - create h(n) by relaxing constraints\n",
              "* **Monotonic** - paths costs strictly increase as you go along a path\n",
              "* **Pruning** - eliminating non-optimal possibilities from consideration without examining\n",
              "* **Bounded suboptimal search** - look for sol that is within factor W of optimal cost\n",
              "* **Bounded-cost search** - find a solution with cost less than some C\n",
              "* **Unbounded-cost search** - accept a solution of any cost\n",
              "* **Speedy search** - solves unbounded cost with h(n) = num actions to reach goal\n",
              "* **Memory-bounded search** - remove states from reached when they are no longer needed\n",
              "* **Reference counts** - keep track of num of times a node has been reached\n",
              "* **Beam search** - limits size of frontier by keeping best options\n",
              "* **Recursive best-first search** - uses f_limit to keep track of f-value of best alt. path\n",
              "* **Backed-up value** - best f-value of a node's children\n",
              "* **Sma*** - does A* until memory is full, when it deletes worst leaf node\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Alpha-beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same time. With random move ordering, the total number of nodes examined is about O(b^(3m/4)) \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Stochastic games introduce randomness. A game tree in backgammon must have MAX, MIN, and chance nodes. \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory deals with choosing among actions based on how desirable the immediate outcome is. A utility function U(S) assigns a number for the desirability of a certain state. \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " A rational agent either prefers every option equally, or has a clear ordering of preference. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Humans have their own unique prefs. Certainty effect means that people tend to like gains that are certain over riskiness. \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " 1997: IBM designs AI called Deep Blue that beats world Chess champion. Over time, AI has gotten better at beating humans in Chess. Google DeepMind's AlphaGo is impressive because Go has so many more possible moves than Chess does.\n",
              "\n",
              "The simplest game environment is multiagent, static, discrete, fully observable, and strategic.\n",
              "\n",
              "Properties of this game are 2 players who alternative moves, zero-sum, clear set of legal moves, and well defined outcomes (win, lose, tie). Let's call our first player MAX and our 2nd MIN. A utility function gives numerical values to terminal states (inf, -inf, 0).\n",
              "\n",
              "We can play a game by searching by\n",
              "- considering all legal successors to current state\n",
              "- evaluate each successor board position\n",
              "- pick move that leads to the best position for us\n",
              "MAX and MIN nodes:\n",
              "- When MAX moves, MAX attempts to maximize MAX's outcome\n",
              "- When MIN moves, MIN attempts to minimize MAX's outcome\n",
              "- Root level 0 is MAX\n",
              "- Assume MAX goes first (even levels MAX)\n",
              "- Evaluation function f(n) gives real number scores to board positions irrelevant of path\n",
              "- If f(n) > 0, then max is currently winning\n",
              "- Ex: for tic tac toe, f(n) = number of 3 lengths open for max - open for min\n",
              "Minimax Rule: Assume that min will respond with the best strategy for itself\n",
              "Computed Using a Recursive Process\n",
              "- Backed-up valie of each node is determined by values of its children\n",
              "- For MAX(MIN) node, the backed-up value is the max(min) of the values of its children\n",
              "Procedure\n",
              "- Until game is over:\n",
              "- Start with current pos as MAX node\n",
              "- Expand the game tree a fixed number of ply\n",
              "- Apply eval func to the leaf positions\n",
              "- Calc back-up values bottom-up\n",
              "- Pick move assigned to MAX at the root\n",
              "- Wait for min's response\n",
              "\n",
              "```\n",
              "def max_value(state):\n",
              "  if state = terminal\n",
              "    return state's utility\n",
              "  v = -inf\n",
              "  for successor of state:\n",
              "    v = max(v, min-value(successor))\n",
              "  return v\n",
              "def min_value(state):\n",
              "  if state = terminal\n",
              "    return state's utility\n",
              "  v = inf\n",
              "  for successor of state:\n",
              "    v = min(v, max-value(successor))\n",
              "  return v\n",
              "```\n",
              "Alpha-Beta Pruning:\n",
              "- During minimax, keep track of alpha (MAX's current lower bound on its outcome), and beta (MIN's current upper bound on MIN's outcome)\n",
              "- MAX will never allow a move that could lead to a worse score than a\n",
              "- MIN will never allow a move that could lead to a better score (for MAX) than B\n",
              "Stop evaluating a branch when:\n",
              "- When evaluating a MAX node, a value v >= b is backed-up\n",
              "- When evaluating a MIN node, a value v <= a is backed-up\n",
              "Alpha: best already explored option along path to the root for maximizer\n",
              "Beta: best already explored option along path to the root for minimizer\n",
              "For max_value: alpha = max(alpha, best_value)\n",
              "For min_value: beta = min(beta, best_value)\n",
              "Expectimax Search\n",
              "- Used when we don't know what the result of an action will be (dice roll, /\n",
              "unpredictable opponents, action fails)\n",
              "- Values should now reflect average-case (expectimax) outcomes\n",
              "Expectimax search: compute the average score under optimal play\n",
              "- MAX nodes are the same as minimax search\n",
              "- Chance nodes are like MIN nodes but the outcome is uncertain\n",
              "- Calculate their expected utilities\n",
              "- Take weighted average (expectation) of children\n",
              "```\n",
              "def value(state):\n",
              "  if state is terminal: return state's utility\n",
              "  if the next agent is MAX: return max-value(state)\n",
              "  if the next agent is EXP: return exp-value(state)\n",
              "def max-value(state):\n",
              "  v = -inf\n",
              "  for successor of state:\n",
              "    v = max(v, value(successor))\n",
              "  return v\n",
              "def exp-value(state):\n",
              "  v = 0\n",
              "  for successor or state:\n",
              "    p = prob(successor)\n",
              "    v += p * value(successor)\n",
              "  return v\n",
              "```\n",
              "\n",
              "AB Code:\n",
              "```\n",
              "        if self.game_over(move_is_vertical) or limit == 0:\n",
              "            return None, self.board_value(max_is_vertical), 1\n",
              "        # initialize return variables\n",
              "        best_move = 0\n",
              "        best_value = float(\"-inf\")\n",
              "        num_leaves = 0\n",
              "        # Find max of self's successors\n",
              "        for move, result in self.successors(move_is_vertical):\n",
              "            new_move, new_value, new_leaves = result.min_value(\n",
              "                max_is_vertical, not move_is_vertical, limit - 1, alpha, beta)\n",
              "            num_leaves += new_leaves\n",
              "            # update variables for new max\n",
              "            if new_value > best_value:\n",
              "                best_value = new_value\n",
              "                best_move = move\n",
              "            if best_value >= beta:\n",
              "                break\n",
              "            alpha = max(alpha, best_value)\n",
              "        return best_move, best_value, num_leaves\n",
              "```\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Static** - no change while the agent is deliberating\n",
              "* **Discrete** - finite set of actions\n",
              "* **Strategic** - next state is determined by curr state and both agents' actions\n",
              "* **Ply** - one move by one player, bringing us one level deeper in the tree\n",
              "* **Type a** - explore a wide but shallow portion of the tree\n",
              "* **Type b** - explore a deep but narrow portion of the tree\n",
              "* **Transpositions** - permutations of move sequence that end in same place\n",
              "* **Transposition table** - caches heuristic value of states\n",
              "* **Forward pruning** - prunes moves that appear to be mad, but could be good\n",
              "* **Late move reduction** - moves that appear later in list are searched in reduced depth\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " CSP (Constraint satisfaction problems) represent the constraints that solutions must satisfy.\n",
              "\n",
              "CSP consists of:\n",
              "- Finite set of variables\n",
              "- Nonempty domain of possible values for each variable\n",
              "- Finite set of constraints\n",
              "\n",
              "A consistent assignment does not violate the constraints. A complete assignment assigns every variable to a value.\n",
              "\n",
              "\n",
              "Applications: map coloring, scheduling, floor planning, Sudoku\n",
              "Constraint graph: nodes are variable, arcs are binary constraints\n",
              "Varieties of CSPs: discrete variables (what we will focus on) vs continuous variables\n",
              "\n",
              "CSP as a search problem:\n",
              "Initial state: empty assignment\n",
              "Successor function: assign value to any unaassigned variable if there's no conflict\n",
              "Goal test: current assignment is complete\n",
              "Path cost: a constant cost for every step\n",
              "\n",
              "Solution is always found at depth n for n variables, so DFS can be used\n",
              "Variable assignments are commutative (order doesn't matter)\n",
              "Therefore it's a tree search, not a graph search\n",
              "\n",
              "We only need to consider assignments to a single variable at each node, so b = d and there are d^n leaves\n",
              "\n",
              "Heuristic 1: Most constrained variable\n",
              "Choose a variable with the fewest legal values (Minimum remaining values)\n",
              "\n",
              "Heuristic 2: Pick most constraining variable\n",
              "Tie-breaker among most constrained variables\n",
              "Choose the varaible with the most constraints on remaining variables\n",
              "\n",
              "Heuristic 3: Least constraining value\n",
              "Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables\n",
              "\n",
              "Heuristic 4: Forward Checking\n",
              "Keep track of remaining legal values for unassigned variables\n",
              "Terminate search when any unassigned variable has no remaining legal values\n",
              "\n",
              "Inference in CSPs\n",
              "- CSP solvers combine search and inference\n",
              "- Search: assigning a value to a variable\n",
              "- Constraint propagation (inference): eliminates possible values\n",
              "\n",
              "Local consistency\n",
              "- Node consistency: satisfies unary constraints\n",
              "- Arc consistency: satisfies binary constraints\n",
              "\n",
              "X -> Y is consistent iff for every value x of X there is some allowed Y\n",
              "If X loses a value, recheck values of neighbors\n",
              "\n",
              "Waltz Algo:\n",
              "Only inefficient part is that we check too many nodes\n",
              "\n",
              "AC3-Algo\n",
              "```\n",
              "    def infer_ac3(self):\n",
              "        queue = collections.deque(Sudoku.ARCS)\n",
              "        while queue:\n",
              "            (cell1, cell2) = queue.pop()\n",
              "            if self.remove_inconsistent_values(cell1, cell2):\n",
              "                cell_1_set = self.board[cell1]\n",
              "                if len(cell_1_set) == 0:\n",
              "                    return False\n",
              "                for neighbor in get_neighbors(cell1):\n",
              "                    if neighbor != cell2:\n",
              "                        queue.append((neighbor, cell1))\n",
              "        return True\n",
              "```\n",
              "AC-3: Worst case O(n^2d^3)\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Identification problem** - choosing assignments to variables\n",
              "* **Backtracking search** - DFS for CSPs with single-variable assignments\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " \n",
              "Knowledge Base\n",
              "- Contains sentences that are written in a knowledge representation language\n",
              "- Hoth is a planet -> planet(hoth)\n",
              "\n",
              "Two kinds of sentences:\n",
              "axioms - a sentence that is given\n",
              "derived - new sentence derived from other sentences\n",
              "\n",
              "Process of deriving sentences is called inference. KB starts with some knowledge about the world and can add through observation. Knowledge based agents can also query the KB for answers.\n",
              "\n",
              "Logic: serves as general class of representations for KBA\n",
              "- KB consists of sentences in the representation language\n",
              "- Representation lang has a syntax that specifies well-formed sentences\n",
              "- Logic defines semantics of the sentences (meaning)\n",
              "- Semantics determines the truth of sentences with regards to the world\n",
              "\n",
              "Models are math abstractions that have a fixed set of truth values (true, false) for each sentence\n",
              "- If sentence a is true in model m, then m satisfies a and m is a model of a\n",
              "- M(a): set of all models of a\n",
              "- Ex: a = there's no pit in [2, 2], M(a) = all configs where [2, 2] has no pit\n",
              "\n",
              "Logical Entailment\n",
              "- One sentence follows logically from another\n",
              "- a entails b iff M(a) is a subset of M(b)\n",
              "- My pet is a cat entails that my pet is an animal\n",
              "KB = set of sentences\n",
              "\n",
              "Propositional Logic\n",
              "- Atomic sentences are represented with single prop. symbols\n",
              "- Prob symbols represent a statement that can be true or false\n",
              "- Ex: facingwest - stands for \"the agent is facing west\"\n",
              "\n",
              "Entailment and Inference\n",
              "- Entailment can be applied to derive conclusions\n",
              "- We want to design inference algos to enumerate these sentences\n",
              "\n",
              "Soundness and Completeness\n",
              "- Sound: the inference algo should only derive entailed sentences\n",
              "- Complete: should derive all entailed sentences\n",
              "\n",
              "Logical Equivalence: see table on handwritten notes\n",
              "\n",
              "Inference rules can be used to derive proofs\n",
              "\n",
              "Search for a Proof\n",
              "- Initial state: the initial KB\n",
              "- Actions: all inference rules applied to all sentences\n",
              "- Result: add sentence to KB\n",
              "- Goal: state that contains the sentence we're trying to prove\n",
              "\n",
              "Conjunctive Normal Form (CNF)\n",
              "- Resolution algorithm: proof by contradition\n",
              "- To show KB |= a, then we can show that KB (conj) not a is unsatisfiable\n",
              "\n",
              "Steps\n",
              "- Convert (KB ^ not a) into CNF\n",
              "- Apply res rule to resulting clauses\n",
              "- Resolve every pair with comp. literals to produce new clause\n",
              "- If new clause isn't present, add to the set\n",
              "- Continue until: no new clauses can be added (KB doesn't entail a) or two clauses yield the empty clause (KB does entail a)\n",
              "\n",
              "Horn Clauses and Definite Clauses\n",
              "- Res algo is complete\n",
              "- Definite clause: disj w exactly 1 positive\n",
              "- Horn clause: disj w at least 1 positive (closed under resolution)\n",
              "If you apply resolution to a horn clause, you'll get a horn clause\n",
              "\n",
              "Forward Chaining Algorithm: KB has to be a set of prop clauses with def clauses\n",
              "Entailment with Horn Clauses can be done in linear time (size of KB)\n",
              "\n",
              "Backwards Chaining: works backwards from a query and asks KB to arrive at that\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge-based agents** - use process of reasoning over an internal representation of knowledge\n",
              "* **Model checking** - enumerating all possible models that are compatible with the KB\n",
              "* **Logical inference** - derive conclusions from existing sentences\n",
              "* **Complex sentences** - combine simpler ones with parentheses and logical connectives\n",
              "* **Logical equivalence** - a and b are true in same models\n",
              "* **Monotonicity** - we can safely add to the KB without invalidating anything\n",
              "* **Complete** - method derives all entailed sentences\n",
              "* **Resolution** - given compl. literals, we can eliminate them until we reach resolution\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
