{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "561aefd5-abb0-4e82-85a6-5cf96dce1e42"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b753167e-0675-4e42-d005-0429f2653a35"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" There are two dimensions when it comes to designing AI: \\\n",
        "human-like vs. rational and thought vs. behavior. The four combinations are \\\n",
        "different types of AI (human-like thinker, human-like behaver, rational thinker, \\\n",
        "and rational behaver). Machine intelligence can be evaluated through a Turing \\\n",
        "test (in which humans have to determine whether they're communicating with a \\\n",
        "human or machine). Total Turing tests also involve the machine having to \\\n",
        "physically imitate a human. The field of AI has mainly focused on studying and \\\n",
        "creating agents that act rationally (the rational behaver combination), that \\\n",
        "do the right thing. Perfect rationality is often infeasible as it's too \\\n",
        "computationally taxing to consider every possibility, so limited rationality \\\n",
        "(acting optimally given that you can't consider as many possibilities as you'd \\\n",
        "like) is often seen instead. When designing AI, we must make sure that we set \\\n",
        "its values and objectives to match our own, otherwise the machines might take\n",
        "uncomfortable actions to achieve their goals. This process is called the value \\\n",
        "alignment problem. In the end, we want AI that benefit humanity (that pursue \\\n",
        "our goals for us, not theirs).\"\"\" \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 = \"\"\"Philosopher John Searle distinguished between weak AI (machines \\\n",
        "that could only pretend to be intelligent) and strong AI (machines that were \\\n",
        "actually intelligent, machines that consciously thought). This strong AI is \\\n",
        "what's now referred to as human-level AI or general AI. Turing (with his argument \\\n",
        "from informality of behavior) believed that human behavior was too complicated \\\n",
        "to be described by a formal set of rules, meaning that it would be impossible to \\\n",
        "program a machine with human behavior. Arguments from disability claim that \\\n",
        "machines cannot attain human-like minds because they cannot do various things \\\n",
        "that humans can (such as fall in love or have a sense of humor). Some have said \\\n",
        "that machines are mentally inferior to humans because since machines are formal \\\n",
        "systems, they fall prety to the incompleteness theorem and cannot establish the \\\n",
        "truth of certain sentences (but there are certain sentences that humans cannot \\\n",
        "determine as true or false, humans can't prove impossible to prove statements \\\n",
        "either, so it's an invalid argument). AI researchers haven't really focused on \\\n",
        "AI chatbots (no AI has still passed the Turing test with a well-trained judge), \\\n",
        "instead preferring to design AI for games (chess, StarCraftII) and other tasks \\\n",
        "such as object identification.\"\"\"\n",
        "chapter27_2 = \"\"\"John Searle's Chinese Room scenario involves a human in a room \\\n",
        "with a rule book that explains in English which Chinese symbols to output for a \\\n",
        "given input of Chinese symbols. The room receives some symbol inputs, the human \\\n",
        "uses the rule book to make and output correct symbol outputs. To an outsider, it \\\n",
        "looks like the room is able to generate intelligent Chinese responses to Chinese \\\n",
        "sentences, but the guy in the room doesn't know Chinese, the rule book doesn't \\\n",
        "know Chinese. There's no understanding of Chinese, only very extensive pattern \\\n",
        "matching. Searle explains that this is essentially what computers do, so computers \\\n",
        "have no real understanding, they're just matching inputs to outputs. There's also \\\n",
        "a debate over whether machines can have consciousness or qualia. We can't give \\\n",
        "machines human-like consciousnes yet, but we can imbue them with smaller, \\\n",
        "individual parts of consciousness like awareness.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"Anything that perceives its environment via sensors and then takes \\\n",
        "action via actuators is considered an agent. Percepts are whatever information \\\n",
        "an agent receives through its sensors. The ordered history of all the percepts \\\n",
        "the agent has received over time is called the percept sequence. If you map every \\\n",
        "possible percept sequence to a valid action, you have an agent function (which \\\n",
        "completely describes the agent's behavior). The actual implementation of this \\\n",
        "agent function is the agent program (runs on some physical system).\"\"\"\n",
        "chapter2_2 = \"\"\"If an agent always does the right thing, they are a rational \\\n",
        "agent. Usually, the right thing is evaluated through a consequentialist lens. \\\n",
        "If the sequence of states that results from the agent's chosen sequence of actions \\\n",
        "is desirable, then the agent has done a good job. We quantify this with a \\\n",
        "performance measure that will evaluate any sequence of states. When desiging a \\\n",
        "performance measure, it's better to align it with what you want to be done in \\\n",
        "the environment as opposed to how you think the AI should act. What action is \\\n",
        "rational depends on the performance measure, the agent's prior knowledge of \\\n",
        "the environment, the legal actions the agent can take, and the agent's percept \\\n",
        "sequence. Rationality is not the same as perfection. Rationality entails maximizing \\\n",
        "expected performance given what we currently know. A crucial part of rationality \\\n",
        "is information gathering (taking some actions in order to get more info and percepts \\\n",
        "to better advise future actions). Rational agents should be autonomous (meaning \\\n",
        "they're capable of learning so as to expand upon their initially incorrect or \\\n",
        "incomplete prior knowledge).\"\"\"\n",
        "chapter2_3 = \"\"\"The task environemnt (PEAS: Performance, Environment, Actuators, \\\n",
        "Sensors) needs to be specified when creating an agent. Task environments can be \\\n",
        "fully observable (sensors receive all info relevant to choosing an action) or \\\n",
        "partially observable (some info is hidden). They can be single-agent or multi-agent \\\n",
        "(referring to the number of agents trying to maximize their performance measures \\\n",
        "in the environment). They can be deterministic or nondeterministic (referring to \\\n",
        "whether the next state is 100% determined by the current state and the chosen \\\n",
        "action). If the next state is randomized with unknown probabilities, the environment \\\n",
        "is nondeterministic, but if we know the probabilities, then it's stochastic. \\\n",
        "They can be episodic or sequential (does the next action to take depend on just the \\\n",
        "current state or does it depend on previous states and actions as well?). They can \\\n",
        "be static or dynamic (referring to whether the environment can change while the \\\n",
        "agent is choosing an action). They can be discrete or continuous (are there a \\\n",
        "discrete or finite number of states, actions, and percepts or is there a continuous \\\n",
        "state space?). They can be known or unknown (are the outcomes for all actions given?). \"\"\"\n",
        "chapter2_4 = \"\"\"We want to design an agent program that implements the agent function \\\n",
        "(which maps percepts to actions). The physical device the agent program runs on \\\n",
        "is the agent architecture. The agent is the combination of the architecture and \\\n",
        "the program. Simple reflex agents only choose actions based on the current percept. \\\n",
        "A transition model tells us which actions in which states take us to which states. \\\n",
        "Model-based agents use transition models. Goal-based agents are given a goal and \\\n",
        "choose actions to realize said goal. A utility function will give a score to each \\\n",
        "sequence of states (determining its desirability), and if this utility function \\\n",
        "aligns with the performance measure, an agent choosing actions to maximize their \\\n",
        "utility will also be rational based on that performance measure. Trying to maximize \\\n",
        "expected utility is rational (as the agent often faces uncertainty).\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"While there are four main views of AI (thinking humanly, \\\n",
        "thinking rationally, acting humanly, and acting rationally), the main focus is \\\n",
        "on acting rationally. An agent is something that perceives its environment and \\\n",
        "takes action. The agent's perceptual input at any certain time is called a percept. \\\n",
        "An agent is specified through its agent function (which maps sequences of percepts \\\n",
        "to a legal action). A performance measure is some criteria for evaluating an \\\n",
        "agent's behavior given its perceptual inputs. A rational agent will always choose \\\n",
        "the action that maximizes the expected value of its performance measure (expected, \\\n",
        "not actual... it doesn't have to know exactly what the future will bring). Given \\\n",
        "a PEAS (Performance measure, Environment, Actuators, Sensors) task environment, \\\n",
        "you'll need to create an agent function that maximizes the expected value of the \\\n",
        "performance measure (this is the abstract mathematical description) and then \\\n",
        "create an agent program (the actual implementation) that implements that agent \\\n",
        "function on a specific physical architecture. The hardest task environment is \\\n",
        "continuous, partially observable, stochastic, and multi-agent.\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"something that the agent perceives (receives as info) through its sensors\",\n",
        "\"rational agent\" : \"an agent that behaves so as to induce the best outcome or best expected outcome if uncertainty exists\",\n",
        "\"weak AI\" : \"machines that could only pretend to be intelligent\",\n",
        "\"strong AI\" : \"machines that were actually intelligent, machines that consciously thought\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tH_47WDKLbzX"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"Python is strongly typed (meaning each object has a \\\n",
        "fixed type, so you wouldn't be allowed to do something like \"abc\" + 2 as they're \\\n",
        "incompatible types). Python is also dynamically typed (meaning variables can switch \\\n",
        "around types whenever you want, unlike in Java how you'd have to say String y = \"abc\" \\\n",
        "and y has to stay a String... you can say y = \"abc\" and later update it to y = 3 \\\n",
        "with no problems in Python). Functions won't have type signatures (return types) \\\n",
        "either. The problem with this is that type errors will only be caught during runtime \\\n",
        "as opposed to at compile time with static typing in Java. Strings are immutable \\\n",
        "in Python. You can create Strings with variables inserted into placeholders using \\\n",
        "% (\"%s is a really cool guy with %d cookies\" % (\"CoolGuyName\", 17)). Lists are \\\n",
        "mutable and unordered. You can use list_name[:] to get a shallow copy of the list \\\n",
        "(new object of the same value). Tuples are immutable, ordered and can contain \\\n",
        "items of mixed type. Lists can be sliced (returning a copy but of various parts) \\\n",
        "like this... list_name[start_index:end_index:step] where start_index specifies \\\n",
        "where we start slicing from, end_index specifies where we stop (not including this \\\n",
        "ending index), and step states whether we're taking every other, third, fourth, etc... \\\n",
        "element. A negative index means ith from the end of the list (as opposed to normally \\\n",
        "ith from the start). Omitting an index defaults to starting from the start or ending \\\n",
        "at the end depending on which was missing. Omitting the step defaults to not skipping \\\n",
        "elements. Dictionaries are unordered and their keys must be immutable. Python functions \\\n",
        "can return multiple values as a tuple. You can provide default arguments for a \\\n",
        "function's arguments (making those arguments optional when calling the function). \\\n",
        "Non-default arguments should always come before default arguments. Functions can \\\n",
        "be called with arguments out of order (so long as you do inputx = 2 or something \\\n",
        "when calling), but these keyword arguments have to come after all other arguments. \\\n",
        "Use *args when you want to accept a variable amount of non-keyword arguments in \\\n",
        "a function. Use **kwargs when you want to accept a variable number of keyword \\\n",
        "arguments in a function. Python uses dynamic scope (meaning functions see the \\\n",
        "most current value of a variable.) Functions are first-class citizens (you can \\\n",
        "pass functions as arguments to other functions, return functions from other functions, \\\n",
        "assign functions to variables or store them in data structures). Higher order functions \\\n",
        "take functions as inputs. List comprehensions take this form [expression for name in list if filter]. \\\n",
        "range(x) will generate 0, 1, ..., x - 1. Generators are iterators (which are \\\n",
        "returned when using yield instead of return).\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"Refers to whether you're able to change an object once it's been initialized.\",\n",
        "\"Tuples\" : \"Immutable, ordered sequences that can contain items of mixed type.\",\n",
        "\"Strings\" : \"Immutable\",\n",
        "\"Lists\" : \"Mutable, ordered sequences that can contain items of mixed type.\",\n",
        "\"Shallow Copy\" : \"A copy where changes to the copy are also seen in the original.\",\n",
        "\"Deep Copy\" : \"A copy where changes to the copy are not transferred to the original.\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"The four-phase problem-solving process first involves formulating \\\n",
        "a goal (this will help determine behavior by limiting objectives and thus the actions \\\n",
        "that need to be considered), then formulating the problem (what are the states and \\\n",
        "the actions), search (simulating sequences of actions until it finds one that \\\n",
        "reaches a the goal, with this goal-reaching sequence being called a solution), \\\n",
        "and execution (actually do the discovered solution). A search problem can be defined \\\n",
        "by the set of states, the initial state, a set of goal states, the legal actions, \\\n",
        "the transition model (specifying which state each current state, action pair lead \\\n",
        "you to), and the action cost function (which tells you the cost of each transition). \\\n",
        "A path is a sequence of actions, and a solution is a path from the initial state to \\\n",
        "a goal state. An optimal solution has the lowest path cost compared to all other \\\n",
        "solutions.\"\"\"\n",
        "chapter3_2 = \"\"\"Standardized problems are mainly just used to test various \\\n",
        "problem-solving methods. They have exact descriptions, and so they're easy to \\\n",
        "use to test and compare the performance of various search algorithms. Real-world \\\n",
        "problems are ones in which the solutions are actually useful and where the problem \\\n",
        "formulation is more complicated and individualized.\"\"\"\n",
        "chapter3_3 = \"\"\"Best-first search determines the next node from the frontier to \\\n",
        "expand next based on whichever node has the lowest f(n) value where f(n) is some \\\n",
        "evaluation function. Best-first search is a graph search algorithm. Graph search \\\n",
        "means that the algorithm checks for redundant paths. A tree search would mean that \\\n",
        "the algorithm does not check for redundant paths. There are four ways to evaluate \\\n",
        "an algorithm's performance (completeness: will the algorithm 100% find a solution \\\n",
        "if one exists and report failure otherwise?, optimality: does it find an optimal \\\n",
        "(lowest path cost) solution?, time complexity: how long does it take to find a \\\n",
        "solution?, and space complexity: how much memory does it take to find a solution?). \\\n",
        "b = branching factor (number of successors of each node to consider), m = the maximum \\\n",
        "path length, and d = the maximum depth of a solution. \"\"\"\n",
        "chapter3_4 = \"\"\"Breadth-first search (BFS) takes O(b^d) time and space. BFS is \\\n",
        "complete. BFS is optimal (when actions all have the same cost). Uniform-cost search \\\n",
        "(Dijkstra's) expands nodes in the frontier with minimal g(n) first (smallest path \\\n",
        "cost from initial state). UCS checks for a goal when popping a node off the queue, \\\n",
        "not when expanding a node and finding its successors. Depth-first search (DFS) takes \\\n",
        "only O(bm) space and O(b^m) time. DFS is not complete (can fail in infinite depth \\\n",
        "spaces or when there are cycles). DFS is not optimal either. Its main draw is its \\\n",
        "low space complexity. Depth-limited search is a form of DFS that only descends to \\\n",
        "a max of depth l. Depth-limited search takes (b^l) time and O(bl) space. Iterative \\\n",
        "deepening search will run depth-limited search with a depth of 0, then 1, then 2, \\\n",
        "etc... until it finally finds a solution (or we pass a certain depth that we want \\\n",
        "to stop searching after). Iterative deepening takes O(bd) space when there's a \\\n",
        "solution and O(bm) space otherwise. Iterative deepening takes O(b^d) time when \\\n",
        "there's a solution and O(b^m) time otherwise. Iterative deepening is optimal \\\n",
        "(assuming all action costs are equivalent) and it's complete. Bidirectional search \\\n",
        "searches from the initial state and backwards from the goal states at the same time. \\\n",
        "BFS is complete, optimal (assuming equal action costs), takes O(b^d) time and space. \\\n",
        "DFS is not complete, not optimal, takes O(b^m) time and O(bm) space. Depth-limited search \\\n",
        "is not copmlete, not optimal, takes O(b^l) time and O(bl) space. Iterative deepening \\\n",
        "search is complete, optimal (assuming equal action costs), takes O(b^d) time and O(bd) space.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"A simple reflex agent just selects an action based on \\\n",
        "the current percept alone. A problem-solving agent will seek a sequence of actions \\\n",
        "that consitute a path to a goal state (such a sequence is called a solution). \\\n",
        "If the task environment is fully observable, deterministic, and a known environment, \\\n",
        "then the solution will be a fixed sequence of actions. But if the environment is \\\n",
        "partially observable and nondeterministic, then the solution will need to recommend \\\n",
        "different action sequences based on what specific percepts it receives. A search \\\n",
        "problem is defined by the states, the initial state, the actions, the transition \\\n",
        "model (tells you the resulting state for each state, action pair), the action cost \\\n",
        "or path cost function, and a goal test (so you know when you've made it). A solution \\\n",
        "is optimal if no other solution has a lower path cost. Uninformed search strategies \\\n",
        "use only information from the problem definition. We can evaluate an algorithm through \\\n",
        "four properties (completeness : does it always find a solution?, optimality: does \\\n",
        "it find a solution with the lowest cost?, time complexity: how many nodes does \\\n",
        "it generate in the worst case?, and space complexity: how many nodes does it \\\n",
        "hold in memory at the same time in the worst case?). b = maximum branching factor \\\n",
        "of the search tree. d = depth of the shallowest goal node. m = maximum path length \\\n",
        "in the search tree. Breadth-first search (BFS) involves expanding the shallowest \\\n",
        "unexpanded nodes first. BFS is complete assuming b is finite, takes O(b^d) time \\\n",
        "and space, and is optimal (assuming action costs are all equal). Depth-first search \\\n",
        "(DFS) expands the deepest unexpanded nodes first. DFS is not complete (failing in \\\n",
        "infinite-depth and cyclic search spaces), it's not optimal, it takes O(b^m) time \\\n",
        "but only takes O(bm) space. Depth-limited search is DFS but with a depth limit l. \\\n",
        "If l = d, then it's optimal, but if l < d, it's not complete, and if l > d, then \\\n",
        "it's not optimal. Depth-limited search takes O(b^l) time and O(bl) space. Iterative \\\n",
        "deepening does depth-limited searches at increased depth limits until a solution \\\n",
        "is found. Iterative deepening is both optimal and complete, taking O(b^d) time and \\\n",
        "O(bd) space. So BFS is complete and optimal (assuming action costs are equal), \\\n",
        "and takes O(b^d) time and space. DFS is not complete and not optimal, takes O(b^m) time, \\\n",
        "but takes only O(bm) space. Depth-limited search is not complete and not optimal, takes \\\n",
        "O(b^l) time and O(bl) space. Iterative deepening is both complete and optimal, \\\n",
        "takes O(b^d) time, and takes O(bd) space.\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"Optimal Solution\" : \"The solution with the lowest path cost compared to all other solutions.\",\n",
        "\"Graph Search\" : \"Checks for redundant paths\",\n",
        "\"Tree Search\" : \"Does not check for redundant paths\",\n",
        "\"Completeness\" : \"Will the algorithm 100% find a solution if one exists and report failure otherwise?\",\n",
        "\"Optimality\" : \"Will the algorithm find a solution with the lowest path cost?\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Informed search has access to the problem definition as well as \\\n",
        "a heuristic function h(n) that estimates the cheapest path cost from some state n \\\n",
        "to a goal state. Greedy best-first search expands the node with lowest h(n) first. \\\n",
        "Greedy best-first search is complete in finite state spaces, and with a good h(n), \\\n",
        "it takes O(bm) time and space. Greedy-best first search is not optimal. A* search \\\n",
        "expands the node with lowest f(n) = g(n) + h(n), so it combines greedy best-first \\\n",
        "search and uniform cost search. A* search is complete and it is also optimal \\\n",
        "(assuming we're using an admissible heuristic). An admissible heuristic is one that \\\n",
        "never overestimates the cost to reach a goal (so it's optimistic in that it always \\\n",
        "lowballs or is accurate). Satisficing solutions are suboptimal but still good enough. \\\n",
        "We can use an inadmissible heuristic with A* search to take less time and space but \\\n",
        "end up with a satisficing solution. We can do this with weighted A* search (in which \\\n",
        "we use f(n) = g(n) + (W * h(n)), weighting the heuristic). With bounded suboptimal search, \\\n",
        "we search for a solution that's within a constant factor of W from the optimal cost. \\\n",
        "Weighted A* guarantees this. In bounded-cost search, we want a solution that costs \\\n",
        "less than a constant C. In unbounded-cost search, we just want any solution so long \\\n",
        "as we can find it fast. Beam search imposes a limit on the frontier (only keep a \\\n",
        "certain number of nodes that have the best f(n) values). There's also iterative-deepening A* search \\\n",
        "(which uses a f-cost cutoff of the smallest node's f(n) that exceeded the cutoff \\\n",
        "from the last iteration).\"\"\"\n",
        "chapter3_6 = \"\"\"If A* generates N nodes in its search and the solution depth was d, \\\n",
        "then b* (the effective branching factor) is the branching factor that a uniform \\\n",
        "tree with depth d would have to have to contain N + 1 nodes. Heuristics can be \\\n",
        "evaluated and compared based on their effective branching factors (b*). Good \\\n",
        "heuristics will have a b* value close to 1. If one heuristic is always better \\\n",
        "than another (provides a higher estimate but still an underestimate), then that \\\n",
        "heuristic dominates the other. A good way to generate heuristics is to consider \\\n",
        "relaxed versions of the problem (with less constraints) and get path lengths for \\\n",
        "those relaxed versions.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Uniform-Cost search expands nodes with minimal g(n) first. \\\n",
        "Uniform-Cost search only tests if a state is a goal state when it's selected for \\\n",
        "expansion, not when we first discover it. A heuristic function h(n) gives you an \\\n",
        "estimate of the distance from n to a goal state. Greedy best-first search expands \\\n",
        "nodes with minimal h(n) first. Greedy best-first search is neither complete nor \\\n",
        "optimal. A* search expands nodes with minimal f(n) = g(n) + h(n) first. An admissible \\\n",
        "heuristic is one that never overestimates the real cost to go from the input state \\\n",
        "to a goal state (it's optimistic). If we use an admissible heuristic, then A* search \\\n",
        "is optimal. The cost of an optimal solution to a relaxed problem (meaning one in \\\n",
        "which some of the constraints of the original problem were loosened) is an admissible \\\n",
        "heuristic for the original problem. If h2(n) >= h1(n) for all n and both heuristics \\\n",
        "are admissible, then h2 dominates h1 (meaning h2 still never overestimates but always \\\n",
        "gives a closer estimate than h1). h*(n) is the best heuristic (the true distance from \\\n",
        "n to a goal state). It dominates all other heuristics. h(n) = 0 is the worst heuristic \\\n",
        "(biggest underestimate possible). It is dominated by all other heuristics. So then \\\n",
        "a heuristic is admissible if 0 <= h(n) <= h*(n). \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Admissible Heuristic\" : \"Always gives an estimate that is <= to the true cost from a state to a goal state\",\n",
        "\"Dominates\" : \"A heuristic dominates another whenever it always gives a higher (closer) estimate while still being optimistic.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO"
      },
      "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\", module4_sections, module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Adversarial search often occurs in perfect information, zero-sum \\\n",
        "games (in which perfect information means fully observable and zero-sum means that \\\n",
        "one player's benefit is another player's detriment). A game can be defined with \\\n",
        "the initial state, a function to determine whose turn it is in a state s, the set \\\n",
        "of actions for each state, the transition model (which tells you which state you go to \\\n",
        "after taking an action in a specific state), a terminal test (that checks if the game \\\n",
        "is over or not), and a utility function (which tells you the utility for a player \\\n",
        "in a particular terminal state). \"\"\"\n",
        "chapter5_2 = \"\"\"With Minimax search, we can find the optimal stategy by finding \\\n",
        "the minimax value of each state in the tree. For a MAX node, this is the maximum value \\\n",
        "of its children. For a MIN node, this is the minimum value of its children. (We're \\\n",
        "assuming both players are playing optimally). Minimax performs similarly to depth-first \\\n",
        "search. Minimax takes O(b^m) time and O(bm) space. We can improve upon Minimax with \\\n",
        "alpha-beta pruning. Alpha is the value of the best choice along the path for MAX \\\n",
        "(meaning highest value). Alpha is \"at least\". Beta is the value of the best choice \\\n",
        "along the path for MIN (meaning lowest value). Beta is \"at most\". As we go through \\\n",
        "a minimax search, whenever we encounter a node whose value is worse than the current \\\n",
        "alpha or beta value for a MAX or MIN node respectively, we can stop considering it \\\n",
        "(and its children) as it would never be selected. Alpha-beta pruning's effectiveness \\\n",
        "is highly dependent on the order in which we consider nodes in the search tree.\"\"\"\n",
        "chapter5_3 = \"\"\"We can swap the utility function with a heuristic evaluation function \\\n",
        "which estimates the utility for a player in a particular state (and for terminal \\\n",
        "states, this estimate would be spot on). We could determine that any moves were \\\n",
        "cutoff terminal states (terminal states just for the purposes of keeping our search \\\n",
        "from searching too far in the future and going on for too long) and calculate the \\\n",
        "utilities with this evaluation function. Forward pruning involves pruning moves \\\n",
        "that look like they're bad moves (but might not be). It's faster, but could mess up. \\\n",
        "One way of doing forward pruning is with beam search (at each level, only consider \\\n",
        "the best n moves according to the evaluation function).\"\"\"\n",
        "chapter5_5 = \"\"\"With stochastic games, we have chance nodes that choose various \\\n",
        "actions with different probabilites. Now, we can only calculate the expected value \\\n",
        "of a position (as we can't infer what the opponent will play). Instead of minimax, \\\n",
        "we have expectimax. MIN and MAX nodes work the same way as with minimax, but chance \\\n",
        "nodes just have a value according to their expected value.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"The utility function models the agent's preferences and gives a \\\n",
        "single number to model the desirability of a state. The expected utility is just the \\\n",
        "sum of all the outcome utilities for an action weighted by the probability of that outcome. \\\n",
        "The principle of maximum expected utility (MEU) states that a rational agent should \\\n",
        "take the action that maximizes their expected utility.\"\"\"\n",
        "chapter16_2 = \"\"\"There are six constraints for any reasonable preference relation. \\\n",
        "Orderability: (A > B), (B > A), or (A ~ B), meaning the agent has to either prefer \\\n",
        "A over B, B over A or be indifferent between them. Transitivity: (A > B) and (B > C) --> (A > C) \\\n",
        "Continuity: (A > B > C) --> there's some probability p such that [p, A; 1-p, C] ~ B \\\n",
        "(meaning you're indifferent between B and a lottery between A and C such that the probability \\\n",
        "of getting A is p). Substitutability: A ~ B --> [p, A; 1-p, C] ~ [p, B; 1-p, C] \\\n",
        "(meaning if you're indifferent between A and B, then you can swap them out in lotteries \\\n",
        "and it'll make no difference). Monotonicity: A > B --> (p > q <--> [p, A; 1-p, B] > [q, A; 1-q, B]) \\\n",
        "(meaning if you prefer A over B, then you should prefer the lottery that gives you \\\n",
        "a higher chance of A than B). Decomposability: [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C] \\\n",
        "(meaning you can reduce compound lotteries to simpler ones using probability laws). \\\n",
        "If an agent's preferences follow the axioms of utility, then there's a utility function \\\n",
        "that exists such that preferred states have higher utility than others and pairs \\\n",
        "of indifferent states have equal utilities.\"\"\"\n",
        "chapter16_3 = \"\"\"Normalized utilities use a scale between 0 and 1. A micromort is \\\n",
        "a one in a million chance of death (often used to calculate how much people value \\\n",
        "their lives). Humans are generally risk-averse (they prefer certain rewards often \\\n",
        "even if they're lower than the expected reward from a gamble). But with losses, \\\n",
        "humans are risk-seeking (they'd prefer a gamble with a potentially greater loss \\\n",
        "than a lesser, sure loss). Decision theory is a normative theory (as it details \\\n",
        "how a rational agent is supposed to act. A descriptive theory describes how real \\\n",
        "agents (like humans) actually act.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"To formulate games as search problems, you need an initial \\\n",
        "state, a successfor function (a list of move, state pairs corresponding to legal moves), \\\n",
        "a terminal test (to test if the game's finished in a specific state), and a utility function \\\n",
        "(that gives a value to terminal states). An evaluation function gives a score for \\\n",
        "how good a state is for a certain player (it's positive when MAX is winning in that state, \\\n",
        "negative when MAX is losing, and 0 when MAX and MIN are tied). For two player deterministic \\\n",
        "games, you can use minimax search (choose the best option for MAX assuming MIN chooses \\\n",
        "their best option). Compute the minimax values for each node (for a MAX node, this is \\\n",
        "just the max of its children, and for a MIN node, it's the min of its children). \\\n",
        "We can improve upon minimax with alpha-beta pruning. Alpha is MAX's current lower \\\n",
        "bound on their outcome. Beta is MIN's current uppoer bound on MIN's outcome. \\\n",
        "MAX will never permit a move that could give a worse score for them than alpha, and \\\n",
        "MIN will never permit a move that could give a better score for MAX than beta. \\\n",
        "Use that knowledge to stop evaluating certain nodes when you know their parent \\\n",
        "would never choose them. With expectimax, we're dealing with an element of chance. \\\n",
        "Outcomes aren't certain, so node values now reflect average-case outcomes instead \\\n",
        "of worst-case outcomes. For chance nodes, their value will be their expected utilities. \\\n",
        "MAX nodes will behave the same way (choose the max child value as its value).\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Alpha\" : \"The value of the best choice along the path for MAX (highest value), think 'at least'\",\n",
        "\"Beta\" : \"The value of the best choice along the path for MIN (lowest value), think 'at most'\",\n",
        "\"Orderability\" : \"A rational agent has to either prefer one lottery over another or be indifferent between them\",\n",
        "\"Transitivity\" : \"If you prefer A to B and B to C, then you prefer A to C\",\n",
        "\"Continuity\" : \"If lottery B's between A and C, there's a probability where a lottery between A and C's indifferent to B\",\n",
        "\"Substitutability\" : \"If you're indifferent between A and B, you can swap between them in lotteries without altering preferences.\",\n",
        "\"Monotonicity\" : \"If you prefer A to B, you'd prefer a lottery with a higher chance of A (all else being equal)\",\n",
        "\"Decomposability\" : \"You can reduce compound lotteries to simpler ones using probability rules.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"Constraint satisfaction problems (CSPs) have three components: \\\n",
        "a set of variables, a set of domains (one for each variable), and a set of constraints \\\n",
        "that specify the allowable combinations of values. Each domain contains a set of \\\n",
        "allowable values for its variable. CSPs concern themselves with assignments of values to \\\n",
        "variables. If an assignment doesn't violate any constraints, then it is a consistent \\\n",
        "assignment. An assignment in which every variable is assigned a value is a complete \\\n",
        "assignment. A solution to a CSP is an assignment that is both consistent and complete. \\\n",
        "A partial assignment has some unassigned variables and a partial solution is a \\\n",
        "consistent but partial assignment. A unary constrait restricts the value of only \\\n",
        "one variable. A binary constraint details a relationship between two variables. \\\n",
        "A binary CSP only has unary and binary constraints. If a constraint involves some \\\n",
        "arbitrary number of variables, it's a global constraint.\"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propagation entails using constraints to reduce the \\\n",
        "number of allowed values for a variable, which can then reduce the number for \\\n",
        "another variable, and so on. A variable is node-consistent if every value in that \\\n",
        "variable's domain satisfies the variable's unary constraints. A variable is arc-consistent \\\n",
        "if every value in that variable's domain satisfies the variable's binary constraints. \\\n",
        "(So X_i is arc-consistent with X_j if for every value in domain D_i, there is a \\\n",
        "value in D_j that satisfies the binary constraint on the (X_i, X_j) arc). Enforcing \\\n",
        "arc consistency can be done with AC-3. AC-3 takes O(cd^3) time (where c is the \\\n",
        "number of binary constraints (arcs) and d is the max domain size). It takes O(d^2) time \\\n",
        "to check the consistency of a single arc. Path consistency involves consistency \\\n",
        "between sets of three variables at a time. A CSP is k-consistent if for any \\\n",
        "set of k - 1 variables and for any consistent assignment to those variables, you \\\n",
        "can assign a consistent value to a kth variable. A CSP is strongly k-consistent \\\n",
        "if it's k-consistent and k-1 consistent and k-2 consistent, ... , and 1 consistent.\"\"\"\n",
        "chapter6_3 = \"\"\"A problem is commutative if the order in which we assign values to \\\n",
        "the variables doesn't matter. Backtracking search will repeatedly choose an unassigned \\\n",
        "variable and then try all values in that variable's domain (extending into each possibility \\\n",
        "via a recursive call). If the value led to a solution, it'll return that solution. \\\n",
        "If not, we return to the previous state and try the next value. If no value works, \\\n",
        "then we report failure. When it comes time to choose the next unassigned variable, \\\n",
        "we can choose the variable with the fewest legal values remaining (the minimum-remaining-values, \\\n",
        "MRV, heuristic). Or we could choose the variable involved in the highest number of constraints \\\n",
        "on other unassigned variables. Once we have chosen an unassigned variable, we can use the \\\n",
        "least-constraining-value heuristic to choose the value that rules out the lowest number of \\\n",
        "allowable values for neighboring variables. Forward checking involves establishing arc \\\n",
        "consistency for each newly assigned variable (now that some new variable has been \\\n",
        "assigned, we can rule out some values for variables it shares a constraint with). \\\n",
        "MAC (Maintaining Arc Consistency) is an algorithm that calls AC-3 every time \\\n",
        "a new variable is assigned (but only on the arcs that involve unassigned neighbors \\\n",
        "to this newly assigned variable as opposed to all the arcs). So MAC does better \\\n",
        "than normal forward checking as forward checking doesn't keep enforcing arc consistency after \\\n",
        "the first round of updates based on the newly assigned variables (so it uses X's assignment \\\n",
        "to change Y's domain, but then doesn't use Y's changes to update other domains). \\\n",
        "MAC does though. With backtracking, it might be a better idea to backtrack to a variable \\\n",
        "that could fix the problem (as opposed to the most recently assigned variable). \\\n",
        "You can keep track of a set of assignments that conflict with each assigned variable value \\\n",
        "(conflict sets). Then, when we encounter a problem, we backjump to the most recent \\\n",
        "assignemnt in the conflic set. \"\"\"\n",
        "chapter6_4 = \"\"\"Local search algorithms can be really helpful in solving CSPs. \\\n",
        "If you start off with a complete assignment (which likely has many constraint violations), \\\n",
        "and then choose some conflicted variable and change its value to whatever will result \\\n",
        "in the minimum number of conflicts with other variables, we can often quickly find a solution. \\\n",
        "This is called the min-conflicts heuristic. Constraint weighting will focus the \\\n",
        "search on the most important constraints. Each constraint starts off at value 1. \\\n",
        "At each step, the algorithm chooses a variable/value pair to update to result in \\\n",
        "the lowest total weight of all violated constraints. Then the constraint weights \\\n",
        "are updated by incrementing the weight of each constraint that's still violated \\\n",
        "by the current assignment.\"\"\"\n",
        "chapter6_5 = \"\"\"You can find a solution in linear time to any tree-structured CSP \\\n",
        "(linear in the number of variables). Cutset conditioning algorithm: first choose \\\n",
        "a subset of the CSP's variables so that the constraint graph is a tree after removing \\\n",
        "that subset. That subset is the cycle cutset. Then, for each possible assignment to the \\\n",
        "variables in that subset that satisfy all the constraints within it, remove from \\\n",
        "the domains of any remaining variables the values that are inconsistent with the assignment \\\n",
        "for that subset and if the remaining CSP has a solution, then return it alongside \\\n",
        "the assignment for S. This process is called cutset conditioning. A tree decomposition \\\n",
        "involves a transformation of the original graph into a tree with nodes consisting of \\\n",
        "a set of variables. There are three requirements for a tree decomposition (every \\\n",
        "variable in the original problem has to be found in at least one tree node, if two \\\n",
        "variables are involved in a constraint in the original problem, they have to be found \\\n",
        "together alongside the constraint in at least one tree node, and if a variable \\\n",
        "is in two nodes in the tree, it has to appear in every node along the path between \\\n",
        "those two nodes). The tree width of a tree decomposition is the size of the largest node - 1. \\\n",
        "CSPs with constraint graphs with a bounded tree width can be solved in polynomial time. \\\n",
        "Tree decomposition is faster than cutset conditioning, but cutset conditioning takes \\\n",
        "less space. You can include symmetry-breaking constraints to reduce the search space \\\n",
        "to eliminate equivalent solutions (like in map coloring, if three zones have to be \\\n",
        "different colors, it doesn't matter if its R, G, B or G, R, B, it just matters that they're different).\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"A CSP consists of a finite state of variables, \\\n",
        "a nonempty domain of allowable values for each variable, and a finite set of \\\n",
        "constraints. A state is a specific assignment of values to some or all varaibles. \\\n",
        "A consistent assignement doesn't violate any constraints. A complete assignment \\\n",
        "has assigned a value to each variable. A solution is a complete and consistent \\\n",
        "assignment. CSPs can automatically prune off any branch in the search tree that \\\n",
        "violates constraints (speeding up the process). CSPs can be represented as \\\n",
        "constraint graphs (where nodes are variables and edges are binary constraints). \\\n",
        "Unary constraints involve a single variable. Binary constraints involve pairs \\\n",
        "of variables. Higher-order constraints involve 3+ variables. Preference (soft \\\n",
        "constraints) can be represetned with a cost for each variable assignment (red > green \\\n",
        "for example). CSPs can be expressed as search problems (with an initial state being \\\n",
        "the empty assignment, a successor function which can assign a value to any unassigned \\\n",
        "variable assuming there's no constraint conflict, a goal test (is the current assignment \\\n",
        "complete?), and a path cost function (a constant cost per step). The solution is \\\n",
        "always at depth n (n variables), so depth first search can be used. Depth first search \\\n",
        "for CSPs with single-variable assignments at each step is backtracking search. \\\n",
        "It'll backtrack when a variable has no legal values left to assign. It's the most \\\n",
        "basic uninformed algorithm for CSPs. We can improve backtracking efficiency by \\\n",
        "choosing the next variable to assign as the one with the fewest legal values remaining. \\\n",
        "This is called the minimum remaining values (MRV) heuristic. And if we have a tie, \\\n",
        "we can choose the variable with the most constraints on reamining unassigned variables. \\\n",
        "Once we've chosen a variable to assign, we can choose the value that rules out the \\\n",
        "fewest values in the remaining variables. We can also keep track of remaining legal \\\n",
        "values for unassigned variables and terminate the search process if any unassigned \\\n",
        "variables have no legal values left. Forward checking propagates info from assigned \\\n",
        "to unassigned variables, but doesn't always provide early failure detection. Constraint \\\n",
        "propagation goes further and repeatedly enforces constraints locally. This is inference. \\\n",
        "Node consistency entails satisfying unary constraints. Arc consistency entails satisfying \\\n",
        "binary constraints (two variables are arc consistent if for every value remaining for one, \\\n",
        "there's some remaining value for the other that satisfies the binary constraint \\\n",
        "between them). With d values, checking an arc takes O(d^2) time. AC-3 is used to \\\n",
        "enforce arc consistency. AC-3 takes O(n^2d^3) time where n is the number of variables \\\n",
        "and d is the max domain size.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Consistent Assignment\" : \"One that doesn't violate any constraints\",\n",
        "\"Complete Assignment\" : \"One that assigns values to all variables\",\n",
        "\"Solution\" : \"A consistent and complete assignment\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "19ae0459-f915-4cd7-ed90-d1f5fb1fbcb2"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"A knowledge base is a set of sentences that are written in a \\\n",
        "knowledge representation language and represent an assertion about the world. \\\n",
        "If a sentence is taken as a given without needing to be derived from other sentences, \\\n",
        "it's an axiom. Inference involves deriving new correct sentences from current ones. \\\n",
        "The agent might initially be given a knowledge base that contains some background \\\n",
        "information (from which it can explore the world and expand its knowledge base, \\\n",
        "using it to find an optimal solution to its problem).\"\"\"\n",
        "chapter7_2 = \"\"\"For an agent in its environment, the hardest challenge stems from \\\n",
        "its initial lack of knowledge about the layout of the environment. To overcome this \\\n",
        "ignorance, it'll require logical reasoning (to deduce new information). Every time \\\n",
        "the agent comes to a new conclusion from its available information, that conclusion \\\n",
        "is 100% correct if the available information was correct. This is simply a property \\\n",
        "of logical reasoning.\"\"\"\n",
        "chapter7_3 = \"\"\"Syntax specifies the well-formed (allowed) sentences for a \\\n",
        "representation language (doesn't mean they're true, just that their structure \\\n",
        "is correct). Semantics defines the truth of a sentence with regard to each \\\n",
        "possible world (might be true in one world but not another). Each statement \\\n",
        "has to be true or false in a particular world (no in-between). If a particular \\\n",
        "sentence is true in a model, then that model satisfies the sentence or that model \\\n",
        "is a model of that sentence. M(a) = set of all models of sentence a. \\\n",
        "a |= b iff M(a) is a subset of M(b) (definition of logical entailment). \\\n",
        "This would mean a is a stronger assertion than b (as it rules out more possible \\\n",
        "worlds). Logical entailment is used for logical inference. Model checking involves \\\n",
        "going through all possible models to check that sentence a is true in all models \\\n",
        "in which the knowledge base is true (meaning that M(KB) is a subset of M(a)). \\\n",
        "If an inference algorithm only concludes entailed sentences, it is sound (aka \\\n",
        "truth-preserving). If an inference algorithm can conclude all entailable sentences, \\\n",
        "it is complete.\"\"\"\n",
        "chapter7_4 = \"\"\"Atmoic sentences are made up of a single proposition symbol. \\\n",
        "Complex sentences are made out of simpler sentences using parentheses and logical \\\n",
        "connectives (like not, and, or, -->, and <-->). A literal can be an atomic sentence \\\n",
        "(positive literal) or a negated atomic sentence (negative literal). If a sentence's \\\n",
        "main connective is \"and\", then it's a conjunction and its parts are conjuncts. \\\n",
        "Similarly, if a sentence's main connective is \"or\", then it's a disjunction and \\\n",
        "its parts are disjuncts. The sentence A --> B is an implication or conditional \\\n",
        "and A is its premise/antecedent and B is its conclusion or consequent. Sentences with \\\n",
        "<--> are biconditionals. A model assigns a truth value to each proposition symbol. \\\n",
        "In a model m, not P is true iff P is false in m, P and Q is true iff both P and Q \\\n",
        "are true in m, P or Q is true iff either P or Q is true in m, P --> Q is true unless \\\n",
        "P is true and Q is false in m, and P <--> Q is true iff P and Q are both true or \\\n",
        "both false in m. All inference algorithms for propositional logic have a worst-case \\\n",
        "runtime that is exponential with regard to the input size.\"\"\"\n",
        "chapter7_5 = \"\"\"Theorem proving involves using the rules of inference on the sentences \\\n",
        "in a knowledge base to generate a proof for a desired sentence without needing to \\\n",
        "consult any models. This will be more efficient than model checking if there are a \\\n",
        "lot of models to check but the proof is relatively short. Two sentences are logically \\\n",
        "equivalent if they hold true in exactly the same set of models. This is written \\\n",
        "as a (triple line equals) b. Sentence a is logically equivalent to sentence b iff \\\n",
        "a entails b and b entails a. A valid sentence is one that is true in all models. \\\n",
        "Valid sentences are also called tautologies (they're necessarily true). \\\n",
        "The deduction theorem is that for any senteces a and b, a entails b iff the sentence \\\n",
        "\"a implies b\" is valid. A satisfiable sentence is one that is true in some model. \\\n",
        "Inference rules can be applied to make a proof. They're written like this: \\\n",
        "sentence a, sentence b (dividing horizontal line) sentence c. If sentence a and b \\\n",
        "are true, then you can conclude sentence c. Modus Ponens holds that if you have \\\n",
        "\"a implies b\" and \"a\", then you can conclude \"b\". And-Elimination holds that if \\\n",
        "you have \"a and b\", then you can conclude \"a\". (You can have any number of given \\\n",
        "sentences in the top part and presumably any number of concludable sentences in \\\n",
        "the bottom part). The inference rule called resolution can be combined with \\\n",
        "any complete search algorithm to get a complete inference algorithm. The resolution \\\n",
        "rule looks like this: (top) l_1 or ... or l_k, m_1 or ... or m_n (dividing horizontal line) \\\n",
        "(bottom) l_1 or ... or l_i-1 or l_i+1 or ... or l_k or m_1 or ... or m_j-1 or m_j+1 or ... or m_n \\\n",
        "(where l_i and m_j are complementary literals). Basically, resolution will take \\\n",
        "two clauses and give you a new clause that has every literal of the original two \\\n",
        "but without those two complementary literals (l_i and m_j got eliminated). \\\n",
        "Also, the resulting clause should only have one copy of each literal, so if there \\\n",
        "are copies, remove them until one is left. This process is called factoring. \\\n",
        "If a sentence is just a conjunction of clauses (clause1 and clause2 and clause3 and ...), \\\n",
        "then it's in conjunctive normal form (CNF). To convert to CNF, use biconditional elimination, \n",
        "conditional elimination, DeMorgan's rules, and the distributivity law (of or over and). \\\n",
        "Resolution algorithms will convert (knowledge base and not sentence a) into CNF \n",
        "(we want to know that sentence a is true or not), then keep resolving each clause \\\n",
        "until either there are no new clauses that can be added (meaning the knowledge base did \\\n",
        "not entail sentence a) or we resolve two clauses into the empty clause (meaning the knowledge \\\n",
        "base does entail sentence a). The definite clause is a disjunction of literals where \\\n",
        "only one is positive. The Horn clause is a disjunction of literas where a max of one \\\n",
        "is positive.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Knowledge-based agents reason over an internal representation \\\n",
        "of knowledge to choose an action. A knowledge base is a set of sentences \\\n",
        "that are written in a knowledge representation language (and each sentence is a \\\n",
        "statement about the environment). Axioms are given sentences and derived sentences \\\n",
        "are those that follow from other sentences. This derivation process is inference. \\\n",
        "Syntax defines which sentences are well-formed. Semantics defines the meaning \\\n",
        "(truth value) of sentences. Models are true/false value assignments to \\\n",
        "each literal in all the sentences. If a sentence is true in a model, that model \\\n",
        "satisfies the sentence or the model is a model of that sentence. M(a) means the \\\n",
        "set of all models that satisfy sentence a. Sentence a logically entails sentence b \\\n",
        "iff M(a) is a subset of M(b). This means a is more specific than b \\\n",
        "(rules out more models). A knowledge base is false in models that contradict \\\n",
        "the agent's knowledge. Model checking involves enumerating every possible model \\\n",
        "that doesn't contradict the agent's knowledge base. Atomic sentences are made \\\n",
        "with just a single propositional symbol. Complex sentences are created from \\\n",
        "simpler ones using ()'s and logical connectives (not, and, or, implies, biconditional). \\\n",
        "Soundness is when the inference algorithm only derives entailed sentences. \\\n",
        "Copmleteness is when the inference algorithm can derive all entailable setences. \\\n",
        "Sentences are logically equivalent if they're true in exactly the same set of models. \\\n",
        "(They're logically equivalent if they each entail the other). Monotonicity refers \\\n",
        "to the fact that if the knowledge base entails a sentence a, then (knowledge base \\\n",
        "and b) entails a (meaning we can add other things to the knowledge base without \\\n",
        "invalidating anything else we've inferred). To put a sentence in CNF, eliminate \\\n",
        "biconditionals (a <--> turns to (a --> b) and (b --> a)), eliminate conditionals \\\n",
        "((a --> b) turns to ((not a) or b)), then apply De Morgan's rules, and \\\n",
        "then use the distributivity law to distribute or's over and's until it's in CNF. \\\n",
        "Horn clauses are closed under resolution (meaning that appling resolution to \\\n",
        "Horn clauses gives you back another Horn clause.) It only takes linear \\\n",
        "time (with respect to knowledge base size) to decide entailment with Horn clauses. \\\n",
        "Forward chaining is a type of data-driven reasoning. The agent can start with some \\\n",
        "known data and add premises when new percepts are acquired and incrementally \\\n",
        "apply the forward chaining algorithm to discover new conclusions. The \\\n",
        "agent doesn't have to specifically test for a desired setence. Backward chaining \\\n",
        "works its way backwards from a query. If the query is known to be correct, then \\\n",
        "nothing has to be done. Otherwise, the algorithm will find implications in the \\\n",
        "knowledge base whose conclusions are the query. If you can prove that all the premises \\\n",
        "of one such implications are true (via backwards chaining), that would mean that \\\n",
        "the query (conclusion) is true. Backward chaining is thus a goal-directed form of reasoning.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Sound/Truth-Preserving\" : \"When an inference algorithm only concludes sentences that follow from the knowledge base (are entailed)\",\n",
        "\"Complete\" : \"When an inference algorithm concludes/finds all entailed sentences\",\n",
        "\"Logical Equivalence\" : \"Two sentences are logically equivalent if they're true in exactly the same set of models\",\n",
        "\"Validity\" : \"A valid sentence is true in every single model\",\n",
        "\"Satisfiability\" : \"A satisfiable sentence is true in at least one model\",\n",
        "\"Definite Clause\" : \"Disjunction of literals where only one is positive\",\n",
        "\"Horn Clause\" : \"Disjunction of literals where at max one is positive\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 480\n",
            "The length in characters is 2998\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 8100
        },
        "id": "T3cm1WV542_a",
        "outputId": "5ad1034e-e6fe-4615-d39b-22fe33039bcc"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 72,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n There are two dimensions when it comes to designing AI: human-like vs. rational and thought vs. behavior. The four combinations are different types of AI (human-like thinker, human-like behaver, rational thinker, and rational behaver). Machine intelligence can be evaluated through a Turing test (in which humans have to determine whether they're communicating with a human or machine). Total Turing tests also involve the machine having to physically imitate a human. The field of AI has mainly focused on studying and creating agents that act rationally (the rational behaver combination), that do the right thing. Perfect rationality is often infeasible as it's too computationally taxing to consider every possibility, so limited rationality (acting optimally given that you can't consider as many possibilities as you'd like) is often seen instead. When designing AI, we must make sure that we set its values and objectives to match our own, otherwise the machines might take\nuncomfortable actions to achieve their goals. This process is called the value alignment problem. In the end, we want AI that benefit humanity (that pursue our goals for us, not theirs).\n\n## AIMA Chapter 27.1 The Limits of AI\nPhilosopher John Searle distinguished between weak AI (machines that could only pretend to be intelligent) and strong AI (machines that were actually intelligent, machines that consciously thought). This strong AI is what's now referred to as human-level AI or general AI. Turing (with his argument from informality of behavior) believed that human behavior was too complicated to be described by a formal set of rules, meaning that it would be impossible to program a machine with human behavior. Arguments from disability claim that machines cannot attain human-like minds because they cannot do various things that humans can (such as fall in love or have a sense of humor). Some have said that machines are mentally inferior to humans because since machines are formal systems, they fall prety to the incompleteness theorem and cannot establish the truth of certain sentences (but there are certain sentences that humans cannot determine as true or false, humans can't prove impossible to prove statements either, so it's an invalid argument). AI researchers haven't really focused on AI chatbots (no AI has still passed the Turing test with a well-trained judge), instead preferring to design AI for games (chess, StarCraftII) and other tasks such as object identification.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nJohn Searle's Chinese Room scenario involves a human in a room with a rule book that explains in English which Chinese symbols to output for a given input of Chinese symbols. The room receives some symbol inputs, the human uses the rule book to make and output correct symbol outputs. To an outsider, it looks like the room is able to generate intelligent Chinese responses to Chinese sentences, but the guy in the room doesn't know Chinese, the rule book doesn't know Chinese. There's no understanding of Chinese, only very extensive pattern matching. Searle explains that this is essentially what computers do, so computers have no real understanding, they're just matching inputs to outputs. There's also a debate over whether machines can have consciousness or qualia. We can't give machines human-like consciousnes yet, but we can imbue them with smaller, individual parts of consciousness like awareness.\n\n## AIMA 2.1 Agents and Environments\nAnything that perceives its environment via sensors and then takes action via actuators is considered an agent. Percepts are whatever information an agent receives through its sensors. The ordered history of all the percepts the agent has received over time is called the percept sequence. If you map every possible percept sequence to a valid action, you have an agent function (which completely describes the agent's behavior). The actual implementation of this agent function is the agent program (runs on some physical system).\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nIf an agent always does the right thing, they are a rational agent. Usually, the right thing is evaluated through a consequentialist lens. If the sequence of states that results from the agent's chosen sequence of actions is desirable, then the agent has done a good job. We quantify this with a performance measure that will evaluate any sequence of states. When desiging a performance measure, it's better to align it with what you want to be done in the environment as opposed to how you think the AI should act. What action is rational depends on the performance measure, the agent's prior knowledge of the environment, the legal actions the agent can take, and the agent's percept sequence. Rationality is not the same as perfection. Rationality entails maximizing expected performance given what we currently know. A crucial part of rationality is information gathering (taking some actions in order to get more info and percepts to better advise future actions). Rational agents should be autonomous (meaning they're capable of learning so as to expand upon their initially incorrect or incomplete prior knowledge).\n\n## AIMA 2.3 The Nature of Environments\nThe task environemnt (PEAS: Performance, Environment, Actuators, Sensors) needs to be specified when creating an agent. Task environments can be fully observable (sensors receive all info relevant to choosing an action) or partially observable (some info is hidden). They can be single-agent or multi-agent (referring to the number of agents trying to maximize their performance measures in the environment). They can be deterministic or nondeterministic (referring to whether the next state is 100% determined by the current state and the chosen action). If the next state is randomized with unknown probabilities, the environment is nondeterministic, but if we know the probabilities, then it's stochastic. They can be episodic or sequential (does the next action to take depend on just the current state or does it depend on previous states and actions as well?). They can be static or dynamic (referring to whether the environment can change while the agent is choosing an action). They can be discrete or continuous (are there a discrete or finite number of states, actions, and percepts or is there a continuous state space?). They can be known or unknown (are the outcomes for all actions given?). \n\n## AIMA 2.4 The Structure of Agents\nWe want to design an agent program that implements the agent function (which maps percepts to actions). The physical device the agent program runs on is the agent architecture. The agent is the combination of the architecture and the program. Simple reflex agents only choose actions based on the current percept. A transition model tells us which actions in which states take us to which states. Model-based agents use transition models. Goal-based agents are given a goal and choose actions to realize said goal. A utility function will give a score to each sequence of states (determining its desirability), and if this utility function aligns with the performance measure, an agent choosing actions to maximize their utility will also be rational based on that performance measure. Trying to maximize expected utility is rational (as the agent often faces uncertainty).\n\n## Module 1 Lecture Notes\nWhile there are four main views of AI (thinking humanly, thinking rationally, acting humanly, and acting rationally), the main focus is on acting rationally. An agent is something that perceives its environment and takes action. The agent's perceptual input at any certain time is called a percept. An agent is specified through its agent function (which maps sequences of percepts to a legal action). A performance measure is some criteria for evaluating an agent's behavior given its perceptual inputs. A rational agent will always choose the action that maximizes the expected value of its performance measure (expected, not actual... it doesn't have to know exactly what the future will bring). Given a PEAS (Performance measure, Environment, Actuators, Sensors) task environment, you'll need to create an agent function that maximizes the expected value of the performance measure (this is the abstract mathematical description) and then create an agent program (the actual implementation) that implements that agent function on a specific physical architecture. The hardest task environment is continuous, partially observable, stochastic, and multi-agent.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - something that the agent perceives (receives as info) through its sensors\n* **Rational agent** - an agent that behaves so as to induce the best outcome or best expected outcome if uncertainty exists\n* **Weak ai** - machines that could only pretend to be intelligent\n* **Strong ai** - machines that were actually intelligent, machines that consciously thought\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nPython is strongly typed (meaning each object has a fixed type, so you wouldn't be allowed to do something like \"abc\" + 2 as they're incompatible types). Python is also dynamically typed (meaning variables can switch around types whenever you want, unlike in Java how you'd have to say String y = \"abc\" and y has to stay a String... you can say y = \"abc\" and later update it to y = 3 with no problems in Python). Functions won't have type signatures (return types) either. The problem with this is that type errors will only be caught during runtime as opposed to at compile time with static typing in Java. Strings are immutable in Python. You can create Strings with variables inserted into placeholders using % (\"%s is a really cool guy with %d cookies\" % (\"CoolGuyName\", 17)). Lists are mutable and unordered. You can use list_name[:] to get a shallow copy of the list (new object of the same value). Tuples are immutable, ordered and can contain items of mixed type. Lists can be sliced (returning a copy but of various parts) like this... list_name[start_index:end_index:step] where start_index specifies where we start slicing from, end_index specifies where we stop (not including this ending index), and step states whether we're taking every other, third, fourth, etc... element. A negative index means ith from the end of the list (as opposed to normally ith from the start). Omitting an index defaults to starting from the start or ending at the end depending on which was missing. Omitting the step defaults to not skipping elements. Dictionaries are unordered and their keys must be immutable. Python functions can return multiple values as a tuple. You can provide default arguments for a function's arguments (making those arguments optional when calling the function). Non-default arguments should always come before default arguments. Functions can be called with arguments out of order (so long as you do inputx = 2 or something when calling), but these keyword arguments have to come after all other arguments. Use *args when you want to accept a variable amount of non-keyword arguments in a function. Use **kwargs when you want to accept a variable number of keyword arguments in a function. Python uses dynamic scope (meaning functions see the most current value of a variable.) Functions are first-class citizens (you can pass functions as arguments to other functions, return functions from other functions, assign functions to variables or store them in data structures). Higher order functions take functions as inputs. List comprehensions take this form [expression for name in list if filter]. range(x) will generate 0, 1, ..., x - 1. Generators are iterators (which are returned when using yield instead of return).\n\n\n## Module 2 Definitions\n* **Mutability** - Refers to whether you're able to change an object once it's been initialized.\n* **Tuples** - Immutable, ordered sequences that can contain items of mixed type.\n* **Strings** - Immutable\n* **Lists** - Mutable, ordered sequences that can contain items of mixed type.\n* **Shallow copy** - A copy where changes to the copy are also seen in the original.\n* **Deep copy** - A copy where changes to the copy are not transferred to the original.\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nThe four-phase problem-solving process first involves formulating a goal (this will help determine behavior by limiting objectives and thus the actions that need to be considered), then formulating the problem (what are the states and the actions), search (simulating sequences of actions until it finds one that reaches a the goal, with this goal-reaching sequence being called a solution), and execution (actually do the discovered solution). A search problem can be defined by the set of states, the initial state, a set of goal states, the legal actions, the transition model (specifying which state each current state, action pair lead you to), and the action cost function (which tells you the cost of each transition). A path is a sequence of actions, and a solution is a path from the initial state to a goal state. An optimal solution has the lowest path cost compared to all other solutions.\n\n## AIMA Chapter 3.2 Example Problems\nStandardized problems are mainly just used to test various problem-solving methods. They have exact descriptions, and so they're easy to use to test and compare the performance of various search algorithms. Real-world problems are ones in which the solutions are actually useful and where the problem formulation is more complicated and individualized.\n\n## AIMA Chapter 3.3 Search Algorithms\nBest-first search determines the next node from the frontier to expand next based on whichever node has the lowest f(n) value where f(n) is some evaluation function. Best-first search is a graph search algorithm. Graph search means that the algorithm checks for redundant paths. A tree search would mean that the algorithm does not check for redundant paths. There are four ways to evaluate an algorithm's performance (completeness: will the algorithm 100% find a solution if one exists and report failure otherwise?, optimality: does it find an optimal (lowest path cost) solution?, time complexity: how long does it take to find a solution?, and space complexity: how much memory does it take to find a solution?). b = branching factor (number of successors of each node to consider), m = the maximum path length, and d = the maximum depth of a solution. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nBreadth-first search (BFS) takes O(b^d) time and space. BFS is complete. BFS is optimal (when actions all have the same cost). Uniform-cost search (Dijkstra's) expands nodes in the frontier with minimal g(n) first (smallest path cost from initial state). UCS checks for a goal when popping a node off the queue, not when expanding a node and finding its successors. Depth-first search (DFS) takes only O(bm) space and O(b^m) time. DFS is not complete (can fail in infinite depth spaces or when there are cycles). DFS is not optimal either. Its main draw is its low space complexity. Depth-limited search is a form of DFS that only descends to a max of depth l. Depth-limited search takes (b^l) time and O(bl) space. Iterative deepening search will run depth-limited search with a depth of 0, then 1, then 2, etc... until it finally finds a solution (or we pass a certain depth that we want to stop searching after). Iterative deepening takes O(bd) space when there's a solution and O(bm) space otherwise. Iterative deepening takes O(b^d) time when there's a solution and O(b^m) time otherwise. Iterative deepening is optimal (assuming all action costs are equivalent) and it's complete. Bidirectional search searches from the initial state and backwards from the goal states at the same time. BFS is complete, optimal (assuming equal action costs), takes O(b^d) time and space. DFS is not complete, not optimal, takes O(b^m) time and O(bm) space. Depth-limited search is not copmlete, not optimal, takes O(b^l) time and O(bl) space. Iterative deepening search is complete, optimal (assuming equal action costs), takes O(b^d) time and O(bd) space.\n\n## Module 3 Lecture Notes\nA simple reflex agent just selects an action based on the current percept alone. A problem-solving agent will seek a sequence of actions that consitute a path to a goal state (such a sequence is called a solution). If the task environment is fully observable, deterministic, and a known environment, then the solution will be a fixed sequence of actions. But if the environment is partially observable and nondeterministic, then the solution will need to recommend different action sequences based on what specific percepts it receives. A search problem is defined by the states, the initial state, the actions, the transition model (tells you the resulting state for each state, action pair), the action cost or path cost function, and a goal test (so you know when you've made it). A solution is optimal if no other solution has a lower path cost. Uninformed search strategies use only information from the problem definition. We can evaluate an algorithm through four properties (completeness : does it always find a solution?, optimality: does it find a solution with the lowest cost?, time complexity: how many nodes does it generate in the worst case?, and space complexity: how many nodes does it hold in memory at the same time in the worst case?). b = maximum branching factor of the search tree. d = depth of the shallowest goal node. m = maximum path length in the search tree. Breadth-first search (BFS) involves expanding the shallowest unexpanded nodes first. BFS is complete assuming b is finite, takes O(b^d) time and space, and is optimal (assuming action costs are all equal). Depth-first search (DFS) expands the deepest unexpanded nodes first. DFS is not complete (failing in infinite-depth and cyclic search spaces), it's not optimal, it takes O(b^m) time but only takes O(bm) space. Depth-limited search is DFS but with a depth limit l. If l = d, then it's optimal, but if l < d, it's not complete, and if l > d, then it's not optimal. Depth-limited search takes O(b^l) time and O(bl) space. Iterative deepening does depth-limited searches at increased depth limits until a solution is found. Iterative deepening is both optimal and complete, taking O(b^d) time and O(bd) space. So BFS is complete and optimal (assuming action costs are equal), and takes O(b^d) time and space. DFS is not complete and not optimal, takes O(b^m) time, but takes only O(bm) space. Depth-limited search is not complete and not optimal, takes O(b^l) time and O(bl) space. Iterative deepening is both complete and optimal, takes O(b^d) time, and takes O(bd) space.\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Optimal solution** - The solution with the lowest path cost compared to all other solutions.\n* **Graph search** - Checks for redundant paths\n* **Tree search** - Does not check for redundant paths\n* **Completeness** - Will the algorithm 100% find a solution if one exists and report failure otherwise?\n* **Optimality** - Will the algorithm find a solution with the lowest path cost?\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed search has access to the problem definition as well as a heuristic function h(n) that estimates the cheapest path cost from some state n to a goal state. Greedy best-first search expands the node with lowest h(n) first. Greedy best-first search is complete in finite state spaces, and with a good h(n), it takes O(bm) time and space. Greedy-best first search is not optimal. A* search expands the node with lowest f(n) = g(n) + h(n), so it combines greedy best-first search and uniform cost search. A* search is complete and it is also optimal (assuming we're using an admissible heuristic). An admissible heuristic is one that never overestimates the cost to reach a goal (so it's optimistic in that it always lowballs or is accurate). Satisficing solutions are suboptimal but still good enough. We can use an inadmissible heuristic with A* search to take less time and space but end up with a satisficing solution. We can do this with weighted A* search (in which we use f(n) = g(n) + (W * h(n)), weighting the heuristic). With bounded suboptimal search, we search for a solution that's within a constant factor of W from the optimal cost. Weighted A* guarantees this. In bounded-cost search, we want a solution that costs less than a constant C. In unbounded-cost search, we just want any solution so long as we can find it fast. Beam search imposes a limit on the frontier (only keep a certain number of nodes that have the best f(n) values). There's also iterative-deepening A* search (which uses a f-cost cutoff of the smallest node's f(n) that exceeded the cutoff from the last iteration).\n\n## AIMA Chapter 3.6 Heuristic Functions\nIf A* generates N nodes in its search and the solution depth was d, then b* (the effective branching factor) is the branching factor that a uniform tree with depth d would have to have to contain N + 1 nodes. Heuristics can be evaluated and compared based on their effective branching factors (b*). Good heuristics will have a b* value close to 1. If one heuristic is always better than another (provides a higher estimate but still an underestimate), then that heuristic dominates the other. A good way to generate heuristics is to consider relaxed versions of the problem (with less constraints) and get path lengths for those relaxed versions.\n\n## Module 4 Lecture Notes\nUniform-Cost search expands nodes with minimal g(n) first. Uniform-Cost search only tests if a state is a goal state when it's selected for expansion, not when we first discover it. A heuristic function h(n) gives you an estimate of the distance from n to a goal state. Greedy best-first search expands nodes with minimal h(n) first. Greedy best-first search is neither complete nor optimal. A* search expands nodes with minimal f(n) = g(n) + h(n) first. An admissible heuristic is one that never overestimates the real cost to go from the input state to a goal state (it's optimistic). If we use an admissible heuristic, then A* search is optimal. The cost of an optimal solution to a relaxed problem (meaning one in which some of the constraints of the original problem were loosened) is an admissible heuristic for the original problem. If h2(n) >= h1(n) for all n and both heuristics are admissible, then h2 dominates h1 (meaning h2 still never overestimates but always gives a closer estimate than h1). h*(n) is the best heuristic (the true distance from n to a goal state). It dominates all other heuristics. h(n) = 0 is the worst heuristic (biggest underestimate possible). It is dominated by all other heuristics. So then a heuristic is admissible if 0 <= h(n) <= h*(n). \n\n## Module 4 Definitions\n* **Admissible heuristic** - Always gives an estimate that is <= to the true cost from a state to a goal state\n* **Dominates** - A heuristic dominates another whenever it always gives a higher (closer) estimate while still being optimistic.\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nAdversarial search often occurs in perfect information, zero-sum games (in which perfect information means fully observable and zero-sum means that one player's benefit is another player's detriment). A game can be defined with the initial state, a function to determine whose turn it is in a state s, the set of actions for each state, the transition model (which tells you which state you go to after taking an action in a specific state), a terminal test (that checks if the game is over or not), and a utility function (which tells you the utility for a player in a particular terminal state). \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nWith Minimax search, we can find the optimal stategy by finding the minimax value of each state in the tree. For a MAX node, this is the maximum value of its children. For a MIN node, this is the minimum value of its children. (We're assuming both players are playing optimally). Minimax performs similarly to depth-first search. Minimax takes O(b^m) time and O(bm) space. We can improve upon Minimax with alpha-beta pruning. Alpha is the value of the best choice along the path for MAX (meaning highest value). Alpha is \"at least\". Beta is the value of the best choice along the path for MIN (meaning lowest value). Beta is \"at most\". As we go through a minimax search, whenever we encounter a node whose value is worse than the current alpha or beta value for a MAX or MIN node respectively, we can stop considering it (and its children) as it would never be selected. Alpha-beta pruning's effectiveness is highly dependent on the order in which we consider nodes in the search tree.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nWe can swap the utility function with a heuristic evaluation function which estimates the utility for a player in a particular state (and for terminal states, this estimate would be spot on). We could determine that any moves were cutoff terminal states (terminal states just for the purposes of keeping our search from searching too far in the future and going on for too long) and calculate the utilities with this evaluation function. Forward pruning involves pruning moves that look like they're bad moves (but might not be). It's faster, but could mess up. One way of doing forward pruning is with beam search (at each level, only consider the best n moves according to the evaluation function).\n\n## AIMA Chapter 5.5 Stochastic Games\nWith stochastic games, we have chance nodes that choose various actions with different probabilites. Now, we can only calculate the expected value of a position (as we can't infer what the opponent will play). Instead of minimax, we have expectimax. MIN and MAX nodes work the same way as with minimax, but chance nodes just have a value according to their expected value.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe utility function models the agent's preferences and gives a single number to model the desirability of a state. The expected utility is just the sum of all the outcome utilities for an action weighted by the probability of that outcome. The principle of maximum expected utility (MEU) states that a rational agent should take the action that maximizes their expected utility.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nThere are six constraints for any reasonable preference relation. Orderability: (A > B), (B > A), or (A ~ B), meaning the agent has to either prefer A over B, B over A or be indifferent between them. Transitivity: (A > B) and (B > C) --> (A > C) Continuity: (A > B > C) --> there's some probability p such that [p, A; 1-p, C] ~ B (meaning you're indifferent between B and a lottery between A and C such that the probability of getting A is p). Substitutability: A ~ B --> [p, A; 1-p, C] ~ [p, B; 1-p, C] (meaning if you're indifferent between A and B, then you can swap them out in lotteries and it'll make no difference). Monotonicity: A > B --> (p > q <--> [p, A; 1-p, B] > [q, A; 1-q, B]) (meaning if you prefer A over B, then you should prefer the lottery that gives you a higher chance of A than B). Decomposability: [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C] (meaning you can reduce compound lotteries to simpler ones using probability laws). If an agent's preferences follow the axioms of utility, then there's a utility function that exists such that preferred states have higher utility than others and pairs of indifferent states have equal utilities.\n\n## AIMA Chapter 16.3 Utility Functions\nNormalized utilities use a scale between 0 and 1. A micromort is a one in a million chance of death (often used to calculate how much people value their lives). Humans are generally risk-averse (they prefer certain rewards often even if they're lower than the expected reward from a gamble). But with losses, humans are risk-seeking (they'd prefer a gamble with a potentially greater loss than a lesser, sure loss). Decision theory is a normative theory (as it details how a rational agent is supposed to act. A descriptive theory describes how real agents (like humans) actually act.\n\n## Module 5 Lecture Notes\nTo formulate games as search problems, you need an initial state, a successfor function (a list of move, state pairs corresponding to legal moves), a terminal test (to test if the game's finished in a specific state), and a utility function (that gives a value to terminal states). An evaluation function gives a score for how good a state is for a certain player (it's positive when MAX is winning in that state, negative when MAX is losing, and 0 when MAX and MIN are tied). For two player deterministic games, you can use minimax search (choose the best option for MAX assuming MIN chooses their best option). Compute the minimax values for each node (for a MAX node, this is just the max of its children, and for a MIN node, it's the min of its children). We can improve upon minimax with alpha-beta pruning. Alpha is MAX's current lower bound on their outcome. Beta is MIN's current uppoer bound on MIN's outcome. MAX will never permit a move that could give a worse score for them than alpha, and MIN will never permit a move that could give a better score for MAX than beta. Use that knowledge to stop evaluating certain nodes when you know their parent would never choose them. With expectimax, we're dealing with an element of chance. Outcomes aren't certain, so node values now reflect average-case outcomes instead of worst-case outcomes. For chance nodes, their value will be their expected utilities. MAX nodes will behave the same way (choose the max child value as its value).\n\n## Module 5 Definitions\n* **Alpha** - The value of the best choice along the path for MAX (highest value), think 'at least'\n* **Beta** - The value of the best choice along the path for MIN (lowest value), think 'at most'\n* **Orderability** - A rational agent has to either prefer one lottery over another or be indifferent between them\n* **Transitivity** - If you prefer A to B and B to C, then you prefer A to C\n* **Continuity** - If lottery B's between A and C, there's a probability where a lottery between A and C's indifferent to B\n* **Substitutability** - If you're indifferent between A and B, you can swap between them in lotteries without altering preferences.\n* **Monotonicity** - If you prefer A to B, you'd prefer a lottery with a higher chance of A (all else being equal)\n* **Decomposability** - You can reduce compound lotteries to simpler ones using probability rules.\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nConstraint satisfaction problems (CSPs) have three components: a set of variables, a set of domains (one for each variable), and a set of constraints that specify the allowable combinations of values. Each domain contains a set of allowable values for its variable. CSPs concern themselves with assignments of values to variables. If an assignment doesn't violate any constraints, then it is a consistent assignment. An assignment in which every variable is assigned a value is a complete assignment. A solution to a CSP is an assignment that is both consistent and complete. A partial assignment has some unassigned variables and a partial solution is a consistent but partial assignment. A unary constrait restricts the value of only one variable. A binary constraint details a relationship between two variables. A binary CSP only has unary and binary constraints. If a constraint involves some arbitrary number of variables, it's a global constraint.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation entails using constraints to reduce the number of allowed values for a variable, which can then reduce the number for another variable, and so on. A variable is node-consistent if every value in that variable's domain satisfies the variable's unary constraints. A variable is arc-consistent if every value in that variable's domain satisfies the variable's binary constraints. (So X_i is arc-consistent with X_j if for every value in domain D_i, there is a value in D_j that satisfies the binary constraint on the (X_i, X_j) arc). Enforcing arc consistency can be done with AC-3. AC-3 takes O(cd^3) time (where c is the number of binary constraints (arcs) and d is the max domain size). It takes O(d^2) time to check the consistency of a single arc. Path consistency involves consistency between sets of three variables at a time. A CSP is k-consistent if for any set of k - 1 variables and for any consistent assignment to those variables, you can assign a consistent value to a kth variable. A CSP is strongly k-consistent if it's k-consistent and k-1 consistent and k-2 consistent, ... , and 1 consistent.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nA problem is commutative if the order in which we assign values to the variables doesn't matter. Backtracking search will repeatedly choose an unassigned variable and then try all values in that variable's domain (extending into each possibility via a recursive call). If the value led to a solution, it'll return that solution. If not, we return to the previous state and try the next value. If no value works, then we report failure. When it comes time to choose the next unassigned variable, we can choose the variable with the fewest legal values remaining (the minimum-remaining-values, MRV, heuristic). Or we could choose the variable involved in the highest number of constraints on other unassigned variables. Once we have chosen an unassigned variable, we can use the least-constraining-value heuristic to choose the value that rules out the lowest number of allowable values for neighboring variables. Forward checking involves establishing arc consistency for each newly assigned variable (now that some new variable has been assigned, we can rule out some values for variables it shares a constraint with). MAC (Maintaining Arc Consistency) is an algorithm that calls AC-3 every time a new variable is assigned (but only on the arcs that involve unassigned neighbors to this newly assigned variable as opposed to all the arcs). So MAC does better than normal forward checking as forward checking doesn't keep enforcing arc consistency after the first round of updates based on the newly assigned variables (so it uses X's assignment to change Y's domain, but then doesn't use Y's changes to update other domains). MAC does though. With backtracking, it might be a better idea to backtrack to a variable that could fix the problem (as opposed to the most recently assigned variable). You can keep track of a set of assignments that conflict with each assigned variable value (conflict sets). Then, when we encounter a problem, we backjump to the most recent assignemnt in the conflic set. \n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal search algorithms can be really helpful in solving CSPs. If you start off with a complete assignment (which likely has many constraint violations), and then choose some conflicted variable and change its value to whatever will result in the minimum number of conflicts with other variables, we can often quickly find a solution. This is called the min-conflicts heuristic. Constraint weighting will focus the search on the most important constraints. Each constraint starts off at value 1. At each step, the algorithm chooses a variable/value pair to update to result in the lowest total weight of all violated constraints. Then the constraint weights are updated by incrementing the weight of each constraint that's still violated by the current assignment.\n\n## AIMA Chapter 6.5 The Structure of Problems\nYou can find a solution in linear time to any tree-structured CSP (linear in the number of variables). Cutset conditioning algorithm: first choose a subset of the CSP's variables so that the constraint graph is a tree after removing that subset. That subset is the cycle cutset. Then, for each possible assignment to the variables in that subset that satisfy all the constraints within it, remove from the domains of any remaining variables the values that are inconsistent with the assignment for that subset and if the remaining CSP has a solution, then return it alongside the assignment for S. This process is called cutset conditioning. A tree decomposition involves a transformation of the original graph into a tree with nodes consisting of a set of variables. There are three requirements for a tree decomposition (every variable in the original problem has to be found in at least one tree node, if two variables are involved in a constraint in the original problem, they have to be found together alongside the constraint in at least one tree node, and if a variable is in two nodes in the tree, it has to appear in every node along the path between those two nodes). The tree width of a tree decomposition is the size of the largest node - 1. CSPs with constraint graphs with a bounded tree width can be solved in polynomial time. Tree decomposition is faster than cutset conditioning, but cutset conditioning takes less space. You can include symmetry-breaking constraints to reduce the search space to eliminate equivalent solutions (like in map coloring, if three zones have to be different colors, it doesn't matter if its R, G, B or G, R, B, it just matters that they're different).\n\n## Module 6 Lecture Notes\nA CSP consists of a finite state of variables, a nonempty domain of allowable values for each variable, and a finite set of constraints. A state is a specific assignment of values to some or all varaibles. A consistent assignement doesn't violate any constraints. A complete assignment has assigned a value to each variable. A solution is a complete and consistent assignment. CSPs can automatically prune off any branch in the search tree that violates constraints (speeding up the process). CSPs can be represented as constraint graphs (where nodes are variables and edges are binary constraints). Unary constraints involve a single variable. Binary constraints involve pairs of variables. Higher-order constraints involve 3+ variables. Preference (soft constraints) can be represetned with a cost for each variable assignment (red > green for example). CSPs can be expressed as search problems (with an initial state being the empty assignment, a successor function which can assign a value to any unassigned variable assuming there's no constraint conflict, a goal test (is the current assignment complete?), and a path cost function (a constant cost per step). The solution is always at depth n (n variables), so depth first search can be used. Depth first search for CSPs with single-variable assignments at each step is backtracking search. It'll backtrack when a variable has no legal values left to assign. It's the most basic uninformed algorithm for CSPs. We can improve backtracking efficiency by choosing the next variable to assign as the one with the fewest legal values remaining. This is called the minimum remaining values (MRV) heuristic. And if we have a tie, we can choose the variable with the most constraints on reamining unassigned variables. Once we've chosen a variable to assign, we can choose the value that rules out the fewest values in the remaining variables. We can also keep track of remaining legal values for unassigned variables and terminate the search process if any unassigned variables have no legal values left. Forward checking propagates info from assigned to unassigned variables, but doesn't always provide early failure detection. Constraint propagation goes further and repeatedly enforces constraints locally. This is inference. Node consistency entails satisfying unary constraints. Arc consistency entails satisfying binary constraints (two variables are arc consistent if for every value remaining for one, there's some remaining value for the other that satisfies the binary constraint between them). With d values, checking an arc takes O(d^2) time. AC-3 is used to enforce arc consistency. AC-3 takes O(n^2d^3) time where n is the number of variables and d is the max domain size.\n\n## Module 6 Definitions\n* **Consistent assignment** - One that doesn't violate any constraints\n* **Complete assignment** - One that assigns values to all variables\n* **Solution** - A consistent and complete assignment\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nA knowledge base is a set of sentences that are written in a knowledge representation language and represent an assertion about the world. If a sentence is taken as a given without needing to be derived from other sentences, it's an axiom. Inference involves deriving new correct sentences from current ones. The agent might initially be given a knowledge base that contains some background information (from which it can explore the world and expand its knowledge base, using it to find an optimal solution to its problem).\n\n## AIMA Chapter 7.2 The Wumpus World\nFor an agent in its environment, the hardest challenge stems from its initial lack of knowledge about the layout of the environment. To overcome this ignorance, it'll require logical reasoning (to deduce new information). Every time the agent comes to a new conclusion from its available information, that conclusion is 100% correct if the available information was correct. This is simply a property of logical reasoning.\n\n## AIMA Chapter 7.3 Logic\nSyntax specifies the well-formed (allowed) sentences for a representation language (doesn't mean they're true, just that their structure is correct). Semantics defines the truth of a sentence with regard to each possible world (might be true in one world but not another). Each statement has to be true or false in a particular world (no in-between). If a particular sentence is true in a model, then that model satisfies the sentence or that model is a model of that sentence. M(a) = set of all models of sentence a. a |= b iff M(a) is a subset of M(b) (definition of logical entailment). This would mean a is a stronger assertion than b (as it rules out more possible worlds). Logical entailment is used for logical inference. Model checking involves going through all possible models to check that sentence a is true in all models in which the knowledge base is true (meaning that M(KB) is a subset of M(a)). If an inference algorithm only concludes entailed sentences, it is sound (aka truth-preserving). If an inference algorithm can conclude all entailable sentences, it is complete.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nAtmoic sentences are made up of a single proposition symbol. Complex sentences are made out of simpler sentences using parentheses and logical connectives (like not, and, or, -->, and <-->). A literal can be an atomic sentence (positive literal) or a negated atomic sentence (negative literal). If a sentence's main connective is \"and\", then it's a conjunction and its parts are conjuncts. Similarly, if a sentence's main connective is \"or\", then it's a disjunction and its parts are disjuncts. The sentence A --> B is an implication or conditional and A is its premise/antecedent and B is its conclusion or consequent. Sentences with <--> are biconditionals. A model assigns a truth value to each proposition symbol. In a model m, not P is true iff P is false in m, P and Q is true iff both P and Q are true in m, P or Q is true iff either P or Q is true in m, P --> Q is true unless P is true and Q is false in m, and P <--> Q is true iff P and Q are both true or both false in m. All inference algorithms for propositional logic have a worst-case runtime that is exponential with regard to the input size.\n\n## AIMA 7.5 Propositional Theorem Proving\nTheorem proving involves using the rules of inference on the sentences in a knowledge base to generate a proof for a desired sentence without needing to consult any models. This will be more efficient than model checking if there are a lot of models to check but the proof is relatively short. Two sentences are logically equivalent if they hold true in exactly the same set of models. This is written as a (triple line equals) b. Sentence a is logically equivalent to sentence b iff a entails b and b entails a. A valid sentence is one that is true in all models. Valid sentences are also called tautologies (they're necessarily true). The deduction theorem is that for any senteces a and b, a entails b iff the sentence \"a implies b\" is valid. A satisfiable sentence is one that is true in some model. Inference rules can be applied to make a proof. They're written like this: sentence a, sentence b (dividing horizontal line) sentence c. If sentence a and b are true, then you can conclude sentence c. Modus Ponens holds that if you have \"a implies b\" and \"a\", then you can conclude \"b\". And-Elimination holds that if you have \"a and b\", then you can conclude \"a\". (You can have any number of given sentences in the top part and presumably any number of concludable sentences in the bottom part). The inference rule called resolution can be combined with any complete search algorithm to get a complete inference algorithm. The resolution rule looks like this: (top) l_1 or ... or l_k, m_1 or ... or m_n (dividing horizontal line) (bottom) l_1 or ... or l_i-1 or l_i+1 or ... or l_k or m_1 or ... or m_j-1 or m_j+1 or ... or m_n (where l_i and m_j are complementary literals). Basically, resolution will take two clauses and give you a new clause that has every literal of the original two but without those two complementary literals (l_i and m_j got eliminated). Also, the resulting clause should only have one copy of each literal, so if there are copies, remove them until one is left. This process is called factoring. If a sentence is just a conjunction of clauses (clause1 and clause2 and clause3 and ...), then it's in conjunctive normal form (CNF). To convert to CNF, use biconditional elimination, \nconditional elimination, DeMorgan's rules, and the distributivity law (of or over and). Resolution algorithms will convert (knowledge base and not sentence a) into CNF \n(we want to know that sentence a is true or not), then keep resolving each clause until either there are no new clauses that can be added (meaning the knowledge base did not entail sentence a) or we resolve two clauses into the empty clause (meaning the knowledge base does entail sentence a). The definite clause is a disjunction of literals where only one is positive. The Horn clause is a disjunction of literas where a max of one is positive.\n\n## Module 7 Lecture Notes\nKnowledge-based agents reason over an internal representation of knowledge to choose an action. A knowledge base is a set of sentences that are written in a knowledge representation language (and each sentence is a statement about the environment). Axioms are given sentences and derived sentences are those that follow from other sentences. This derivation process is inference. Syntax defines which sentences are well-formed. Semantics defines the meaning (truth value) of sentences. Models are true/false value assignments to each literal in all the sentences. If a sentence is true in a model, that model satisfies the sentence or the model is a model of that sentence. M(a) means the set of all models that satisfy sentence a. Sentence a logically entails sentence b iff M(a) is a subset of M(b). This means a is more specific than b (rules out more models). A knowledge base is false in models that contradict the agent's knowledge. Model checking involves enumerating every possible model that doesn't contradict the agent's knowledge base. Atomic sentences are made with just a single propositional symbol. Complex sentences are created from simpler ones using ()'s and logical connectives (not, and, or, implies, biconditional). Soundness is when the inference algorithm only derives entailed sentences. Copmleteness is when the inference algorithm can derive all entailable setences. Sentences are logically equivalent if they're true in exactly the same set of models. (They're logically equivalent if they each entail the other). Monotonicity refers to the fact that if the knowledge base entails a sentence a, then (knowledge base and b) entails a (meaning we can add other things to the knowledge base without invalidating anything else we've inferred). To put a sentence in CNF, eliminate biconditionals (a <--> turns to (a --> b) and (b --> a)), eliminate conditionals ((a --> b) turns to ((not a) or b)), then apply De Morgan's rules, and then use the distributivity law to distribute or's over and's until it's in CNF. Horn clauses are closed under resolution (meaning that appling resolution to Horn clauses gives you back another Horn clause.) It only takes linear time (with respect to knowledge base size) to decide entailment with Horn clauses. Forward chaining is a type of data-driven reasoning. The agent can start with some known data and add premises when new percepts are acquired and incrementally apply the forward chaining algorithm to discover new conclusions. The agent doesn't have to specifically test for a desired setence. Backward chaining works its way backwards from a query. If the query is known to be correct, then nothing has to be done. Otherwise, the algorithm will find implications in the knowledge base whose conclusions are the query. If you can prove that all the premises of one such implications are true (via backwards chaining), that would mean that the query (conclusion) is true. Backward chaining is thus a goal-directed form of reasoning.\n\n## Module 7 Definitions\n* **Sound/truth-preserving** - When an inference algorithm only concludes sentences that follow from the knowledge base (are entailed)\n* **Complete** - When an inference algorithm concludes/finds all entailed sentences\n* **Logical equivalence** - Two sentences are logically equivalent if they're true in exactly the same set of models\n* **Validity** - A valid sentence is true in every single model\n* **Satisfiability** - A satisfiable sentence is true in at least one model\n* **Definite clause** - Disjunction of literals where only one is positive\n* **Horn clause** - Disjunction of literals where at max one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}