{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "wriga FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c711b9a3-e7e3-4502-a627-b7e68fe1bc9b"
      },
      "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": 289,
      "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": "2c309017-df4e-42c0-a344-c4d0e179a738"
      },
      "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": 290,
      "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 = \"Amber Wright\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 291,
      "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 = \"\"\" \n",
        "The field of AI has taken several different versions and can be categorized in four ways: human vs rational and thought vs behavior. The pursuit \\\n",
        "of human like intelligence relates to psychology whereas rational relies on math, engineering, statistics, control theory and economics. \n",
        "\n",
        "The Turing Test was designed to help answer the question \"Can a machine think?\". If a human cannot tell if a written response (after some posed questions) \\\n",
        "comes from a computer or a human, the computer passes the test. In order to pass a test, a computer would need 4 capabilities: natural language processing, \\\n",
        "knowledge representation, automated reasoning, & machine learning.Technically, this method would not require a person to demonstrate intelligence. \\\n",
        "A Total Turing Test requires interactions with real people and objects. Therefore a robot would also need: computer vision & robotics. Researchers have not \\\n",
        "intensely focused on trying to pass the Turing Test but have focused on studying the principles of intelligence. \n",
        "\n",
        "To learn how humans think, consider three things: introspection, psycological experiemnts, and brain imaging. With a theory of the mind, we could use this \\\n",
        "theory to create a computer program with inputs/outputs corresponding with human behavior. General Problem Solving (GPS) inventors (Newell & Simon) didn't only \\\n",
        "want the algorithm to solve problems, but to also mimic the sequence and timings of the steps with those that a human would take (aka cognitive science). \n",
        "\n",
        "Aristole tried to codify \"right thinking\" into syllogisms, the start logic. Logic requires knowledge of the world that is certain. Where certainty is not possible \\\n",
        "we rely on probability. These two allow us to construct a comprehensive model of rational thought, but it not does generate intelligent behavior. For that, we \\\n",
        "would need a theory of rational action, not only rational thought.\n",
        "\n",
        "In the \"laws of thought\" approach to AI, they focused on correct inferences, but that is only part of being a rational agent. There are also other ways to act \\\n",
        "rationally that do not include inferences, such as reflexes. The rational agent approach has two advantages: it is more general than the \"laws of thought\" approach \\\n",
        "since other mechanisms are possible for acheiving rationality and it is more responsive to scientific development since it is mathematically defined and general. \\\n",
        "The rational agent approach has prevailed in AR since they are built on logical foundations and formed definite plans to achieve specific goals. It focuses on \\\n",
        "\"doing the right thing\", defined by the objective provided to the agent.\n",
        "\n",
        "We don't always have a fully specified objective to give to the machine, so we cannot always use a standard model. Therefore, we have to introduce tradeoffs and \\\n",
        "how to deal with those tradeoffs by creating value alignment problems. We want to make sure machines behave and do not take some drastic measure to reach an objective, \\\n",
        "therefore we need to make sure we formulate correctly.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "Dreyfus believed that human behavior cannot be captured by a set of rules, we are too complex, and therefore could never be coded into a computer program. They critizied \\\n",
        "Good Old Fashion AI as not being able to product durable results, refering to AI as a simple logical agent. It is difficult to capture every possible appropriate behavior \\\n",
        "in a set of logical rules (refered to as a qualification problem). Probabalistic reasoning allows for more open ended domains while deep learning does well with 'informal' \\\n",
        "tasks. We have expanded upon the different techniques available in AI and thus can go beyond the original critique that Dreyfus had.\n",
        "\n",
        "Situated agents should be used to embody the entire experience, such as being able to watch, run, play, and pet a dog, compared to just a logical inference engine that just \\\n",
        "knows Dog(x) => Mammal(x). Embodied cognition includes the whole body and brain, not just the brain. Therefore this means that sensors and cameras are necessary instead of \\\n",
        "peripheral. \n",
        "\n",
        "Godel Sentence:\n",
        "* G(F) is a sentence of F, but cannot be proved within F.\n",
        "* If F is consistent, then G(F) is true.\n",
        "\n",
        "Godel's Incompleteness Theorem states that machines cannot establish the truth of their own Godel Sentences. This only applies to machines that can do arithmetic with infinite. \n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "The Chinese Room\n",
        "You have a man in a box. The man is given a paper with symbols. The man has a book to help decipher the symbols. Once dechipered, the man passes the translation back out of the box.\\\n",
        "One can argue the man does not know chinese. The box is no different than a computer, the computer does not think or understand, it just does. \n",
        "\n",
        "Do machines have consciousness? Are they aware of the outside world and of themselves? Can they feel? We can program intelligence and awareness, but cannot program the same level of \\\n",
        "consciousness that humans have. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "Vacuum Cleaner World\n",
        "* agent = robotic vacuum cleaner\n",
        " * percepts = perceives if there is dirt in the square and its location\n",
        " * sensors = dirt sensor, camera for navigation\n",
        " * actuators = brushes to pick up dirt\n",
        "* actions = move left, right; pick up dirt; do nothing\n",
        "* agent function = if square has dirt, pick it up, otherwise, move to another square\n",
        "* environment = the two squares it has access to. it doesnt care about anything else\n",
        "\n",
        "Robo vacuum's agent function can be tabulated by all the possible states it could take. What is the best way to fill out the table to make \\\n",
        "robo vacuum the best it can be?\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "We can take a measure of the agent doing the right thing with the concept of consequentialism, what are the consequences of the agent's actions. \\\n",
        "An agent will go through a sequence of actions and those actions will result in a sequence of environmental states. If one of those sequences is \\\n",
        "desirable from the human's POV, then the agent has performed desirably. This is captured by a performance measure that evaluates a sequence of \\\n",
        "environmental states. Performance measures can be explicitly known to the agent, or implicitly known, but in the latter the agent will not know \\\n",
        "why it did the right thing.\n",
        "* performance measure = all the floor is clean\n",
        "\n",
        "Design performance measures based on what you want to be done in the environment, not how you think the agent should act. \n",
        "\n",
        "What is rational at a point in time depends on four things:\n",
        "* performance measures\n",
        "* agent's prior knowledge of the environment\n",
        "* actions agent can perform\n",
        "* agent's percept sequence up to the current point in time\n",
        "\n",
        "A rational agent should select an action that will maximize its performance measure, given all the data that it currently has (including built-in knowledge \\\n",
        "and historical knowledge from the given percept sequence) for a possible percept sequence.\n",
        "\n",
        "Rationality is not omsciscience. The agent will not know EXACTLY what the outcome of its actions to know the perfect sequence to take. Rationality maximizes \\\n",
        "expected performance, we should not expect agents to be perfect. We only rely on the percepts we know to date and not any future information. We should also \\\n",
        "make sure that the agent doesn't do anything stupid and gathers information along the way or explores its environment to learn more before taking a further \\\n",
        "action. A rational agent should be autonomous and should learn without the aid of its designer. \n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "Task Environment Properties:\n",
        "* Fully observable vs **partially observable** = knowing all the info in the env vs only part. No need to store an internal state of a fully observable env compared to partially observable. Could also be partially obserable from noisy data or sensors. \\\n",
        "If there are no sensors, then an env could be unobservable. Goals could still be achievable in an unobservable env.\n",
        "* Single agent vs **multiagent** = crossword or sudoku puzzle are single agent. Chess and checkers are (competitive) multiagent. The car would be considered an agent if its behavior is trying to max a performance measure whose value depends on agent A's behavior \\\n",
        "All taxis are agents, but in a partially cooperative env because avoiding collisions helps all their performance measures.\n",
        "* Deterministic vs **nondeterministic** = If next state after the agent makes an action is known, this is deterministic. If the env state is not known after the action, this is nondeterministic. In a fully observable, deterministic env, uncertainty is not a concern. Nondeterministic can be stochastic, where we can have known probabilities for things happening in the env. \n",
        "* Episodic vs **sequential** = In episodic env, the agents actions are divided into episodes; agent receives a percept and performs one action. The next episode will not depend on the previous episode, it is its own instance (starting from scratch). \\\n",
        "In sequential envs, the agent needs to consider what happened before. In chess,  A needs to take an action base on B's move and will need to think ahead for the best possible move.\n",
        "* Static vs **Dynamic** =  In a static env, the agent doesn't worry about changes in the env while selecting an action. If the env is changing continuously, then the env is dynamic and the agent will need to constantly evaluate and will constantly be asked what to do. If the env does NOT change but its performance measure does over time, this is semidynamic. An agent could take a performance hit based taking ample time to reach the goal, such as chess with a timer. \n",
        "* Discrete vs **continuous** = Used to describe the state of the env, how time is handled, percepts and actions. Discrete refers to a finite number. Taxi driving has multiple continuous attributes; speed, location, other vehicles, steering angles, etc.\n",
        "* Known vs **unknown** = In a known env, the outcomes (or outcome probabs) for all actions are given, the agent will know the resulting state after the \\\n",
        "action. If the env is unknown, the agent will have to observe the outcome based on the action taken to know if it was a good decision. \n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "AI is intended to design an agent program that implements the agent function. The agent program will run on an agent architecture. The architecture needs to be \\\n",
        "appropriate for the agent program. If the agent needs to walk, it needs legs, if it needs to be able to see, it needs a camera. \\\n",
        "The architecture makes the percepts from the sensors available to the program, runs the program to decide the next action, and tells the actuators what action \\\n",
        "to take. A agent program takes only the current percept sequence to make a decision, the agent function could take into account the entire percept history. \\\n",
        "Only in very simple scenarios is it possible to have a table driven agent. In most scenarios, there are too many sets of possible percepts for a lookup table. \n",
        "Agent programs:\n",
        "* Simple reflex agents - Select actions based on the current percept, ignoring the rest of the percept history. These can be described with a condition-action rule: \\\n",
        "\"if <thing is happening> then <do something>\". \n",
        "* Model-based agents - Store the percept history in an internal state that the agent can reflect on for some of the unobservable aspects of the current state.  \\\n",
        "The agent will keep track of other knowledge of the env, even if it is not receiving percepts about it currently. Knowledge about what will happen in the world \\\n",
        "when the agent takes an action described by a transition model. Knowledge about the percepts the sensor receives and what they mean can be described by a sensor \\\n",
        "model. Tracking of the transition model and sensor model combined is what makes up a model-based agent. \n",
        "* Goal-based agents - Just knowing about the env is not enough for the agent to produce desirable results, the agent needs to know the goals \\\n",
        "to determine desirable situations. An agent is goal-based if it's decided actions help it reach a given goal. Sometimes it is simple to find a goal, \\\n",
        "it only takes one action. But often times you need a sequence of actions to reach a goal. Use search and planning strategies to find this sequence. \n",
        "* Utility-based agents - Agents that compare the diff between states to decide whether one is better than the other. An agent's utility fcn describes \\\n",
        "the performance measure. The agent can choose actions that max its utliity (\"happiness\") if the utility fcn and performance measure are in alignment. \\\n",
        "If there are conflicting goals, the utility function can help determine tradeoffs. A rational utility-based agent chooses an action that will max the expected \\\n",
        "utlity of the outcomes. A utility based agent has to model and keep track of its env. \n",
        "\n",
        "Learning agents:\n",
        "* learning element makes improvements\n",
        "* performance element selects actions\n",
        "* critic determines the performance element\n",
        "* problem generator suggesting actions\n",
        "\n",
        "Components of agent programs:\n",
        "* atomic - no internal structure, just goes from one state to another\n",
        "* factored - splits states into a fixed set of variables with values\n",
        "* structured - includes objects with attributes and relationships between the objects\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "It is possible to have a known, partially observed env (solitaire). You know all rules, but some of the cards are hidden. An env can be unknown and fully observable. Such as a video game where all the env is viewable, but  the results of the buttons are unknown. \\\n",
        "You could have an unknown performance measure, if we don't know the preferences of the judges.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you must use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"artificial intellience\": \"the field to understand and build intelligent entities that can act effectively and safely in a situation\",\n",
        "\"rationality\" : \"doing the right thing\",\n",
        "\"natural language processing\": \"area of AI for computers being able to understand text and spoken words like a human\",\n",
        "\"knowledge representation\": \"storing known or learned data in a way a computer can understand it\", \n",
        "\"automated reasoning\": \"computers using logic to answer problems and draw conclusions, such as inferences\",\n",
        "\"machine learning\": \"computers learning from data and building models, allowing the results to adapt, detect, and extrapolate patterns to make decisions\",\n",
        "\"computer vision\": \"computers understanding the world through pictures and videos\",\n",
        "\"robotics\": \"machines that can manipulate objects and the world around them through physical movement\",\n",
        "\"introspection\": \"analying internal thoughts\",\n",
        "\"psycological experiments\": \"observation of humans\",\n",
        "\"brain imaging\": \"observation of an active brain\",\n",
        "\"cognitive science\": \"field of computer science that combines AI computer models and psycological experiment techniques to construct theories of the human mind\",\n",
        "\"syllogisms\": \"codifying irrefutable reasoning processes into patterns for argument structures that always yield correct conclusions given correct premises\",\n",
        "\"logic\": \"laws of thought that govern the operation of the mind, given a precise notation for statements\",\n",
        "\"probability\": \"representation of uncertainty\",\n",
        "\"agent\": \"something that acts; could operate autonomously, percieve environment, adapt, and persist to pursue goals\",\n",
        "\"rational agent\": \"agent that acts to achieve the best outcome, following actions that are the 'right thing to do'\",\n",
        "\"standard model\": \"paradigm stating for AI, the right thing is determined by the objective provided to the agent\",\n",
        "\"value alignment problem\": \"problem of achieving agreement between the human's preferences and the objective given to the machine\",\n",
        "\"weak AI\": \"acting intelligently through simulated thinking\",\n",
        "\"strong AI\": \"actually consciously thinking (instead of simulated thinking)\",\n",
        "\"qualification problem\": \"impossibility of being able to create a set of necessary and sufficient logical rules that captures all situations.\",\n",
        "\"agent\": \"anything that can percieve its environment through sensors and can act on its environment through actuators\",\n",
        "\"percept\" : \"data received by the agents sensors. percept sequence is the entire history of data that percept has recieved.\",\n",
        "\"agent function\" : \"an abstract mathematical function that describes the behavior of the agent by mapping a percept sequence to an action\",\n",
        "\"agent program\" : \"concrete implementation that implements the agent function and runs it in the real world\",\n",
        "\"percept sequence\" : \"everything the agent has perceived up until the current point in time\",\n",
        "\"task environment\" : \"the definition of problems for a rational agent to solve\",\n",
        "\"agent architecture\" : \"some computing device with physical sensors and actuators. agent = architecture + program\",\n",
        "\"expected utility\" : \"the average utility the agent can achieve given the probabilities and utilities of each outcome\",\n",
        "\"task environment\" : \"defined by PEAS\",\n",
        "\"Performance\" : \"peformance measure to aspire towards\",\n",
        "\"Environment\" : \"surroundings that the agent needs to be concerned with, both physical and virtual\",\n",
        "\"Acutators\" : \"controls allowing the agent to take actions\",\n",
        "\"Sensors\" : \"means for gathering percepts, seeing, hearing, etc.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 292,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7a3523f7-dbb8-4793-f8aa-80f34032f5f5"
      },
      "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": 293,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nThe field of AI has taken several different versions and can be categorized in four ways: human vs rational and thought vs behavior. The pursuit of human like intelligence relates to psychology whereas rational relies on math, engineering, statistics, control theory and economics. \n\nThe Turing Test was designed to help answer the question \"Can a machine think?\". If a human cannot tell if a written response (after some posed questions) comes from a computer or a human, the computer passes the test. In order to pass a test, a computer would need 4 capabilities: natural language processing, knowledge representation, automated reasoning, & machine learning.Technically, this method would not require a person to demonstrate intelligence. A Total Turing Test requires interactions with real people and objects. Therefore a robot would also need: computer vision & robotics. Researchers have not intensely focused on trying to pass the Turing Test but have focused on studying the principles of intelligence. \n\nTo learn how humans think, consider three things: introspection, psycological experiemnts, and brain imaging. With a theory of the mind, we could use this theory to create a computer program with inputs/outputs corresponding with human behavior. General Problem Solving (GPS) inventors (Newell & Simon) didn't only want the algorithm to solve problems, but to also mimic the sequence and timings of the steps with those that a human would take (aka cognitive science). \n\nAristole tried to codify \"right thinking\" into syllogisms, the start logic. Logic requires knowledge of the world that is certain. Where certainty is not possible we rely on probability. These two allow us to construct a comprehensive model of rational thought, but it not does generate intelligent behavior. For that, we would need a theory of rational action, not only rational thought.\n\nIn the \"laws of thought\" approach to AI, they focused on correct inferences, but that is only part of being a rational agent. There are also other ways to act rationally that do not include inferences, such as reflexes. The rational agent approach has two advantages: it is more general than the \"laws of thought\" approach since other mechanisms are possible for acheiving rationality and it is more responsive to scientific development since it is mathematically defined and general. The rational agent approach has prevailed in AR since they are built on logical foundations and formed definite plans to achieve specific goals. It focuses on \"doing the right thing\", defined by the objective provided to the agent.\n\nWe don't always have a fully specified objective to give to the machine, so we cannot always use a standard model. Therefore, we have to introduce tradeoffs and how to deal with those tradeoffs by creating value alignment problems. We want to make sure machines behave and do not take some drastic measure to reach an objective, therefore we need to make sure we formulate correctly.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nDreyfus believed that human behavior cannot be captured by a set of rules, we are too complex, and therefore could never be coded into a computer program. They critizied Good Old Fashion AI as not being able to product durable results, refering to AI as a simple logical agent. It is difficult to capture every possible appropriate behavior in a set of logical rules (refered to as a qualification problem). Probabalistic reasoning allows for more open ended domains while deep learning does well with 'informal' tasks. We have expanded upon the different techniques available in AI and thus can go beyond the original critique that Dreyfus had.\n\nSituated agents should be used to embody the entire experience, such as being able to watch, run, play, and pet a dog, compared to just a logical inference engine that just knows Dog(x) => Mammal(x). Embodied cognition includes the whole body and brain, not just the brain. Therefore this means that sensors and cameras are necessary instead of peripheral. \n\nGodel Sentence:\n* G(F) is a sentence of F, but cannot be proved within F.\n* If F is consistent, then G(F) is true.\n\nGodel's Incompleteness Theorem states that machines cannot establish the truth of their own Godel Sentences. This only applies to machines that can do arithmetic with infinite. \n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nThe Chinese Room\nYou have a man in a box. The man is given a paper with symbols. The man has a book to help decipher the symbols. Once dechipered, the man passes the translation back out of the box.One can argue the man does not know chinese. The box is no different than a computer, the computer does not think or understand, it just does. \n\nDo machines have consciousness? Are they aware of the outside world and of themselves? Can they feel? We can program intelligence and awareness, but cannot program the same level of consciousness that humans have. \n\n\n## AIMA 2.1 Agents and Environments\n\nVacuum Cleaner World\n* agent = robotic vacuum cleaner\n * percepts = perceives if there is dirt in the square and its location\n * sensors = dirt sensor, camera for navigation\n * actuators = brushes to pick up dirt\n* actions = move left, right; pick up dirt; do nothing\n* agent function = if square has dirt, pick it up, otherwise, move to another square\n* environment = the two squares it has access to. it doesnt care about anything else\n\nRobo vacuum's agent function can be tabulated by all the possible states it could take. What is the best way to fill out the table to make robo vacuum the best it can be?\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWe can take a measure of the agent doing the right thing with the concept of consequentialism, what are the consequences of the agent's actions. An agent will go through a sequence of actions and those actions will result in a sequence of environmental states. If one of those sequences is desirable from the human's POV, then the agent has performed desirably. This is captured by a performance measure that evaluates a sequence of environmental states. Performance measures can be explicitly known to the agent, or implicitly known, but in the latter the agent will not know why it did the right thing.\n* performance measure = all the floor is clean\n\nDesign performance measures based on what you want to be done in the environment, not how you think the agent should act. \n\nWhat is rational at a point in time depends on four things:\n* performance measures\n* agent's prior knowledge of the environment\n* actions agent can perform\n* agent's percept sequence up to the current point in time\n\nA rational agent should select an action that will maximize its performance measure, given all the data that it currently has (including built-in knowledge and historical knowledge from the given percept sequence) for a possible percept sequence.\n\nRationality is not omsciscience. The agent will not know EXACTLY what the outcome of its actions to know the perfect sequence to take. Rationality maximizes expected performance, we should not expect agents to be perfect. We only rely on the percepts we know to date and not any future information. We should also make sure that the agent doesn't do anything stupid and gathers information along the way or explores its environment to learn more before taking a further action. A rational agent should be autonomous and should learn without the aid of its designer. \n\n\n## AIMA 2.3 The Nature of Environments\n\nTask Environment Properties:\n* Fully observable vs **partially observable** = knowing all the info in the env vs only part. No need to store an internal state of a fully observable env compared to partially observable. Could also be partially obserable from noisy data or sensors. If there are no sensors, then an env could be unobservable. Goals could still be achievable in an unobservable env.\n* Single agent vs **multiagent** = crossword or sudoku puzzle are single agent. Chess and checkers are (competitive) multiagent. The car would be considered an agent if its behavior is trying to max a performance measure whose value depends on agent A's behavior All taxis are agents, but in a partially cooperative env because avoiding collisions helps all their performance measures.\n* Deterministic vs **nondeterministic** = If next state after the agent makes an action is known, this is deterministic. If the env state is not known after the action, this is nondeterministic. In a fully observable, deterministic env, uncertainty is not a concern. Nondeterministic can be stochastic, where we can have known probabilities for things happening in the env. \n* Episodic vs **sequential** = In episodic env, the agents actions are divided into episodes; agent receives a percept and performs one action. The next episode will not depend on the previous episode, it is its own instance (starting from scratch). In sequential envs, the agent needs to consider what happened before. In chess,  A needs to take an action base on B's move and will need to think ahead for the best possible move.\n* Static vs **Dynamic** =  In a static env, the agent doesn't worry about changes in the env while selecting an action. If the env is changing continuously, then the env is dynamic and the agent will need to constantly evaluate and will constantly be asked what to do. If the env does NOT change but its performance measure does over time, this is semidynamic. An agent could take a performance hit based taking ample time to reach the goal, such as chess with a timer. \n* Discrete vs **continuous** = Used to describe the state of the env, how time is handled, percepts and actions. Discrete refers to a finite number. Taxi driving has multiple continuous attributes; speed, location, other vehicles, steering angles, etc.\n* Known vs **unknown** = In a known env, the outcomes (or outcome probabs) for all actions are given, the agent will know the resulting state after the action. If the env is unknown, the agent will have to observe the outcome based on the action taken to know if it was a good decision. \n\n\n## AIMA 2.4 The Structure of Agents\n \nAI is intended to design an agent program that implements the agent function. The agent program will run on an agent architecture. The architecture needs to be appropriate for the agent program. If the agent needs to walk, it needs legs, if it needs to be able to see, it needs a camera. The architecture makes the percepts from the sensors available to the program, runs the program to decide the next action, and tells the actuators what action to take. A agent program takes only the current percept sequence to make a decision, the agent function could take into account the entire percept history. Only in very simple scenarios is it possible to have a table driven agent. In most scenarios, there are too many sets of possible percepts for a lookup table. \nAgent programs:\n* Simple reflex agents - Select actions based on the current percept, ignoring the rest of the percept history. These can be described with a condition-action rule: \"if <thing is happening> then <do something>\". \n* Model-based agents - Store the percept history in an internal state that the agent can reflect on for some of the unobservable aspects of the current state.  The agent will keep track of other knowledge of the env, even if it is not receiving percepts about it currently. Knowledge about what will happen in the world when the agent takes an action described by a transition model. Knowledge about the percepts the sensor receives and what they mean can be described by a sensor model. Tracking of the transition model and sensor model combined is what makes up a model-based agent. \n* Goal-based agents - Just knowing about the env is not enough for the agent to produce desirable results, the agent needs to know the goals to determine desirable situations. An agent is goal-based if it's decided actions help it reach a given goal. Sometimes it is simple to find a goal, it only takes one action. But often times you need a sequence of actions to reach a goal. Use search and planning strategies to find this sequence. \n* Utility-based agents - Agents that compare the diff between states to decide whether one is better than the other. An agent's utility fcn describes the performance measure. The agent can choose actions that max its utliity (\"happiness\") if the utility fcn and performance measure are in alignment. If there are conflicting goals, the utility function can help determine tradeoffs. A rational utility-based agent chooses an action that will max the expected utlity of the outcomes. A utility based agent has to model and keep track of its env. \n\nLearning agents:\n* learning element makes improvements\n* performance element selects actions\n* critic determines the performance element\n* problem generator suggesting actions\n\nComponents of agent programs:\n* atomic - no internal structure, just goes from one state to another\n* factored - splits states into a fixed set of variables with values\n* structured - includes objects with attributes and relationships between the objects\n\n\n## Module 1 Lecture Notes\n\nIt is possible to have a known, partially observed env (solitaire). You know all rules, but some of the cards are hidden. An env can be unknown and fully observable. Such as a video game where all the env is viewable, but  the results of the buttons are unknown. You could have an unknown performance measure, if we don't know the preferences of the judges.\n\n\n## Module 1 Definitions\n* **Artificial intellience** - the field to understand and build intelligent entities that can act effectively and safely in a situation\n* **Rationality** - doing the right thing\n* **Natural language processing** - area of AI for computers being able to understand text and spoken words like a human\n* **Knowledge representation** - storing known or learned data in a way a computer can understand it\n* **Automated reasoning** - computers using logic to answer problems and draw conclusions, such as inferences\n* **Machine learning** - computers learning from data and building models, allowing the results to adapt, detect, and extrapolate patterns to make decisions\n* **Computer vision** - computers understanding the world through pictures and videos\n* **Robotics** - machines that can manipulate objects and the world around them through physical movement\n* **Introspection** - analying internal thoughts\n* **Psycological experiments** - observation of humans\n* **Brain imaging** - observation of an active brain\n* **Cognitive science** - field of computer science that combines AI computer models and psycological experiment techniques to construct theories of the human mind\n* **Syllogisms** - codifying irrefutable reasoning processes into patterns for argument structures that always yield correct conclusions given correct premises\n* **Logic** - laws of thought that govern the operation of the mind, given a precise notation for statements\n* **Probability** - representation of uncertainty\n* **Agent** - anything that can percieve its environment through sensors and can act on its environment through actuators\n* **Rational agent** - agent that acts to achieve the best outcome, following actions that are the 'right thing to do'\n* **Standard model** - paradigm stating for AI, the right thing is determined by the objective provided to the agent\n* **Value alignment problem** - problem of achieving agreement between the human's preferences and the objective given to the machine\n* **Weak ai** - acting intelligently through simulated thinking\n* **Strong ai** - actually consciously thinking (instead of simulated thinking)\n* **Qualification problem** - impossibility of being able to create a set of necessary and sufficient logical rules that captures all situations.\n* **Percept** - data received by the agents sensors. percept sequence is the entire history of data that percept has recieved.\n* **Agent function** - an abstract mathematical function that describes the behavior of the agent by mapping a percept sequence to an action\n* **Agent program** - concrete implementation that implements the agent function and runs it in the real world\n* **Percept sequence** - everything the agent has perceived up until the current point in time\n* **Task environment** - defined by PEAS\n* **Agent architecture** - some computing device with physical sensors and actuators. agent = architecture + program\n* **Expected utility** - the average utility the agent can achieve given the probabilities and utilities of each outcome\n* **Performance** - peformance measure to aspire towards\n* **Environment** - surroundings that the agent needs to be concerned with, both physical and virtual\n* **Acutators** - controls allowing the agent to take actions\n* **Sensors** - means for gathering percepts, seeing, hearing, etc.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 294,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "c5da1fb4-f673-47e7-e208-b02634ef9999"
      },
      "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": 295,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        " First we will work with episodic, single agent, fully observable, deterministic, static, discrete, and known environment. If we assume that the agent will \\\n",
        " always have access to info about the world, they can follow a four phase problem solving process:\n",
        " * Goal Formulation: agent adopts a goal and uses it to limit its objectives and organize its behavior/actions\n",
        " * Problem Formulation: abstract model of the wolrd using descriptions of states and actions to reach a goal.\n",
        " * Search: simulating sequences of actions to reach a goal. A correct sequence that reaches a goal is a solution. The agent might have to try multiple sequences \\\n",
        " before it finds a solution or discovers no solution is possible.\n",
        " * Execution: execution of the actions in the solution sequence.\n",
        "\n",
        " In a fully observable, deterministic, known environment, the solution is a fixed sequence of actions. If the model is correct, the agent can execute the \\\n",
        " actions without any percepts since the solution is guranteed to reach a goal. If model is incorrect or the environment is nondeterministic, then a closed-loop \\\n",
        " approach is needed. In partially observable or nondeterministic, a solution might need branches depending on the percepts received to decide actions.\n",
        "\n",
        " Search Problem:\n",
        " * set of possible states (state space)\n",
        " * initial state\n",
        " * set of goal states\n",
        " * set of actions applicable in a state; ACTIONS(s)\n",
        " * transition model\n",
        " * action cost function - problem solving agent should use an action cost function that refects its performance measures\n",
        "\n",
        "Action costs are additive along a path. State spaces can be represented as a graph; vertices are states, directed edges are actions between the states. \\\n",
        "Good problem formulation has just the right amount of detail/level of abstraction. An abstraction is *valid* if we can apply the resulting solution \\\n",
        "to the real world. An abstraction is *useful* if it is possible to carry out each of the actions in the solution without additional solving. A good abstraction \\\n",
        "removes as much detail as possible while retailing validity and the ability to carry out the actions.  \n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Vacuum World Example\n",
        "* States = instances of the grid world stating which objects (dirt) are in which cells. $n cells = n*2^n states$\n",
        "* Initial state = chosen state to start\n",
        "* Actions = suck, move left, move right. (could add move up, move down in 2d world)  \n",
        "* Transition Model\n",
        " * Suck = Removes dirt\n",
        " * Turn (left or right) = Change direction 180deg\n",
        " * Forward = move one cell (if possible)\n",
        " * Backward = move in opposite direction\n",
        "* Goal states = every cell in grid world is clean\n",
        "* Action cost = each action costs 1\n",
        "\n",
        "Routing-finding problem examples include driving directions, routing video streams in computer networks, military operations planning.\n",
        "Airline Travel Example\n",
        "* States = location and current time, plus any historical information\n",
        "* Initial state = home airport\n",
        "* Actions = take flight in a seat class at a time after current time with enough time for any transfers\n",
        "* Transition Model\n",
        " * taking a flight = flight destination and arrival time\n",
        "* Goal states = destination city\n",
        "* Action cost = price of flight, waiting time, flight time, custom & immigration procedures, seal quality, time of day, type of airplane, preferred airline, etc.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Many search problems can be formulated as search trees with the root as the initial state. We will expand nodes in the search tree until we find a goal state. \\\n",
        "Expand nodes using the available actions for that state to generate child/successor nodes for the resulting state.\n",
        "\n",
        "Best-First Search\n",
        "* Add initial node to the frontier\n",
        "* while frontier is not empty\n",
        "* Pop a node\n",
        "* If the node is a goal state, return node\n",
        "* For each child in EXPAND\n",
        " * if the state has not been reached before or the cost is less than the reached cost (looking for minimum cost)\n",
        "  * note child as reached\n",
        "  * add child to frontier\n",
        "* if no solution is found, return failure\n",
        "\n",
        "EXPAND\n",
        "* For each action for the given node\n",
        " * Run the evaluation function (path-cost + action-cost)\n",
        " * Evaluate the resulting state\n",
        " * Yield new node as the state, parent, action, and cost\n",
        "\n",
        "Each state is represented by a node. The node holds information about the\n",
        "* state = environment state\n",
        "* parent = node of the tree that generated this node\n",
        "* action = action that generated this node\n",
        "* path cost = total cost of the path from initial state to this node\n",
        "\n",
        "Queues are used to store the frontier since we need operations for is-empty, pop, top (returns node but does not remove it), and add.\n",
        "\n",
        "Algorithms are not efficient if they repeat paths they have already visited.\n",
        "* Remember all previously visited states (like best first search). Only possible if table of reached states will fit in memory.\n",
        "* Problem formulations does not result in loops. Path from A-B but not B-A.\n",
        "* Check for cycles, but not redundant paths.\n",
        "\n",
        "Tree search uses less memory since it doesn't have to remember visited nodes. If there are loops, it will run slower than graph search. \\\n",
        "In finite state spaces, a complete algorithm can explore every state that is reachable from an initial state as long as it keeps track of paths \\\n",
        "and cuts off cycles. In infinite state spaces, the search algorithm must systematically explore the state space to ensure it reaches any state \\\n",
        "connected to the initial state. If there is no solution for an inifinite state space, there needs to be a way to terminate so it doesn't search \\\n",
        "forever. Size of state space can be represented as |V|+|E| or for implicit state spaces, depth (d), max number of actions in a path (m), branching factor (b).\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Uninformed search algorithms do not know how close they are to the goal. If all actions have the same cost, Breadth-First Search (BFS) can be used. \\\n",
        "BFS is a systematic search strategy that is complete even in infinite state spaces. BFS always find an optimal solution if all actions have the same cost. \\\n",
        "BFS time and space complexity is $O(b^d)$. Since it is exponential, large state spaces would take too long, but even worst, would take too much space.\n",
        "\n",
        "Dijkstra's Algorithm or Uniform-Cost Search (UCS) is BFS where the actions have different costs. The evaluation function is the cost of the path from the \\\n",
        "root node to the current node. UCS is best-first search with the path costs.\n",
        "* expand the node with the least total path cost\n",
        "* as nodes are expanded, check to see if the node (not the child) is the goal\n",
        "* if node has a lower path cost, replace path in reached and add to frontier. There is no reason to visit nodes with higher path costs. \n",
        "\n",
        "Depth-First Search (DFS) is implemented as a tree search (does not keep track of reached) where it expands to the deepest node before going to the next branch. \\\n",
        "If it reaches the end of the branch, it backs up to the previous deepest node that has unexpanded children. DFS will return the first solution it finds \\\n",
        "(not cost-optimal). DFS can get stuck going down an infinite path or in cycles. It is not systematic, therefore not complete. DFS uses much less memory than BFS  \\\n",
        "since it does not keep track of reached. In a variant of DFS, backtracking uses less memory because it only generates one child at a time by modifying the current \\\n",
        "state description directly. Because we modify it directly, we have to be able to undo the actions when we backtrack. \n",
        "\n",
        "Depth-limited Search can keep DFS from going down an infinite path by supplying a depth limit (l) where children at l are treated like they are leaves. \\\n",
        "If we pick l poorly, it will fail to reach a solution. l can be chosen based on the problem or knowing the diameter of the state space. Often we will not \\\n",
        "know that until we have solved the problem. \n",
        "\n",
        "Iterative Deepening solves the problems of depth-limited by trying all values of l until it reaches a solution or hits a cutoff depth. Iterative deepening is \\\n",
        "the preferred uninformed search method when the state space is larger than what can fit in memory and the depth is unknown.\n",
        "\n",
        "Bidirectional search searches both from the initial state and backward from the goal state(s), in hopes that the searches will meet. It needs to keep track \\\n",
        "of two frontiers and reached states. We would also need to be able to reason backwards to determine who are the successors of who. The solution is found when \\\n",
        "the searches meet in the middle. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "**BFS**\n",
        "* If node is a goal state, return node\n",
        "* add node to FIFO frontier\n",
        "* while frontier is not empty\n",
        " * pop the oldest node\n",
        " * for each child of the node\n",
        "  * if child is a goal state, return (we are able to do an early goal test right after child is generated instead of after popped from frontier)\n",
        "  * if child's state has not been reached\n",
        "   * add state to reached\n",
        "   * add child to frontier\n",
        "* if goal is not found, return failure\n",
        "\n",
        "\n",
        "**Comparison Table**\n",
        "\n",
        "| Syntax        \t|    BFS   \t|         UCS        \t|    DFS   \t| Depth-Limited \t| Iterative Deepening \t|\n",
        "|---------------\t|:--------:\t|:------------------:\t|:--------:\t|:-------------:\t|:-------------------:\t|     \n",
        "| Complete?     \t|   Yes 1  \t|       Yes 1,2      \t|    No    \t|       No      \t|        Yes 1        \t|\n",
        "| Optimal cost? \t|   Yes 3  \t|         Yes        \t|    No    \t|       No      \t|        Yes 3        \t|\n",
        "| Time          \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t| $O(b^m)$ \t|    $O(b^l)$   \t|       $O(b^d)$      \t|  \n",
        "| Space         \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t|  $O(bm)$ \t|    $O(bl)$    \t|       $O(bd)$       \t|  \n",
        "\n",
        "| Syntax        \t| Bidirectional \t| Minimax           | Alpha-beta        |  Expectiminimax   |  AC-3             |\n",
        "|---------------\t|:-------------:\t|:-------------:    |:-------------:    |:-------------:    |:-------------:    |     \n",
        "| Complete?     \t|    Yes 1,4    \t|        \t          |                   |                   |                   |\n",
        "| Optimal cost? \t|    Yes 3,4    \t|       \t          |                   |                   |                   |\n",
        "| Time          \t|  $O(b^{d/2})$ \t|  $O(b^{m})$   \t  |  $O(b^{m/2})$     | $O(b^{m}n^m)$     |  $O(cd^{3})$      |  \n",
        "| Space         \t|  $O(b^{d/2})$ \t|  $O(bm)$ \t        |                   |                   |                   | \n",
        "1. if b is finite and state space has solution or is finite\n",
        "2. all action costs are > 0\n",
        "3. all action costs are identical\n",
        "4. both directions are BFS or UCS\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search using atomic representations\",\n",
        "\"planning agents\" : \"an agent that can formulate a plan via search using factored or structured representations of states\",    \n",
        "\"open-loop\": \"system where the solution can be executed without any percepts\",\n",
        "\"closed-loop\": \"system where the agent will need to monitor percepts while executing a solution\",\n",
        "\"transition model\": \"describes what each action does and the resulting state; RESULT(s,a) = s'\",\n",
        "\"action cost function\": \"supplies the numeric cost of an action from one state to another; ACTION-COST(s,a,s')\",\n",
        "\"path\": \"sequences of actions\",\n",
        "\"solution\": \"path from state to a goal state\",\n",
        "\"optimal solution\": \"lowest path cost among all solutions\",\n",
        "\"model\": \"abstract mathematical description of a problem\",\n",
        "\"abstraction\": \"removing detail from a representation\",\n",
        "\"standardized problem\": \"used to exercise problem-solving methods and serve as a benchmark to compare performance of algorithms\",\n",
        "\"real-world problem\": \"distinct formulation of a problem to find a usable solution\",\n",
        "\"egocentric actions\": \"actions relative to the agent's POV (forward, backward, turnright, turnleft)\",\n",
        "\"route-finding problem\": \"locations and transitions along edges between the locations\",\n",
        "\"touring problems\": \"set of locations that must be visited\",\n",
        "\"traveling sales plan problem (TSP)\": \"touring problem where every city is visited with the lowest total cost\",\n",
        "\"search algorithm\": \"takes a search problem as input and returns a solution or failure as the output\",\n",
        "\"frontier\": \"unexpanded nodes in a search tree\",\n",
        "\"reached\": \"any state in a search tree that has been generated (doesn't have to be expanded)\",\n",
        "\"priority queue\": \"pops node with min cost according to eval function\",\n",
        "\"FIFO queue\": \"first-in-first-out; pops node added to the queue first (used in BFS)\",\n",
        "\"LIFO queue\": \"last-in-first-out (stack); pops most recently added node\",\n",
        "\"cycle\": \"loopy path, special case of a redundant path\",\n",
        "\"graph search\": \"checks for redundant paths (best first search)\",\n",
        "\"tree search\": \"does not check for redundant paths\",\n",
        "\"completeness\": \"guranteed to find a solution if there is one or report failure if there is not one\",\n",
        "\"cost optimality\": \"find solution with lowest path costs\",\n",
        "\"time complexity\": \"amount of time it takes to find a solution\",\n",
        "\"space complexity\": \"amount of memory it takes to perform the search\",\n",
        "\"depth\": \"d; number of actions in an optimal solution\",\n",
        "\"branching factor\": \"number of successors/childern of a node that need to be considered\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 296,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a1997bd0-db09-48fb-9924-1a03bdbd57e6"
      },
      "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": 297,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n First we will work with episodic, single agent, fully observable, deterministic, static, discrete, and known environment. If we assume that the agent will  always have access to info about the world, they can follow a four phase problem solving process:\n * Goal Formulation: agent adopts a goal and uses it to limit its objectives and organize its behavior/actions\n * Problem Formulation: abstract model of the wolrd using descriptions of states and actions to reach a goal.\n * Search: simulating sequences of actions to reach a goal. A correct sequence that reaches a goal is a solution. The agent might have to try multiple sequences  before it finds a solution or discovers no solution is possible.\n * Execution: execution of the actions in the solution sequence.\n\n In a fully observable, deterministic, known environment, the solution is a fixed sequence of actions. If the model is correct, the agent can execute the  actions without any percepts since the solution is guranteed to reach a goal. If model is incorrect or the environment is nondeterministic, then a closed-loop  approach is needed. In partially observable or nondeterministic, a solution might need branches depending on the percepts received to decide actions.\n\n Search Problem:\n * set of possible states (state space)\n * initial state\n * set of goal states\n * set of actions applicable in a state; ACTIONS(s)\n * transition model\n * action cost function - problem solving agent should use an action cost function that refects its performance measures\n\nAction costs are additive along a path. State spaces can be represented as a graph; vertices are states, directed edges are actions between the states. Good problem formulation has just the right amount of detail/level of abstraction. An abstraction is *valid* if we can apply the resulting solution to the real world. An abstraction is *useful* if it is possible to carry out each of the actions in the solution without additional solving. A good abstraction removes as much detail as possible while retailing validity and the ability to carry out the actions.  \n \n\n## AIMA Chapter 3.2 Example Problems\n\nVacuum World Example\n* States = instances of the grid world stating which objects (dirt) are in which cells. $n cells = n*2^n states$\n* Initial state = chosen state to start\n* Actions = suck, move left, move right. (could add move up, move down in 2d world)  \n* Transition Model\n * Suck = Removes dirt\n * Turn (left or right) = Change direction 180deg\n * Forward = move one cell (if possible)\n * Backward = move in opposite direction\n* Goal states = every cell in grid world is clean\n* Action cost = each action costs 1\n\nRouting-finding problem examples include driving directions, routing video streams in computer networks, military operations planning.\nAirline Travel Example\n* States = location and current time, plus any historical information\n* Initial state = home airport\n* Actions = take flight in a seat class at a time after current time with enough time for any transfers\n* Transition Model\n * taking a flight = flight destination and arrival time\n* Goal states = destination city\n* Action cost = price of flight, waiting time, flight time, custom & immigration procedures, seal quality, time of day, type of airplane, preferred airline, etc.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nMany search problems can be formulated as search trees with the root as the initial state. We will expand nodes in the search tree until we find a goal state. Expand nodes using the available actions for that state to generate child/successor nodes for the resulting state.\n\nBest-First Search\n* Add initial node to the frontier\n* while frontier is not empty\n* Pop a node\n* If the node is a goal state, return node\n* For each child in EXPAND\n * if the state has not been reached before or the cost is less than the reached cost (looking for minimum cost)\n  * note child as reached\n  * add child to frontier\n* if no solution is found, return failure\n\nEXPAND\n* For each action for the given node\n * Run the evaluation function (path-cost + action-cost)\n * Evaluate the resulting state\n * Yield new node as the state, parent, action, and cost\n\nEach state is represented by a node. The node holds information about the\n* state = environment state\n* parent = node of the tree that generated this node\n* action = action that generated this node\n* path cost = total cost of the path from initial state to this node\n\nQueues are used to store the frontier since we need operations for is-empty, pop, top (returns node but does not remove it), and add.\n\nAlgorithms are not efficient if they repeat paths they have already visited.\n* Remember all previously visited states (like best first search). Only possible if table of reached states will fit in memory.\n* Problem formulations does not result in loops. Path from A-B but not B-A.\n* Check for cycles, but not redundant paths.\n\nTree search uses less memory since it doesn't have to remember visited nodes. If there are loops, it will run slower than graph search. In finite state spaces, a complete algorithm can explore every state that is reachable from an initial state as long as it keeps track of paths and cuts off cycles. In infinite state spaces, the search algorithm must systematically explore the state space to ensure it reaches any state connected to the initial state. If there is no solution for an inifinite state space, there needs to be a way to terminate so it doesn't search forever. Size of state space can be represented as |V|+|E| or for implicit state spaces, depth (d), max number of actions in a path (m), branching factor (b).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nUninformed search algorithms do not know how close they are to the goal. If all actions have the same cost, Breadth-First Search (BFS) can be used. BFS is a systematic search strategy that is complete even in infinite state spaces. BFS always find an optimal solution if all actions have the same cost. BFS time and space complexity is $O(b^d)$. Since it is exponential, large state spaces would take too long, but even worst, would take too much space.\n\nDijkstra's Algorithm or Uniform-Cost Search (UCS) is BFS where the actions have different costs. The evaluation function is the cost of the path from the root node to the current node. UCS is best-first search with the path costs.\n* expand the node with the least total path cost\n* as nodes are expanded, check to see if the node (not the child) is the goal\n* if node has a lower path cost, replace path in reached and add to frontier. There is no reason to visit nodes with higher path costs. \n\nDepth-First Search (DFS) is implemented as a tree search (does not keep track of reached) where it expands to the deepest node before going to the next branch. If it reaches the end of the branch, it backs up to the previous deepest node that has unexpanded children. DFS will return the first solution it finds (not cost-optimal). DFS can get stuck going down an infinite path or in cycles. It is not systematic, therefore not complete. DFS uses much less memory than BFS  since it does not keep track of reached. In a variant of DFS, backtracking uses less memory because it only generates one child at a time by modifying the current state description directly. Because we modify it directly, we have to be able to undo the actions when we backtrack. \n\nDepth-limited Search can keep DFS from going down an infinite path by supplying a depth limit (l) where children at l are treated like they are leaves. If we pick l poorly, it will fail to reach a solution. l can be chosen based on the problem or knowing the diameter of the state space. Often we will not know that until we have solved the problem. \n\nIterative Deepening solves the problems of depth-limited by trying all values of l until it reaches a solution or hits a cutoff depth. Iterative deepening is the preferred uninformed search method when the state space is larger than what can fit in memory and the depth is unknown.\n\nBidirectional search searches both from the initial state and backward from the goal state(s), in hopes that the searches will meet. It needs to keep track of two frontiers and reached states. We would also need to be able to reason backwards to determine who are the successors of who. The solution is found when the searches meet in the middle. \n\n\n## Module 3 Lecture Notes\n\n**BFS**\n* If node is a goal state, return node\n* add node to FIFO frontier\n* while frontier is not empty\n * pop the oldest node\n * for each child of the node\n  * if child is a goal state, return (we are able to do an early goal test right after child is generated instead of after popped from frontier)\n  * if child's state has not been reached\n   * add state to reached\n   * add child to frontier\n* if goal is not found, return failure\n\n\n**Comparison Table**\n\n| Syntax        \t|    BFS   \t|         UCS        \t|    DFS   \t| Depth-Limited \t| Iterative Deepening \t|\n|---------------\t|:--------:\t|:------------------:\t|:--------:\t|:-------------:\t|:-------------------:\t|     \n| Complete?     \t|   Yes 1  \t|       Yes 1,2      \t|    No    \t|       No      \t|        Yes 1        \t|\n| Optimal cost? \t|   Yes 3  \t|         Yes        \t|    No    \t|       No      \t|        Yes 3        \t|\n| Time          \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t| $O(b^m)$ \t|    $O(b^l)$   \t|       $O(b^d)$      \t|  \n| Space         \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t|  $O(bm)$ \t|    $O(bl)$    \t|       $O(bd)$       \t|  \n\n| Syntax        \t| Bidirectional \t| Minimax           | Alpha-beta        |  Expectiminimax   |  AC-3             |\n|---------------\t|:-------------:\t|:-------------:    |:-------------:    |:-------------:    |:-------------:    |     \n| Complete?     \t|    Yes 1,4    \t|        \t          |                   |                   |                   |\n| Optimal cost? \t|    Yes 3,4    \t|       \t          |                   |                   |                   |\n| Time          \t|  $O(b^{d/2})$ \t|  $O(b^{m})$   \t  |  $O(b^{m/2})$     | $O(b^{m}n^m)$     |  $O(cd^{3})$      |  \n| Space         \t|  $O(b^{d/2})$ \t|  $O(bm)$ \t        |                   |                   |                   | \n1. if b is finite and state space has solution or is finite\n2. all action costs are > 0\n3. all action costs are identical\n4. both directions are BFS or UCS\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search using atomic representations\n* **Planning agents** - an agent that can formulate a plan via search using factored or structured representations of states\n* **Open-loop** - system where the solution can be executed without any percepts\n* **Closed-loop** - system where the agent will need to monitor percepts while executing a solution\n* **Transition model** - describes what each action does and the resulting state; RESULT(s,a) = s'\n* **Action cost function** - supplies the numeric cost of an action from one state to another; ACTION-COST(s,a,s')\n* **Path** - sequences of actions\n* **Solution** - path from state to a goal state\n* **Optimal solution** - lowest path cost among all solutions\n* **Model** - abstract mathematical description of a problem\n* **Abstraction** - removing detail from a representation\n* **Standardized problem** - used to exercise problem-solving methods and serve as a benchmark to compare performance of algorithms\n* **Real-world problem** - distinct formulation of a problem to find a usable solution\n* **Egocentric actions** - actions relative to the agent's POV (forward, backward, turnright, turnleft)\n* **Route-finding problem** - locations and transitions along edges between the locations\n* **Touring problems** - set of locations that must be visited\n* **Traveling sales plan problem (tsp)** - touring problem where every city is visited with the lowest total cost\n* **Search algorithm** - takes a search problem as input and returns a solution or failure as the output\n* **Frontier** - unexpanded nodes in a search tree\n* **Reached** - any state in a search tree that has been generated (doesn't have to be expanded)\n* **Priority queue** - pops node with min cost according to eval function\n* **Fifo queue** - first-in-first-out; pops node added to the queue first (used in BFS)\n* **Lifo queue** - last-in-first-out (stack); pops most recently added node\n* **Cycle** - loopy path, special case of a redundant path\n* **Graph search** - checks for redundant paths (best first search)\n* **Tree search** - does not check for redundant paths\n* **Completeness** - guranteed to find a solution if there is one or report failure if there is not one\n* **Cost optimality** - find solution with lowest path costs\n* **Time complexity** - amount of time it takes to find a solution\n* **Space complexity** - amount of memory it takes to perform the search\n* **Depth** - d; number of actions in an optimal solution\n* **Branching factor** - number of successors/childern of a node that need to be considered\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Informed algorithms can estimates how far the initial state is from the goal. Greedy Best-first search expands first the node with the lowest f(n) = h(n). \\\n",
        "It is possible for greedy best-first search to not find the most optimal solution since it will always take the lowest cost. It is complete in finite spaces  \\\n",
        "with a space/time complexity of $O(|V|)$ with the possibility of reaching $O(bm)$ with a good h(n).\n",
        "\n",
        "A* Search is a best first search that uses the evaluation function $f(n) = h(n) + g(n)$ where g(n) is the current total path cost from initial state to n \\\n",
        "and h(n) is the estimated cost of the shortest path from n to a goal state. A* is complete, but is guaranteed to be cost optimal only if it h(n) is admissible. \\\n",
        "Every consistent heuristic is admissible but not every admissible heuristic is consistent.\n",
        "\n",
        "Path costs are strictly monotonic if they always increase as you go along a path and just monotonic if they either increase or stay the same. A* is optimally \\\n",
        "efficient if it has a consistent heuristic. A* isn't the answer to everything, in some problems, the number of nodes expanded can be exponential in the length \\\n",
        "of the solution. A* expands a lot of nodes, taking more time and space. If we are OK with a suboptimal solution, we can use an inadmissible heuristic to be more \\\n",
        "accurate and expand less nodes to find a suboptimal solution. We can use a Weighted A* Search with eval function $f(n)=g(n) + W*h(n) for W>1$. A* search uses \\\n",
        "a lot of memory between the frontier and the reached states. \n",
        "\n",
        "Other informed search algorithms that use a heuristic function are:\n",
        "* Bidirectional A* Search = sometimes more efficient than A*\n",
        "* IDA* (Iterative deepening A* search) = iterative deepening version of A*, address the space complexity issue. in the original the cutoff was depth, for IDA*, \\\n",
        "it is the f-cost (g+h).  \n",
        "* RBFS (recursive best-first search) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* \\\n",
        "would run out of memory. resembles a recursive DFS, but uses an f_limit to keep track of the f_value of the best alternative path available from any ancestor of \\\n",
        "the current node. \n",
        "* SMA* (simplified memory-bound A*) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* \\\n",
        "would run out of memory. drops the worse leaf node (highest f-value), the back ups the value of the forgotten node to the parent. SMA* expands the best leaf and \\\n",
        "deletes the oldest worst leaf. complete if there is a reachable solution.\n",
        "* Beam Search = puts a limit on the size of the frontier. results in the algorithm being incomplete and suboptimal, but can find reasonably good solution and runs \\\n",
        "faster than complete searches. Only exploes a focused portion with the best candidates\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Consider how heuristics can be invented. For the sliding tile n-puzzle, we could use either admissible h(n):\n",
        "* number of misplaced tiles (not including the blank)\n",
        "* sum of the distances of the tiles from their goal positions using Manhattan distance\n",
        "\n",
        "The quality of a heuristic can be characterize by its effective branching factor (b*), with a well designed heuristic having a b* value close to 1. \\\n",
        "If $h2(n) \\ge h1(n)$ h2 dominates h1, which means that h2 is more efficient than h1 and will expand less nodes if h2 is used. It is generally better to \\\n",
        "use a heuristic with higher values as long as it is consistent and the computation time is not too long. We can create heuristics using a version of the \\\n",
        "problem with fewer restrictions (relaxed problem). A relaxed problem would have a state-space larger than the original since removal of restrictions creates \\\n",
        "added edges in the graph (supergraph). An optimal solution in the original problem would be a solution for the supergraph, but not the other way around. The \\\n",
        "cost of an optimal solution to a relaxed problem is an admissible heauristic for the original problem. Another method to create heuristics is using the \\\n",
        "solution for a subproblem. For the n-tile puzzle, this is more accurate than the Manhattan distance. Solutions to these subproblems can be stored in a \\\n",
        "pattern database. Other methods for creating heuristics include defining landmarks or by learning from experience.  \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "**Heuristics**\n",
        "* A*: $g(n) + h(n)$ (W=1)\n",
        "* UCS: $g(n)$ (W=0)\n",
        "* Greedy Best First: $h(n)$ (W=inf)\n",
        "* Weighted A*: $g(n)+W*h(n)$ (1<W<inf)\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"h(n); estimated cost of the cheapest path from a state to the goal\",\n",
        "\"straight-line distance heuristic\": \"heuristic using distance 'as the crow flys' between two locations, can be computed using distance formula\",   \n",
        "\"admissibility\": \"an admissible heuristic is one that never over estimates the cost to reach a goal (optimistic)\",\n",
        "\"consistency\": \"h(n) is consistent if $h(n) \\ge (the cost of the action from n to n') + h(n')$; triangle inequality\",\n",
        "\"triangle inequality\": \"side of a triangle cannot be longer than the sum of the other two sides\", \n",
        "\"monotonic\": \"path costs increase as you go along a path, since action costs are always positive\",\n",
        "\"prunes\": \"eliminates nodes/branches from consideration that are not necessary for finding a solution\",\n",
        "\"bounded suboptimal search\": \"looks for a solution guaranteed to be within a constant factor W of the optimal cost, like weighted A*\",\n",
        "\"bounded-cost search\": \"looks for a solution whose cost is less than some constant C\",\n",
        "\"unbounded-cost search\": \"accepts a solution of any cost, as long as it can be found quickly\",\n",
        "\"Manhattan distance\": \"sum of horizontal and vertical distances, no diagonals ('city block distance')\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 298,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0707f6f6-c6b3-418c-ed2f-43434ff8d599"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 299,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed algorithms can estimates how far the initial state is from the goal. Greedy Best-first search expands first the node with the lowest f(n) = h(n). It is possible for greedy best-first search to not find the most optimal solution since it will always take the lowest cost. It is complete in finite spaces  with a space/time complexity of $O(|V|)$ with the possibility of reaching $O(bm)$ with a good h(n).\n\nA* Search is a best first search that uses the evaluation function $f(n) = h(n) + g(n)$ where g(n) is the current total path cost from initial state to n and h(n) is the estimated cost of the shortest path from n to a goal state. A* is complete, but is guaranteed to be cost optimal only if it h(n) is admissible. Every consistent heuristic is admissible but not every admissible heuristic is consistent.\n\nPath costs are strictly monotonic if they always increase as you go along a path and just monotonic if they either increase or stay the same. A* is optimally efficient if it has a consistent heuristic. A* isn't the answer to everything, in some problems, the number of nodes expanded can be exponential in the length of the solution. A* expands a lot of nodes, taking more time and space. If we are OK with a suboptimal solution, we can use an inadmissible heuristic to be more accurate and expand less nodes to find a suboptimal solution. We can use a Weighted A* Search with eval function $f(n)=g(n) + W*h(n) for W>1$. A* search uses a lot of memory between the frontier and the reached states. \n\nOther informed search algorithms that use a heuristic function are:\n* Bidirectional A* Search = sometimes more efficient than A*\n* IDA* (Iterative deepening A* search) = iterative deepening version of A*, address the space complexity issue. in the original the cutoff was depth, for IDA*, it is the f-cost (g+h).  \n* RBFS (recursive best-first search) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* would run out of memory. resembles a recursive DFS, but uses an f_limit to keep track of the f_value of the best alternative path available from any ancestor of the current node. \n* SMA* (simplified memory-bound A*) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* would run out of memory. drops the worse leaf node (highest f-value), the back ups the value of the forgotten node to the parent. SMA* expands the best leaf and deletes the oldest worst leaf. complete if there is a reachable solution.\n* Beam Search = puts a limit on the size of the frontier. results in the algorithm being incomplete and suboptimal, but can find reasonably good solution and runs faster than complete searches. Only exploes a focused portion with the best candidates\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nConsider how heuristics can be invented. For the sliding tile n-puzzle, we could use either admissible h(n):\n* number of misplaced tiles (not including the blank)\n* sum of the distances of the tiles from their goal positions using Manhattan distance\n\nThe quality of a heuristic can be characterize by its effective branching factor (b*), with a well designed heuristic having a b* value close to 1. If $h2(n) \\ge h1(n)$ h2 dominates h1, which means that h2 is more efficient than h1 and will expand less nodes if h2 is used. It is generally better to use a heuristic with higher values as long as it is consistent and the computation time is not too long. We can create heuristics using a version of the problem with fewer restrictions (relaxed problem). A relaxed problem would have a state-space larger than the original since removal of restrictions creates added edges in the graph (supergraph). An optimal solution in the original problem would be a solution for the supergraph, but not the other way around. The cost of an optimal solution to a relaxed problem is an admissible heauristic for the original problem. Another method to create heuristics is using the solution for a subproblem. For the n-tile puzzle, this is more accurate than the Manhattan distance. Solutions to these subproblems can be stored in a pattern database. Other methods for creating heuristics include defining landmarks or by learning from experience.  \n\n\n## Module 4 Lecture Notes\n\n**Heuristics**\n* A*: $g(n) + h(n)$ (W=1)\n* UCS: $g(n)$ (W=0)\n* Greedy Best First: $h(n)$ (W=inf)\n* Weighted A*: $g(n)+W*h(n)$ (1<W<inf)\n \n\n## Module 4 Definitions\n* **Heuristic function** - h(n); estimated cost of the cheapest path from a state to the goal\n* **Straight-line distance heuristic** - heuristic using distance 'as the crow flys' between two locations, can be computed using distance formula\n* **Admissibility** - an admissible heuristic is one that never over estimates the cost to reach a goal (optimistic)\n* **Consistency** - h(n) is consistent if $h(n) \\ge (the cost of the action from n to n') + h(n')$; triangle inequality\n* **Triangle inequality** - side of a triangle cannot be longer than the sum of the other two sides\n* **Monotonic** - path costs increase as you go along a path, since action costs are always positive\n* **Prunes** - eliminates nodes/branches from consideration that are not necessary for finding a solution\n* **Bounded suboptimal search** - looks for a solution guaranteed to be within a constant factor W of the optimal cost, like weighted A*\n* **Bounded-cost search** - looks for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accepts a solution of any cost, as long as it can be found quickly\n* **Manhattan distance** - sum of horizontal and vertical distances, no diagonals ('city block distance')\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "There are three ways to consider multi-agent environments:\n",
        "* As an aggregate for very large numbers of agents (an economy)\n",
        "* As part of the environment, results in a nondeterministic environment.\n",
        "* Explicitly model the agent.\n",
        "\n",
        "The most commonly studied games are two player, turn taking, deterministic, perfect information (fully observable), zero sum games. Zero sum refers to \\\n",
        "that there is no cooperation, what is good for one player is bad for another. We call the players MAX and MIN where MAX always moves first. A game is \\\n",
        "defined as:\n",
        "* S0 = initial state, how the game is set up\n",
        "* TO-MOVE(s) = player whose turn to move in state s\n",
        "* ACTIONS(s) = set of legal moves for state s\n",
        "* RESULT(s,a) = the transition model, which defines the resulting state from taking action a in state s\n",
        "* IS-TERMINAL(s) = a terminal test that determines whether the game is over (true) or not (false). \n",
        "* UTLITY(s,p) = utility function that computes the final numeric value to the player when the game ends in terminal state. \n",
        " * example) Win = 1, Loss = 0, Draw = 0.5\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax search is for games with multiple outcome scores. We find the minimax value of each state in the tree (MINIMAX(s)). The minimax value for a terminal \\\n",
        "state is just the utility, for MAX it is the max of the possible children values, for MIN it is the min of the possible children values. The minimax algorithm \\\n",
        "is a recursive algorithm that goes all the way down the tree (DFS) and then backups the minimax values as the recursion rewinds. Exponential complexity for \\\n",
        "minimax search makes it impractical for complex games (like chess).\n",
        "\n",
        "FOr large state spaces, since the total number of game states is exponential in the depth of the tree, we need to use pruning to ignore parts of the tree that \\\n",
        "make no difference to the outcome. We can use alpha-beta pruning to prune leaves or subtrees of the game tree. \n",
        "* $\\\\alpha$ = the highest value choice found so far at any point along the path for MAX (MAX can get 'at least' this many points)\n",
        "* $\\\\beta$ = the lowest value choice found so far at any point along the path for MIN (MIN can get 'at most' this many points; MIN wants less points)\n",
        "\n",
        "Alpha-beta search updates the values of $\\\\alpha$ and $\\\\beta$ along the way and prunes branches or nodes that would result in values worst than the current \\\n",
        "$\\\\alpha$ or $\\\\beta$ values. Alpha-beta pruning is highly dependent on the order that the states are visited.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "To reduce the amount of computational power needed, we can cut off the search early and apply a heuristic evaluation function to the states, treating non-terminal \\\n",
        "nodes like they were terminal. The terminal test will be replaced by a cutoff test which returns true for terminal states but otherwises decides when to cutoff the \\\n",
        "search. The evaluation function EVAL(s,p) retuns an estimate for the expected utility of state s to player p. The eval function will be the same as the utility \\\n",
        "function for terminal states. For non-terminal states, the evaluation function will be somewhere between a loss and a win. \n",
        "\n",
        "A good evaluation function needs to not take too long. It also needs to be strongly correlated with the chances of winning. But if it reaches the cutoff before \\\n",
        "a terminal state, then it will be uncertain about the final outcome. For these games, there is no chance involved, as long as everyone plays optimally, the \\\n",
        "result is predetermined. Eval functions are determined by using features of the state (e.g. how many pieces are left). The pieces could be weighed by importance \\\n",
        "and given corresponding (material) values. The eval function might not know which states will result in which player winning, but it can return a single value that estimates \\\n",
        "the proportion of states with each outcome as the expected value. \n",
        "* weighted linear function = $\\sum_{i=1}^{n} w_i*f_i(s)$\n",
        " * $f_i$ = feature of the position (# of bishops)\n",
        " * $w_i$ = weight of the feature\n",
        "\n",
        "Adding up the features requires the features to be independent of the values of the other features. Other methods might use nonlinear combinations, such as \\\n",
        "giving higher scores than 2x for a pair of bishops.\n",
        "\n",
        "Along with the heuristic evaluation function, we can apply a cutoff function that is set at a fixed depth, so that it will return true for all greater depths \\\n",
        "and terminal states. You could also apply iterative deepening to increase the limit. If time runs out, then it will select a move from the deepest completed search. \n",
        "Forward pruning can look ahead to find poor or good moves. If we combine all these techniques together (heuristic evaluation function, cutoff, quiescence search, \\\n",
        "minimax) we can create a creditable game playing program.\n",
        "\n",
        "Programs can also use lookup tables for known information, such as opening and ending positions for chess. This allows the program to take advantage of known \\\n",
        "information gathered by humans. \n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic game trees include chance nodes that denote all possible values and their probablity. Since it is not certain that the action will lead to that state, \\\n",
        "we cannot calculate definite minimax values, but instead will use expected values of the positions. Like with minimax, we can made an approximation by cutting off \\\n",
        "search at some point and apply an evaluation function to the leaves.The evaluation function needs to be a linear relationship to the probablity. Because we need \\\n",
        "all the possible probabilistic values, we have to add a lot more nodes to the tree for the possible sequences. The time complexity is $O(b^{m}n^m)$ where m is the \\\n",
        "max depth of the tree and n is the number of distinct probabilistic values. Therefore, we are limited to how far we can look ahead. Before, we had certain outcomes \\\n",
        "now none of the outcomes are certain so we need to consider them all. But, we can consider pruning if we place bounds on the leaf node utility values. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "An agent needs to make a decision and there might be uncertainty about the current state.\n",
        "$$P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$$\n",
        "* P(s) = probability for state s\n",
        "* P(s'|s,a) = transition model probablity that action a in state s reaches s'\n",
        "* P(RESULT(a)=s') = probablity of reaching s' through action a in the current state\n",
        "\n",
        "Expected utility: $EU(a) = sum_{s'} P(RESULT(a)=s')U(s')$\n",
        "* EU(a) = expected utility of an action \n",
        "* U(s) = value to express the desirablity of a state\n",
        "\n",
        "Maximum Expected Utility: An agent should choose the action that maximimzes the expected utility. MEU principle formulizes that an agent should do the right \\\n",
        "thing, but it does not operationalize it. If an agent acts so that it maximizes a utility function that reflects the performance measure, the agent will achieve \\\n",
        "the highest possible performance score. The performance measure gives a score of a historical sequence of states while the utility function applies to the next \\\n",
        "state, therefore can guide actions step by step. \n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "* A > B = prefer A over B\n",
        "* A ~ B = indifferent between A and B\n",
        "* $A \\\\ge B$ = prefers A over B or is indifferent\n",
        "\n",
        "lottery L = [p1,S1; p2,S2; ... pn,Sn]\n",
        "* each S can be an atomic state or another lottery\n",
        "\n",
        "Axioms of Utility Theory (preferences)\n",
        "* Orderability = either prefer one or rate them as equality preferable. agent cannot avoid deciding. \n",
        " * exactly one of $(A>B), (B>A), or (A~B)$ holds\n",
        "* Transitivity = given 3 lotteries, if an agent prefers A to B and B to C, then agent must prefer A to C\n",
        " * $(A>B) \\\\lor (B>C) \\\\implies (A>C)$\n",
        "* Continuity = if B is between A and C in preference, then there is some probability p where the agent will be indifferent between B and the lottery \\\n",
        "that yields A with probability p and C with probability 1-p\n",
        " * $A>B>C \\\\implies \\\\exists p [p,A; 1-p,C] ~ B$\n",
        "* Substitutability = if agent is indifferent between A and B, then agent is indifferent between two more complex lotteries that are the same except that B is \\\n",
        "substituted for A in one of them\n",
        " * $A~B \\\\implies [p,A; 1-p, C] \\\\sim [p,B; 1-p,C]  $\n",
        "* Monotonicity = if two lotteries have the same possible outcomes (A and B) and an agent prefers A to B, then the agent must rprefer to lotter that has a higher \\\n",
        "probability for A\n",
        " * $A>B \\\\implies (p>q \\\\iff [p,A; 1-p,B] > [q,A; 1-q,B]) $\n",
        "* Decomposability = Using the laws of probability, compound lotteries can be reduced to simplier ones. Compresses two consequtive lotteries into a single \\\n",
        "equivalent lottery\n",
        " * $[p,A; 1-p,[q,B; 1-q,C]] \\\\sim [p,A; (1-p)q,B; (1-p)(1-q),C]$\n",
        "\n",
        "Consequences\n",
        "* Existence of Utility Function = If the preferences obey the axioms, then there exists a function U such that U(A)<U(B) iff A is preferred to B, and \\\n",
        "U(A)=U(B) iff the agent is different between A and B. The utility of a compound lottery is completely determined once the probabilities and utilities \\\n",
        "of the possible outcome states are specified. \n",
        " * $U(A)>U(B) \\\\iff A>B and U(A)=U(B) \\\\iff A~B $\n",
        "* Expected Utility of a Lottery = utility of a lottery is the sum of the probablities of each outcome times the utility of that outcome\n",
        " * $U([p1,S1; ...; pn, Sn]) = \\\\sum_i piU(Si) $ \n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "It is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any \\\n",
        "two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to \\\n",
        "choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all \\\n",
        "lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for \\\n",
        "deciding the value of a childs life vs removing asbestos from the school. \n",
        "\n",
        "Utility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is \\\n",
        "heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A \\\n",
        "millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. \\\n",
        "The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\\n",
        "\\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Minimax Procedure:\n",
        "* Until game is over:\n",
        " * Start with the current position as a MAX node.\n",
        " * Expand the game tree a fixed number of ply.\n",
        " * Apply the evaluation function to the leaf positions.\n",
        " * Calculate back-up values bottom-up.\n",
        " * Pick the move assigned to MAX at the root\n",
        " * Wait for MIN to respond\n",
        "\n",
        "Expectimax search: compute the average score under optimal play\n",
        "* Max nodes just like in minimax search\n",
        "* Chance nodes are treated similiar to min nodes but the outcome is uncertain\n",
        "* Calculate the expected utilities for the chance nodes\n",
        " * i.e take weighted average (expectation) of the children nodes\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"adversarial search\" : \"competitive environments where two or more agents have conflicting goals\",  \n",
        "\"move\": \"synonym for action\",\n",
        "\"position\": \"synonym for state\",  \n",
        "\"terminal states\": \"end game states\",\n",
        "\"state space graph\": \"defined by the initial state, ACTIONS, RESULT functions to create a graph of states (vertices) and moves (edges)\",\n",
        "\"game tree\": \"complete search tree that has every possible sequence of moves to a terminal state\",\n",
        "\"ply\": \"move by one player, one level in a game tree\",\n",
        "\"minimax value\": \"utility of being in that state, assuming both players play optimally\",\n",
        "\"expected value\": \"sum of value*probablility\",\n",
        "\"quiscent\": \"where there is no pending move that would widly swing the evaluation\",\n",
        "\"quiescence search\": \"limits search to only certain types of moves (e.g. capture moves) that will resolve uncertainies in the state\",\n",
        "\"horizon effect\": \"unavoidable opponent move that will cause serious damage, but can be temporarily delayed\",\n",
        "\"policy\": \"mapping of every possible state to the best move in that state\",\n",
        "\"stochastic games\": \"games with random elements, chance, probability\",\n",
        "\"expectiminimax value\": \"generalization of minimax value for deterministic games\",\n",
        "\"maximum expected utility (MEU)\" : \"produces values for the state(s) where a rational agent chooses the value to max EU\",\n",
        "\"lottery\": \"set of outcomes for each action\",\n",
        "\"value function or ordinal utility function\": \"numeric values do not matter in a deterministic environment, the agent only needs a perference ranking for the states\",\n",
        "\"preference elicitation\": \"process of figuring out the human's utility function. presents choices to humans and uses observed preferences to create utility function\",\n",
        "\"normalized utilities\": \"uses scale of 0 to 1\",\n",
        "\"standard lottery\": \"$[p, u_{upper}; (1-p), u_{lower}] $\",\n",
        "\"micromort\": \"one million chance of death\",\n",
        "\"monotonic preference\": \"given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\",\n",
        "\"expected monetary value\": \"(EMV), sum of probabilities times value\",\n",
        "\"risk-adverse\": \"prefer a sure thing over a gamble\",\n",
        "\"certainty equivalent\": \"amount someone would accept in lieu of the gamble\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 300,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c95c6d14-c74b-42f7-b39e-2ae1fcabb4ff"
      },
      "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": 301,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nThere are three ways to consider multi-agent environments:\n* As an aggregate for very large numbers of agents (an economy)\n* As part of the environment, results in a nondeterministic environment.\n* Explicitly model the agent.\n\nThe most commonly studied games are two player, turn taking, deterministic, perfect information (fully observable), zero sum games. Zero sum refers to that there is no cooperation, what is good for one player is bad for another. We call the players MAX and MIN where MAX always moves first. A game is defined as:\n* S0 = initial state, how the game is set up\n* TO-MOVE(s) = player whose turn to move in state s\n* ACTIONS(s) = set of legal moves for state s\n* RESULT(s,a) = the transition model, which defines the resulting state from taking action a in state s\n* IS-TERMINAL(s) = a terminal test that determines whether the game is over (true) or not (false). \n* UTLITY(s,p) = utility function that computes the final numeric value to the player when the game ends in terminal state. \n * example) Win = 1, Loss = 0, Draw = 0.5\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax search is for games with multiple outcome scores. We find the minimax value of each state in the tree (MINIMAX(s)). The minimax value for a terminal state is just the utility, for MAX it is the max of the possible children values, for MIN it is the min of the possible children values. The minimax algorithm is a recursive algorithm that goes all the way down the tree (DFS) and then backups the minimax values as the recursion rewinds. Exponential complexity for minimax search makes it impractical for complex games (like chess).\n\nFOr large state spaces, since the total number of game states is exponential in the depth of the tree, we need to use pruning to ignore parts of the tree that make no difference to the outcome. We can use alpha-beta pruning to prune leaves or subtrees of the game tree. \n* $\\alpha$ = the highest value choice found so far at any point along the path for MAX (MAX can get 'at least' this many points)\n* $\\beta$ = the lowest value choice found so far at any point along the path for MIN (MIN can get 'at most' this many points; MIN wants less points)\n\nAlpha-beta search updates the values of $\\alpha$ and $\\beta$ along the way and prunes branches or nodes that would result in values worst than the current $\\alpha$ or $\\beta$ values. Alpha-beta pruning is highly dependent on the order that the states are visited.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo reduce the amount of computational power needed, we can cut off the search early and apply a heuristic evaluation function to the states, treating non-terminal nodes like they were terminal. The terminal test will be replaced by a cutoff test which returns true for terminal states but otherwises decides when to cutoff the search. The evaluation function EVAL(s,p) retuns an estimate for the expected utility of state s to player p. The eval function will be the same as the utility function for terminal states. For non-terminal states, the evaluation function will be somewhere between a loss and a win. \n\nA good evaluation function needs to not take too long. It also needs to be strongly correlated with the chances of winning. But if it reaches the cutoff before a terminal state, then it will be uncertain about the final outcome. For these games, there is no chance involved, as long as everyone plays optimally, the result is predetermined. Eval functions are determined by using features of the state (e.g. how many pieces are left). The pieces could be weighed by importance and given corresponding (material) values. The eval function might not know which states will result in which player winning, but it can return a single value that estimates the proportion of states with each outcome as the expected value. \n* weighted linear function = $\\sum_{i=1}^{n} w_i*f_i(s)$\n * $f_i$ = feature of the position (# of bishops)\n * $w_i$ = weight of the feature\n\nAdding up the features requires the features to be independent of the values of the other features. Other methods might use nonlinear combinations, such as giving higher scores than 2x for a pair of bishops.\n\nAlong with the heuristic evaluation function, we can apply a cutoff function that is set at a fixed depth, so that it will return true for all greater depths and terminal states. You could also apply iterative deepening to increase the limit. If time runs out, then it will select a move from the deepest completed search. \nForward pruning can look ahead to find poor or good moves. If we combine all these techniques together (heuristic evaluation function, cutoff, quiescence search, minimax) we can create a creditable game playing program.\n\nPrograms can also use lookup tables for known information, such as opening and ending positions for chess. This allows the program to take advantage of known information gathered by humans. \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic game trees include chance nodes that denote all possible values and their probablity. Since it is not certain that the action will lead to that state, we cannot calculate definite minimax values, but instead will use expected values of the positions. Like with minimax, we can made an approximation by cutting off search at some point and apply an evaluation function to the leaves.The evaluation function needs to be a linear relationship to the probablity. Because we need all the possible probabilistic values, we have to add a lot more nodes to the tree for the possible sequences. The time complexity is $O(b^{m}n^m)$ where m is the max depth of the tree and n is the number of distinct probabilistic values. Therefore, we are limited to how far we can look ahead. Before, we had certain outcomes now none of the outcomes are certain so we need to consider them all. But, we can consider pruning if we place bounds on the leaf node utility values. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nAn agent needs to make a decision and there might be uncertainty about the current state.\n$$P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$$\n* P(s) = probability for state s\n* P(s'|s,a) = transition model probablity that action a in state s reaches s'\n* P(RESULT(a)=s') = probablity of reaching s' through action a in the current state\n\nExpected utility: $EU(a) = sum_{s'} P(RESULT(a)=s')U(s')$\n* EU(a) = expected utility of an action \n* U(s) = value to express the desirablity of a state\n\nMaximum Expected Utility: An agent should choose the action that maximimzes the expected utility. MEU principle formulizes that an agent should do the right thing, but it does not operationalize it. If an agent acts so that it maximizes a utility function that reflects the performance measure, the agent will achieve the highest possible performance score. The performance measure gives a score of a historical sequence of states while the utility function applies to the next state, therefore can guide actions step by step. \n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* A > B = prefer A over B\n* A ~ B = indifferent between A and B\n* $A \\ge B$ = prefers A over B or is indifferent\n\nlottery L = [p1,S1; p2,S2; ... pn,Sn]\n* each S can be an atomic state or another lottery\n\nAxioms of Utility Theory (preferences)\n* Orderability = either prefer one or rate them as equality preferable. agent cannot avoid deciding. \n * exactly one of $(A>B), (B>A), or (A~B)$ holds\n* Transitivity = given 3 lotteries, if an agent prefers A to B and B to C, then agent must prefer A to C\n * $(A>B) \\lor (B>C) \\implies (A>C)$\n* Continuity = if B is between A and C in preference, then there is some probability p where the agent will be indifferent between B and the lottery that yields A with probability p and C with probability 1-p\n * $A>B>C \\implies \\exists p [p,A; 1-p,C] ~ B$\n* Substitutability = if agent is indifferent between A and B, then agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n * $A~B \\implies [p,A; 1-p, C] \\sim [p,B; 1-p,C]  $\n* Monotonicity = if two lotteries have the same possible outcomes (A and B) and an agent prefers A to B, then the agent must rprefer to lotter that has a higher probability for A\n * $A>B \\implies (p>q \\iff [p,A; 1-p,B] > [q,A; 1-q,B]) $\n* Decomposability = Using the laws of probability, compound lotteries can be reduced to simplier ones. Compresses two consequtive lotteries into a single equivalent lottery\n * $[p,A; 1-p,[q,B; 1-q,C]] \\sim [p,A; (1-p)q,B; (1-p)(1-q),C]$\n\nConsequences\n* Existence of Utility Function = If the preferences obey the axioms, then there exists a function U such that U(A)<U(B) iff A is preferred to B, and U(A)=U(B) iff the agent is different between A and B. The utility of a compound lottery is completely determined once the probabilities and utilities of the possible outcome states are specified. \n * $U(A)>U(B) \\iff A>B and U(A)=U(B) \\iff A~B $\n* Expected Utility of a Lottery = utility of a lottery is the sum of the probablities of each outcome times the utility of that outcome\n * $U([p1,S1; ...; pn, Sn]) = \\sum_i piU(Si) $ \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nIt is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for deciding the value of a childs life vs removing asbestos from the school. \n\nUtility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n\n\n## Module 5 Lecture Notes\n\nMinimax Procedure:\n* Until game is over:\n * Start with the current position as a MAX node.\n * Expand the game tree a fixed number of ply.\n * Apply the evaluation function to the leaf positions.\n * Calculate back-up values bottom-up.\n * Pick the move assigned to MAX at the root\n * Wait for MIN to respond\n\nExpectimax search: compute the average score under optimal play\n* Max nodes just like in minimax search\n* Chance nodes are treated similiar to min nodes but the outcome is uncertain\n* Calculate the expected utilities for the chance nodes\n * i.e take weighted average (expectation) of the children nodes\n\n\n\n## Module 5 Definitions\n* **Adversarial search** - competitive environments where two or more agents have conflicting goals\n* **Move** - synonym for action\n* **Position** - synonym for state\n* **Terminal states** - end game states\n* **State space graph** - defined by the initial state, ACTIONS, RESULT functions to create a graph of states (vertices) and moves (edges)\n* **Game tree** - complete search tree that has every possible sequence of moves to a terminal state\n* **Ply** - move by one player, one level in a game tree\n* **Minimax value** - utility of being in that state, assuming both players play optimally\n* **Expected value** - sum of value*probablility\n* **Quiscent** - where there is no pending move that would widly swing the evaluation\n* **Quiescence search** - limits search to only certain types of moves (e.g. capture moves) that will resolve uncertainies in the state\n* **Horizon effect** - unavoidable opponent move that will cause serious damage, but can be temporarily delayed\n* **Policy** - mapping of every possible state to the best move in that state\n* **Stochastic games** - games with random elements, chance, probability\n* **Expectiminimax value** - generalization of minimax value for deterministic games\n* **Maximum expected utility (meu)** - produces values for the state(s) where a rational agent chooses the value to max EU\n* **Lottery** - set of outcomes for each action\n* **Value function or ordinal utility function** - numeric values do not matter in a deterministic environment, the agent only needs a perference ranking for the states\n* **Preference elicitation** - process of figuring out the human's utility function. presents choices to humans and uses observed preferences to create utility function\n* **Normalized utilities** - uses scale of 0 to 1\n* **Standard lottery** - $[p, u_{upper}; (1-p), u_{lower}] $\n* **Micromort** - one million chance of death\n* **Monotonic preference** - given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\n* **Expected monetary value** - (EMV), sum of probabilities times value\n* **Risk-adverse** - prefer a sure thing over a gamble\n* **Certainty equivalent** - amount someone would accept in lieu of the gamble\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "Constraint Statisfaction Problems solve problems that use a factored representation for each state with a solution where all variables has a value that \\\n",
        "satisfies all the constraints on the variable. CSPs use general heuristic rather than domain specific by taking advantage of the structure of the states \\\n",
        "to solve complex problems. It eliminates large portions of the search space by identifying variable/value combinations that violate the constraints. \\\n",
        "* set of variables X = {X1,...Xn}\n",
        "* set of domains D = {D1,...Dn}\n",
        "* set of contraints C that specify allowable combinations of values, pair of <scope, relation>\n",
        " * scope = tuple of variables that participate in the contraint\n",
        " * relation = defines the values that those variables can take on, representated as a tuple of value that satisfy the constraint or as a function that can \\\n",
        " determine whether the tuple is a member of the relation.\n",
        "\n",
        "CSPs can be solved fast and efficiently and can quickly prune large areas of a search space that an atomic state solver cannot. In an atomic search space, \\\n",
        "the only question we can ask is if the atomic state is a goal or not. With CSPs, if a partial assignment violates a constraint, we can discard futher \\\n",
        "refinements of the partial assignment. The simplest CSPs have variables with discrete, finite domains. Discrete domains can be infinite (like for time), \\\n",
        "but these domains would use implicit constraints instead of a domain of values. Linear Programming problems are the best known category of continuous \\\n",
        "domain CSPs where the constriants are linear (in)equalities. These can be solved in time polynomial in the number of variables. \n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "Unlike an atomic state space seach algorithm that can only make progress by expanding nodes to visit successors, CSPs can either generate successors by \\\n",
        "choosing a new variable assignment or it can use inference called constraint propagation. Constraint propagation can be done during the search or as \\\n",
        "preprocessing. The idea is that we want to enforce local consistency of each of the nodes so that inconsistent values are eliminated throughout the graph.\n",
        "Unary constraints can easily be eliminated at the start of the solving process. Often, all n-ary constraints can be transformed to binary constraints, \\\n",
        "so many CSP solvers only deal with binary constraints. \n",
        "\n",
        "A graph is arc consistent if all variables are arc consistent with one another. Variable Xi is arc consistent with another variable Xj if for every value \\\n",
        "in variable Xi's domain Di there is a value in variable Xj's domain Dj that satisfies the binary constraint for the arc (Xi, Xj).\n",
        "Example: For constraint Y = $X^2$, the domain D of X and Y is the set of decimal digits\n",
        "* X domain = {0, 1, 2, 3}\n",
        "* Y domain = {0, 1, 4, 9}\n",
        "\n",
        "Each value of X has a value Y that upholds the constraint. This has reduced the original domain D of X and Y.\n",
        "\n",
        "AC-3 is the most popular algorithm for enforcing arc-consistency. With a domain size of at most d and c binary constraints (cars), each arc can be inserted \\\n",
        "into the queue d times because a variable would have at most d values to delete. Therefore the total worst-case time is $O(cd^{3})$.  \n",
        "\n",
        "Global constraints are common in real life problems and can be handled by special purpose algorithms instead of general ones. \n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Sometimes when we finish the constraint propagation process, there are still variables with multiple possible values. Now we will need to search for the rest \\\n",
        "of the solution. Since CSPs are commutative, we can select a variable to deal with and try the possible values. We could pick the variable in order or \\\n",
        "we could pick one randomly, but neither of these approaches are ideal. Instead we can choose the variable with the fewest legal values \\\n",
        "(minimum-remaining-values (MRV) heuristic). This heuristic will pick the most constrained variable and is most likely to fail soon, allowing that part of \\\n",
        "the tree to be pruned. Another heuristic that could be used is a degree heuristic. It attempts to reduce the branching factor for future choices by selecting \\\n",
        "the variable that is involved in the largest number of constraints on other unassigned variables (aka it is included in the most arcs). Once we pick which variable \\\n",
        "we are going to evaluate, then we need to pick the order that we examine the values. The least-constraining-value heuristic prefers the value that rules out \\\n",
        "the fewest choices for the neighboring variables in the constraint graph. We want to try to leave the most flexibility possible to the rest of the graph. \\\n",
        "We want to fail first because all variables need an assignment eventually, whereas the values we don't want to fail as much because that means we would have to \\\n",
        "backtrack more, we are only looking for one solution of variable assignments. \n",
        "\n",
        "AC-3 can reduce the domain of the variables before we begin the search and inference can be used during the search for further domain reductions. When a value is \\\n",
        "assigned for a variable X, we can use forward checking to check each unassigned variable that is connected to X in an arc constraint and delete any value from \\\n",
        "variable Y's domain that is inconsistent with the value chosen for X. We can combine the MRV heuristic with forward checking for a more efficient algorithm. \\\n",
        "Forward checking reduces inconsistencies, but not all of them because it doesn't look forward far enough, only by one arc. Maintaining Arc Consistency (MAC) \\\n",
        "algorithm checkes for inconsistencies and backtracks if it finds any. Forward checking does not recursively propagate constraints when changes are made \\\n",
        "to the variable's domains. If a branch of the search fails, it just backs up to the previous variable and tries a different value (chronological backtracking). \\\n",
        "A more intelligent approach would be to keep track of the conflict set of assignments for a variable and backtrack to the most recent assignment in the conflict \\\n",
        "set (backjumping). Backjumping would be redundant in a forward checking search, you need to do one or the other.  \n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Min-conflict heuristics work well for many CSPs, such as n-queens and the Hubble scheduling problems.  \n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "To deal with real world problems, they need to be broken down (decomposed) into subproblems. Subproblems can be independent if they do not depend on the rest \\\n",
        "of the graph (not connected with the other variables in the graph). A constraint graph modeled as a tree can be solved in linear time in the number of variables \\\n",
        "using directional arc consistency. To set up a CSPs as a tree, pick one of the variables to be the root and order the variables such that each variable appears \\\n",
        "after its parent in the tree with a topological sort ordering. \n",
        "\n",
        "Cutset conditioning can reduce a constraint graph by picking a variable, assigning a value, removing that value from the other variables domains, and then \\\n",
        "removing the variable from the problem. The variables chosen to cut can allow us to reduce the graph to a tree-structured problem. \n",
        "\n",
        "Tree decomposition can reduce the constraint graph by transforming the original graph into a tree where each node in the three consists of a set of variables.\\\n",
        "* Every variable in the original problem appears at least once, ensuring all variables are represented\n",
        "* If two variables are connected by a constraint in the original problem, they must appear together (with the constraint) in at least one of the tree nodes, \\\n",
        "ensuring all constraints are represented\n",
        "* If a variable appears in two nodes of the tree, it must appear in every node along the path connecting those nodes. This ensures that values in the original \\\n",
        "problem are still in the decomposition. \n",
        "\n",
        "The tree decomposition is like a tree of subgraphs of the original problem. Trees of this nature can be solved in $O(nd^2)$ time. When creating a tree \\\n",
        "decomposition, we want to make the subproblems as small as possible. Time considerations favor tree decomposition, but cutset has the advantage that it \\\n",
        "can be executed in linear memory while tree decomposition needs expotential memory for tree width w.\n",
        "\n",
        "If we have the same number of domain values as variables, this is known as value symmetry. Since this results in d! search space, we want to reduce that \\\n",
        "by breaking the symmetry with a symmetry-breaking constraint. This new constraint could be something like the colors of the regions need to be in \\\n",
        "alphabetical order. That would result in only one possible solution instead of three. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"factored representation\" : \"each state has a set of variables with corresponding value\",   \n",
        "\"consistent\": \"assignment of values to variables where the assignment does not violate any constraint; (legal assignment)\",\n",
        "\"complete assignment\": \"every variable is assigned a value\",\n",
        "\"solution\": \"for a CSP, this is a consistent and complete assignment\",\n",
        "\"partial assignment\": \"leaves some variables unassigned\",\n",
        "\"partial solution\": \"partial assignment that is consistent\",\n",
        "\"constraint graph\": \"nodes are variables of the problem, edges connect any two variables that participant in a constraint\",\n",
        "\"unary constraint\": \"restricts the value of a single variable\",\n",
        "\"binary constraint\": \"relates two values as the restriction\",\n",
        "\"binary CSP\": \"only has unary and binary constraints\",\n",
        "\"global constraint\": \"constraint involving an arbitrary number of variables, does not mean it involves all the variables in a problem\",\n",
        "\"preference constraints\": \"indicates which solution is preferred, compared to absolute constraints\",\n",
        "\"constrained optimization problem\": \"COP, CSPs with preferences can be solved with optimization search methods (path based or local)\",\n",
        "\"constraint propagation\": \"uses constraints to reduce the number of legal values for a variable, and propagating that constraint to another variable, etc.\",\n",
        "\"node-consistent\": \"if all the values in a single variable's domain satisfy the unary constraint\",\n",
        "\"arc-consistent\": \"if every value in the domain satisfies the binary constraint\",\n",
        "\"path-consistent\": \"looks at triple set of variables using implicit constraints\",\n",
        "\"k-consistent\": \"for any set of $k-1$ variables and any consistent assignment to those variables, a consistent value can be assigned \",\n",
        "\"strongly k-consistent\": \"if a CSP is k-consistent, $k-1$ consistent, ..., 1-consistent\",\n",
        "\"resource constraint\": \"atmost constraint\",\n",
        "\"bounds propagation\": \"domains representated as upper and lower bounds\",\n",
        "\"bounds-consistent\": \"for lower and upper bounds, for every variable X there exists value that satisfies the constraint (X,Y) for every Y\",\n",
        "\"commutativity\": \"a problem is commutative if the order of the set of actions does not matter\",\n",
        "\"constraint learning\": \"finding a minimum set of variables from the conflict set that causes the problem\",\n",
        "\"no-good\": \"constraint learning set of variables with their values\",\n",
        "\"min-conflicts heuristic\": \"select a value that results in the min number of conflicts with another variable\",\n",
        "\"tabu search\": \"small list of recently visited states that the algorithm is not allowed to return to\",\n",
        "\"constraint weighting\": \"concentrates the search on imporant constraints by assigning weights\",\n",
        "\"directional arc consistency\": \"if and only if every variable Xi is arc consistent with each Xj for j>i\",\n",
        "}\n"
      ],
      "execution_count": 302,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "99c66c90-8d2e-486f-afd6-3969d5fe98b4"
      },
      "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": 303,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Statisfaction Problems solve problems that use a factored representation for each state with a solution where all variables has a value that satisfies all the constraints on the variable. CSPs use general heuristic rather than domain specific by taking advantage of the structure of the states to solve complex problems. It eliminates large portions of the search space by identifying variable/value combinations that violate the constraints. * set of variables X = {X1,...Xn}\n* set of domains D = {D1,...Dn}\n* set of contraints C that specify allowable combinations of values, pair of <scope, relation>\n * scope = tuple of variables that participate in the contraint\n * relation = defines the values that those variables can take on, representated as a tuple of value that satisfy the constraint or as a function that can  determine whether the tuple is a member of the relation.\n\nCSPs can be solved fast and efficiently and can quickly prune large areas of a search space that an atomic state solver cannot. In an atomic search space, the only question we can ask is if the atomic state is a goal or not. With CSPs, if a partial assignment violates a constraint, we can discard futher refinements of the partial assignment. The simplest CSPs have variables with discrete, finite domains. Discrete domains can be infinite (like for time), but these domains would use implicit constraints instead of a domain of values. Linear Programming problems are the best known category of continuous domain CSPs where the constriants are linear (in)equalities. These can be solved in time polynomial in the number of variables. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nUnlike an atomic state space seach algorithm that can only make progress by expanding nodes to visit successors, CSPs can either generate successors by choosing a new variable assignment or it can use inference called constraint propagation. Constraint propagation can be done during the search or as preprocessing. The idea is that we want to enforce local consistency of each of the nodes so that inconsistent values are eliminated throughout the graph.\nUnary constraints can easily be eliminated at the start of the solving process. Often, all n-ary constraints can be transformed to binary constraints, so many CSP solvers only deal with binary constraints. \n\nA graph is arc consistent if all variables are arc consistent with one another. Variable Xi is arc consistent with another variable Xj if for every value in variable Xi's domain Di there is a value in variable Xj's domain Dj that satisfies the binary constraint for the arc (Xi, Xj).\nExample: For constraint Y = $X^2$, the domain D of X and Y is the set of decimal digits\n* X domain = {0, 1, 2, 3}\n* Y domain = {0, 1, 4, 9}\n\nEach value of X has a value Y that upholds the constraint. This has reduced the original domain D of X and Y.\n\nAC-3 is the most popular algorithm for enforcing arc-consistency. With a domain size of at most d and c binary constraints (cars), each arc can be inserted into the queue d times because a variable would have at most d values to delete. Therefore the total worst-case time is $O(cd^{3})$.  \n\nGlobal constraints are common in real life problems and can be handled by special purpose algorithms instead of general ones. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nSometimes when we finish the constraint propagation process, there are still variables with multiple possible values. Now we will need to search for the rest of the solution. Since CSPs are commutative, we can select a variable to deal with and try the possible values. We could pick the variable in order or we could pick one randomly, but neither of these approaches are ideal. Instead we can choose the variable with the fewest legal values (minimum-remaining-values (MRV) heuristic). This heuristic will pick the most constrained variable and is most likely to fail soon, allowing that part of the tree to be pruned. Another heuristic that could be used is a degree heuristic. It attempts to reduce the branching factor for future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables (aka it is included in the most arcs). Once we pick which variable we are going to evaluate, then we need to pick the order that we examine the values. The least-constraining-value heuristic prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. We want to try to leave the most flexibility possible to the rest of the graph. We want to fail first because all variables need an assignment eventually, whereas the values we don't want to fail as much because that means we would have to backtrack more, we are only looking for one solution of variable assignments. \n\nAC-3 can reduce the domain of the variables before we begin the search and inference can be used during the search for further domain reductions. When a value is assigned for a variable X, we can use forward checking to check each unassigned variable that is connected to X in an arc constraint and delete any value from variable Y's domain that is inconsistent with the value chosen for X. We can combine the MRV heuristic with forward checking for a more efficient algorithm. Forward checking reduces inconsistencies, but not all of them because it doesn't look forward far enough, only by one arc. Maintaining Arc Consistency (MAC) algorithm checkes for inconsistencies and backtracks if it finds any. Forward checking does not recursively propagate constraints when changes are made to the variable's domains. If a branch of the search fails, it just backs up to the previous variable and tries a different value (chronological backtracking). A more intelligent approach would be to keep track of the conflict set of assignments for a variable and backtrack to the most recent assignment in the conflict set (backjumping). Backjumping would be redundant in a forward checking search, you need to do one or the other.  \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nMin-conflict heuristics work well for many CSPs, such as n-queens and the Hubble scheduling problems.  \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nTo deal with real world problems, they need to be broken down (decomposed) into subproblems. Subproblems can be independent if they do not depend on the rest of the graph (not connected with the other variables in the graph). A constraint graph modeled as a tree can be solved in linear time in the number of variables using directional arc consistency. To set up a CSPs as a tree, pick one of the variables to be the root and order the variables such that each variable appears after its parent in the tree with a topological sort ordering. \n\nCutset conditioning can reduce a constraint graph by picking a variable, assigning a value, removing that value from the other variables domains, and then removing the variable from the problem. The variables chosen to cut can allow us to reduce the graph to a tree-structured problem. \n\nTree decomposition can reduce the constraint graph by transforming the original graph into a tree where each node in the three consists of a set of variables.* Every variable in the original problem appears at least once, ensuring all variables are represented\n* If two variables are connected by a constraint in the original problem, they must appear together (with the constraint) in at least one of the tree nodes, ensuring all constraints are represented\n* If a variable appears in two nodes of the tree, it must appear in every node along the path connecting those nodes. This ensures that values in the original problem are still in the decomposition. \n\nThe tree decomposition is like a tree of subgraphs of the original problem. Trees of this nature can be solved in $O(nd^2)$ time. When creating a tree decomposition, we want to make the subproblems as small as possible. Time considerations favor tree decomposition, but cutset has the advantage that it can be executed in linear memory while tree decomposition needs expotential memory for tree width w.\n\nIf we have the same number of domain values as variables, this is known as value symmetry. Since this results in d! search space, we want to reduce that by breaking the symmetry with a symmetry-breaking constraint. This new constraint could be something like the colors of the regions need to be in alphabetical order. That would result in only one possible solution instead of three. \n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Factored representation** - each state has a set of variables with corresponding value\n* **Consistent** - assignment of values to variables where the assignment does not violate any constraint; (legal assignment)\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - for a CSP, this is a consistent and complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables of the problem, edges connect any two variables that participant in a constraint\n* **Unary constraint** - restricts the value of a single variable\n* **Binary constraint** - relates two values as the restriction\n* **Binary csp** - only has unary and binary constraints\n* **Global constraint** - constraint involving an arbitrary number of variables, does not mean it involves all the variables in a problem\n* **Preference constraints** - indicates which solution is preferred, compared to absolute constraints\n* **Constrained optimization problem** - COP, CSPs with preferences can be solved with optimization search methods (path based or local)\n* **Constraint propagation** - uses constraints to reduce the number of legal values for a variable, and propagating that constraint to another variable, etc.\n* **Node-consistent** - if all the values in a single variable's domain satisfy the unary constraint\n* **Arc-consistent** - if every value in the domain satisfies the binary constraint\n* **Path-consistent** - looks at triple set of variables using implicit constraints\n* **K-consistent** - for any set of $k-1$ variables and any consistent assignment to those variables, a consistent value can be assigned \n* **Strongly k-consistent** - if a CSP is k-consistent, $k-1$ consistent, ..., 1-consistent\n* **Resource constraint** - atmost constraint\n* **Bounds propagation** - domains representated as upper and lower bounds\n* **Bounds-consistent** - for lower and upper bounds, for every variable X there exists value that satisfies the constraint (X,Y) for every Y\n* **Commutativity** - a problem is commutative if the order of the set of actions does not matter\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - constraint learning set of variables with their values\n* **Min-conflicts heuristic** - select a value that results in the min number of conflicts with another variable\n* **Tabu search** - small list of recently visited states that the algorithm is not allowed to return to\n* **Constraint weighting** - concentrates the search on imporant constraints by assigning weights\n* **Directional arc consistency** - if and only if every variable Xi is arc consistent with each Xj for j>i\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "The key component to a knowledge based agent is the knowledge base, composed of sentences either add manually to the knowledge based from background knowledge \\\n",
        "or inferred from other existing sentences. The program need to know what the agent known and what the goals are in order to determine the behavior it needs to \\\n",
        "take. A declarative approach to system building involves the agent starting with an empty knowledge base and then giving the agent sentences to learn until \\\n",
        "it knows how to operate in its environment. The procedural approach encodes the desired behaviors directly into the program. A successful agent will often use \\\n",
        "a combination of these two approaches to solve a problem. \n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "* Performance Measure: +1000 to leave with gold, -1000 if caught by wumpus, -1 for each action taken, -10 for using an arrow\n",
        " * game ends when the agent dies or leaves the cave\n",
        "* Environment: 4x4 grid. gold and wupus locations are random with one each. other squares have p=0.2 of being a pit\n",
        "* Actuators: forward, turnleft 90deg, turnright 90deg\n",
        " * pit or wumpus is death\n",
        " * grab to pick up the gold\n",
        " * shoot to fire an arrow in a straight line. arrow continues until it hits a wall or wumpus. agent only has one arrow\n",
        " * climb to climb out of the cave, only from (0,0)\n",
        "* Sensors: 5 different sensors, percepts are given as a list of five symbols, one for each sensor\n",
        " * stench - perceives stench if in a square adjacent to wumpus \n",
        " * breeze - perceives breeze if in square adjacent to pit\n",
        " * glitter - perceived if in square with gold\n",
        " * bump - perceived if wall is found\n",
        " * scream - perceived if wumpus is killed, anywhere in the cave\n",
        "\n",
        "environment is deterministic, discrete, static, and single agent (wumpus is part of the environment and doesn't move). It is also sequential, partially \\\n",
        "observable, and transition model is completely known.  \n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "Each of the sentences in the knowledge base need to follow a syntax so that they are well formed and have defined semantics (meaning) to determine the truth \\\n",
        "of the sentence in the possible world. The world can be described as a model where each of the sentences have fixed true/false values. We would say that \\\n",
        "model m satisfies sentence a if sentence a is true in model m. $M(\\\\alpha)$ represents the set of all models where $\\\\alpha$ is true.\n",
        "\n",
        "Logical entailment: $\\\\alpha \\\\models \\\\beta if and only if M(\\\\alpha) \\\\subseteq M(\\\\beta) $ \n",
        "example) sentence x=0 entails sentence xy=0\n",
        "\n",
        "Logical entailment can be applied to derive conclusion (logical inference). Model checking enumerates all possible modesl to check that sentence a is true \\\n",
        "in all models where KB is true. When inferring sentences, we want to make sure they are sound and complete. Unsound inferences are potentially creating \\\n",
        "untrue sentences. Model checking is a sound procedure. The last characteristic is grounding. The sensors create connections that ensure that the KB is \\\n",
        "valid in the world. \n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Use letters and subscripts to denote symbols for the logical sentences. For example, $W_{1,3}$ could be wumpus in square (1,3).\n",
        "\n",
        "Connectives:\n",
        "* negation: not\n",
        "* conjunction: and (parts are conjuncts)\n",
        "* disjuction: or (parts are disjucts)\n",
        "* implication: implies, if-then statements (rules). premise/antecedent followed by a conclusion/consequent. \n",
        "* biconditional: if and only if \n",
        "\n",
        "For determining truth values, there are 5 rules\n",
        "* $\\\\neg P$ is true iff P is false in model m\n",
        "* $P \\\\land Q$ is true iff both P and Q are true in m\n",
        "* $P \\\\lor Q$ is true iff either P or Q is true in m\n",
        "* $P \\\\implies Q$ if true unless P is true and Q is flase in m\n",
        "* $P \\\\iff Q$ if true iff P and Q are both true or both false in m\n",
        "\n",
        "We can build a knowledge base for the wumpus world using the logical sentences, starting with the immutable aspects of the world. Next is to try to \\\n",
        "infer additional sentences using entailment and model checking. This will ensure the algorithm stays sound and complete.  \n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Before we determined entailment via model checking, we can also show entailment via theorem proving. If the number of models is large but the length of the \\\n",
        "proof is short, then it can be more efficient then model checking. \n",
        "* logical equivalence: $\\\\alpha \\\\equiv \\\\beta iff \\\\alpha \\\\models \\\\beta and \\\\beta \\\\models \\\\alpha $\n",
        "* deduction theorem: For any sentences $\\\\alpha$ and $\\\\beta$, iff the sentence $(\\\\alpha \\\\implies \\\\beta)$ is valid\n",
        "* validity and satisfiability connection: $\\\\alpha \\\\models \\\\beta $ if and only if the sentence $(\\\\alpha \\\\lor \\\\neg \\\\beta)$ is unsatisfiable\n",
        " * This is proved by proof by contradition, where one assume sentence $\\\\beta$ to be false and it leads to a contradiction with $\\\\alpha$. \n",
        "\n",
        "We can use any of the previous search algorithms to find a solution if the proof problem is structured like so:\n",
        "* INITIAL STATE: initial knowledge base\n",
        "* ACTIONS: set of actions consisting of all the inference rules applied to all of the sentences that match the top half of the inference rule\n",
        "* RESULT: result of an action is to add the sentence in the bottom half of the inference rule\n",
        "* GOAL: state that contains the sentence we are trying to prove\n",
        "\n",
        "Searching for proves is an alternative to enumerating models. Logical system are motononicity, the set of entailed sentences can only get bigger as information \\\n",
        "is added to the KB. \n",
        "\n",
        "For knowledge bases expressed in conjunctive normal form (CNF), the resolution rule yields a complete inference algorithm. The resolution rule will take each \\\n",
        "pair complemenary literals from the CNF and add it to the KB if it is not already there. This will continue until:\n",
        "* there are no new clauses that can be added (KB does not entail $\\\\alpha$)\n",
        "* two clauses resolve to yield the empty clause (KB entails $\\\\alpha$)\n",
        "\n",
        "All definite clauses are Horn clauses, including clauses with no positive literals. These are our goal clauses. If you resolve two Horn clauses, you get a \\\n",
        "Horn clause back. They are closed under resolution. The premise of a Horn form clause is the body and the conclusion is the head. Knowledge bases containing only definite clauses...\n",
        "* Every definite clause can be written as an implication whose premise is a conjunction of positive literals and its conclusion is a single positive literal.\n",
        "* Inference with Horn clauses can be done with forward-chaining and backward chaining\n",
        "* Deciding entailment with Horn clauses can be done in linear time to the size of the knowledge base\n",
        "\n",
        "Forward chaining is sound, each inference is an application of Modus Ponens. It is also complete since every entailed atomic sentence is derived. Both \\\n",
        "forward-chaining and backward-chaining implementations run in linear time. Backward chaining is goal-directed reasoning.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Forward chaining starts with the known data the agent has and adds new premises (sentences) as new percepts are given \\\n",
        "and incrementally applies the forward chaining algorithm to derive new conclusions. It is a type of data-driven reasoning. \\\n",
        "It does not have to start with a query.\n",
        "\n",
        "Backwards chaining does start with a query and works backwards. If the query is true, then nothing needs to be done. If the \\\n",
        "query is false, then it finds implications in the knowledge base where the conclusion is the inital query. If all the premises \\\n",
        "of one of the implications can prove to be true (via backward chaining) then the query is true. This is a form of goal-directed \\\n",
        "reasoning.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"kb, set of sentences expressed in a knowledge representation language\",\n",
        "\"sentence\": \"expressed in a knowledge representation language with some assertion about the world\",\n",
        "\"axiom\": \"a sentence that was not derived from another sentence\",\n",
        "\"syntax\": \"all sentences are well-formed\",\n",
        "\"semantics\": \"meaning of the sentences, defining the truth of each sentence wrt each possible world\",\n",
        "\"entailment\": \"a sentence follows logically from another sentence\",\n",
        "\"sound (truth-preserving)\": \"only sentences that are derived from entailed sentences are inferred\",\n",
        "\"completeness\": \"inference algorithm is complete if it can derive any sentence that is entailed\",\n",
        "\"grounding\": \"ensuring that the connetions between the logical reasoning process and the real environment are true\",\n",
        "\"atomic sentences/literals\": \"logical sentences that only consist of one logical operator (proposition symbol)\",\n",
        "\"complex sentences\": \"constructed from simpler sentences\",\n",
        "\"logical connectors\": \"parentheses and operators\",\n",
        "\"theorem proving\": \"applying rules of inference directly to the sentences to construct a proof of the desired sentence without checking models\",\n",
        "\"logical equivalence\": \"two sentences are logically equivalent if they are true in the same set of models\",\n",
        "\"validity\": \"if a sentence is true in all models. also known as tautologies, they are necessarily true\",\n",
        "\"satisfiability\": \"a sentence is satisfiable if it is true in some model\",\n",
        "\"ground resolution theorem\": \"if a set of clauses is unsatisfiable, then the resolution closure contains the empty clause\",\n",
        "\"definite clause\": \"disjunction (or) of literals where exactly one is positive (rest are negated)\",\n",
        "\"Horn clause\": \"disjunction of literals where most one is positive\",\n",
        "\"fact\": \"sentence consisting of a single positive literal\",\n",
        "\"data-driven reasoning\": \"reasoning where the focus starts with the known data\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 304,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "49ccbf8d-6e1c-489c-d421-3d438f2ce2f4"
      },
      "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": 305,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nThe key component to a knowledge based agent is the knowledge base, composed of sentences either add manually to the knowledge based from background knowledge or inferred from other existing sentences. The program need to know what the agent known and what the goals are in order to determine the behavior it needs to take. A declarative approach to system building involves the agent starting with an empty knowledge base and then giving the agent sentences to learn until it knows how to operate in its environment. The procedural approach encodes the desired behaviors directly into the program. A successful agent will often use a combination of these two approaches to solve a problem. \n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n* Performance Measure: +1000 to leave with gold, -1000 if caught by wumpus, -1 for each action taken, -10 for using an arrow\n * game ends when the agent dies or leaves the cave\n* Environment: 4x4 grid. gold and wupus locations are random with one each. other squares have p=0.2 of being a pit\n* Actuators: forward, turnleft 90deg, turnright 90deg\n * pit or wumpus is death\n * grab to pick up the gold\n * shoot to fire an arrow in a straight line. arrow continues until it hits a wall or wumpus. agent only has one arrow\n * climb to climb out of the cave, only from (0,0)\n* Sensors: 5 different sensors, percepts are given as a list of five symbols, one for each sensor\n * stench - perceives stench if in a square adjacent to wumpus \n * breeze - perceives breeze if in square adjacent to pit\n * glitter - perceived if in square with gold\n * bump - perceived if wall is found\n * scream - perceived if wumpus is killed, anywhere in the cave\n\nenvironment is deterministic, discrete, static, and single agent (wumpus is part of the environment and doesn't move). It is also sequential, partially observable, and transition model is completely known.  \n\n\n## AIMA Chapter 7.3 Logic\n\nEach of the sentences in the knowledge base need to follow a syntax so that they are well formed and have defined semantics (meaning) to determine the truth of the sentence in the possible world. The world can be described as a model where each of the sentences have fixed true/false values. We would say that model m satisfies sentence a if sentence a is true in model m. $M(\\alpha)$ represents the set of all models where $\\alpha$ is true.\n\nLogical entailment: $\\alpha \\models \\beta if and only if M(\\alpha) \\subseteq M(\\beta) $ \nexample) sentence x=0 entails sentence xy=0\n\nLogical entailment can be applied to derive conclusion (logical inference). Model checking enumerates all possible modesl to check that sentence a is true in all models where KB is true. When inferring sentences, we want to make sure they are sound and complete. Unsound inferences are potentially creating untrue sentences. Model checking is a sound procedure. The last characteristic is grounding. The sensors create connections that ensure that the KB is valid in the world. \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nUse letters and subscripts to denote symbols for the logical sentences. For example, $W_{1,3}$ could be wumpus in square (1,3).\n\nConnectives:\n* negation: not\n* conjunction: and (parts are conjuncts)\n* disjuction: or (parts are disjucts)\n* implication: implies, if-then statements (rules). premise/antecedent followed by a conclusion/consequent. \n* biconditional: if and only if \n\nFor determining truth values, there are 5 rules\n* $\\neg P$ is true iff P is false in model m\n* $P \\land Q$ is true iff both P and Q are true in m\n* $P \\lor Q$ is true iff either P or Q is true in m\n* $P \\implies Q$ if true unless P is true and Q is flase in m\n* $P \\iff Q$ if true iff P and Q are both true or both false in m\n\nWe can build a knowledge base for the wumpus world using the logical sentences, starting with the immutable aspects of the world. Next is to try to infer additional sentences using entailment and model checking. This will ensure the algorithm stays sound and complete.  \n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nBefore we determined entailment via model checking, we can also show entailment via theorem proving. If the number of models is large but the length of the proof is short, then it can be more efficient then model checking. \n* logical equivalence: $\\alpha \\equiv \\beta iff \\alpha \\models \\beta and \\beta \\models \\alpha $\n* deduction theorem: For any sentences $\\alpha$ and $\\beta$, iff the sentence $(\\alpha \\implies \\beta)$ is valid\n* validity and satisfiability connection: $\\alpha \\models \\beta $ if and only if the sentence $(\\alpha \\lor \\neg \\beta)$ is unsatisfiable\n * This is proved by proof by contradition, where one assume sentence $\\beta$ to be false and it leads to a contradiction with $\\alpha$. \n\nWe can use any of the previous search algorithms to find a solution if the proof problem is structured like so:\n* INITIAL STATE: initial knowledge base\n* ACTIONS: set of actions consisting of all the inference rules applied to all of the sentences that match the top half of the inference rule\n* RESULT: result of an action is to add the sentence in the bottom half of the inference rule\n* GOAL: state that contains the sentence we are trying to prove\n\nSearching for proves is an alternative to enumerating models. Logical system are motononicity, the set of entailed sentences can only get bigger as information is added to the KB. \n\nFor knowledge bases expressed in conjunctive normal form (CNF), the resolution rule yields a complete inference algorithm. The resolution rule will take each pair complemenary literals from the CNF and add it to the KB if it is not already there. This will continue until:\n* there are no new clauses that can be added (KB does not entail $\\alpha$)\n* two clauses resolve to yield the empty clause (KB entails $\\alpha$)\n\nAll definite clauses are Horn clauses, including clauses with no positive literals. These are our goal clauses. If you resolve two Horn clauses, you get a Horn clause back. They are closed under resolution. The premise of a Horn form clause is the body and the conclusion is the head. Knowledge bases containing only definite clauses...\n* Every definite clause can be written as an implication whose premise is a conjunction of positive literals and its conclusion is a single positive literal.\n* Inference with Horn clauses can be done with forward-chaining and backward chaining\n* Deciding entailment with Horn clauses can be done in linear time to the size of the knowledge base\n\nForward chaining is sound, each inference is an application of Modus Ponens. It is also complete since every entailed atomic sentence is derived. Both forward-chaining and backward-chaining implementations run in linear time. Backward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nForward chaining starts with the known data the agent has and adds new premises (sentences) as new percepts are given and incrementally applies the forward chaining algorithm to derive new conclusions. It is a type of data-driven reasoning. It does not have to start with a query.\n\nBackwards chaining does start with a query and works backwards. If the query is true, then nothing needs to be done. If the query is false, then it finds implications in the knowledge base where the conclusion is the inital query. If all the premises of one of the implications can prove to be true (via backward chaining) then the query is true. This is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Knowledge base** - kb, set of sentences expressed in a knowledge representation language\n* **Sentence** - expressed in a knowledge representation language with some assertion about the world\n* **Axiom** - a sentence that was not derived from another sentence\n* **Syntax** - all sentences are well-formed\n* **Semantics** - meaning of the sentences, defining the truth of each sentence wrt each possible world\n* **Entailment** - a sentence follows logically from another sentence\n* **Sound (truth-preserving)** - only sentences that are derived from entailed sentences are inferred\n* **Completeness** - inference algorithm is complete if it can derive any sentence that is entailed\n* **Grounding** - ensuring that the connetions between the logical reasoning process and the real environment are true\n* **Atomic sentences/literals** - logical sentences that only consist of one logical operator (proposition symbol)\n* **Complex sentences** - constructed from simpler sentences\n* **Logical connectors** - parentheses and operators\n* **Theorem proving** - applying rules of inference directly to the sentences to construct a proof of the desired sentence without checking models\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - if a sentence is true in all models. also known as tautologies, they are necessarily true\n* **Satisfiability** - a sentence is satisfiable if it is true in some model\n* **Ground resolution theorem** - if a set of clauses is unsatisfiable, then the resolution closure contains the empty clause\n* **Definite clause** - disjunction (or) of literals where exactly one is positive (rest are negated)\n* **Horn clause** - disjunction of literals where most one is positive\n* **Fact** - sentence consisting of a single positive literal\n* **Data-driven reasoning** - reasoning where the focus starts with the known data\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "bf3009e1-7fb4-498f-b709-ff7bc5261be1"
      },
      "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": 306,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nThe field of AI has taken several different versions and can be categorized in four ways: human vs rational and thought vs behavior. The pursuit of human like intelligence relates to psychology whereas rational relies on math, engineering, statistics, control theory and economics. \n\nThe Turing Test was designed to help answer the question \"Can a machine think?\". If a human cannot tell if a written response (after some posed questions) comes from a computer or a human, the computer passes the test. In order to pass a test, a computer would need 4 capabilities: natural language processing, knowledge representation, automated reasoning, & machine learning.Technically, this method would not require a person to demonstrate intelligence. A Total Turing Test requires interactions with real people and objects. Therefore a robot would also need: computer vision & robotics. Researchers have not intensely focused on trying to pass the Turing Test but have focused on studying the principles of intelligence. \n\nTo learn how humans think, consider three things: introspection, psycological experiemnts, and brain imaging. With a theory of the mind, we could use this theory to create a computer program with inputs/outputs corresponding with human behavior. General Problem Solving (GPS) inventors (Newell & Simon) didn't only want the algorithm to solve problems, but to also mimic the sequence and timings of the steps with those that a human would take (aka cognitive science). \n\nAristole tried to codify \"right thinking\" into syllogisms, the start logic. Logic requires knowledge of the world that is certain. Where certainty is not possible we rely on probability. These two allow us to construct a comprehensive model of rational thought, but it not does generate intelligent behavior. For that, we would need a theory of rational action, not only rational thought.\n\nIn the \"laws of thought\" approach to AI, they focused on correct inferences, but that is only part of being a rational agent. There are also other ways to act rationally that do not include inferences, such as reflexes. The rational agent approach has two advantages: it is more general than the \"laws of thought\" approach since other mechanisms are possible for acheiving rationality and it is more responsive to scientific development since it is mathematically defined and general. The rational agent approach has prevailed in AR since they are built on logical foundations and formed definite plans to achieve specific goals. It focuses on \"doing the right thing\", defined by the objective provided to the agent.\n\nWe don't always have a fully specified objective to give to the machine, so we cannot always use a standard model. Therefore, we have to introduce tradeoffs and how to deal with those tradeoffs by creating value alignment problems. We want to make sure machines behave and do not take some drastic measure to reach an objective, therefore we need to make sure we formulate correctly.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nDreyfus believed that human behavior cannot be captured by a set of rules, we are too complex, and therefore could never be coded into a computer program. They critizied Good Old Fashion AI as not being able to product durable results, refering to AI as a simple logical agent. It is difficult to capture every possible appropriate behavior in a set of logical rules (refered to as a qualification problem). Probabalistic reasoning allows for more open ended domains while deep learning does well with 'informal' tasks. We have expanded upon the different techniques available in AI and thus can go beyond the original critique that Dreyfus had.\n\nSituated agents should be used to embody the entire experience, such as being able to watch, run, play, and pet a dog, compared to just a logical inference engine that just knows Dog(x) => Mammal(x). Embodied cognition includes the whole body and brain, not just the brain. Therefore this means that sensors and cameras are necessary instead of peripheral. \n\nGodel Sentence:\n* G(F) is a sentence of F, but cannot be proved within F.\n* If F is consistent, then G(F) is true.\n\nGodel's Incompleteness Theorem states that machines cannot establish the truth of their own Godel Sentences. This only applies to machines that can do arithmetic with infinite. \n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nThe Chinese Room\nYou have a man in a box. The man is given a paper with symbols. The man has a book to help decipher the symbols. Once dechipered, the man passes the translation back out of the box.One can argue the man does not know chinese. The box is no different than a computer, the computer does not think or understand, it just does. \n\nDo machines have consciousness? Are they aware of the outside world and of themselves? Can they feel? We can program intelligence and awareness, but cannot program the same level of consciousness that humans have. \n\n\n## AIMA 2.1 Agents and Environments\n\nVacuum Cleaner World\n* agent = robotic vacuum cleaner\n * percepts = perceives if there is dirt in the square and its location\n * sensors = dirt sensor, camera for navigation\n * actuators = brushes to pick up dirt\n* actions = move left, right; pick up dirt; do nothing\n* agent function = if square has dirt, pick it up, otherwise, move to another square\n* environment = the two squares it has access to. it doesnt care about anything else\n\nRobo vacuum's agent function can be tabulated by all the possible states it could take. What is the best way to fill out the table to make robo vacuum the best it can be?\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWe can take a measure of the agent doing the right thing with the concept of consequentialism, what are the consequences of the agent's actions. An agent will go through a sequence of actions and those actions will result in a sequence of environmental states. If one of those sequences is desirable from the human's POV, then the agent has performed desirably. This is captured by a performance measure that evaluates a sequence of environmental states. Performance measures can be explicitly known to the agent, or implicitly known, but in the latter the agent will not know why it did the right thing.\n* performance measure = all the floor is clean\n\nDesign performance measures based on what you want to be done in the environment, not how you think the agent should act. \n\nWhat is rational at a point in time depends on four things:\n* performance measures\n* agent's prior knowledge of the environment\n* actions agent can perform\n* agent's percept sequence up to the current point in time\n\nA rational agent should select an action that will maximize its performance measure, given all the data that it currently has (including built-in knowledge and historical knowledge from the given percept sequence) for a possible percept sequence.\n\nRationality is not omsciscience. The agent will not know EXACTLY what the outcome of its actions to know the perfect sequence to take. Rationality maximizes expected performance, we should not expect agents to be perfect. We only rely on the percepts we know to date and not any future information. We should also make sure that the agent doesn't do anything stupid and gathers information along the way or explores its environment to learn more before taking a further action. A rational agent should be autonomous and should learn without the aid of its designer. \n\n\n## AIMA 2.3 The Nature of Environments\n\nTask Environment Properties:\n* Fully observable vs **partially observable** = knowing all the info in the env vs only part. No need to store an internal state of a fully observable env compared to partially observable. Could also be partially obserable from noisy data or sensors. If there are no sensors, then an env could be unobservable. Goals could still be achievable in an unobservable env.\n* Single agent vs **multiagent** = crossword or sudoku puzzle are single agent. Chess and checkers are (competitive) multiagent. The car would be considered an agent if its behavior is trying to max a performance measure whose value depends on agent A's behavior All taxis are agents, but in a partially cooperative env because avoiding collisions helps all their performance measures.\n* Deterministic vs **nondeterministic** = If next state after the agent makes an action is known, this is deterministic. If the env state is not known after the action, this is nondeterministic. In a fully observable, deterministic env, uncertainty is not a concern. Nondeterministic can be stochastic, where we can have known probabilities for things happening in the env. \n* Episodic vs **sequential** = In episodic env, the agents actions are divided into episodes; agent receives a percept and performs one action. The next episode will not depend on the previous episode, it is its own instance (starting from scratch). In sequential envs, the agent needs to consider what happened before. In chess,  A needs to take an action base on B's move and will need to think ahead for the best possible move.\n* Static vs **Dynamic** =  In a static env, the agent doesn't worry about changes in the env while selecting an action. If the env is changing continuously, then the env is dynamic and the agent will need to constantly evaluate and will constantly be asked what to do. If the env does NOT change but its performance measure does over time, this is semidynamic. An agent could take a performance hit based taking ample time to reach the goal, such as chess with a timer. \n* Discrete vs **continuous** = Used to describe the state of the env, how time is handled, percepts and actions. Discrete refers to a finite number. Taxi driving has multiple continuous attributes; speed, location, other vehicles, steering angles, etc.\n* Known vs **unknown** = In a known env, the outcomes (or outcome probabs) for all actions are given, the agent will know the resulting state after the action. If the env is unknown, the agent will have to observe the outcome based on the action taken to know if it was a good decision. \n\n\n## AIMA 2.4 The Structure of Agents\n \nAI is intended to design an agent program that implements the agent function. The agent program will run on an agent architecture. The architecture needs to be appropriate for the agent program. If the agent needs to walk, it needs legs, if it needs to be able to see, it needs a camera. The architecture makes the percepts from the sensors available to the program, runs the program to decide the next action, and tells the actuators what action to take. A agent program takes only the current percept sequence to make a decision, the agent function could take into account the entire percept history. Only in very simple scenarios is it possible to have a table driven agent. In most scenarios, there are too many sets of possible percepts for a lookup table. \nAgent programs:\n* Simple reflex agents - Select actions based on the current percept, ignoring the rest of the percept history. These can be described with a condition-action rule: \"if <thing is happening> then <do something>\". \n* Model-based agents - Store the percept history in an internal state that the agent can reflect on for some of the unobservable aspects of the current state.  The agent will keep track of other knowledge of the env, even if it is not receiving percepts about it currently. Knowledge about what will happen in the world when the agent takes an action described by a transition model. Knowledge about the percepts the sensor receives and what they mean can be described by a sensor model. Tracking of the transition model and sensor model combined is what makes up a model-based agent. \n* Goal-based agents - Just knowing about the env is not enough for the agent to produce desirable results, the agent needs to know the goals to determine desirable situations. An agent is goal-based if it's decided actions help it reach a given goal. Sometimes it is simple to find a goal, it only takes one action. But often times you need a sequence of actions to reach a goal. Use search and planning strategies to find this sequence. \n* Utility-based agents - Agents that compare the diff between states to decide whether one is better than the other. An agent's utility fcn describes the performance measure. The agent can choose actions that max its utliity (\"happiness\") if the utility fcn and performance measure are in alignment. If there are conflicting goals, the utility function can help determine tradeoffs. A rational utility-based agent chooses an action that will max the expected utlity of the outcomes. A utility based agent has to model and keep track of its env. \n\nLearning agents:\n* learning element makes improvements\n* performance element selects actions\n* critic determines the performance element\n* problem generator suggesting actions\n\nComponents of agent programs:\n* atomic - no internal structure, just goes from one state to another\n* factored - splits states into a fixed set of variables with values\n* structured - includes objects with attributes and relationships between the objects\n\n\n## Module 1 Lecture Notes\n\nIt is possible to have a known, partially observed env (solitaire). You know all rules, but some of the cards are hidden. An env can be unknown and fully observable. Such as a video game where all the env is viewable, but  the results of the buttons are unknown. You could have an unknown performance measure, if we don't know the preferences of the judges.\n\n\n## Module 1 Definitions\n* **Artificial intellience** - the field to understand and build intelligent entities that can act effectively and safely in a situation\n* **Rationality** - doing the right thing\n* **Natural language processing** - area of AI for computers being able to understand text and spoken words like a human\n* **Knowledge representation** - storing known or learned data in a way a computer can understand it\n* **Automated reasoning** - computers using logic to answer problems and draw conclusions, such as inferences\n* **Machine learning** - computers learning from data and building models, allowing the results to adapt, detect, and extrapolate patterns to make decisions\n* **Computer vision** - computers understanding the world through pictures and videos\n* **Robotics** - machines that can manipulate objects and the world around them through physical movement\n* **Introspection** - analying internal thoughts\n* **Psycological experiments** - observation of humans\n* **Brain imaging** - observation of an active brain\n* **Cognitive science** - field of computer science that combines AI computer models and psycological experiment techniques to construct theories of the human mind\n* **Syllogisms** - codifying irrefutable reasoning processes into patterns for argument structures that always yield correct conclusions given correct premises\n* **Logic** - laws of thought that govern the operation of the mind, given a precise notation for statements\n* **Probability** - representation of uncertainty\n* **Agent** - anything that can percieve its environment through sensors and can act on its environment through actuators\n* **Rational agent** - agent that acts to achieve the best outcome, following actions that are the 'right thing to do'\n* **Standard model** - paradigm stating for AI, the right thing is determined by the objective provided to the agent\n* **Value alignment problem** - problem of achieving agreement between the human's preferences and the objective given to the machine\n* **Weak ai** - acting intelligently through simulated thinking\n* **Strong ai** - actually consciously thinking (instead of simulated thinking)\n* **Qualification problem** - impossibility of being able to create a set of necessary and sufficient logical rules that captures all situations.\n* **Percept** - data received by the agents sensors. percept sequence is the entire history of data that percept has recieved.\n* **Agent function** - an abstract mathematical function that describes the behavior of the agent by mapping a percept sequence to an action\n* **Agent program** - concrete implementation that implements the agent function and runs it in the real world\n* **Percept sequence** - everything the agent has perceived up until the current point in time\n* **Task environment** - defined by PEAS\n* **Agent architecture** - some computing device with physical sensors and actuators. agent = architecture + program\n* **Expected utility** - the average utility the agent can achieve given the probabilities and utilities of each outcome\n* **Performance** - peformance measure to aspire towards\n* **Environment** - surroundings that the agent needs to be concerned with, both physical and virtual\n* **Acutators** - controls allowing the agent to take actions\n* **Sensors** - means for gathering percepts, seeing, hearing, etc.\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n First we will work with episodic, single agent, fully observable, deterministic, static, discrete, and known environment. If we assume that the agent will  always have access to info about the world, they can follow a four phase problem solving process:\n * Goal Formulation: agent adopts a goal and uses it to limit its objectives and organize its behavior/actions\n * Problem Formulation: abstract model of the wolrd using descriptions of states and actions to reach a goal.\n * Search: simulating sequences of actions to reach a goal. A correct sequence that reaches a goal is a solution. The agent might have to try multiple sequences  before it finds a solution or discovers no solution is possible.\n * Execution: execution of the actions in the solution sequence.\n\n In a fully observable, deterministic, known environment, the solution is a fixed sequence of actions. If the model is correct, the agent can execute the  actions without any percepts since the solution is guranteed to reach a goal. If model is incorrect or the environment is nondeterministic, then a closed-loop  approach is needed. In partially observable or nondeterministic, a solution might need branches depending on the percepts received to decide actions.\n\n Search Problem:\n * set of possible states (state space)\n * initial state\n * set of goal states\n * set of actions applicable in a state; ACTIONS(s)\n * transition model\n * action cost function - problem solving agent should use an action cost function that refects its performance measures\n\nAction costs are additive along a path. State spaces can be represented as a graph; vertices are states, directed edges are actions between the states. Good problem formulation has just the right amount of detail/level of abstraction. An abstraction is *valid* if we can apply the resulting solution to the real world. An abstraction is *useful* if it is possible to carry out each of the actions in the solution without additional solving. A good abstraction removes as much detail as possible while retailing validity and the ability to carry out the actions.  \n \n\n## AIMA Chapter 3.2 Example Problems\n\nVacuum World Example\n* States = instances of the grid world stating which objects (dirt) are in which cells. $n cells = n*2^n states$\n* Initial state = chosen state to start\n* Actions = suck, move left, move right. (could add move up, move down in 2d world)  \n* Transition Model\n * Suck = Removes dirt\n * Turn (left or right) = Change direction 180deg\n * Forward = move one cell (if possible)\n * Backward = move in opposite direction\n* Goal states = every cell in grid world is clean\n* Action cost = each action costs 1\n\nRouting-finding problem examples include driving directions, routing video streams in computer networks, military operations planning.\nAirline Travel Example\n* States = location and current time, plus any historical information\n* Initial state = home airport\n* Actions = take flight in a seat class at a time after current time with enough time for any transfers\n* Transition Model\n * taking a flight = flight destination and arrival time\n* Goal states = destination city\n* Action cost = price of flight, waiting time, flight time, custom & immigration procedures, seal quality, time of day, type of airplane, preferred airline, etc.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nMany search problems can be formulated as search trees with the root as the initial state. We will expand nodes in the search tree until we find a goal state. Expand nodes using the available actions for that state to generate child/successor nodes for the resulting state.\n\nBest-First Search\n* Add initial node to the frontier\n* while frontier is not empty\n* Pop a node\n* If the node is a goal state, return node\n* For each child in EXPAND\n * if the state has not been reached before or the cost is less than the reached cost (looking for minimum cost)\n  * note child as reached\n  * add child to frontier\n* if no solution is found, return failure\n\nEXPAND\n* For each action for the given node\n * Run the evaluation function (path-cost + action-cost)\n * Evaluate the resulting state\n * Yield new node as the state, parent, action, and cost\n\nEach state is represented by a node. The node holds information about the\n* state = environment state\n* parent = node of the tree that generated this node\n* action = action that generated this node\n* path cost = total cost of the path from initial state to this node\n\nQueues are used to store the frontier since we need operations for is-empty, pop, top (returns node but does not remove it), and add.\n\nAlgorithms are not efficient if they repeat paths they have already visited.\n* Remember all previously visited states (like best first search). Only possible if table of reached states will fit in memory.\n* Problem formulations does not result in loops. Path from A-B but not B-A.\n* Check for cycles, but not redundant paths.\n\nTree search uses less memory since it doesn't have to remember visited nodes. If there are loops, it will run slower than graph search. In finite state spaces, a complete algorithm can explore every state that is reachable from an initial state as long as it keeps track of paths and cuts off cycles. In infinite state spaces, the search algorithm must systematically explore the state space to ensure it reaches any state connected to the initial state. If there is no solution for an inifinite state space, there needs to be a way to terminate so it doesn't search forever. Size of state space can be represented as |V|+|E| or for implicit state spaces, depth (d), max number of actions in a path (m), branching factor (b).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nUninformed search algorithms do not know how close they are to the goal. If all actions have the same cost, Breadth-First Search (BFS) can be used. BFS is a systematic search strategy that is complete even in infinite state spaces. BFS always find an optimal solution if all actions have the same cost. BFS time and space complexity is $O(b^d)$. Since it is exponential, large state spaces would take too long, but even worst, would take too much space.\n\nDijkstra's Algorithm or Uniform-Cost Search (UCS) is BFS where the actions have different costs. The evaluation function is the cost of the path from the root node to the current node. UCS is best-first search with the path costs.\n* expand the node with the least total path cost\n* as nodes are expanded, check to see if the node (not the child) is the goal\n* if node has a lower path cost, replace path in reached and add to frontier. There is no reason to visit nodes with higher path costs. \n\nDepth-First Search (DFS) is implemented as a tree search (does not keep track of reached) where it expands to the deepest node before going to the next branch. If it reaches the end of the branch, it backs up to the previous deepest node that has unexpanded children. DFS will return the first solution it finds (not cost-optimal). DFS can get stuck going down an infinite path or in cycles. It is not systematic, therefore not complete. DFS uses much less memory than BFS  since it does not keep track of reached. In a variant of DFS, backtracking uses less memory because it only generates one child at a time by modifying the current state description directly. Because we modify it directly, we have to be able to undo the actions when we backtrack. \n\nDepth-limited Search can keep DFS from going down an infinite path by supplying a depth limit (l) where children at l are treated like they are leaves. If we pick l poorly, it will fail to reach a solution. l can be chosen based on the problem or knowing the diameter of the state space. Often we will not know that until we have solved the problem. \n\nIterative Deepening solves the problems of depth-limited by trying all values of l until it reaches a solution or hits a cutoff depth. Iterative deepening is the preferred uninformed search method when the state space is larger than what can fit in memory and the depth is unknown.\n\nBidirectional search searches both from the initial state and backward from the goal state(s), in hopes that the searches will meet. It needs to keep track of two frontiers and reached states. We would also need to be able to reason backwards to determine who are the successors of who. The solution is found when the searches meet in the middle. \n\n\n## Module 3 Lecture Notes\n\n**BFS**\n* If node is a goal state, return node\n* add node to FIFO frontier\n* while frontier is not empty\n * pop the oldest node\n * for each child of the node\n  * if child is a goal state, return (we are able to do an early goal test right after child is generated instead of after popped from frontier)\n  * if child's state has not been reached\n   * add state to reached\n   * add child to frontier\n* if goal is not found, return failure\n\n\n**Comparison Table**\n\n| Syntax        \t|    BFS   \t|         UCS        \t|    DFS   \t| Depth-Limited \t| Iterative Deepening \t|\n|---------------\t|:--------:\t|:------------------:\t|:--------:\t|:-------------:\t|:-------------------:\t|     \n| Complete?     \t|   Yes 1  \t|       Yes 1,2      \t|    No    \t|       No      \t|        Yes 1        \t|\n| Optimal cost? \t|   Yes 3  \t|         Yes        \t|    No    \t|       No      \t|        Yes 3        \t|\n| Time          \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t| $O(b^m)$ \t|    $O(b^l)$   \t|       $O(b^d)$      \t|  \n| Space         \t| $O(b^d)$ \t| $O(b^(1+[C^*/e]))$ \t|  $O(bm)$ \t|    $O(bl)$    \t|       $O(bd)$       \t|  \n\n| Syntax        \t| Bidirectional \t| Minimax           | Alpha-beta        |  Expectiminimax   |  AC-3             |\n|---------------\t|:-------------:\t|:-------------:    |:-------------:    |:-------------:    |:-------------:    |     \n| Complete?     \t|    Yes 1,4    \t|        \t          |                   |                   |                   |\n| Optimal cost? \t|    Yes 3,4    \t|       \t          |                   |                   |                   |\n| Time          \t|  $O(b^{d/2})$ \t|  $O(b^{m})$   \t  |  $O(b^{m/2})$     | $O(b^{m}n^m)$     |  $O(cd^{3})$      |  \n| Space         \t|  $O(b^{d/2})$ \t|  $O(bm)$ \t        |                   |                   |                   | \n1. if b is finite and state space has solution or is finite\n2. all action costs are > 0\n3. all action costs are identical\n4. both directions are BFS or UCS\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search using atomic representations\n* **Planning agents** - an agent that can formulate a plan via search using factored or structured representations of states\n* **Open-loop** - system where the solution can be executed without any percepts\n* **Closed-loop** - system where the agent will need to monitor percepts while executing a solution\n* **Transition model** - describes what each action does and the resulting state; RESULT(s,a) = s'\n* **Action cost function** - supplies the numeric cost of an action from one state to another; ACTION-COST(s,a,s')\n* **Path** - sequences of actions\n* **Solution** - path from state to a goal state\n* **Optimal solution** - lowest path cost among all solutions\n* **Model** - abstract mathematical description of a problem\n* **Abstraction** - removing detail from a representation\n* **Standardized problem** - used to exercise problem-solving methods and serve as a benchmark to compare performance of algorithms\n* **Real-world problem** - distinct formulation of a problem to find a usable solution\n* **Egocentric actions** - actions relative to the agent's POV (forward, backward, turnright, turnleft)\n* **Route-finding problem** - locations and transitions along edges between the locations\n* **Touring problems** - set of locations that must be visited\n* **Traveling sales plan problem (tsp)** - touring problem where every city is visited with the lowest total cost\n* **Search algorithm** - takes a search problem as input and returns a solution or failure as the output\n* **Frontier** - unexpanded nodes in a search tree\n* **Reached** - any state in a search tree that has been generated (doesn't have to be expanded)\n* **Priority queue** - pops node with min cost according to eval function\n* **Fifo queue** - first-in-first-out; pops node added to the queue first (used in BFS)\n* **Lifo queue** - last-in-first-out (stack); pops most recently added node\n* **Cycle** - loopy path, special case of a redundant path\n* **Graph search** - checks for redundant paths (best first search)\n* **Tree search** - does not check for redundant paths\n* **Completeness** - guranteed to find a solution if there is one or report failure if there is not one\n* **Cost optimality** - find solution with lowest path costs\n* **Time complexity** - amount of time it takes to find a solution\n* **Space complexity** - amount of memory it takes to perform the search\n* **Depth** - d; number of actions in an optimal solution\n* **Branching factor** - number of successors/childern of a node that need to be considered\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed algorithms can estimates how far the initial state is from the goal. Greedy Best-first search expands first the node with the lowest f(n) = h(n). It is possible for greedy best-first search to not find the most optimal solution since it will always take the lowest cost. It is complete in finite spaces  with a space/time complexity of $O(|V|)$ with the possibility of reaching $O(bm)$ with a good h(n).\n\nA* Search is a best first search that uses the evaluation function $f(n) = h(n) + g(n)$ where g(n) is the current total path cost from initial state to n and h(n) is the estimated cost of the shortest path from n to a goal state. A* is complete, but is guaranteed to be cost optimal only if it h(n) is admissible. Every consistent heuristic is admissible but not every admissible heuristic is consistent.\n\nPath costs are strictly monotonic if they always increase as you go along a path and just monotonic if they either increase or stay the same. A* is optimally efficient if it has a consistent heuristic. A* isn't the answer to everything, in some problems, the number of nodes expanded can be exponential in the length of the solution. A* expands a lot of nodes, taking more time and space. If we are OK with a suboptimal solution, we can use an inadmissible heuristic to be more accurate and expand less nodes to find a suboptimal solution. We can use a Weighted A* Search with eval function $f(n)=g(n) + W*h(n) for W>1$. A* search uses a lot of memory between the frontier and the reached states. \n\nOther informed search algorithms that use a heuristic function are:\n* Bidirectional A* Search = sometimes more efficient than A*\n* IDA* (Iterative deepening A* search) = iterative deepening version of A*, address the space complexity issue. in the original the cutoff was depth, for IDA*, it is the f-cost (g+h).  \n* RBFS (recursive best-first search) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* would run out of memory. resembles a recursive DFS, but uses an f_limit to keep track of the f_value of the best alternative path available from any ancestor of the current node. \n* SMA* (simplified memory-bound A*) = robust, optimal search algorithm that uses a limited amount of memory. given enough time, they can solve problems where A* would run out of memory. drops the worse leaf node (highest f-value), the back ups the value of the forgotten node to the parent. SMA* expands the best leaf and deletes the oldest worst leaf. complete if there is a reachable solution.\n* Beam Search = puts a limit on the size of the frontier. results in the algorithm being incomplete and suboptimal, but can find reasonably good solution and runs faster than complete searches. Only exploes a focused portion with the best candidates\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nConsider how heuristics can be invented. For the sliding tile n-puzzle, we could use either admissible h(n):\n* number of misplaced tiles (not including the blank)\n* sum of the distances of the tiles from their goal positions using Manhattan distance\n\nThe quality of a heuristic can be characterize by its effective branching factor (b*), with a well designed heuristic having a b* value close to 1. If $h2(n) \\ge h1(n)$ h2 dominates h1, which means that h2 is more efficient than h1 and will expand less nodes if h2 is used. It is generally better to use a heuristic with higher values as long as it is consistent and the computation time is not too long. We can create heuristics using a version of the problem with fewer restrictions (relaxed problem). A relaxed problem would have a state-space larger than the original since removal of restrictions creates added edges in the graph (supergraph). An optimal solution in the original problem would be a solution for the supergraph, but not the other way around. The cost of an optimal solution to a relaxed problem is an admissible heauristic for the original problem. Another method to create heuristics is using the solution for a subproblem. For the n-tile puzzle, this is more accurate than the Manhattan distance. Solutions to these subproblems can be stored in a pattern database. Other methods for creating heuristics include defining landmarks or by learning from experience.  \n\n\n## Module 4 Lecture Notes\n\n**Heuristics**\n* A*: $g(n) + h(n)$ (W=1)\n* UCS: $g(n)$ (W=0)\n* Greedy Best First: $h(n)$ (W=inf)\n* Weighted A*: $g(n)+W*h(n)$ (1<W<inf)\n \n\n## Module 4 Definitions\n* **Heuristic function** - h(n); estimated cost of the cheapest path from a state to the goal\n* **Straight-line distance heuristic** - heuristic using distance 'as the crow flys' between two locations, can be computed using distance formula\n* **Admissibility** - an admissible heuristic is one that never over estimates the cost to reach a goal (optimistic)\n* **Consistency** - h(n) is consistent if $h(n) \\ge (the cost of the action from n to n') + h(n')$; triangle inequality\n* **Triangle inequality** - side of a triangle cannot be longer than the sum of the other two sides\n* **Monotonic** - path costs increase as you go along a path, since action costs are always positive\n* **Prunes** - eliminates nodes/branches from consideration that are not necessary for finding a solution\n* **Bounded suboptimal search** - looks for a solution guaranteed to be within a constant factor W of the optimal cost, like weighted A*\n* **Bounded-cost search** - looks for a solution whose cost is less than some constant C\n* **Unbounded-cost search** - accepts a solution of any cost, as long as it can be found quickly\n* **Manhattan distance** - sum of horizontal and vertical distances, no diagonals ('city block distance')\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nThere are three ways to consider multi-agent environments:\n* As an aggregate for very large numbers of agents (an economy)\n* As part of the environment, results in a nondeterministic environment.\n* Explicitly model the agent.\n\nThe most commonly studied games are two player, turn taking, deterministic, perfect information (fully observable), zero sum games. Zero sum refers to that there is no cooperation, what is good for one player is bad for another. We call the players MAX and MIN where MAX always moves first. A game is defined as:\n* S0 = initial state, how the game is set up\n* TO-MOVE(s) = player whose turn to move in state s\n* ACTIONS(s) = set of legal moves for state s\n* RESULT(s,a) = the transition model, which defines the resulting state from taking action a in state s\n* IS-TERMINAL(s) = a terminal test that determines whether the game is over (true) or not (false). \n* UTLITY(s,p) = utility function that computes the final numeric value to the player when the game ends in terminal state. \n * example) Win = 1, Loss = 0, Draw = 0.5\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax search is for games with multiple outcome scores. We find the minimax value of each state in the tree (MINIMAX(s)). The minimax value for a terminal state is just the utility, for MAX it is the max of the possible children values, for MIN it is the min of the possible children values. The minimax algorithm is a recursive algorithm that goes all the way down the tree (DFS) and then backups the minimax values as the recursion rewinds. Exponential complexity for minimax search makes it impractical for complex games (like chess).\n\nFOr large state spaces, since the total number of game states is exponential in the depth of the tree, we need to use pruning to ignore parts of the tree that make no difference to the outcome. We can use alpha-beta pruning to prune leaves or subtrees of the game tree. \n* $\\alpha$ = the highest value choice found so far at any point along the path for MAX (MAX can get 'at least' this many points)\n* $\\beta$ = the lowest value choice found so far at any point along the path for MIN (MIN can get 'at most' this many points; MIN wants less points)\n\nAlpha-beta search updates the values of $\\alpha$ and $\\beta$ along the way and prunes branches or nodes that would result in values worst than the current $\\alpha$ or $\\beta$ values. Alpha-beta pruning is highly dependent on the order that the states are visited.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo reduce the amount of computational power needed, we can cut off the search early and apply a heuristic evaluation function to the states, treating non-terminal nodes like they were terminal. The terminal test will be replaced by a cutoff test which returns true for terminal states but otherwises decides when to cutoff the search. The evaluation function EVAL(s,p) retuns an estimate for the expected utility of state s to player p. The eval function will be the same as the utility function for terminal states. For non-terminal states, the evaluation function will be somewhere between a loss and a win. \n\nA good evaluation function needs to not take too long. It also needs to be strongly correlated with the chances of winning. But if it reaches the cutoff before a terminal state, then it will be uncertain about the final outcome. For these games, there is no chance involved, as long as everyone plays optimally, the result is predetermined. Eval functions are determined by using features of the state (e.g. how many pieces are left). The pieces could be weighed by importance and given corresponding (material) values. The eval function might not know which states will result in which player winning, but it can return a single value that estimates the proportion of states with each outcome as the expected value. \n* weighted linear function = $\\sum_{i=1}^{n} w_i*f_i(s)$\n * $f_i$ = feature of the position (# of bishops)\n * $w_i$ = weight of the feature\n\nAdding up the features requires the features to be independent of the values of the other features. Other methods might use nonlinear combinations, such as giving higher scores than 2x for a pair of bishops.\n\nAlong with the heuristic evaluation function, we can apply a cutoff function that is set at a fixed depth, so that it will return true for all greater depths and terminal states. You could also apply iterative deepening to increase the limit. If time runs out, then it will select a move from the deepest completed search. \nForward pruning can look ahead to find poor or good moves. If we combine all these techniques together (heuristic evaluation function, cutoff, quiescence search, minimax) we can create a creditable game playing program.\n\nPrograms can also use lookup tables for known information, such as opening and ending positions for chess. This allows the program to take advantage of known information gathered by humans. \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic game trees include chance nodes that denote all possible values and their probablity. Since it is not certain that the action will lead to that state, we cannot calculate definite minimax values, but instead will use expected values of the positions. Like with minimax, we can made an approximation by cutting off search at some point and apply an evaluation function to the leaves.The evaluation function needs to be a linear relationship to the probablity. Because we need all the possible probabilistic values, we have to add a lot more nodes to the tree for the possible sequences. The time complexity is $O(b^{m}n^m)$ where m is the max depth of the tree and n is the number of distinct probabilistic values. Therefore, we are limited to how far we can look ahead. Before, we had certain outcomes now none of the outcomes are certain so we need to consider them all. But, we can consider pruning if we place bounds on the leaf node utility values. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nAn agent needs to make a decision and there might be uncertainty about the current state.\n$$P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$$\n* P(s) = probability for state s\n* P(s'|s,a) = transition model probablity that action a in state s reaches s'\n* P(RESULT(a)=s') = probablity of reaching s' through action a in the current state\n\nExpected utility: $EU(a) = sum_{s'} P(RESULT(a)=s')U(s')$\n* EU(a) = expected utility of an action \n* U(s) = value to express the desirablity of a state\n\nMaximum Expected Utility: An agent should choose the action that maximimzes the expected utility. MEU principle formulizes that an agent should do the right thing, but it does not operationalize it. If an agent acts so that it maximizes a utility function that reflects the performance measure, the agent will achieve the highest possible performance score. The performance measure gives a score of a historical sequence of states while the utility function applies to the next state, therefore can guide actions step by step. \n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* A > B = prefer A over B\n* A ~ B = indifferent between A and B\n* $A \\ge B$ = prefers A over B or is indifferent\n\nlottery L = [p1,S1; p2,S2; ... pn,Sn]\n* each S can be an atomic state or another lottery\n\nAxioms of Utility Theory (preferences)\n* Orderability = either prefer one or rate them as equality preferable. agent cannot avoid deciding. \n * exactly one of $(A>B), (B>A), or (A~B)$ holds\n* Transitivity = given 3 lotteries, if an agent prefers A to B and B to C, then agent must prefer A to C\n * $(A>B) \\lor (B>C) \\implies (A>C)$\n* Continuity = if B is between A and C in preference, then there is some probability p where the agent will be indifferent between B and the lottery that yields A with probability p and C with probability 1-p\n * $A>B>C \\implies \\exists p [p,A; 1-p,C] ~ B$\n* Substitutability = if agent is indifferent between A and B, then agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n * $A~B \\implies [p,A; 1-p, C] \\sim [p,B; 1-p,C]  $\n* Monotonicity = if two lotteries have the same possible outcomes (A and B) and an agent prefers A to B, then the agent must rprefer to lotter that has a higher probability for A\n * $A>B \\implies (p>q \\iff [p,A; 1-p,B] > [q,A; 1-q,B]) $\n* Decomposability = Using the laws of probability, compound lotteries can be reduced to simplier ones. Compresses two consequtive lotteries into a single equivalent lottery\n * $[p,A; 1-p,[q,B; 1-q,C]] \\sim [p,A; (1-p)q,B; (1-p)(1-q),C]$\n\nConsequences\n* Existence of Utility Function = If the preferences obey the axioms, then there exists a function U such that U(A)<U(B) iff A is preferred to B, and U(A)=U(B) iff the agent is different between A and B. The utility of a compound lottery is completely determined once the probabilities and utilities of the possible outcome states are specified. \n * $U(A)>U(B) \\iff A>B and U(A)=U(B) \\iff A~B $\n* Expected Utility of a Lottery = utility of a lottery is the sum of the probablities of each outcome times the utility of that outcome\n * $U([p1,S1; ...; pn, Sn]) = \\sum_i piU(Si) $ \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nIt is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for deciding the value of a childs life vs removing asbestos from the school. \n\nUtility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n\n\n## Module 5 Lecture Notes\n\nMinimax Procedure:\n* Until game is over:\n * Start with the current position as a MAX node.\n * Expand the game tree a fixed number of ply.\n * Apply the evaluation function to the leaf positions.\n * Calculate back-up values bottom-up.\n * Pick the move assigned to MAX at the root\n * Wait for MIN to respond\n\nExpectimax search: compute the average score under optimal play\n* Max nodes just like in minimax search\n* Chance nodes are treated similiar to min nodes but the outcome is uncertain\n* Calculate the expected utilities for the chance nodes\n * i.e take weighted average (expectation) of the children nodes\n\n\n\n## Module 5 Definitions\n* **Adversarial search** - competitive environments where two or more agents have conflicting goals\n* **Move** - synonym for action\n* **Position** - synonym for state\n* **Terminal states** - end game states\n* **State space graph** - defined by the initial state, ACTIONS, RESULT functions to create a graph of states (vertices) and moves (edges)\n* **Game tree** - complete search tree that has every possible sequence of moves to a terminal state\n* **Ply** - move by one player, one level in a game tree\n* **Minimax value** - utility of being in that state, assuming both players play optimally\n* **Expected value** - sum of value*probablility\n* **Quiscent** - where there is no pending move that would widly swing the evaluation\n* **Quiescence search** - limits search to only certain types of moves (e.g. capture moves) that will resolve uncertainies in the state\n* **Horizon effect** - unavoidable opponent move that will cause serious damage, but can be temporarily delayed\n* **Policy** - mapping of every possible state to the best move in that state\n* **Stochastic games** - games with random elements, chance, probability\n* **Expectiminimax value** - generalization of minimax value for deterministic games\n* **Maximum expected utility (meu)** - produces values for the state(s) where a rational agent chooses the value to max EU\n* **Lottery** - set of outcomes for each action\n* **Value function or ordinal utility function** - numeric values do not matter in a deterministic environment, the agent only needs a perference ranking for the states\n* **Preference elicitation** - process of figuring out the human's utility function. presents choices to humans and uses observed preferences to create utility function\n* **Normalized utilities** - uses scale of 0 to 1\n* **Standard lottery** - $[p, u_{upper}; (1-p), u_{lower}] $\n* **Micromort** - one million chance of death\n* **Monotonic preference** - given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\n* **Expected monetary value** - (EMV), sum of probabilities times value\n* **Risk-adverse** - prefer a sure thing over a gamble\n* **Certainty equivalent** - amount someone would accept in lieu of the gamble\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Statisfaction Problems solve problems that use a factored representation for each state with a solution where all variables has a value that satisfies all the constraints on the variable. CSPs use general heuristic rather than domain specific by taking advantage of the structure of the states to solve complex problems. It eliminates large portions of the search space by identifying variable/value combinations that violate the constraints. * set of variables X = {X1,...Xn}\n* set of domains D = {D1,...Dn}\n* set of contraints C that specify allowable combinations of values, pair of <scope, relation>\n * scope = tuple of variables that participate in the contraint\n * relation = defines the values that those variables can take on, representated as a tuple of value that satisfy the constraint or as a function that can  determine whether the tuple is a member of the relation.\n\nCSPs can be solved fast and efficiently and can quickly prune large areas of a search space that an atomic state solver cannot. In an atomic search space, the only question we can ask is if the atomic state is a goal or not. With CSPs, if a partial assignment violates a constraint, we can discard futher refinements of the partial assignment. The simplest CSPs have variables with discrete, finite domains. Discrete domains can be infinite (like for time), but these domains would use implicit constraints instead of a domain of values. Linear Programming problems are the best known category of continuous domain CSPs where the constriants are linear (in)equalities. These can be solved in time polynomial in the number of variables. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nUnlike an atomic state space seach algorithm that can only make progress by expanding nodes to visit successors, CSPs can either generate successors by choosing a new variable assignment or it can use inference called constraint propagation. Constraint propagation can be done during the search or as preprocessing. The idea is that we want to enforce local consistency of each of the nodes so that inconsistent values are eliminated throughout the graph.\nUnary constraints can easily be eliminated at the start of the solving process. Often, all n-ary constraints can be transformed to binary constraints, so many CSP solvers only deal with binary constraints. \n\nA graph is arc consistent if all variables are arc consistent with one another. Variable Xi is arc consistent with another variable Xj if for every value in variable Xi's domain Di there is a value in variable Xj's domain Dj that satisfies the binary constraint for the arc (Xi, Xj).\nExample: For constraint Y = $X^2$, the domain D of X and Y is the set of decimal digits\n* X domain = {0, 1, 2, 3}\n* Y domain = {0, 1, 4, 9}\n\nEach value of X has a value Y that upholds the constraint. This has reduced the original domain D of X and Y.\n\nAC-3 is the most popular algorithm for enforcing arc-consistency. With a domain size of at most d and c binary constraints (cars), each arc can be inserted into the queue d times because a variable would have at most d values to delete. Therefore the total worst-case time is $O(cd^{3})$.  \n\nGlobal constraints are common in real life problems and can be handled by special purpose algorithms instead of general ones. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nSometimes when we finish the constraint propagation process, there are still variables with multiple possible values. Now we will need to search for the rest of the solution. Since CSPs are commutative, we can select a variable to deal with and try the possible values. We could pick the variable in order or we could pick one randomly, but neither of these approaches are ideal. Instead we can choose the variable with the fewest legal values (minimum-remaining-values (MRV) heuristic). This heuristic will pick the most constrained variable and is most likely to fail soon, allowing that part of the tree to be pruned. Another heuristic that could be used is a degree heuristic. It attempts to reduce the branching factor for future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables (aka it is included in the most arcs). Once we pick which variable we are going to evaluate, then we need to pick the order that we examine the values. The least-constraining-value heuristic prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. We want to try to leave the most flexibility possible to the rest of the graph. We want to fail first because all variables need an assignment eventually, whereas the values we don't want to fail as much because that means we would have to backtrack more, we are only looking for one solution of variable assignments. \n\nAC-3 can reduce the domain of the variables before we begin the search and inference can be used during the search for further domain reductions. When a value is assigned for a variable X, we can use forward checking to check each unassigned variable that is connected to X in an arc constraint and delete any value from variable Y's domain that is inconsistent with the value chosen for X. We can combine the MRV heuristic with forward checking for a more efficient algorithm. Forward checking reduces inconsistencies, but not all of them because it doesn't look forward far enough, only by one arc. Maintaining Arc Consistency (MAC) algorithm checkes for inconsistencies and backtracks if it finds any. Forward checking does not recursively propagate constraints when changes are made to the variable's domains. If a branch of the search fails, it just backs up to the previous variable and tries a different value (chronological backtracking). A more intelligent approach would be to keep track of the conflict set of assignments for a variable and backtrack to the most recent assignment in the conflict set (backjumping). Backjumping would be redundant in a forward checking search, you need to do one or the other.  \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nMin-conflict heuristics work well for many CSPs, such as n-queens and the Hubble scheduling problems.  \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nTo deal with real world problems, they need to be broken down (decomposed) into subproblems. Subproblems can be independent if they do not depend on the rest of the graph (not connected with the other variables in the graph). A constraint graph modeled as a tree can be solved in linear time in the number of variables using directional arc consistency. To set up a CSPs as a tree, pick one of the variables to be the root and order the variables such that each variable appears after its parent in the tree with a topological sort ordering. \n\nCutset conditioning can reduce a constraint graph by picking a variable, assigning a value, removing that value from the other variables domains, and then removing the variable from the problem. The variables chosen to cut can allow us to reduce the graph to a tree-structured problem. \n\nTree decomposition can reduce the constraint graph by transforming the original graph into a tree where each node in the three consists of a set of variables.* Every variable in the original problem appears at least once, ensuring all variables are represented\n* If two variables are connected by a constraint in the original problem, they must appear together (with the constraint) in at least one of the tree nodes, ensuring all constraints are represented\n* If a variable appears in two nodes of the tree, it must appear in every node along the path connecting those nodes. This ensures that values in the original problem are still in the decomposition. \n\nThe tree decomposition is like a tree of subgraphs of the original problem. Trees of this nature can be solved in $O(nd^2)$ time. When creating a tree decomposition, we want to make the subproblems as small as possible. Time considerations favor tree decomposition, but cutset has the advantage that it can be executed in linear memory while tree decomposition needs expotential memory for tree width w.\n\nIf we have the same number of domain values as variables, this is known as value symmetry. Since this results in d! search space, we want to reduce that by breaking the symmetry with a symmetry-breaking constraint. This new constraint could be something like the colors of the regions need to be in alphabetical order. That would result in only one possible solution instead of three. \n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Factored representation** - each state has a set of variables with corresponding value\n* **Consistent** - assignment of values to variables where the assignment does not violate any constraint; (legal assignment)\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - for a CSP, this is a consistent and complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables of the problem, edges connect any two variables that participant in a constraint\n* **Unary constraint** - restricts the value of a single variable\n* **Binary constraint** - relates two values as the restriction\n* **Binary csp** - only has unary and binary constraints\n* **Global constraint** - constraint involving an arbitrary number of variables, does not mean it involves all the variables in a problem\n* **Preference constraints** - indicates which solution is preferred, compared to absolute constraints\n* **Constrained optimization problem** - COP, CSPs with preferences can be solved with optimization search methods (path based or local)\n* **Constraint propagation** - uses constraints to reduce the number of legal values for a variable, and propagating that constraint to another variable, etc.\n* **Node-consistent** - if all the values in a single variable's domain satisfy the unary constraint\n* **Arc-consistent** - if every value in the domain satisfies the binary constraint\n* **Path-consistent** - looks at triple set of variables using implicit constraints\n* **K-consistent** - for any set of $k-1$ variables and any consistent assignment to those variables, a consistent value can be assigned \n* **Strongly k-consistent** - if a CSP is k-consistent, $k-1$ consistent, ..., 1-consistent\n* **Resource constraint** - atmost constraint\n* **Bounds propagation** - domains representated as upper and lower bounds\n* **Bounds-consistent** - for lower and upper bounds, for every variable X there exists value that satisfies the constraint (X,Y) for every Y\n* **Commutativity** - a problem is commutative if the order of the set of actions does not matter\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - constraint learning set of variables with their values\n* **Min-conflicts heuristic** - select a value that results in the min number of conflicts with another variable\n* **Tabu search** - small list of recently visited states that the algorithm is not allowed to return to\n* **Constraint weighting** - concentrates the search on imporant constraints by assigning weights\n* **Directional arc consistency** - if and only if every variable Xi is arc consistent with each Xj for j>i\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nThe key component to a knowledge based agent is the knowledge base, composed of sentences either add manually to the knowledge based from background knowledge or inferred from other existing sentences. The program need to know what the agent known and what the goals are in order to determine the behavior it needs to take. A declarative approach to system building involves the agent starting with an empty knowledge base and then giving the agent sentences to learn until it knows how to operate in its environment. The procedural approach encodes the desired behaviors directly into the program. A successful agent will often use a combination of these two approaches to solve a problem. \n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n* Performance Measure: +1000 to leave with gold, -1000 if caught by wumpus, -1 for each action taken, -10 for using an arrow\n * game ends when the agent dies or leaves the cave\n* Environment: 4x4 grid. gold and wupus locations are random with one each. other squares have p=0.2 of being a pit\n* Actuators: forward, turnleft 90deg, turnright 90deg\n * pit or wumpus is death\n * grab to pick up the gold\n * shoot to fire an arrow in a straight line. arrow continues until it hits a wall or wumpus. agent only has one arrow\n * climb to climb out of the cave, only from (0,0)\n* Sensors: 5 different sensors, percepts are given as a list of five symbols, one for each sensor\n * stench - perceives stench if in a square adjacent to wumpus \n * breeze - perceives breeze if in square adjacent to pit\n * glitter - perceived if in square with gold\n * bump - perceived if wall is found\n * scream - perceived if wumpus is killed, anywhere in the cave\n\nenvironment is deterministic, discrete, static, and single agent (wumpus is part of the environment and doesn't move). It is also sequential, partially observable, and transition model is completely known.  \n\n\n## AIMA Chapter 7.3 Logic\n\nEach of the sentences in the knowledge base need to follow a syntax so that they are well formed and have defined semantics (meaning) to determine the truth of the sentence in the possible world. The world can be described as a model where each of the sentences have fixed true/false values. We would say that model m satisfies sentence a if sentence a is true in model m. $M(\\alpha)$ represents the set of all models where $\\alpha$ is true.\n\nLogical entailment: $\\alpha \\models \\beta if and only if M(\\alpha) \\subseteq M(\\beta) $ \nexample) sentence x=0 entails sentence xy=0\n\nLogical entailment can be applied to derive conclusion (logical inference). Model checking enumerates all possible modesl to check that sentence a is true in all models where KB is true. When inferring sentences, we want to make sure they are sound and complete. Unsound inferences are potentially creating untrue sentences. Model checking is a sound procedure. The last characteristic is grounding. The sensors create connections that ensure that the KB is valid in the world. \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nUse letters and subscripts to denote symbols for the logical sentences. For example, $W_{1,3}$ could be wumpus in square (1,3).\n\nConnectives:\n* negation: not\n* conjunction: and (parts are conjuncts)\n* disjuction: or (parts are disjucts)\n* implication: implies, if-then statements (rules). premise/antecedent followed by a conclusion/consequent. \n* biconditional: if and only if \n\nFor determining truth values, there are 5 rules\n* $\\neg P$ is true iff P is false in model m\n* $P \\land Q$ is true iff both P and Q are true in m\n* $P \\lor Q$ is true iff either P or Q is true in m\n* $P \\implies Q$ if true unless P is true and Q is flase in m\n* $P \\iff Q$ if true iff P and Q are both true or both false in m\n\nWe can build a knowledge base for the wumpus world using the logical sentences, starting with the immutable aspects of the world. Next is to try to infer additional sentences using entailment and model checking. This will ensure the algorithm stays sound and complete.  \n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nBefore we determined entailment via model checking, we can also show entailment via theorem proving. If the number of models is large but the length of the proof is short, then it can be more efficient then model checking. \n* logical equivalence: $\\alpha \\equiv \\beta iff \\alpha \\models \\beta and \\beta \\models \\alpha $\n* deduction theorem: For any sentences $\\alpha$ and $\\beta$, iff the sentence $(\\alpha \\implies \\beta)$ is valid\n* validity and satisfiability connection: $\\alpha \\models \\beta $ if and only if the sentence $(\\alpha \\lor \\neg \\beta)$ is unsatisfiable\n * This is proved by proof by contradition, where one assume sentence $\\beta$ to be false and it leads to a contradiction with $\\alpha$. \n\nWe can use any of the previous search algorithms to find a solution if the proof problem is structured like so:\n* INITIAL STATE: initial knowledge base\n* ACTIONS: set of actions consisting of all the inference rules applied to all of the sentences that match the top half of the inference rule\n* RESULT: result of an action is to add the sentence in the bottom half of the inference rule\n* GOAL: state that contains the sentence we are trying to prove\n\nSearching for proves is an alternative to enumerating models. Logical system are motononicity, the set of entailed sentences can only get bigger as information is added to the KB. \n\nFor knowledge bases expressed in conjunctive normal form (CNF), the resolution rule yields a complete inference algorithm. The resolution rule will take each pair complemenary literals from the CNF and add it to the KB if it is not already there. This will continue until:\n* there are no new clauses that can be added (KB does not entail $\\alpha$)\n* two clauses resolve to yield the empty clause (KB entails $\\alpha$)\n\nAll definite clauses are Horn clauses, including clauses with no positive literals. These are our goal clauses. If you resolve two Horn clauses, you get a Horn clause back. They are closed under resolution. The premise of a Horn form clause is the body and the conclusion is the head. Knowledge bases containing only definite clauses...\n* Every definite clause can be written as an implication whose premise is a conjunction of positive literals and its conclusion is a single positive literal.\n* Inference with Horn clauses can be done with forward-chaining and backward chaining\n* Deciding entailment with Horn clauses can be done in linear time to the size of the knowledge base\n\nForward chaining is sound, each inference is an application of Modus Ponens. It is also complete since every entailed atomic sentence is derived. Both forward-chaining and backward-chaining implementations run in linear time. Backward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nForward chaining starts with the known data the agent has and adds new premises (sentences) as new percepts are given and incrementally applies the forward chaining algorithm to derive new conclusions. It is a type of data-driven reasoning. It does not have to start with a query.\n\nBackwards chaining does start with a query and works backwards. If the query is true, then nothing needs to be done. If the query is false, then it finds implications in the knowledge base where the conclusion is the inital query. If all the premises of one of the implications can prove to be true (via backward chaining) then the query is true. This is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Knowledge base** - kb, set of sentences expressed in a knowledge representation language\n* **Sentence** - expressed in a knowledge representation language with some assertion about the world\n* **Axiom** - a sentence that was not derived from another sentence\n* **Syntax** - all sentences are well-formed\n* **Semantics** - meaning of the sentences, defining the truth of each sentence wrt each possible world\n* **Entailment** - a sentence follows logically from another sentence\n* **Sound (truth-preserving)** - only sentences that are derived from entailed sentences are inferred\n* **Completeness** - inference algorithm is complete if it can derive any sentence that is entailed\n* **Grounding** - ensuring that the connetions between the logical reasoning process and the real environment are true\n* **Atomic sentences/literals** - logical sentences that only consist of one logical operator (proposition symbol)\n* **Complex sentences** - constructed from simpler sentences\n* **Logical connectors** - parentheses and operators\n* **Theorem proving** - applying rules of inference directly to the sentences to construct a proof of the desired sentence without checking models\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - if a sentence is true in all models. also known as tautologies, they are necessarily true\n* **Satisfiability** - a sentence is satisfiable if it is true in some model\n* **Ground resolution theorem** - if a set of clauses is unsatisfiable, then the resolution closure contains the empty clause\n* **Definite clause** - disjunction (or) of literals where exactly one is positive (rest are negated)\n* **Horn clause** - disjunction of literals where most one is positive\n* **Fact** - sentence consisting of a single positive literal\n* **Data-driven reasoning** - reasoning where the focus starts with the known data\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}